Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace oooooooo LR(k) překlady Zpracování silných LR(k) gramatik Šárka Vavrečková Ústav informatiky, FPF SU Opava sarka.vavreckova@fpf.slu.cz Poslední aktualizace: 23. listopadu 2023 □ 3 < 1 ► 1 ~00>0 Rozkladová tabulka •oooo Příklad OOOO Matematické výrazy ooo Implementace oooooooo Překladový automat pro silnou LR gramatiku Princip • na vstupu je terminálni řetězec • ve zpracovávaném řetězci hledáme pravé strany pravidel, redukujeme je na levé (tj. na přepisované neterminály) • použitelné operace: O reduce(i) - redukce podle z-tého pravidla O push - do zásobníku vloží jeden symbol ze vstupu O accept - akceptování vstupu, sestrojili jsme pravý rozklad reprezentující derivační strom, vstup je celý zpracovaný a zásobník prázdný O error (resp. prázdná buňka tabulky) - syntaktická chyba □ g - = = -OQ,o Rozkladová tabulka o«ooo Příklad oooo Matematické výrazy ooo Implementace oooooooo Definice (Překladový automat pro silnou LR(k) gramatiku) Překladový automat pro silnou LR(k) (rozšířenou) gramatiku G = (N, T, P, S) je zásobníkový automat s jediným stavem, rozšířený o výstupní pásku a definovaný dále popsanou rozkladovou tabulkou. Konfigurace překladového automatu má tvar (a, f3,7), kde a je nepřečtená část vstupní pásky, /3 je obsah zásobníku a 7 je obsah výstupní pásky. Počáteční konfigurace má tvar (w, #, e), kde w je vstupní řetězec a # symbol konce zásobníku. Rozkladová tabulka automatu pro silnou LR(k) gramatiku je zobrazení M : (TUNU {#}) x (TU {§})k {reduce(l),... ,reduce(n),push,accept,error}, kde jednotlivé funkční hodnoty mají tento význam: □ g - = = -OQ,o Rozkladová tabulka oo»oo Příklad oooo Matematické výrazy ooo Implementace oooooooo Definice (Překladový automat pro silnou LR(k) gramatiku) • reduce(i), 1 < i < n: Je-li A ->> a i-té pravidlo gramatiky, na vrcholu zásobníku je řetězec a, na vstupu symbol x, provede automat změnu konfigurace (xcr, 7) h (xcr, jí), tedy v zásobníku nahradí řetězec a levou stranou pravidla A ->> a a na výstupní pásku připíše číslo i. 9 push: Automat vloží symbol ze vstupu do zásobníku, načte další symbol ze vstupu, tedy je-li na vstupu symbol x, provede změnu konfigurace (xcr, 0,7) h (cr, x0,7). • accept: K přijetí vstupu dojde, pokud je v zásobníku pouze startovací symbol gramatiky a vstup je celý přečtený. Na výstupní pásce je pravý rozklad vstupní věty • error: Syntaktická chyba. □ g - = = -OQ,o Rozkladová tabulka ooo»o Příklad oooo Matematické výrazy ooo Implementace oooooooo Rozkladová tabulka pro silnou LR(k) gramatiku U r(í) r(í) v $ acc push z-té pravidlo gramatiky: A —>• ax x G (N U T) A -> e x G BEFORE (A) w G FOLLOWfc(A) y G EFFfc(7 • FOLLOWfc(B)) ■ Vstup r- Akce: push Zásobí • reduce • accept • push • error □ g - = = -OQ>0 Rozkladová tabulka oooo* Příklad oooo Matematické výrazy ooo Implementace oooooooo Rozkladová tabulka pro silnou LR(k) gramatiku Postup vytvoření O Ke gramatice G vytvoříme rozšířenou gramatiku G = (N U {S'}, T U {#}, P U {Sř S7). O Vypočteme množiny BEFORE(X) a FOLLOWfc(X) pro všechny neterminály gramatiky podle potřeby EFFfc. Q Tvoříme obsah tabulky F(řádek, sloupec): □ ™ Rozkladová tabulka oooo* Příklad oooo Matematické výrazy ooo Implementace oooooooo Rozkladová tabulka pro silnou LR(k) gramatiku Postup vytvoření O Ke gramatice G vytvoříme rozšířenou gramatiku G = (N U {S'}, T U {#}, P U {Sř S7). O Vypočteme množiny BEFORE(X) a FOLLOWfc(X) pro všechny neterminály gramatiky podle potřeby EFFfc. Q Tvoříme obsah tabulky F(řádek, sloupec): □ ™ Rozkladová tabulka oooo* Příklad oooo Matematické výrazy ooo Implementace oooooooo Rozkladová tabulka pro silnou LR(k) gramatiku Postup vytvoření O Ke gramatice G vytvoříme rozšířenou gramatiku G = (N U {S'}, T U {#}, P U {Sř S7). O Vypočteme množiny BEFORE(X) a FOLLOWfc(X) pro všechny neterminály gramatiky podle potřeby EFFfc. 0 Tvoříme obsah tabulky F(řádek, sloupec): • pro každé A aX (i-té) pravidlo gramatiky, pro všechny řetězce u aABc, A^c FOLLOW(S) n FOLLOW(A) = 0 (b) Není co testovat. (c) Není co testovat. O (a) Není co testovat. (b) S e, Sř #S FOLLOW(S) n EFF(S • FOLLOW(S') = 0 (C) S e, Sf #S FOLLOW(S) n EFF(#S • FOLLOW(S') = 0 □ g - = = -OQ,o Rozkladová tabulka ooooo Příklad oo»o Matematické výrazy ooo Implementace oooooooo Gramatika S'^#S S —>• aABc e A Ab I c B Bd m ® 5),(6 BEFORE(S') = {#} BEFORE(S) = {#} BEFORE (A) = {a} BEFORE (B) = {A} FOLLOW(S') FOLLOW(S) : FOLLOW(A) FOLLOW(B) :{$} {$} {ni, b} a b c d m $ acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 A -+ aX ® m e FOLLOWfc(A) F(X, w) = reduce (i) A^e ® X e BEFORE (A) u G FOLLOWfc(A) F(X, w) = reduce (i) B /3X7 7 + e u e EFFfc(7 • FOLLOWfc(B)) F(X, w) = pws/z F(S, $) = accept Rozkladová tabulka ooooo Příklad oo»o Matematické výrazy ooo Implementace oooooooo Gramatika S'^#S S —>• aABc e A Ab I c B Bd m ® 5),(6 BEFORE(S') = {#} BEFORE(S) = {#} BEFORE (A) = {a} BEFORE (B) = {A} FOLLOW(S') FOLLOW(S) : FOLLOW(A) FOLLOW(B) :{$} {$} {ni, b} a b c d m $ acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 A -+ aX ® m e FOLLOWfc(A) F(X, w) = reduce (i) A^e ® X e BEFORE (A) u G FOLLOWfc(A) F(X, w) = reduce (i) B (3Xj u e EFFfc(7 • FOLLOWfc(B)) F(X, u) = push F(S, $) = accept Rozkladová tabulka ooooo Příklad oo»o Matematické výrazy ooo Implementace oooooooo Gramatika S'^#S S —>• aABc e A Ab I c B Bd m ® 5),(6 BEFORE(S') = {#} BEFORE(S) = {#} BEFORE (A) = {a} BEFORE (B) = {A} FOLLOW(S') FOLLOW(S) : FOLLOW(A) FOLLOW(B) :{$} {$} {ni, b} a b c d m $ acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 A -+ aX ® m e FOLLOWfc(A) F(X, w) = reduce (i) A -+ e ® X e BEFORE (A) m G FOLLOWfc(A) F(X, w) = reduce (i) B /3X7 7 ^ £ m G EFFfc(7 • FOLLOWfc(B)) F(X, w) = push F(S, $) = accept Rozkladová tabulka ooooo Příklad oo»o Matematické výrazy ooo Implementace oooooooo Gramatika S'^#S S —>• aABc e A Ab I c B Bd m ® 5),(6 BEFORE(S') = {#} BEFORE(S) = {#} BEFORE (A) = {a} BEFORE (B) = {A} FOLLOW(S') FOLLOW(S) : FOLLOW(A) FOLLOW(B) :{$} {$} {ni, b} a b c d m $ acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 A -+ aX ® m e FOLLOWfc(A) F(X, w) = reduce(/) A^e ® X e BEFORE (A) u G FOLLOWfc(A) F(X, w) = reduce (i) B /3X7 u e EFFfc(7 • FOLLOWfc(B)) F(X, w) = pws/z F(S, $) = accept Rozkladová tabulka ooooo Příklad oo»o Matematické výrazy ooo Implementace oooooooo Gramatika S'^#S S —>• aABc e A Ab I c B ^ Bd m ® 5),(6 BEFORE(S') = {#} BEFORE(S) = {#} BEFORE (A) = {a} BEFORE (B) = {A} FOLLOW(S') FOLLOW(S) : FOLLOW(A) FOLLOW(B) :{$} {$} {ni, b} a b c d m $ acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 A —)► aX ® m G FOLLOWfc(A) F(X, w) = reduce (i) A^e ® X e BEFORE (A) m G FOLLOWfc(A) F(X, w) = reduce (i) B /3X7 7 ^ £ m G EFFfc(7 • FOLLOWfc(B)) F(X, w) = pws/z F(S, $) = accept Rozkladová tabulka ooooo Příklad ooo» Matematické výrazy ooo Implementace oooooooo Zpracování vstupu podle tabulky a b c d m $ S' acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 Gramatika: Automat: ($, #, e)h($, #S, 2)h($, S', 2,0) □ g - = = «0^0 Rozkladová tabulka ooooo Příklad ooo» Matematické výrazy ooo Implementace oooooooo Zpracování vstupu podle tabulky a b c d m $ S' acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 Gramatika: S' S aABc aABdc aAmdc acmdc Automat: (acmdc%, #, e) h (cmdc%, #a, e) h (mdc%, #ac, e) h (mdc%, #aA, 4) h h (dc$, #flAm, 4) h (dc$, #aAB, 4,6) h (c$, #aABd, 4,6) h h (c$, #aAB, 4,6,5) h ($, #aABc, 4,6,5) h ($, #S, 4,6,5,1) h ($, S', 4,6,5,1,0) Rozkladová tabulka ooooo Příklad ooo» Matematické výrazy ooo Implementace oooooooo Zpracování vstupu podle tabulky a b c d m $ S' acc s rO A push push B push push a push b r3 r3 c r4 r4 r1 d r5 r5 m r6 r6 # push r2 Odvození slova nepatřícího do jazyka rozpoznávaného automatem: (aba%, #, e) \~ (ba%, #a, e) h error □ g - = = -00,0 Rozkladová tabulka ooooo Příklad oooo Matematické výrazy •oo Implementace oooooooo Příklad 2 E^ AT A^E+ T^BF B T* I F —>• n I / T/|e I (E) FOLLOW(S) = {$} FOLLOW(E) = {+,-,),$} FOLLOW (A) = {«,/,(} FOLLOW(T) = {*,/, +,-,),$} FOLLOW(B) = {n, z, (} FOLLOW(F) = {*,/, +,-,),$} EFF(+ • FOLLOW (A)) = {+} EFF(— • FOLLOW (A)) = {-} EFF( ) • FOLLOW(F)) = { )} EFF(* • FOLLOW(B)) = {*} EFF(/ • FOLLOW(B)) = {/} ® ® © ©,©,© 9) ,09,0$ BEFORE (S) BEFORE (E) BEFORE (A) BEFORE (T) BEFORE (B) BEFORE (F) {#} {(,#} {(,#} {A} {A} {B} EFF(E • FOLLOW(S)) = 0 EFF(E) • FOLLOW (F)) = 0 EFF(T • FOLLOW(E)) = 0 EFF(F • FOLLOW(T)) = {n, i, ( } W C33 H ^ ft CD 4- 4- 4- 4- -i- 4- s Höh — * ^ + H tn hi hi 33 O N ?r OJ Q. O < O" (U 00 00 + 03 O) O) CO CO ro ro CO CO CO Ul Ul 00 00 + ©0 © ©@©©e© o w w o hrt w o o w w w w O O 33 w O w w O O O w w w w O O :>:> "d Dd H rt cn o :g O ôT O °- CO O) CO ro □ CO CO 00 Ul Ul Cd cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www o o o < N I Hl ..... ó p O 3 O -o O CD O 3 O ro O * o ro + -n CH tm en W C33 H ^ ft CD 4- 4- 4^ 4- -i- 4- s Höh — * ^+ H W tri hl J3 o N ?r fu Q. O < 3" O" O) O) CO CO ľO ľO 00 00 CO CO CO Ul Ul + ©0 © o w w o w w o o w w w w O O :>:> O w w O hrt w O O w w w w O O :>:> ^ ta n ^ rt to o :° O ôT O CL CO O) CO ľO 00 □ CO CO Ul Ul Cd cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www w ca h ^ w to o o o < N I ca ^ ^: Hl ..... ó p O 3 O -o O a> O 3 O $D O * O <1> + -n CH W tu H ^ hi ^ 4- 4- 4^ 4- -i- 4- — * W _i_ h tí tTj tTj I 00 J3 O N ?r OJ Q. O < O" (U O) O) CO OJ ro ro cn cn 00 00 CO CO CO cn cn cn cn t3 cn t3 cn + VO ON ©0 © O w w O w hri O O w w w w O O :>:> O w w O O O w w w w O O :>:> "ti öd h ^ tm cr> o :° O ôT O CL CO cn O) 00 ro cn 00 □ CO CO cn cn cn Cd Cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www o o o < N I Hl ..... ó p O 3 O -o O CD O 3 O ro O * o ro W C33 H ^ ft CD 4- 4- 4- 4- -i- 4- s Höh — * ^ + H tn hi hi 33 O N ?r OJ Q. O < O" (U 00 00 + 03 O) O) CO CO ro CO CO CO Ul Ul 00 00 + ©0 © ©@©©e© w o w w o o o w w w w O O :>:> O w w O w hri O O w w w w O O :>:> "d Dd H rt cn o :g O ôT O CL CO O) CO □ CO CO 00 Ul Ul Cd cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www W 03 H ^ W 0-> o o o CD- < N I Ca ^ ^: Hl ..... Ó p O 3 O -o O CD O 3 O $D O * O <1> + 03 tm Ti öd H tn-j cr> "i- >ť 4" -\r s Höh — * ^ + H m w hl o N ?r fu Q. O < 3" O" O) O) CO CO ro t3 t3 00 00 CO CO CO Ul Ul + VO ON ©0 © w o r1 r1 o hrt w o o r1 w r1 r1 O O :>:> O r1 r1 O w w O O w r1 r1 r1 O O :>:> Ti öd H tn-j cr> o :° O ôT O °- CO O) CO ro t3 00 □ CO CO Ul Ul Cd cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www Ti öd H W cr> o O o CD- < N I öd ^ ^: Hl ..... Ó p O 3 O -o O CD O 3 O $D O * O <1> + -n CH tm en W C33 H ^ ft CD 4- 4- 4^ 4- -i- 4- s Höh - * ^ + H m tri hl o N ?r fu Q. O < 3" O" O) O) CO CO ľO ľO 00 00 CO CO CO Ul Ul t3 + VO ON ©0 © o r1 w o hrt w o o r1 r1 r1 r1 O O :>:> w O w r1 O hrt w O O r1 r1 r1 w O O :>:> ^ ta n ^ rt to o :g O ôT O CL CO t3 O) CO ľO 00 □ CO CO Ul Ul Cd cd cd WWW WWW O O O >d >d >d www Cd cd cd www www O O O >d >d >d www w ca h ^ w to o O o < N I ca ^ ^: Hl ..... ó p O 3 O -o O a> O 3 O $D O * O <1> Rozkladová tabulka ooooo Příklad oooo Matematické výrazy Implementace oooooooo S^#E © FOLLOW(S) = {$} BEFORE(S) = {#} E^AF © FOLLOW(E) = {+,-),$} BEFORE(E) = {(,#} A^E+ E— £ ©,©,© FOLLOW(A) BEFORE(A) = {(,#} T ^BF © FOLLOW(T) = {*,/,+,-),$} BEFORE(T) = {A} B —^ T* F j | e ©,©,© FOLLOW(B) = {M, (} BEFORE(B) = {A} F —>> n \ i | (E) FOLLOW(F) = {*,/,+,-),$} BEFORE(F) = {B} n i + — * / ( ) $ S flCC E push push push rO r8 r8 r8 T r1 r1 push push r1 r1 B push push push F r5 r5 r5 r5 r5 r5 n r9 r9 r9 r9 r9 r9 i r10 r10 r10 r10 r10 r10 + r2 r2 r2 — r3 r3 r3 * r6 r6 r6 / rľ rľ rľ ( r4 r4 r4 ) r11 r11 r11 r11 r11 r11 # r4 r4 r4 □ Rozkladová tabulka ooooo Příklad oooo Matematické výrazy Implementace oooooooo S^#E © FOLLOW(S) = {$} BEFORE(S) = {#} E^AF © FOLLOW(E) = {+,-),$} BEFORE(E) = {(,#} A^E+ E— £ ©,©,© FOLLOW(A) BEFORE(A) = {(,#} T ^ BF © FOLLOW(T) = {*,/,+,-),$} BEFORE(T) = {A} B —^ T* F j | e ©,©,© FOLLOW(B) = {M, (} BEFORE(B) -{A} F —>> n \ i | (E) FOLLOW(F) = {*,/,+,-),$} BEFORE(F) = {B} n i + — * / ( ) $ S acc £ push push push rO A r8 r8 r8 T r1 r1 push push r1 r1 B push push push F r5 r5 r5 r5 r5 r5 r9 r9 r9 r9 r9 r9 MO MO r10 r10 r10 r10 + r2 r2 r2 — r3 r3 r3 * r6 r6 r6 / rľ rľ rľ ( r4 r4 r4 ) r11 r11 r11 r11 r11 r11 # r4 r4 r4 □ Rozkladová tabulka ooooo Příklad oooo Matematické výrazy Implementace oooooooo S^#E © FOLLOW(S) = {$} BEFORE(S) = {#} E^AT © FOLLOW(E) = {+,-),$} BEFORE(E) = {(,#} A^E+ E— £ ©,©,© FOLLOW(A) BEFORE(A) = {(,#} T ^BF © FOLLOW(T) = {*,/,+,-),$} BEFORE(T) = {A} B —^ T* F j | e ©,©,© FOLLOW(B) = {M, (} BEFORE(B) = {A} F —>> n \ i 1 (£ FOLLOW(F) = {*,/,+,-),$} BEFORE(F) = {B} n z + — * / ( ) $ S flCC £ push push push rO A r8 r8 r8 T r1 r1 push push r1 r1 B push push push F r5 r5 r5 r5 r5 r5 n r9 r9 r9 r9 r9 r9 i MO MO r10 r10 r10 r10 + r2 r2 r2 — r3 r3 r3 * r6 r6 r6 / rľ rľ rľ ( r4 r4 r4 r11 r11 r11 r11 r11 r11 # r4 r4 r4 □ Rozkladová tabulka ooooo Příklad oooo Matematické výrazy n i + — * / ( ) $ s flCC E push push push rO A r8 r8 r8 T r1 r1 push push r1 r1 B push push push F r5 r5 r5 r5 r5 r5 n r9 r9 r9 r9 r9 r9 i MO MO MO MO MO MO + r2 r2 r2 — r3 r3 r3 * r6 r6 r6 / r7 r7 r7 ( r4 r4 r4 ) r11 r11 r11 r11 r11 r11 # r4 r4 r4 (n + ž * n$, #, e) h (n + ž * n$, #A, 4) h (n + i * n$, #AB, 4,8) h (+ž * n$, #ABn, 4, 8) h h (+i * n$, #ABF, 4,8,9) h (+z * n$, #AT, 4,8,9,5) h (+z * n$, #E, 4,8,9,5,1) h h (z * n$, #E+, 4,8,9,5,1) h (z * n$, #A, 4,8,9,5,1,2) h (z * n$, #AB, 4,8,9,5,1,2,8) h h (*n$, #ABz, 4,8,9,5,1,2,8) h (*n$, #ABF, 4,8,9,5,1,2,8,10) h (*n$, #AT, 4,8,9,5,1,2,8,10,5) h h (n$, #AT*, 4,8,9,5,1,2,8,10,5) h (n$, #AB, 4,8,9,5,1,2,8,10,5) h ($, #ABn, 4,8,9,5,1,2,8,10,5) h ($, #E, 4,8,9,5,1,2,8,10,5,1) h ($, S, 4, 8,9,5,1,2,8,10,5,1,0) h accept Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace •ooooooo Implementace přepisem rozkladové tabulky Průběh analýzy O Používáme zásobník. O Zavoláme funkci iex o („přednačteme" jeden symbol), typ a atribut symbolu uložíme do globální proměnné typu TSymboi. O V cyklu jsou volány funkce redukce pravidel v zásobníku a vkládání terminálů ze vstupu do zásobníku. O Pokud v derivaci nelze dále pokračovat tak, aby byl vygenerován přesně takový řetězec, jaký je na vstupu syntaktická chyba. □ g - = = -OQ,o Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace O0OOOOOO Potřebujeme tyto funkce: • reduce (čí sio_pravidia) - pro A a vyjme ze zásobníku a a vloží A) a na výstup přidá číslo pravidla, • push o vloží symbol ze vstupu do zásobníku a zavolá iex o , • accept (), • error() , • Akce o v cyklu provádí tyto kroky: O podle vrcholu zásobníku a symbolu na vstupu určí řádek a sloupec tabulky, O podle obsahu buňky zavolá reduce, push, accept nebo error (prázdná buňka), • init o otevře potřebné soubory inicializuje zásobník (vloží symbol # - s_hash) a provede první volání iex (), • Done() - úklid. □ g - = = -O0>0 Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace oo»ooooo Podle příkladu S^#E E^ AT A^E+ E e ® ® T ^BF B -+ T* I T/ I e F ->n\i \ (E) ®,©,@ enum TTypSymbolu { S_NOTHING, S_ENDOFFILE, S_LPAR, S_RPAR, S_ID, S_NUM, S_IS, S_PLUS, S_MINUS, S_MUL, S_DIV, S_NS, S_NE, S_NA, S_NT, S_NB, S_NF, S_HASH }; terminály neterminály J struct TSymbol { TTypSymbolu typ; string atrib; In- struct TVstup { char znak; int cisloRad; int pozice; int konec; }; TSymbol symbol; TVstup vstup; bool konec; TZasobnik zasobnik; TTypSymbolu vrchol_zas; _J - -1 y L J ■ L J i L i Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace ooo«oooo Redukce v zásobníku int reduce(int cislo_prav) switch(cislo_prav) { { case 0: Vyjmi_ze_zasobniku(); // E Vyjmi_ze_zasobniku(); // # Pridej_do_zasobniku(S_NS); break; case 1: Vyjmi_ze_zasobniku(); // T Vyjmi_ze_zasobniku() ; // A Pridej_do_zasobniku(S_NE); break; case 2: Vyjmi_ze_zasobniku(); // + Vyjmi_ze_zasobniku() ; // E break; case 3: Vyjmi_ze_zasobniku() ; // - Vyjmi_ze_zasobniku; // E Pridej_do_zasobniku(S_NA); break; case 4: Pridej_do_zasobniku(S_NA); break; pro každé pravidlo gramatiky zredukujeme v zásobníku pravou stranu pravidla na levou }; vystup(cislo_prav); S E Ä A A #E AT E+ E- }; □ g - = = -o^o Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace oooo»ooo Ošetření chyb, zpracování terminálů a akceptování void error(string hláska) { konec = true; printf("Chyba při syntaktické analýze na řádku %d, sloupci %d: %s", vstup.cisloRad, vstup.pozice, hláska); } int push() { Pridej_do_zasobniku(symbol.typ); lex(); // lexikální analyzátor načte další symbol } void accept() { konec = true; } □ g - = = -OQ>0 Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace ooooo»oo Inicializace, průběh a ukončení void Init () { . . . // inicializace vstupu a výstupu konec = falše; Vytvor_zasobnik() ; Pridej_do_zasobniku(S_HASH); // symbol konce zásobníku lex() ; // načte symbol ze vstupu do symbol } void Done () { Zlikviduj_zasobnik() ; } uvolní paměť zabranou zásobníkem uzavření vstupu a výstupu void Syntakticka_analyza() { Init () ; while(!konec) Akce () ; Done(); } Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace oooooo«o Řízení výpočtu n i + — * / ( ) $ s flCC E push push push rO A r8 r8 r8 T r1 r1 push push r1 r1 B push push push F r5 r5 r5 r5 r5 r5 n r9 r9 r9 r9 r9 r9 i MO MO MO MO MO MO + r2 r2 r2 — r3 r3 r3 * r6 r6 r6 / r7 r7 r7 ( r4 r4 r4 ) r11 r11 r11 r11 r11 r11 # r4 r4 r4 □ g - = = -o^o Rozkladová tabulka ooooo Příklad oooo Matematické výrazy ooo Implementace ooooooo* Řízení výpočtu void Akce() { vrchol_zas = Nahledni_do_zasobniku(); // nebo vyjmeme a zase vrátíme switch (vrchol_zas) { case S_NS: if (symbol.typ == S_ENDOFFILE) accept (); else error("Chybný symbol na vstupu " + symbol.typ); break; case S_NE: if (symbol.typ == S_PLUS || symbol.typ == S_MINUS || symbol.typ == S_RPAR) push(); else if (symbol.typ == S_ENDOFFILE) reduce(0); else error("Chybný symbol na vstupu " + symbol.typ); break; case S_NA: if (symbol.typ == S_ID || symbol.typ == S_NUM || symbol.typ == S_LPAR) reduce(8); else error("Chybný symbol na vstupu " + symbol.typ); break; case S_LPAR: case S_HASH: if (symbol.typ == S_ID || symbol.typ == S_NUM || symbol.typ == S_LPAR) reduce(4); else error("Chybný symbol na vstupu " + symbol.typ); break; }; } □ g - = = -Oc\o