Lexical Analysis with the Use of Aho-Korasick Automata in Prolog Language

Abstract

This paper discusses implementation in Prolog and the use of Aho-Korasick automata in lexical analysis. The choice of any of the system approaches known so far depends, among other things, on the choice of the lexical analyser's implementation language. Although ali algorithms referred to in the paper are procedura!, the algorithm based on Aho-Korasick automata is suitable for an implementation in Prolog as a non-procedural language, since the predicates realizing finite automata can be implemented relatively easy. Besides, as a single-pass algorithm, it recognizes ali key-words from the input word. The automaton constructed and the program it is implemented in are a part of a deductive mechanism preprocessor for the estimation of multiple valued dependences of relation data base model.

Ovaj se rad bavi implementacijom u Prologu i primjenom Aho-Korasickova automata u rješavanju problema leksičke analize. Izbor bilo kojeg od danas poznatih sistemskih pristupa rješavanju problema leksičke analize ovisi medu ostalim i o izboru jezika implementacije leksičkog analizatora. lako su svi algoritmi koji se u radu spominju proceduralnog tipa, algoritam temeljen na Aho-Korasickovim automatima pogodan je za implementaciju u Prologu kao neproceduralnom jeziku, jer se predikati koji ostvaruju konačne automate dadu relativno lako implementirati. S druge strane algoritam je jednoprolazan i u tome jedinom prolazu raspoznaje sve ključne riječi koje se pojavljuju u zadanoj ulaznoj riječi. Konstruirani automat i program u kojem je implementiran dio su pretprocesora za deduktivni mehanizam za račun višeznačnih ovisnosti relacijskog modela podataka.