Jezici specifični za domen
Tekstualne sintakse
Prof. dr Igor Dejanović (igord at uns ac rs)
Kreirano 2020-12-10 Thu 12:10, pritisni ESC za mapu, m za meni, Ctrl+Shift+F za pretragu
Sadržaj
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 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.3 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.1
- 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.4 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.5 Stablo parsiranja - primer
Stablo parsiranja za ulazni string -(4-1)*5/(2+4.67)
1.6 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.7 Primer stabla apstraktne sintakse
-(4-1)*5/(2+4.67)
1.8 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 kao4 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 skupaN (S ∈ N)koga nazivamo početnim simbolom.
2.3 Klasifikacija formalnih gramatika po Čomskom
Formalne gramatike se mogu klasifikovati prema hijerarhijskoj klasifikaciji Noama Čomskog1. 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.4 Konteksno 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.5 Primer kontekstno slobodne gramatike
G = ({S}, {a, b}, P, S)
gde je skup produkcionih pravila P dat kao:
S → aSa S → bSb S → ε
2.6 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.7 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.8 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 )
2.9 Odluke pri izvođenju
- U svakom koraku izvođenja parser donosi dve odluke:
- koji neterminal da zameni?,
- 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.10 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.11 Levo izvođenje - primer
2.12 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-elseklauzule može se dodati ključna rečendif.
2.13 Višeznačna gramatika - primer
2.14 A u ovom slučaju želimo
Stablo koje oslikava prioritet i asocijativnost operacija
2.15 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.16 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.17 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.18 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.19 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 podž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 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 prepoznvanje 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.3
- 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).