• Jezik omogućava određivanje ispravnosti rečenice.
• Svaka rečenica predstavlja sekvencu simbola.
• Jezik možemo definisati kao skup, u opštem slučaju beskonačan, svih validnih rečenica na datom jeziku.

Osnovne klase alata:

• Generators - generišu validne rečenice na nekom jeziku.
• Recognizers - prepoznaju da li rečenica pripada jeziku.
• Parsers - prevode rečenice u stabla.
• Formatters - prevode stabla u rečenice.

• Svaki jezik poseduje alfabet mogućih karaktera koji se mogu pojaviti u sklopu validnih rečenica. Kod računarskih jezika određene kombinacije simbola se tretiraju kao jedinstveni entitet - token.
• Leksička analiza je proces grupisanja niza uzastopnih karaktera ulaznog stringa u tokene. Tekstualni blok koji odgovara tokenu naziva se još i leksema.
• Program koji vrši leksičku analizu naziva se lekser, skener ili tokenizator.
• Leksička analiza prethodi procesu parsiranja tako što se karakteri sa ulaza prvo grupišu u tokene a zatim parser vrši sintaksnu analizu i kreira stablo parsiranja.
• Skeneri mogu biti posebni alati a mogu biti integrisani u parser (scannerless parsing).
• Poznatiji skeneri: flex i lex, JLex…

Posmatrajmo sledeći jednostavan iskaz:

if a > 5:
    print("Veće od 5!")

Ulazni string čine karakteri ovog programskog koda: i, f, <prazno>, a, <prazno>, >, itd. Skeniranje će grupisati pojedinačne karaktere u tokene. Svaki token ima svoje ime (ili tip, npr. identifikator, operacija, varijabla), i vrednost (npr. if, a, >, 5), odnosno deo ulaza koji je prepoznat kao ovaj tip tokena. Proces tokenizacije će za ulazni string da proizvede nisku tokena koja će služiti kao ulaz u proces parsiranja. Za primer sa prethodnog listinga izlaz skenera će imati sledeći oblik (pod pretpostavkom da ignorišemo prazne karaktere):

[Keyword(if), Variable(a), Operator(>), IntLiteral(5),...]

• Obično leksičku analizu obavljamo kao nezavisan proces što dovodi do problema.

array [1..10] of integer

• Interval 1..10 se može tokenizovati kao konstanta 1. tipa real iza koje sledi konstanta .10 istog tipa, ili kao interval od 1 do 10. Tek ukoliko imamo kontekst u kome vršimo skeniranje možemo da razlučimo ove dve situacije.
• Interakcija leksera i parsera - lexer hack). Ovakva arhitektura dovodi do komplikacija u implementaciji i održavanju alata.

• Prethodni problem je uzrokovan nepostojanjem sintaksnog konteksta ali je u nekim situacijama problem složeniji i zahteva semantičke podatke.
• Primer:

a * b

Na programskom jeziku C ovaj iskaz može da se tumači kao množenje varijabli a i b, ali i kao deklaracija varijable b čiji je tip pokazivač na a u zavisnosti od semantike.

• Analiza linearnog zapisa niza simbola na osnovu pravila neke formalne gramatike jezika.
• Transformacija ulaznog stringa u stablo parsiranja ili neku drugu strukturu podataka.

• Nastaje iz niske simbola (ulaznog stringa) procesom skeniranja (tokenizacije ili leksičke analize) i parsiranja.
• Listovi stabla su tokeni prepoznati od strane skenera (terminali) dok su unutrašnji čvorovi stabla (neterminali) definisani gramatikom jezika.
• Stablo parsiranja reflektuje sintaksnu strukturu ulaznog stringa na bazi unapred definisane formalne gramatike.

Stablo parsiranja za ulazni string -(4-1)*5/(2+4.67)

• Svaki iskaz na datom jeziku se može na apstraktan način opisati apstraktnim sintaksnim stablom (Abstract Syntax Tree).
• AST je usmereno labelirano stablo gde čvorovi stabla predstavljaju instance koncepata apstraktne sintakse.
• AST ne sadrži elemente koje ne doprinose semantici kao što su ključne reči, zagrade, "prazni" karakteri i komentari.

-(4-1)*5/(2+4.67)

• Konkretno sintaksno stablo je bazirano na formalnoj gramatici koja opisuje detalje zapisa u tekstualnom obliku.
• Apstraktno sintaksno stablo sadrži suštinu jezičkog iskaza.
• Možemo imati više gramatika za isti jezik odnosno jedno apstraktno sintaksno stablo možemo zapisati na više različitih načina što rezultuje različitim konkretnim sintaksnim stablima.
• Primer: Izraz -(4-1)/5/(2+4.67) možemo u postfiksnoj notaciji (obrnuta poljska notacija) zapisati kao 4 1 - 5 / 2 4.67 + / -. Ovo će rezultovati različitim stablima parsiranja ali je suština izraza ista i rezultovaće istim apstraktnim sintaksnim stablima.

• Definicija jezika na slajdu Jezik nije preterano korisna u praktičnom smislu jer je nemoguće definisati jezik navođenjem svih validnih rečenica.
• Zato moramo imati sistem koji na konačan način omogućava definisanje potencijalno beskonačnog skupa validnih rečenica. U jezičkoj analizi jedan takav sistem je formalna gramatika.

• Predstavlja skup pravila (produkcije) pomoću kojih je moguće generisati sve validne rečenice nekog jezika (formalni jezik) polazeći od startnog simbola.
• Definiše koji od svih mogućih nizova simbola u jeziku predstavljaju validne rečenice tog jezika (ali bez validnosti njihovih značenja).
• Generisanje ispravnih rečenica jezika (generativne gramatike) - često se koriste kao osnova za prepoznavanje validnih rečenica.

Formalna gramatika je $G = (N, \Sigma, P, S)$ gde je:

• $N$ - konačni skup neterminalnih simbola,
• $\Sigma$ - konačni skup terminalnih simbola,
• $P$ - konačni skup produkcionih pravila (produkcija) oblika: $(\Sigma \cup N)* N(\Sigma \cup N)* \rightarrow (\Sigma \cup N)*$
• $S$ - neterminal iz skupa $N$ ($S \in N)$ koga nazivamo početnim simbolom.

• Velika slova alfabeta ($A$, $B$, $C$…) - neterminalni simboli gramatike
• Mala slova alfabeta ($a$, $b$, $c$…), cifre, oznake operatora (+, -, …), oznake interpunkcije (zagrade, zarez, tačka…) - terminalni simboli gramatike
• Velika slova kraja alfabeta ($X$, $Y$, $Z$…) - simboli gramatike, bilo neterminali ili terminali.
• Mala slova alfabeta ($u$, $v$, …, $z$) - niske terminala (moguće prazne)
• Mala grčka slova (α, β, γ…) - niske simbola gramatike (moguće prazne), moguće i terminala i neterminala.

• Skup produkcija: $A \rightarrow \alpha_1, A \rightarrow \alpha_2, A \rightarrow \alpha_3$ može se pisati kao: $A \rightarrow \alpha_1 | \alpha_2 | \alpha_3$ Gde $\alpha_1, \alpha_2, \alpha_3$ nazivamo alternativama produkcije $A$.
• Pišemo $X*$ za skup svih niski koje se mogu kreirati iz elemenata skupa $X$.
• Praznu nisku označavamo sa $\epsilon$.

Formalne gramatike se mogu klasifikovati prema hijerarhijskoj klasifikaciji Noama Čomskog¹. Prema ovoj klasifikaciji gramatike mogu biti:

• tipa 0 - rekurzivno prebrojive - bez ograničenja na oblik produkcija.
• tipa 1 - kontekstno zavisne - produkcije oblika: $\alpha A \beta \rightarrow \alpha \gamma \beta$
• tipa 2 - kontekstno slobodne - produkcije oblika: $A \rightarrow \gamma$
• tipa 3 - regularne - produkcije oblika: $A \rightarrow a | aB$

1. http://en.wikipedia.org/wiki/Chomsky_hierarchy

• Produkcije oblika: $A \rightarrow \gamma$
• Popularne u domenu računarskih jezika. Dovoljno jednostavne za konstrukciju efikasnih algoritama za parsiranje.
• Generišu jezike koje nazivamo kontekstno slobodnim jezicima.
• Postoje algoritmi za parsiranje koji prihvataju ceo skup CFG (npr. Earley, GLR). Njih nazivamo generalizovanim.
• U praksi se češće koriste jednostavniji algoritmi koji prihvataju samo podskup CFG.
• Jezik za definisanje CFG - (Extended) Backus-Naur Form (EBNF).

G = ({S}, {a, b}, P, S)

gde je skup produkcionih pravila P dat kao:

https://en.wikipedia.org/wiki/Context-free_grammar

Ako je $G$ formalna gramatika tada sa $L(G)$ obeležavamo skup svih rečenica koje $G$ može da generiše. Ovaj skup zovemo jezikom koji $G$ generiše ili definiše.

• Generisanje ispravne rečenice, počevši od startnog simbola/neterminala, sukcesivnom primenom produkcija dok ne dobijemo rečenicu koja se sastoji samo od terminala.

  1. $S \rightarrow a S a$
  2. $S \rightarrow b S b$
  3. $S \rightarrow \epsilon$

$S \overset{1}{\rightarrow} aSa \overset{1}{\rightarrow} aaSaa \overset{2}{\rightarrow} aabSbaa \overset{3}{\rightarrow} aabbaa$

https://en.wikipedia.org/wiki/Context-free_grammar

Korak derivacije je element oblika:

$\gamma A \delta \Rightarrow \gamma \alpha \delta$

gde: $\gamma, \delta \in (N \cup T)*$

i $A \rightarrow \alpha$ je pravilo gramatike.

Izvođenje rečenične forme $\tau$ iz rečenične forme $\sigma$ je sekvenca koraka izvođenja:

$\sigma \Rightarrow \beta_1 \Rightarrow \beta_2 \Rightarrow ... \Rightarrow \beta_{n-1} \Rightarrow \tau$

Takođe možemo pisati i $\sigma \overset{*}{\Rightarrow} \tau$, ukoliko imamo 0 ili više koraka, ili $\sigma \overset{n}{\Rightarrow} \tau$ ukoliko imamo tačno $n$ koraka, ili, ukoliko je $n>0$ možemo pisati $\sigma \overset{+}{\Rightarrow} \tau$.

• Bilo koja niska terminala i neterminala koja se može dobiti primenom produkcionih pravila počevši od početnog simbola naziva se rečeničnom formom (Sentential Form). $( x + S ) * S - S * S / ( S + S )$
• Ukoliko se rečenična forma sastoji samo od terminala onda je to rečenica (Sentence). $( x + y ) * x - z * y / ( x + x )$

Odnosno možemo pisati da je rečenična forma niska $\alpha$ za koju važi $S \overset{*}{\Rightarrow} \alpha$. A ukoliko važi i $\alpha \in T*$ onda je $\alpha$ rečenica.

1. S → x
2. S → y
3. S → z
4. S → S + S
5. S → S - S
6. S → S * S
7. S → S / S
8. S → ( S )

S (startni simbol)
→ S - S (pravilo 5)
→ S * S - S (pravilo 6, primenjeno na levi neterminal S)
→ S * S - S / S (pravilo 7, primenjeno na desni neterminal S)
→ ( S ) * S - S / S (pravilo 8, primenjeno na levi S)
→ ( S ) * S - S / ( S ) (pravilo 8, primenjeno na desni S)
→ ( S + S ) * S - S / ( S ) (itd.)
→ ( S + S ) * S - S * S / ( S )
→ ( S + S ) * S - S * S / ( S + S )
→ ( x + S ) * S - S * S / ( S + S )
→ ( x + y ) * S - S * S / ( S + S )
→ ( x + y ) * x - S * y / ( S + S )
→ ( x + y ) * x - S * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + x )

https://en.wikipedia.org/wiki/Context-free_grammar

• U svakom koraku izvođenja parser donosi dve odluke:

  1. koji neterminal da zameni?,
  2. sa kojim pravilom da ga zameni? - ukoliko imamo više mogućnosti.
• Prva odluka je najčešće fiksna (npr. uvek se zamenjuje prvi sleva ili prvi sdesna). Ne utiče na izgled stabla.
• Za drugu odluku koriste se tehnike kao što su lookahead (videti u nastavku).
• Strategija pri donošenju druge odluke utiče na izgled stabla parsiranja.

• Levo izvođenje - uvek se prvo razrešava levi neterminal.
• Desno izvođenje - uvek se prvo razrešava desni neterminal.
• Strategija izvođenja je bitna kod parsera koji izvršavaju određene akcije kod svake primene produkcije jer se redosled primene razlikuje iako mogu rezultovati istim stablima parsiranja.

$S \xrightarrow{1} E \xrightarrow{2} E + E \xrightarrow{7} 3 + E\\ \xrightarrow{4} 3 + E * E \xrightarrow{7} 3 + 4 * E \\ \xrightarrow{6} 3 + 4 * (E) \\ \xrightarrow{3} 3 + 4 * (E - E) \\ \xrightarrow{7} 3 + 4 * (7 - E) \\ \xrightarrow{7} 3 + 4 * (7 - 2)$

1. S → E
2. E → E '+' E
3. E → E '-' E
4. E → E '*' E
5. E → E '/' E
6. E → '(' E ')'
7. E → broj

3 + 4 * (7 - 2)

• Kod kontekstno slobodnih gramatika isti neterminal može da se nađe u više produkcija na levoj strani, odnosno postoji izbor mogućih načina izvođenja neterminala.
• Ova situacija omogućava da parseri u zavisnosti od izbora produkcije koje primenjuju kao rezultat dobiju različita stabla parsiranja.
• U slučaju mogućnosti postojanja više različitih stabala parsiranja za isti ulaz kažemo da je gramatika višeznačna.
• Ovo je neminovno kod parsiranja prirodnih jezika, koji su po prirodi višeznačni, ali je loše kod programskih jezika gde je potrebno obezbediti da, ukoliko se ulaz parsira, uvek odgovara jednom stablu.
• Višeznačnost je uglavnom osobina gramatike a ne jezika.

• Klasičan primer je "viseći else" (eng. dangling else).

• U produkciji:

  IF -> 'if' COND 'then' STMT 'else' STMT
        | 'if' COND 'then' STMT

• definisan je if iskaz nekog jezika:

  if stmt1 then if stmt2 then stmt3 else stmt4

• Ova konstrukcija može da se tumači na dva načina. Kod prvog tumačenja je else deo spoljnjeg if iskaza, odnosno:

  if stmt1 then (if stmt2 then stmt3) else stmt4

• dok je kod drugog tumačenja else deo iskaza u sastavu unutrašnjeg if iskaza, odnosno:

  if stmt1 then (if stmt2 then stmt3 else stmt4)

• Rešenje je dodavanjem pravila prioriteta ili dodavanje konteksta kojim se izbegava višeznačnost. Na primer, u if-else klauzuli može se dodati ključna reč endif.

Stablo koje oslikava prioritet i asocijativnost operacija

S → E
E → E '+' E
E → E '-' E
E → E '*' E
E → E '/' E
E → '(' E ')'
E → broj

Ulaz: $3+4*(7-2)$

\begin{gather*} S \xrightarrow{1} E \xrightarrow{4} E * E \xrightarrow{2} E + E * E
\xrightarrow{7} 3 + E * E \xrightarrow{7} 3 + 4 * E
\xrightarrow{6} 3 + 4 * (E) \xrightarrow{3} 3 + 4 * (E - E)
\xrightarrow{7} 3 + 4 * (7 - E) \xrightarrow{7} 3 + 4 * (7 - 2) \end{gather*}

A trebalo bi:

\begin{gather*} S \xrightarrow{1} E \xrightarrow{2} E + E
\xrightarrow{7} 3 + E
\xrightarrow{4} 3 + E * E
\xrightarrow{7} 3 + 4 * E
\xrightarrow{6} 3 + 4 * (E)
\xrightarrow{3} 3 + 4 * (E - E)
\xrightarrow{7} 3 + 4 * (7 - E)
\xrightarrow{7} 3 + 4 * (7 - 2) \end{gather*}

• Često se gramatika može refaktorisati da ne bude višeznačna.
• Određeni parseri omogućavaju dodatna pravila (npr. pravilo prioriteta) koje pomaže u izboru produkcije koju treba primeniti.
• Generalizovani parseri dozvoljavaju višeznačne gramatike. Ukoliko postoje različite interpretacije ulaza biće vraćena sva moguća stabla/interpretacije.
• Pojedini parseri implicitno razrešavaju višeznačnost. Npr. rekurzivni silazni parseri (videti u nastavku) uvek pokušavaju primenu produkcija po redosledu navođenja (sleva na desno).

• Jedna od tehnika razrešavanja višeznačnosti kroz enkodovanje prioriteta i asocijativnosti operacija na nivou gramatike.

  S → E
  E → E + T | E - T | T
  T → T * F | T / F | F
  F → ( E ) | id

• Na ovom primeru vidimo da gramatička pravila za opis operacija višeg nivoa se definišu na nižem nivou sa stanovišta referenciranja.
• Na primer, pravilo E definiše operacije sabiranja i oduzimanja i referencira pravilo T koje definiše operacije množenja i deljenja višeg prioriteta.

• Za prethodno opisan oblik višeznačnosti kažemo da je sintaksna.
• Postoji i drugi izvor višeznačnosti koji nastaje na leksičkom nivou i nastaje kada lekser može da prepozna više tokena na istom mestu u ulaznom stringu.

Na primer:

Something: INT | FLOAT;

terminals
INT: /\d+/;
FLOAT: /\d+(\.\d+)?/;

• Problem nastaje jer terminalna pravila INT i FLOAT mogu da prepoznaju isti deo ulaza ukoliko u ulaznom broju nemamo decimalnu tačku i cifre iza nje. Ovaj problem nastaje zbog preklapanja na početnom delu definicije (\d+).
• Na primer, ako je ulazni string "3" oba pravila mogu da ga prepoznaju što znači da imamo dva moguća rešenja.

• Određene vrste parsera ne smeju da imaju levo rekurzivne produkcije jer to dovodi do beskonačne rekurzije gde parser primenjuje stalno iste produkcije bez konzumiranja tokena sa ulaza. Na primer: $A \rightarrow A a | \epsilon$ Prepoznaje stringove oblika $a*$ ali kod parsera koji ne dozvoljavaju levu rekurziju će doći do beskonačne rekurzije u pokušaju da se prepozna $A$. $recognize(A) \overset{Aa}{\rightarrow} recognize(A) \ldots$
• Mogu biti direktne i indirektne.
• Direktna leva rekurzija je produkcija oblika $A \rightarrow A \gamma$
• Leve rekurzije se mogu refaktorisati da koriste desno rekurzivne produkcije ali gramatika tada često gubi na intuitivnosti.

Pravilo $A \rightarrow Aa | B$ postaje $A \rightarrow Ba*$

Primer:

$expr \rightarrow expr \; "+" \; term \; | \; number$

postaje:

$expr \rightarrow number ("+" \; term)*$

S → E
E → E '+' E
E → E '-' E
E → E '*' E
E → E '/' E
E → '(' E ')'
E → broj

S  → E
E  → T E'
E' → '+' T E'
E' → '-' T E'
E' → Ɛ
T  → F T'
T' → '*' F T'
T' → '/' F T'
T' → Ɛ
F  → ( E )
F  → broj

ili kompaktnije:

S → E
E → T (('+' | '-') T)*
T → F (('*' | '/') F)*
F → '(' E ')' | broj

Refaktorisana gramatika nije ekvivalentna polaznoj jer definiše prioritet i asocijativnost operacija dok kod nerefaktorisane gramatike pored leve rekurzije imamo višeznačnost jer prioriteti i asocijativnost operatora nisu definisani.

Takođe, stabla parsiranja do kojih dolazimo upotrebom refaktorisane gramatike nisu intuitivna kao kod polazne i zahtevaju dodatni posao prilikom analize izraza.

Za ulaz 3 + 4 * ( 7 - 2 ) dobijamo stablo na desnoj strani.

A za dalju obradu daleko bi bilo pogodnije ovakvo stablo koje oslikava smisao ulaznog stringa.

letter = "A" | "B" | "C" | "D" | "E" | "F" | "G"
       | "H" | "I" | "J" | "K" | "L" | "M" | "N"
       | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
       | "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | "_" ;

identifier = letter , { letter | digit | "_" } ;
terminal = "'" , character , { character } , "'"
         | '"' , character , { character } , '"' ;

lhs = identifier ;
rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

http://en.wikipedia.org/wiki/Extended_Backus-Naur_Form

• Top-down (Silazna)

  • Kreće od polaznog neterminala gramatike i pokušava da generiše(izvede) ulazni string primenom produkcija s leva na desno (lhs -> rhs).
  • Od opšteg ka pojedinačnom.
  • Ukoliko se izabere pogrešna alternativa radi se vraćanje - backtrack.
  • Ukoliko ne koriste vraćanje zovu se prediktivni parseri.
  • LL parseri i rekurzivni silazni parseri (recursive descent) koriste ovu strategiju.
  • LL parseri prirodno primenjuju levo izvođenje stabla parsiranja.

• Bottom-up (Uzlazna)

  • Kreće od terminala i primenom produkcija s desna na levo (lhs <- rhs) pokušava da redukuje ulaz na polazni neterminal gramatike.
  • Od pojedinačnog ka opštem.
  • Shift-Reduce - efikasan metod uzlaznog parsiranja.
  • LR parseri koriste ovu strategiju.
  • LR parseri prirodno primenjuju desno izvođenje stabala parsiranja

• Strategija kod koje se koristi određeni broj nekonzumiranih tokena sa ulaza da bi se odlučilo o sledećim koracima kod parsiranja.
• Manji lookahead znači jednostavniji parser ali takođe i manji skup gramatika koje prihvata.
• Koliko tokena unapred koristimo najčešće piše u oznaci parsera - primer LL(1), LR(k).
• Za većinu programskih jezika potreban je samo jedan token lookahead-a - LL(1), LR(1)…

• Strategija kod koje se u slučaju alternativnih derivacija pokušava redom sa svakom i u slučaju da parsiranje ne uspe vrši vraćanje unazad (na stanje izbora alternative) i pokušava se sa sledećom alternativom.
• Parseri koji implementiraju vraćanje često prihvataju veći skup gramatika tj. manja su ograničenja gramatika koje se prihvataju.
• Mana je što u praksi možemo imati veliki broj alternativa što često dovodi do eksponencijalnog vremena parsiranja.
• Ukoliko ne koriste vraćanje (prediktivni parseri) prihvataju manji skup gramatika.

• Algoritam parsiranja kod koga se ne koristi vraćanje unazad (backtracking).
• Analogno determinističkom potisnom automatu.
• Parseri prihvataju klasu determinističkih kontekstno slobodnih jezika (podskup svih kontekstno slobodnih jezika).
• Linearno vreme parsiranja - popularni u praksi.

Gramatika: S → E    E → T + E    E → T    T → int
Ulaz: int + int + int

Production       Input              Action
---------------------------------------------------------
S                int + int + int    Predict S -> E
E                int + int + int    Predict E -> T + E
T + E            int + int + int    Predict T -> int
int + E          int + int + int    Match int
+ E              + int + int        Match +
E                int + int          Predict E -> T + E
T + E            int + int          Predict T -> int
int + E          int + int          Match int
+ E              + int              Match +
E                int                Predict E -> T
T                int                Predict T -> int
int              int                Match int
                                    Accept

http://stackoverflow.com/questions/5975741/what-is-the-difference-between-ll-and-lr-parsing

http://www.dabeaz.com/ply/ply.html#ply_nn22

• Generalized LR parser.
• Parsiranje višeznačnih gramatika.
• Efektivno radi kao LR parser ali u svakom stanju dozvoljava više prelaza čime simulira nedeterministički algoritam.
• Kod višeznačnih ulaza vraća skup stabala parsiranja (šumu parsiranja - Parse Forest).
• Na korisniku je da odredi ispravno stablo - najčešće dodatnim pravilima (npr. prioritet, asocijativnost).
• Bison u novijim verzijama može da generiše GLR parser.
• SDF parser, Elkhound, DParser, parglare.

• Kod LL parsera problem je predvideti produkciju koju treba primeniti sledeće.
• Kod većine LR parsera (implementiranih kao SHIFT-REDUCE) problem je kada uraditi REDUCE operaciju i na koji neterminal redukovati, odnosno kada uraditi SHIFT.
• I kod jednog i kod drugog algoritma generiše se tablica koja pomaže parseru da donese odluku u toku parsiranja.

• Silazni parser izgrađen na bazi međusobno rekurzivnih procedura.
• Svaka procedura implementira jednu produkciju odnosno prepoznavanje jednog (ne)terminala.
• Kod prediktivnih parsera ne zahteva se vraćanje (backtracking).
• Ukoliko se koristi vraćanje vreme parsiranja može eksponencijalno da poraste kod složenijih gramatika.

• Šematski opis rekurzivnog silaznog parsera sa vraćanjem (recursive descent parser with backtracking). Orijentisan je ka prepoznavanju ulaznog teksta.
• Ideje datiraju unazad u ’70 godine prošlog veka.¹
• Rekurzivni silazni parseri nisu imali veću popularnost u 20. veku jer vreme parsiranja može biti eksponencijalno ukoliko se ne koristi tehnika memoizacije u kom slučaju je linearno ali je potreban značajan memorijski prostor koji direktno zavisi od veličine ulaza.
• Bryan Ford je obnovio interesovanje za TDPL (Top-Down Parsing Language) fomalizam za opis gramatika.²
• Gramatike koje opisuju TDPL Ford naziva gramatikama izraza za parsiranje (Parsing Expression Grammars - PEG).

1. 1. Birman, The tmg recognition schema. PhD thesis, 1970
2. 1. Ford, /Packrat parsing: a practical linear-time algorithm with

   backtracking/. Master thesis, Massachusetts Institute of Technology, 2002

• Formalizam za opis TDPL.
• Osnovna prednost PEG gramatika u odnosu na CFG jeste upotreba operatora uređenog izbora (eng. ordered choice) koji omogućava nedvosmislenost u parsiranju.
• Često se ovaj operator označava sa / umesto sa | da bi se naglasila uređenost.
• Ako ulazni tekst pripada jeziku koji opisuje dati PEG tada postoji samo jedno validno stablo koje ga opisuje.
• Odnosno, gramatike ne mogu biti višeznačne.
• Kod CFG postoji neodređenost jer je redosled izbora alternativa neodređen i u praktičnim primenama zavisi od korišćenog algoritma u implementaciji parsera.
• Vrsta parsera koja koristi PEG i implementirana je kao rekurzivni silazni parser sa bektrekingom i memoizacijom naziva se pakrat parser.

• Rekurzivni silazni parser sa vraćanjem koji koristi tehniku memoizacije (pamćenje derivacija podstabala) da bi obezbedio linearno vreme izvršavanja.
• Prepoznaje bilo koji LL(k)/LR(k) jezik kao i mnoge jezike koji zahtevaju neograničen lookahead.
• Bolje kompozitne osobine od LL/LR parsera što ga čini pogodnim za opis proširivih dinamičkih jezika.

Kako enkodovati pravila prioriteta i eliminisati levu rekurziju?

Gramatike izraza za parsiranje se sastoje od:

• konačnog skupa neterminalnih simbola $N$,
• konačnog skupa terminalnih simbola koji je disjunktan sa $N$, u oznaci $\Sigma$,
• konačnog skupa pravila parsiranja $P$,
• početnog izraza $e_s$

Skup terminalnih simbola (terminala) predstavlja alfabet jezika. Neterminalni simboli (neterminali) su varijable koje predstavljaju nisku sastavljenu od terminala i/ili drugih neterminala.

Pravila parsiranja su oblika $A \leftarrow e$ gde je $A$ neterminal a $e$ predstavlja izraz za parsiranje. Izraz za parsiranje može biti prost i u tom slučaju može biti:

• bilo koji terminalni simbol,
• bilo koji neterminalni simbol,
• prazan string

Ukoliko su $e$, $e_1$ i $e_2$ izrazi za parsiranje tada se složeni izrazi za parsiranje mogu kreirati upotrebom sledećih operatora:

PEG poseduje i posebnu klasu operatora – sintaksne predikate. Oni omogućavaju definisanje dodatnih informacija o kontekstu u kome se nalazi izraz koji pokušavamo da prepoznamo bez konzumiranja ulaznog stringa. Sintaksni predikati su sledeći:

• I predikat: $\&e$ – ukoliko se na ulazu prepozna izraz $e$ predikat ima istinitu vrednost,
• Ne predikat: $!e$ – ukoliko se na ulazu ne prepozna izraz $e$ predikat ima istinitu vrednost.

Sintaksni predikati omogućavaju definisanje izraza za parsiranje oblika $e_1 \&e_2$ – biće prepoznat izraz $e_1$ samo ukoliko iza njega sledi tekst koji se može prepoznati izrazom $e_2$, pri čemu deo ulaznog teksta prepoznatog izrazom $e_2$ neće biti uklonjen sa ulaza (neće biti konzumiran).

• Na osnovu formalne gramatike generišu programski kod parsera koji će prepoznavati rečenice na datom jeziku i pretvarati ulazne stringove u stabla parsiranja.
• Često implementiraju mehanizam za obilazak stabla parsiranja i njegovu transformaciju.
• Mogu generisati i lexer (scanner) a mogu biti i scannerless.
• Neki od poznatijih parser generatora: ANTLR, JavaCC, yacc, bison.

• ANTLR (ANother Tool for Language Recognition) je LL(*) parser generator implementiran na programskom jeziku Java.
• Iz opisa gramatike kreira parser kao i infrastrukturu za analizu stabla (vizitori, akcije koje se izvršavaju kada se prepozna određena konstrukcija).

• Konfigurišu se gramatikom u vreme izvršavanja (run-time) tj. interpretiraju gramatiku.
• Brz round-trip. Nema generisanja parsera. Moguća izmena gramatike "u letu".
• Arpeggio, parglare, i textX rade kao interpreteri.