Sintaksna analiza

Vhod: zaporedje leksikalnih simbolov
Izhod: drevo izpeljav (ali sled izpeljave)

Kontekstno neodvisna gramatika

Kontekstno neodvisna gramatika opisuje sintakso jezika s produkcijami: $simbol\to simbol...simbol$
Simbol je lahko:

• končni: token iz abecede jezika, ki mu pripada semantična vrednost
• vmesni: pojavi se na levi strani produkcije, en mora biti začetni

(Skrajno leva/desna) izpeljava: postopek izpeljave niza iz začetnega simbola z razširjanjem (skrajno levih/desnih) vmesnih simbolov $\to$ leva/desna sled izpeljave
Drevo izpeljav: prikaz izpeljave

Dvoumnost gramatike: niz jezika gramatike ima več možnih dreves izpeljav

Algoritmi

LL (Left-to-right scan producing the Left-most derivation)

Leva sled izpeljave, drevo gradimo od zgoraj navzdol
Šibkejši od LR, ampak lažja implementacija na roke z boljšim upravljanjem napak

LL(k) gramatika: gledamo največ $k$ simbolov vnaprej $\to$ v vseh celicah tabele mora biti največ $k$ produkcij

LL(1) gramatike

LL(1) iz prvega simbola razbere potrebno produkcijo.
Pogoj: za vsaki produkciji $X\to {\gamma }_1$ in $X\to {\gamma }_2$ mora veljati: $FIRST({\gamma }_1)\ne FIRST({\gamma }_2)$

• $nullable(X)=true$ … vmesni simbol $X$ se lahko izpelje v prazen niz $ϵ$
• $FIRST(\gamma )$ … množica možnih končnih simbolov, ki so prvi simbol možnih nizov izpeljav $\gamma$
  • $FIRST(X\gamma )=FIRST(X);nullable(X)=false$
  • $FIRST(X\gamma )=FIRST(X)\cup FIRST(\gamma );nullable(X)=true$

Generacija primerne gramatike za LL analizo:

1. Pretvorba dvoumne v nedvoumno gramatiko:

Dvoumna in nedvoumna gramatika

Dvoumna gramatika:

Primera različnih dreves izpeljave istega niza id := id + id + id:

Nedvoumna gramatika: * je močnejši od +, leva asociativnost, simbol za konec niza

2. Eliminacija leve rekurzije $X\to X\gamma$ z uvedbo desne rekurzije preko novega simbola:

$$\left(\begin{array}{c}X\to X{\gamma }_1\\ X\to X{\gamma }_2\\ X\to {\alpha }_1\\ X\to {\alpha }_2\end{array}\right)\Rightarrow \left(\begin{array}{c}X\to {\alpha }_1{X}^{\prime }\\ X\to {\alpha }_2{X}^{\prime }\\ X^{\prime }\to {\gamma }_1{X}^{\prime }\\ X^{\prime }\to {\gamma }_2{X}^{\prime }\\ X^{\prime }\to \end{array}\right)$$

Primer

Problem stare:

• $E\to E+T$
• $E\to T$

Rešitev za novo:

3. Levo faktoriranje koncev produkcij preko novega simbola:

Primer

Problem stare:

• $S\to ifEthenSelseS$
• $S\to ifEthenS$

Rešitev za novo:

$$\begin{array}{rl}S& \to ifEthenSX\\ X& \to \\ X& \to elseS\end{array}$$

LL algoritem

Na vhodu prejemamo znake, na skladu imamo:

• vmesne simbole - naredimo razvoj glede na tabelo produkcij glede na prvi vhodni simbol
• končne simbole - če je prvi končni simbol na skladu enak prvemu vhodnemu simbolu naredimo pomik (zbrišemo enaka simbola)

LR (Left-to-right scan producing the Right-most derivation)

LR: desna sled izpeljave, drevo gradimo od spodaj navzgor
Analizira vse deterministične kontekstno neodvisne jezike

Zamakne odločitev izbire produkcije dokler ne vidi vseh simbolov desne strani produkcije
Implementacija odločanja med slednjima operacijama preko DKA:

• dodaj naslednji vhodni simbol na sklad
• odstrani simbole desne strani produkcije iz sklada in dodaj levi simbol produkcije na sklad

PEG (Parsing Expression Grammars) - Python

Sintaksni kombinatorji (Parser combinators) - novejši, nedorasli

Parser generatorji

Podamo opis želenega sintaksnega analizatorja, ki ga orodje generira-implementira
ANTLR implementira ALL(*) algoritem, v primeru več kot 1 produkcije uporabi KA za nadaljno analizo možnosti