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

Sorry, your browser does not support SVG.

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

Sorry, your browser does not support SVG.

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

Sorry, your browser does not support SVG.

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-else klauzule može se dodati ključna reč endif.

2.13 Višeznačna gramatika - primer

Sorry, your browser does not support SVG.

2.14 A u ovom slučaju želimo

Stablo koje oslikava prioritet i asocijativnost operacija

Sorry, your browser does not support SVG.

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

LR-Primer.png

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

Sorry, your browser does not support SVG.

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.