Jezici specifični za domen

Tekstualne sintakse

Prof. dr Igor Dejanović (igord at uns ac rs)

Kreirano 2021-11-18 Thu 13:14, pritisni ESC za mapu, m za meni, Ctrl+Shift+F za pretragu

Sadržaj

1. Uvod
2. Formalne gramatike
3. Strategije parsiranja

1. Uvod

1.1. Jezički softver (Language Software)

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.

1.2. Leksička analiza

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…

1.3. Leksična analiza - primer

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),...]

1.4. Parsiranje - sintaksna analiza

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

1.5. Stablo parsiranja

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.

1.6. Stablo parsiranja - primer

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

1.7. Stablo apstraktne sintakse

Svaki iskaz na datom jeziku se može na apstraktan način opisati stablom apstraktne sintakse (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.

1.8. Primer stabla apstraktne sintakse

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

1.9. Razlike između stabla apstraktne i konkretne sintakse

Stablo konkretne sintakse je bazirano na formalnoj gramatici koja opisuje detalje zapisa u tekstualnom obliku.
Stablo apstraktne sintakse sadrži suštinu jezičkog iskaza.
Možemo imati više gramatika za isti jezik odnosno jedno stablo apstraktne sintakse možemo zapisati na više različitih načina što rezultuje različitim stablima konkretne sintakse.
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 može rezultovati istim stablom apstraktne sintakse.

2. Formalne gramatike

2.1. 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.

2.2. Formalna gramatika - definicija

Formalna gramatika je G = (N, Σ, P, S) gde je:

N - konačni skup neterminalnih simbola,
Σ - konačni skup terminalnih simbola,
P - konačni skup produkcionih pravila (produkcija) oblika: (Σ ∪ N)∗ N(Σ ∪ N)∗ → (Σ ∪ N)∗
S - neterminal iz skupa N (S ∈ N) koga nazivamo početnim simbolom.

2.3. Notacija

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 prazan)
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\).

2.4. Klasifikacija formalnih gramatika po Čomskom

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

tipa 3 - rekurzivno prebrojive - bez ograničenja na oblik produkcija.
tipa 2 - kontekstno zavisne - produkcije oblika: αAβ → αγβ
tipa 1 - kontekstno slobodne - produkcije oblika: A → γ
tipa 0 - regularne - produkcije oblika: A → a, A → aB

2.5. Kontekstno slobodne gramatike (Context-Free Grammars - CFGs)

Produkcije oblika: A → γ
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).

2.6. Primer kontekstno slobodne gramatike

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

gde je skup produkcionih pravila P dat kao:

S → aSa
S → bSb
S → ε

2.7. Izvođenje - derivacija (Derivation)

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.

S → aSa    (1)
S → bSb    (2)
S → ε      (3)

S (1)→ aSa (1)→ aaSaa (2)→ aabSbaa  (3)→ aabbaa

2.8. Izvođenje - notacija

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 \(\sigma\) iz rečenične forme \(\tau\) 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\).

2.9. Rečenična forma i rečenica

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.

2.10. Jezik generisan gramatikom

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.

2.11. Primer izvođenja - algebarski izrazi

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 )

2.12. Odluke pri izvođenju

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).
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.

2.13. Strategije izvođenja sa stanovišta izbora neterminala za zamenu

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.

2.14. Levo izvođenje - primer

2.15. Višeznačne gramatike - primer - dangling else

Stablo parsiranja za određeni ulaz nije jednoznačno određeno CFG gramatikom
Višeznačna gramatika je gramatika kod koje postoji ulazni string sa više različitih levih izvođenja.
Ili jednostavnije: ukoliko postoji ulazni string koji može da rezultuje sa više različitih stabala parsiranja.
Klasičan primer je “viseći else”:

if a then if b then s else s2
Može da se parsira kao:
if a then (if b then s) else s2
ili kao:
if a then (if b then s else s2)

Rešavaju se dodavanjem pravila prioriteta ili dodavanjem konteksta kojim se izbegava višeznačnost. Na primer, za kod if-else klauzule može se dodati ključna reč endif.

2.16. Višeznačna gramatika - primer

2.17. A u ovom slučaju želimo

Stablo koje oslikava prioritet i asocijativnost operacija

2.18. Razrešavanje višeznačnosti

Višeznačnost je uglavnom osobina gramatike a ne jezika.
Č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 (s leva na desno).

2.19. Leva rekurzija

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.
Mogu biti direktne i indirektne.
Direktna leva rekurzija je produkcija oblika A → Aγ.
Leve rekurzije se mogu refaktorisati da koriste desno rekurzivne produkcije ali gramatika tada često gubi na intuitivnosti.

2.20. Eliminacija leve rekurzije u opštem slučaju

Pravilo A → Aa | B postaje A → Ba*

Primer:

expr → expr '+' term | number

postaje:

expr → number ('+' term)*

2.21. Extended Backus–Naur Form - EBNF

Meta-sintaksa za zapis kontekstno slobodnih gramatika.
ISO/IEC 14977
Produkcije dodeljuju sekvencu simbola (terminala i neterminala) neterminalima.
U širokoj upotrebi kod parser generatora i interpretera za opis gramatike jezika.

2.22. Primer - EBNF u EBNF-u

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 } ;

3. Strategije parsiranja

3.1. Strategije parsiranja

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

3.2. Lookahead

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)…

3.3. Vraćanje (backtracking)

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.

3.4. LL parser

Top-down parser koji podržava podskup kontekstno slobodnih gramatika.
Konzumira tokene s leva na desno i kreira levo izvođenje.
Klasa gramatika koju podržava LL parser nazivamo LL gramatikama.
LL(k) parser koristi k tokena unapred (lookahead) za odluku koju sledeću produkciju da primeni. Ako takav parser postoji za neku gramatiku, a da ne koristi vraćanje (backtracking) tada kažemo da je gramatika LL(k). Jezik za koji postoji LL(k) gramatika naziva se LL(k) jezik.
LL(*) parseri nisu ograničeni na broj tokena koje mogu preuzeti sa ulaza da bi odlučili o sledećoj produkciji - dinamički se prilagođavaju.
Veće k - moćniji ali i složeniji parser. LL(1) su naročito popularni kod računarskih jezika.

3.5. Primer LL parsiranja

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

3.6. LR parser

Bottom-up parser koji podržava podskup kontekstno slobodnih gramatika.
Implementiraju Shift-Reduce strategiju i koriste tablice stanja-prelaza. Skup gramatika koje prihvata je nadskup skupa koje prihvata prediktivni LL parser.
1965 Donald Knuth.
Gramatika uglavnom ne mora da se prilagođava kao kod LL parsera. Mogu se navoditi rekurzivne produkcije.
Podvarijante: LALR (Look-Ahead), SLR (Simple), GLR (Generalized LR).
Generatori: yacc, GNU Bison, Elkhound…
Interpreteri: parglare

3.7. LR parsiranje - primer

3.8. GLR

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.

3.9. LL - LR napomene

Kod LL parsera problem je određivanje produkcije koju treba primeniti nad neterminalom.
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.

3.10. Rekurzivni silazni parser - Recursive descent parser

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.

3.11. Top-Down Parsing Language

Š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.^1,2
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).

3.12. PEG - Parsing Expression Grammars

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.
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.

3.13. Packrat 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.

3.14. Refaktorisanje gramatike za PEG parsere

Kako enkodovati pravila prioriteta i eliminisati levu rekurziju?

3.15. Determinističko parsiranje

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.

3.16. Pristupi u izradi parsera

Parser generatori
Interpreteri gramatika

3.17. Parser generatori

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.

3.18. ANTLR

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).

3.19. Interpreteri

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.