Memetski algoritem za sklepanje o kontekstno neodvisnih gramatikah in njegova uporaba pri načrtovanju domensko specifičnega jezika : doktorska disertacija

slovenian

doktorska dela

2012

Univerza v Mariboru, Fakulteta za elektrotehniko računalništvo in informatiko

In this dissertation a memetic algorithm for context-free grammar inference MAGIc (Memetic Algorithm for Grammatical Inference) is presented. A memetic algorithm is an evolutionary algorithm with embedded local search. Grammaticalinference belongs to the field of machine learning and represents aset of methods that infer grammars based on positive and optionally negative samples. The algorithm MAGIc is capable of inferring context-free grammars from positive samples only, although we can also provide negative samples as algorithm input. To infer context-free grammar, the differences between positive samples are used to expand current grammar solutions in order to parse more positive input samples. The algorithm was tested on a set of domain-specific languages, a comparison with current 'state-of-the-art' algorithm TBL (tabular representation algorithm) was done and it was extended with an ability to embed domain-specific language constructs into an existing general purpose language grammar. The algorithm was proven to be successful for grammar inference of domain-specific languages and is independent of the input sample order. The most important algorithm operators are local search and generalization

07.08.2023