Prolog er særdeles velegnet til konstruktion af programmer til syntaks analyse. Især det forhold, at mange syntakser er rekursive af natur, gør Prolog sproget velegnet til syntaksanalyse. Det vil vi se et eksempel på med udgangspunkt i løsningen af følgende opgave.
Der ønskes udviklet et program, som kan analysere abesprog. Abesproget har følgende syntaks - angivet i BNF notation:
<stop> ::= b | d
<plosive> ::= <stop> a <syllable> ::= <plosive> | <plosive> <stop> | a <plosive> | a <stop>
<word> ::= <syllable> | <syllable> <word> <syllable> <sentence> ::= <word> | <sentence> _ <word>
_ repræsenterer et blanktegn
Ved hjælp af et lille prolog program, der kan teste korrektheden af en indtastet sætning, skal det være muligt at afsløre, hvilken af nedenstående talere, der er en hemmelig agent forklædt som abe:
Gorilla: ba_ababadada_bad_dabbada
Chimpanse: abdabaadab_ada
Bavian: dad_ad_abaadad_badadbaad
Programmet startes med udførelsen af prædikatet go, hvor vi indlæser en tekst og omdanner den til en liste med heltal, der repræsenterer de enkelte tegn i teksten. Derefter kaldes prædikatet try med listen som argument.
go:-
write('Indtast sætning: '),
read(Svar),
nl, write(Svar), nl,
string_to_list(Svar, Liste),
try(Liste).
Der er to forskellige versioner af try. I den første tester vi, om listen indeholder det syntaktiske element sentence, og dermed er vi i gang med syntaksanalysen. Hvis listen ikke indeholder en sentence, aktiveres den anden version af try.
try(Liste):-
sentence(Liste), !,
write('Sætningen er korrekt'), nl.
try(_):-
write('Sætningen er forkert'), nl.
Opbygningen af kontrollen af de forskellige produktionsregler i syntaksen følger BNF-notationen. Til kontrol af sentence kræves således 2 versioner. I den første undersøges, om listen indeholder et enekelt word. I den anden undersøges, om listen består af følgen sentence _ word. Til den sidste test bruges 2 instanser af standardprædikatet append til opsplitning af listen i tre dele. Denne konstruktion vil systematisk afprøve samtlige mulige opsplitninger af listen i tre dele, indtil enten alle muligheder er afprøvet, uden at vi har fundet en brugbar løsning, eller indtil vi har fundet en brugbar opsplitning, som kan godkendes i den resterende syntaksanalyse.
sentence(Liste):-
word(Liste), !.
sentence(Liste):-
append(Liste1, ListeX, Liste),
append("_", Liste2, ListeX),
sentence(Liste1),
word(Liste2), !.
Analysen af word følger samme mønster som analysen af sentence. I den første version undersøges, om listen er en syllable. I den anden version undersøges, om listen indeholder syllable word syllable.
word(Liste):- syllable(Liste), !. word(Liste):- append(Liste1, ListeX, Liste), append(Liste2, Liste3, ListeX), syllable(Liste1), word(Liste2), syllable(Liste3), !.
Der er fire versioner af syllable:
syllable(Liste):-
plosive(Liste), !.
syllable(Liste):-
append(Liste1, Liste2, Liste),
plosive(Liste1),
stop(Liste2), !.
syllable(Liste):-
append("a", Liste2, Liste),
plosive(Liste2), !.
syllable(Liste):-
append("a", Liste2, Liste),
stop(Liste2), !.
Der er en enkelt version af plosive:
plosive(Liste):- append(Liste1, "a", Liste), stop(Liste1), !.
Og til slut to versioner af stop. Disse er udformet som facts og ikke som produktionsregler - sådan vil det altid være i slutningen af den syntaktiske analyse.
stop("b").
stop("d").
Hele programmet er samlet i følgende tekst-fil.