Sintaktična analiza

Sintaktična analiza je preverjanje, če so stavki na vhodu sintaktično pravilni.

BNF (KNG - kontekstno neodvisne gramatike): <V,T,S,P>

<neterminal> ::= niz terminalov in neterminalov

Opis stavka

Želimo opisati stavek:

<stavek> ::= <osebek> <povedek>

<osebek> se lahko nadomesti z:

<osebek> ::= Tone
<osebek> ::= Tine
<osebek> ::= pes

<povedek> se lahko nadomesti z:

<povedek> ::= gleda
<povedek> ::= laja

Drevo izpeljave

Alternativna notacija

<stavek> ::= <osebek> <povedek>

<osebek> ::= Tone | Tine | pes

<povedek> ::= gleda | laja

Preverjanje sintaktične pravilnosti

Izvedba v Prologu:

stavek(S):-
  osebek(O),
  povedek(P),
  stik(O,P,S).

osebek(['Tone']).
osebek(['Tine']).
osebek([pes]).

povedek([gleda]).
povedek([laja]).

c([Element|Seznam],[Element],Seznam).

stavek(Stavek,Konec):-
  osebek(Stavek,Preostanek),
  povedek(Preostanek,Konec).
osebek(Zacetek,Konec):-
  c(Zacetek,['Tone'],Konec);
  c(Zacetek,['Tine'],Konec);
  c(Zacetek,[pes],Konec);
povedek(Zacetek,Konec):-
  c(Zacetek,[gleda],Konec);
  c(Zacetek,[laja],Konec).

BNF : kontekstno neodvisne gramatike

prolog: gramatična pravila

stavek --> osebek, povedek.
osebek --> ['Tone']; ['Tine']; [pes].
povedek --> [gleda]; [laja].

Analizator

Analizator preveri če je sintaksa pravilna

% if-then-else stavek zapisan z operatorji
:- op(800,xfx,then)
:- op(799,xfx,else).
:- op(799,fx,if).

if P then S1 else S2 :- P,!,S1 ; S2.

preveri :-
  write('vtipkaj izraz : '),
  beri(Znaki),
  struktura(Znaki,[]).

%preberi vrstico v seznam do pike
beri(Znaki) :- beri(Znaki,X-X).

%drugi argument je seznm prebranih znakov
beri(Znaki,S-X) :-
  get0(ZnakA), %ASCII koda znaka
  name(Znak,[ZnakA]), %pretvori v znak
  if Znak = '.'
    then (X = [], Znaki = S)
    else (X = [Znak|Y], beri(Znaki,S-Y)).

?- preveri.
vtipkaj izraz: otrok(tine,tone).
yes
?- preveri.
vtipkaj izraz: ana,tone.
no

Preprečevanje neskončnih zank

<A> ::= <A> b | c

a --> a, [b] ; [c].

?- a([c,b,b],[]). %povzroči ciklanje

Če levo rekurzijo spremenimo v desno rekurzijo se ne zacikla.

a --> [c] , b_pomozni ; [c].
b_pomozni --> [b] , b_pomozni ; [b].

Izpostavljanje

Izpostavljanje pohitri izvajanje.

a --> b; b,c.

Procedura a pokliče najprej proceduro b, če to uspe je končano, sicer je potrebno poklicati proceduro b in preostanek prenesti na c. Ponovno pošiljanje b-ju je nepotrebno. Temu se izognemo tako da b izpostavimo:

a --> b, ([];c).

alternativno:

a --> b, novi.
novi --> [];c.