Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Atributovaný překlad
Typy atributů, implementace Šárka Vavrečková
Ústav informatiky, FPF SU Opava
sarka.vavreckova@ fpf.slu.cz
Poslední aktualizace: 5. prosince 2023
□       g        -        =        s -00,0
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1)
•oooo ooo ooooooooooooo oo oooooooooooooooooooo
Typy atributů
Definice (Syntetizované a dědičné atributy)
Syntetizovaný atribut:
9 hodnota závisí na hodnotách atributů uzlů jeho vlastního podstromu
9 k posílání údajů v derivačním stromě směrem zdola nahoru Dědičný atribut:
• hodnota závisí na hodnotách atributů nadřízeného uzlu nebo uzlů na stejné úrovni
9 k posílání údajů v derivačním stromě směrem dolů nebo vpravo Žádný atribut nemůže být zároveň syntetizovaný a dědičný.
A —>> BnCD        [A.val = B.val + D.val, C.des = (A.m + B.val) * 10 + n.lex] I
• A.val je syntetizovaný, závisí na atributech symbolů-potomků I
• C.des je dědičný, závisí na atributech předka a „bratrů" vlevo I
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1)
o«ooo ooo ooooooooooooo oo oooooooooooooooooooo
Inicializace atributů
Každý atribut musí být někde v derivačním stromě inicializován:
9 dědičné atributy obvykle v kořeni stromu (obecně na horním levém začátku cesty toku hodnoty atributu derivačním stromem),
• syntetizované atributy většinou v listech stromu (tj. v terminálních pravidlech), často lexikálním analyzátorem.
Typy atributů oo»oo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace ooooooooooooooc
Příklad
Gramatika generuje výraz ve tvaru (hledej) (n; L) v (hledej) je klíčové slovo určující příkaz pro hledání čísla v seznamu, n je číslo, které má být hledáno, L generuje seznam čísel,
v je výstupní terminál, do jeho atributu uložíme výsledek
Syntaktická pravidla v překladové gramatice:
S —> (hledej) (n;L)v
L^nA A -kL
e
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i? L^nA A ->,L
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme <^edej) na 4, pozice na 0 (dědičné atributy)
a pozici 1 (zvysil jsme o 1)
poz = 0
iO
□ s
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i? L^nA A ->,L
e
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme {hledej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
poz = 0
iO
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i? L^nA A ->,L
e
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme {hledej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
O do nižšího patra přepošleme dědičné atributy
poz = 0
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i?
L^nA
A ->>,L £
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme <^edej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
O do nižšího patra přepošleme dědičné atributy
O posíláme dolů hledanou hodnotu 4 a pozici 2
poz = 0
iO
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i?
L^nA
A ->>,L £
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme <^edej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
O do nižšího patra přepošleme dědičné atributy
O posíláme dolů hledanou hodnotu 4 a pozici 2
O inicializace syntetizovaného atributu na 0 (zatím nenalezen)
poz = 0
nalez = 0
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i?
L^nA
A ->>,L e
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme {hledej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
O do nižšího patra přepošleme dědičné atributy
O posíláme dolů hledanou hodnotu 4 a pozici 2
O inicializace syntetizovaného atributu na 0 (zatím nenalezen)
O nalezen, místo 0 pošleme pozici (index) prvku
poz = 0
nalez = 0
£
3
Typy atributů ooo»o
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i?
L^nA
A ->>,L e
Zpracování výrazu (hledej) (4; 9,4)
O hledané číslo inicializujeme {hledej) na 4, pozice na 0 (dědičné atributy)
O posíláme dolů hledanou hodnotu 4 a pozici 1 (zvýšili jsme o 1)
O do nižšího patra přepošleme dědičné atributy
O posíláme dolů hledanou hodnotu 4 a pozici 2
O inicializace syntetizovaného atributu na 0 (zatím nenalezen)
O nalezen, místo 0 pošleme pozici (index) prvku
O přeneseme do výstupního atributu
poz = 0
nalez = 0
£
□ s
Typy atributů oooo«
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i? L^nA A ->,L
e
Atributová gramatika
Použijeme atributy
n[lex], L[poz, cis, nalez], A[poz, cis, nalez], v[vysl]
dědičné: poz, cis, vysl • syntetizované: lex, nalez
S —>• (hledej) (n; {L.poz - - 0, L.cis - - n.lex)
Ľ) v {v.vysl - - L.nalez) L —?n {A.poz - - L.poz + 1, A.cis - - L.cis}
A {if n.lex -- A.cis then L.nalez - - A.poz
else L.nalez = A.nalez} A —>• , {L.poz - - A.poz, L.cis - - A.cis) L {A.nalez A^e ÍA.nalez = 0\
g   poz = 0 cis = 4
(hledej)
nalez = 0
L.nalez}
£
Typy atributů oooo«
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
S —>- (hledej) (n; L) i?
L^nA
A ->>,L e
Atributová gramatika
Použijeme atributy
n[lex], L[poz, cis, nalez], A[poz, cis, nalez], v[vysl]
dědičné: poz, cis, vysl • syntetizované: lex, nalez
S —>• (hledej) (n; {L.poz = 0, L.cis = n.lex)
Ľ) v {v.vysl = L.nalez} L —?n {A.poz = L.poz + 1,A.cis = L.cis}
A {if n.lex = A.cis then L.nalez = A.poz
else L.nalez = A.nalez} A —>• , {L.poz = A.poz, L.cis = A.cis} L {A.nalez A —>• e {A.nalez = 0}
g   poz = 0 cis = 4
(hledej)
L.nalez}
nalez = 0
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1)
ooooo »oo ooooooooooooo oo oooooooooooooooooooo
Deterministický překlad výrazů při interpretaci
Požadavky na gramatiku
• gramatika typu LL(1), silná LR(1) nebo jiná, kterou lze použít pro deterministický překlad
• často není třeba použít výstupní terminály
• zachováváme prioritu operátorů
Typy atributů ooooo
Překlad výrazů LL(1) o«o
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Příklad - LL(1) gramatika
S    i = A A^BC C^+BC C^-BC C —>> e B^DE E *D£ E /DE E —>> e D —>> n D i D^(A)
Překlad výrazů LL(1)
ooooo o«o ooooooooooooo oo oooooooooooooooooooo
Příklad - LL(1) gramatika
S —> i = A {U\oz(i.název, A.val)}
A -> B {Cm = B.val} C {A.val = Cval}
C -> +B {Q.m = Q.m + B.val} C {Co.val = C\.val}
C —>> —B {C\.m = C0.m — B.val} C {C0.val = C\.val}
C —> s {Cval = Cm}
B —> D {E.m = D.val} E {B.val = E.val}
E —> *D {Ei.m = E0.m* D.val} E {EQ.val = E\.va\}
E —>> jD {Ei.m = Eo.mjD.val} E {EQ.val = EQ.val}
E —>> e {E.val = E.m}
D —> n {D.val = n.lex}
D —» i {D.val = ZjistiHodnotu(z.nazev)}
D ->> (A) {D.val = A.val}
S —> i — A {Uloz(i.název, A.val)}
A —>• B {Cm — B.val} C {A.val — Cval}
C —>• +£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
C —>• — B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
C —>• e {Cval — Cm}
B —>• D {E.m = D.val} E {B.val — E.val}
E —>• *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
E —>• /D {E\.m — EQ.m/D.val} E {Eq.voI — E\.val}
E —>• e {E.val — E.m}
D —>• n {D.val — n.lex}
D —>• z {D.val — ZjistiHodnotu(z.nflzey)}
D -> (A) {D.yflZ = A.Z7fl/}
C
S —> i — A {Uloz(i.název, A.val)}
A —>• B {Cm — B.val} C {A.val — Cval}
C —>• +£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
C —>• — B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
C —>• e {Cval — Cm}
B —>• D {E.m = D.val} E {B.val — E.val}
E —>• *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
E —>• /D {E\.m — EQ.m/D.val} E {Eq.voI — E\.val}
E —>• e {E.val — E.m}
D —>• n {D.val — n.lex}
D —>• z {D.val — ZjistiHodnotu(z.nflzey)}
D -> (A) {D.yflZ = A.Z7fl/}
C
B
D E
S-
A
C
c c
B E E E D D D
n
£
i — A {Uloz(i.název, A.val)}
B {Cm — B.val} C {A.val — Cval}
+£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
—B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
e {Cval — Cm}
D {E.m — D.val} E {B.val — E.val} *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val} /D {E\.m — Eo.m/D.val} E {Eq.voI — E\.val} £ {E.val — E.m}
■ n {D.val — n.lex}
■ i {D.val — ZjistiHodnotu(z.nflzey)} - (A) {D.val = A.val}
n s £
£
c
S —> i — A {Uloz(i.název, A.val)}
A —>• B {Cm — B.val} C {A.val — Cval}
C —>• +£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
C —>• — B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
C —>• e {Cval — Cm}
B —>• D {£.m = D.val} E {B.val — E.val}
E —>• *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
E —>• /D {E\.m — EQ.m/D.val} E {Eq.voI — E\.val}
E —>• e {E.val — E.m}
D —>• n {D.val — n.lex}
D —>• z {D.val — ZjistiHodnotu(z.nflzey)}
D -> (A) {D.Z7fl/ = A.Z7fl/}
C
c
S —> i — A {Uloz(i.název, A.val)}
A —>• B {Cm — B.val} C {A.val — Cval}
C —>• +£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
C —>• — B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
C —>• e {Cval — Cm}
B —>• D {£.m = D.val} E {B.val — E.val}
E —>• *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
E —>• /D {E\.m — EQ.m/D.val} E {Eq.voI — E\.val}
E —>• e {E.val — E.m}
D —>• n {D.val — n.lex}
D —>• z {D.val — ZjistiHodnotu(z.nflzey)}
D -> (A) {D.Z7fl/ = A.Z7fl/}
C
s
A C
c c
B E E E D D D
i — A {Uloz(i.název, A.val)}
B {Cm — B.val} C {A.val — Cval}
+£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
—B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
e {Cval — Cm}
D {E.m — D.val} E {B.val — E.val}
*D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
/D {E\.m — Eo.m/D.val} E {Eq.voI — E\.val}
£ {E.val — E.m}
n {D.val — n.lex}
i {D.val — ZjistiHodnotu(z.nflzey)} (A) {D.val = A.val}
£
= 30
£
1j   ^    + t S 00 v
£
val = m = 30
S
A C C C B E E E D D D
E ^ + /> B C
eW II D      E £
i — A {Uloz(i.název, A.val)}
B {Cm — B.val} C {A.val — Cval}
+£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
—B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
£ {Cval — Cm}
D {E.m — D.val} E {B.val — E.val}
*D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
/D {E\.m — Eo.m/D.val} E {Eq.voI — E\.val}
£ {E.val — E.m}
n {D.val — n.lex}
i {D.val — ZjistiHodnotu(z.nflzey)} (A) {D.val = A.val}
s
A C
c c
B E E E D D D
i — A {Uloz(i.název, A.val)}
B {Cm — B.val} C {A.val — Cval}
+£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí}
—B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí}
e {Cval — Cm}
D {E.m — D.val} E {B.val — E.val}
*D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val}
/D {E\.m — Eo.m/D.val} E {Eq.voI — E\.val}
e {E.val — E.m}
n {D.val — n.lex}
i {D.val — ZjistiHodnotu(z.nflzey)} (A) {D.val = A.val}
val = m
= A {Uloz(i.název, A.val)} B {Cm — B.val} C {A.val — Cval} +£> {C\.m — Co.m + B.val} C {Cq.voI — C\.vaí} —B {C\.m — Co.m — B.val} C {Cq.voI — C\.vaí} e {Cval — Cm}
D {E.m — D.val} E {B.val — E.val} *D {E\.m — Eo.m * D.val} E {Eq.voI — E\.val} /D {E\.m — Eo.m/D.val} E {Eq.voI — E\.val} £ {E.val — E.m} n {D.val — n.lex}
i {D.val — ZjistiHodnotu(z.nflzey)} (A) {D.val = A.val}
E ^ + /> C
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO «000000000000 oo oooooooooooooooooooo
Implementace LL(1) překladu
Oproti syntaxi rozšíříme: 9 naprogramujeme všechny použité sémantické funkce
9 do funkcí naprogramovaných pro syntaxi přidáme sémantiku - volání sémantických funkcí a vyhodnocování sémantických pravidel
• určíme způsob předávání atributů mezi symboly a pravidly Použijeme metodu rekurzivního sestupu.
i
Terminály i
• vstupní - zpracovávají se stejně jako u syntaxe (funkce pop_in) I
• výstupní - naprogramujeme funkci pop_out ošetřující výstupní terminály I
□      g       -       =       s -00,0
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace o»ooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Atributy přenášíme
Různé typy atributů posíláme uvnitř pravidla lokálními proměnnými; mezi pravidly (předek-potomek) budeme zpracovávat takto:
a syntetizované atributy neterminálů posíláme rekurzí směrem nahoru (parametry volané odkazem),
a WoWi/^nó o ť ť i fi i it\/ n o/o ym i n á 11/ nncí ámo toki ir°7i cmorom /Holi i l no r o m f^Ťťx/
v\Jla.l Ikš I l\J\JI IkJLkJUJ ,
ci/nřoř/7/ni/3nó ořř"i/"w iť\/ i/oři inni^^Ai řof/rnoo/i0/ i il^lci/Hcimo        /"^l^hólnf r^r^monnó
(jsou součástí proměnné typu TSymboi), obvykle je zde ukládá lexikální
^\ Y\ ^\ i \ / ~~7 ^\ i f \ Y
cii i cli y Í-CX iv_/1,
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace o»ooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Atributy přenášíme
Různé typy atributů posíláme uvnitř pravidla lokálními proměnnými; mezi pravidly (předek-potomek) budeme zpracovávat takto:
a syntetizované atributy neterminálů posíláme rekurzí směrem nahoru (parametry volané odkazem),
• dědičné atributy neterminálů posíláme rekurzí směrem dolů (parametry volané hodnotou),
pi/ jjnA ořfi/^i iŤ\/ i/oři ii^níf^h) ťqťmik~)oIi°i i i\/CIcic\cimo c\c\ r*\Ic\\~\ciI\ r^f^monnó
(jsou součástí proměnné typu TSymboi), obvykle je zde ukládá lexikální
^\ Y\ ^\ i \ / ~~7 ^\ i f \ Y
cii i cli y Í-CX iv_/1,
□      3       -       =       s -00,0
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace o»ooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Atributy přenášíme
Různé typy atributů posíláme uvnitř pravidla lokálními proměnnými; mezi pravidly (předek-potomek) budeme zpracovávat takto:
9 syntetizované atributy neterminálů posíláme rekurzí směrem nahoru (parametry volané odkazem),
• dědičné atributy neterminálů posíláme rekurzí směrem dolů (parametry volané hodnotou),
9 syntetizované atributy vstupních terminálů ukládáme do globální proměnné (jsou součástí proměnné typu TSymboi), obvykle je zde ukládá lexikální analyzátor,
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO O0OOOOOOOOOOO oo oooooooooooooooooooo
Atributy přenášíme
Různé typy atributů posíláme uvnitř pravidla lokálními proměnnými; mezi pravidly (předek-potomek) budeme zpracovávat takto:
• syntetizované atributy neterminálů posíláme rekurzí směrem nahoru (parametry volané odkazem),
9 dědičné atributy neterminálů posíláme rekurzí směrem dolů (parametry volané hodnotou),
9 syntetizované atributy vstupních terminálů ukládáme do globální proměnné (jsou součástí proměnné typu TSymboi), obvykle je zde ukládá lexikální analyzátor,
• dědičné atributy výstupních terminálů buď přímo vypisujeme, nebo ukládáme do vhodné globální proměnné.
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
ooooo ooo oo»oooooooooo oo oooooooooooooooooooo
S —> Av {v.vysl = A.val, VypisText(v.vy sl)}
A —> B {Cm = B.val} C {A.val = Cval}
C —> +£> {C\.m = Co.m + B.val} C {C^.val = C\.val}
C —>> —B {C\.m = Co.m — B.val} C {C^.val = C\.val}
C —> e {Cval = Cm}
£> —>► D {E.m = D.val} E {B.val = E.val}
E —> *D {E\.m = Eq-^ * D.val} E {E^.val = Ei.vaí}
E —> /D {E\.m = Eo.m/D.val} E {E^.val = Ei.vaí}
E —> e {E.val = E.m}
D —>► n {D.val = n.Zex}
D —>► i {D.val = ZjistiHodnotu(i.tt0zei?)}
D -» (A) {D.i7fl/ = AiwZ}
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO 000*000000000 oo oooooooooooooooooooo
Datové typy a proměnné
enum TTypSymbolu   {   S_NOTHING,   S_ENDOFFILE,   S_LPAR, S_RPAR, S_ID,   S_NUM,   S_IS,   S_PLUS,   S_MINUS,   S_MUL,   S_DIV };
struct TSymbol { TTypSymbolu typ;
int atribcislo; TObjekt *atribstr;
};
celé číslo (S_NUM) název proměnné (S_ID)
TSymbol symbol;
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO OOOO0OOOOOOOO oo oooooooooooooooooooo
Ošetření chyb a pomocné funkce pro výstup
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); }___
Pomocné funkce pro výpis
9 vypisTyp (TTypSymboiu typ) - převede datový typ na řetězec vypisHodn (TSymbol sym) - převede symbol včetně atributu na řetězec
Implementace Překlad výrazů silný LR(1) Implementace
ooooo ooo ooooo»ooooooo oo oooooooooooooooooooo
Vstupní a výstupní terminály
int pop_in(TSymbol terminal) { if   (symbol.typ == terminal.typ) Lex();
else error (11 chybný symbol na vstupu -"  +VypisTyp (symbol. typ) ) ;
}
int pop_out(TSymbol terminal) {
if   (symbol.typ == terminal.typ)   {        // případně switch
... // například výpis atributu na výstup
}   // chyba není pravděpodobná,,   ale taky můžeme ošetřit
}
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
oooooo«oooooo oo oooooooooooooooooooo
Pravidla
S —>> Au {v.vysl = A.val, VypisText(i?.vysl)}
void s(){
TSymbol pom_sym;
if   (symbol.typ==S_NUM  ||   symbol.typ==S_ID   ||   symbol.typ==S_LZAV) { A(pom_sym);
pom_sym.typ = S_VYSTUP;       // výstupní terminál 'v' pop_out(pom_sym);
}
else
error (11 symbol  "+VypisHodn (symbol) +" není očekávaného typu " + VypisTyp(S_NUM)+"+  "+VypisTyp(S_ID)+"  nebo  "+VypisTyp(S_LZAV));
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
ooooooo«ooooo oo oooooooooooooooooooo
Pravidla
A —)► B {Cm = B.val} C {A.val = Cval}
void A(int Sval) { int pomval;
if   (symbol.typ==S_NUM  ||   symbol.typ==S_ID   ||   symbol.typ==S_LZAV) { B(pomval); C(pomval,val);
}
eise
error (11 symbol  "+VypisHodn (symbol) +" není očekávaného typu " + VypisTyp(S_NUM)+"+  "+VypisTyp(S_ID)+"  nebo  "+VypisTyp(S_LZAV));
□ s1
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace oooooooo»oooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Pravidla
c c
c
+£> {Q.m = Cq.m + B.val} C {Cq.vuI —B {C\.m = Cfj.m — B.val} C {Cq.voI
e {Cval = Cm}
Ci.val} Ci.val}
void C(int m,  int &val) {
int pomval;
switch   (symbol.typ) { case S_PLUS:
pop_in(S_PLUS); B(pomval);
C(m + pomval,val); break; case S_MINUS:
pop_in(S_MINUS); B(pomval);
C(m - pomval,val); break; case S_RZAV:  case S_ENDOFFILE:  val = m; break;
default:  error (11 symbol "+VypisHodn (symbol) +" není očekávaného typu 11+ VypisTyp(S_PLUS)+"+  "+VypisTyp(S_MINUS)+"+  "+VypisTyp(S_RZAV)+ " nebo konec vstupu");
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO OOOOOOOOO0OOO
Pravidla
B —» D {E.m = D.val} E {B.val = E.val}
void B(int &val) { int pomval;
if   (symbol.typ==S_NUM  ||   symbol.typ==S_ID   ||   symbol.typ==S_LZAV) { D(pomval); E(pomval,val);
}
eise error (...);
□ s
=
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
ooooo ooo oooooooooo«oo oo oooooooooooooooooooo
Pravidla
E E
E
*D {E\.m = E0.m * D.val} E {E0.val = E\.val} jD {E\.m = Eo.m/'D.val} E {Eq.voI = E\.val}
e {E.val = E.m}
void E(int m,  int &val) { int pomval; switch   (symbol.typ) { case S_MUL:
pop_in(S_MUL); D(pomval);
E(m * pomval,val); break; case S_DIV:
pop_in(S_DIV); D(pomval);
if (pomval == 0) error("dělení nulou"); else E(m/pomval,val); break;
case S_PLUS:  case S_MINUS:  case S_RZAV:  case S_ENDOFFILE:
val = m; break; default:  error(...);
}
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1)
OOOOO OOO OOOOOOOOOOO0O oo oooooooooooooooooooo
Pravidla
D —> n {D.val = n.lex}
D —>- i {D.val = ZjistiHodnotu(z\ft0zei?)}
D    (A) {D.val = A.val} I
void D(int &val) {
switch   (symbol.typ) { case S_NUM:
val = symbol. atribcis;     // musíme zachytit předem,,  pak bude pop_in(S_NUM);  break;       // přepsáno lexikálním analyzátorem case S_ID:
val = symbol.atribstr->hodnota.i;       // z tabulky symbolů pop_in(S_ID); break; case S_LZAV: pop_in(LZAV); A(val) ;
pop_in(RZAV); break; default:  error (...);
}
}
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace
OOOOOOOOOOOO*
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooooooo
Hlavní funkce
void Překlad() {
init(); // inicializace překladu včetně lexikálního analyzátoru
Lex(); // přednačteme jeden symbol
S(); // spustíme rekurzivní volání
done () ; // ukončení překladu,,   úklid paměti apod.
}
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) •o
Implementace oooooooooooooooooooo
Příklad - silná LR(1) gramatika
S    i = V V -,AM A —>> V+ A V-A -> e M^BF B —>> M* B —>> M/ B^e F —>> n F^i F->(V)
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) •o
Implementace oooooooooooooooooooo
Příklad - silná LR(1) gramatika
S —y i = V {Uloz(z.název, V.val)}
V^AM {if A.op = S_PLUS then V.val = A.val + M.val
else V.val = A.val — M.val} A    V + {A.val = V.val, A.op = S_PLUS} A    V -  {A.val = V.val, A.op = S_MINUS} A    e {A.val = 0,A.op = S_PLUS} M^BF {if B.op = S_MUL then M.val = B.val * F.val
else M.val = B.val jF.val} B    M *  {B.val = M.val, B.op = S_MUL} B    MI {B.val = M.val, B.op = S_DIV} B    e {B.val = \,B.op = S_MUL} F —> n {F.val = n.lex} F —> i {F.val = ZjistiHodnotu(i.název)} F    (V) {F.val = V.val}
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) o«
Implementace
oooooooooooooooooooo
S —>■ i — V {\J\oz(i.název, V.val)}
V^AM {if A.op    S_PLUS then V.val   A.val + M.val
else V.val — A.val — M.val} A -> V + = V.ufl/, A.op = S_PLUS}
A -> V -  {A.val = V.val, A.op = S_MINUS} A^e {A.val = 0,A.op = S_PLUS} M^BF {if B.op = S_MUL then M.val = B.val * F.val
else M.val — B.val/F.val} B -> M * = M.ircZ, B.op = S_MUL}
B -> M / {B.Z7A/ = M.iwZ, B.op = S_DIV} B -> e {B.val = 1, B.op = S_MUL} F —>• n {F.val — n.lex} F —> z {F.val — ZjistiHodnotu(z.nflzei7)}
F -> (V)   {F.Z7fl/ =
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
•ooooooooooooooooooo
Postup
• použijeme metodu přepisu rozkladové tabulky se zásobníkem « do zásobníku ukládáme celé symboly včetně atributů
• atributy jsou jen syntetizované
□       g        -        =        s -00,0
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
o«oooooooooooooooooo
s'   #s ©
S —>• / = y {Uloz(i.název, V.val)} ©
V    AM {if A.op = S_PLUS then V.z7aZ = A.iw/ + M.val ©
else V.pflZ = A.val — M.val}
A     V + {A.™/ = V.val, A.op = S_PLUS} ©
A     V -  {A.val = V.val, A.op = S_MINUS} ©
A^e {A.val = O,A.op = S_PLUS} ©
M^BF {if B.op = S_MUL then M.val = B.val * V.val ©
else M.val = B.val/F.val}
B^M* {B.val = M.val,B.op = S_MUL} ©
B^M/ {B.val = M.val,B.op = S_DIV} ©
B -+ e {B.val = 1, B.op = S_MUL} ©
F —t n {F.val = n.lex} @
F —>• / {F.val = ZjistiHodnotu(/.nazec)} (Q)
F     (V) {F.val = V.val} ©
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
oo»ooooooooooooooooo
Datové typy
enum TTypSymbolu   {   S_NOTHING,   S_ENDOFFILE,   S_LPAR, S_RPAR,
S_ID,   S_NUM,   S_IS,   S_PLUS,   S_MINUS,   S_MUL,   S_DIV, // terminály
S_NS,   S_NSC,   S_NV,   S_NA,   S_NM,   S_NB,   S_NF,   S_HASH  };   // neterminály
struct TSymbol {
TTypSymbolu typ; int atribcislo; TObjekt *atribstr;
};
bool konec; TSymbol symbol; TSymbolZasob vrchol_zas; TZasobnik zasobnik;
struct TSymbolZasob { TTypSymbolu typ; TTypSymbolu atribop; int atribcislo; TObjekt *atribstr;
};
pro S_PLUS,   . . ., S_D\EV atributy val a lex atribut název
indikátor ukončení vypočtu aktuální symbol ze vstupu symbol na vrcholu zásobníku prvky jsou typu TSymbolZasob
další používané datové typy a proměnné
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
ooo«oooooooooooooooo
Pravidla
void reduce(int cislo_prav) { TSymbolZasob SymbolZas; int val;
switch  (cislo_prav) { case 0: ...
1 •    • • •
at d.
doplníme podle pravidel
J
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooo«ooooooooooooooo
Pravidla
case 0:
Vyjmi_ze_zasobniku(vrchol_zas); // S
Vyjmi_ze_zasobniku(vrchol_zas); // #
SymbolZas.typ = S_NSC;
Pridej_do_zasobniku(SymbolZas);
break;
□       g        - =
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace ooooo»oooooooooooooo
Pravidla
S -> i = V {Uloz(i.nazev, V.val)}
case 1:
Vyjmi_ze_zasobniku(vrchol_zas); // V
val = vrchol_zas.atribcislo;
Vyjmi_ze_zasobniku(vrchol_zas); // =
Vyjmi_ze_zasobniku(vrchol_zas); // i
// uložíme vypočtenou hodnotu do tabulky symbolů:
vrchol_zas.atribstr->(hodnota.i)   = val;
SymbolZas.typ = S_NS;
Pridej_do_zasobniku(SymbolZas);
break;
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooo«ooooooooooooo
Pravidla
V    AM {if A.op = S_PLUS then V.val = A.val+M.val @
else V.twZ = A.i?flZ — M.val}
case 2:
Vyjmi_ze_zasobniku(vrchol_zas); // M
val = vrchol_zas.atribcislo;
Vyjmi_ze_zasobniku(vrchol_zas); // A
SymbolZas.typ = S_NV;
if   (vrchol_zas.atribop == S_PLUS)
SymbolZas.atribcislo =    vrchol_zas.atribcislo + val; else if  (vrchol_zas.atribop == S_MINUS)
SymbolZas.atribcislo =    vrchol_zas.atribcislo - val; else error ("chyba v syntaxi aritmetického výrazu,  nenalezen žádný
ze symbolů  11 + VypisTyp (S_PLUS) +"  nebo  "+VypisTyp (S_MINUS) ) ; Pridej_do_zasobniku(SymbolZas); break;
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace ooooooo«oooooooooooo
Pravidla
A -> V + {A.val = V.ircZ, Aop = S_PLUS}
case 3:
Vyjmi_ze_zasobniku(vrchol_zas); Vyjmi_ze_zasobniku(vrchol_zas);
// + // V
SymbolZas.typ = S_NA; SymbolZas.atribop = S_PLUS;
SymbolZas.atribcislo = vrchol_zas.atribcislo;
Pridej_do_zasobniku(SymbolZas);
break;
□       g        - =
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooo»ooooooooooo
Pravidla
A^V -  {A.val = V.val,A.op = S_MINUS}
case 4:
Vyjmi_ze_zasobniku(vrchol_zas); Vyjmi_ze_zasobniku(vrchol_zas);
// -// V
SymbolZas.typ = S_NA; SymbolZas.atribop = S_MINUS;
SymbolZas.atribcislo = vrchol_zas.atribcislo;
Pridej_do_zasobniku(SymbolZas);
break;
□       g        - =
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace ooooooooo»oooooooooo
Pravidla
A ->■ e {A.val = 0, A.op
S_PLUS}
©J
case 5:
SymbolZas.typ = S_NA; SymbolZas.atribop = S_PLUS; SymbolZas.atribcislo = 0; Pridej_do_zasobniku(SymbolZas); break;
...   // pro symboly M a B to bude podobné jako pro V a A, // ale nesmíme zapomenout ošetřit dělení nulou
□       g        - =
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1) Implementace
OOOOO OOOOOOOOOOOOO 0000000000*000000000
Pravidla
F —> n {F.val = n.lex} ©
case 10:
Vyjmi_ze_zasobniku(vrchol_zas) ; // n
SymbolZas.typ = S_NF;
SymbolZas.atribcislo = vrchol_zas.atribcislo;
Pridej_do_zasobniku(SymbolZas);
break;
□ 3
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
OOOOOOOOOOO0OOOOOOOO
Pravidla
F —> i {F.val = ZjistiHodnotu(/.nazez;)}
case 11:
Vyjmi_ze_zasobniku(vrchol_zas); // i
SymbolZas.typ = S_NF;
SymbolZas.atribcislo = vrchol_zas.atribstr->hodnota.i;
Pridej_do_zasobniku(SymbolZas);
break;
©J
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooo»ooooooo
Pravidla
F -> (V) {F.val = V.val]
case 12:
Vyjmi_ze_zasobniku(vrchol_zas); // (
Vyjmi_ze_zasobniku(vrchol_zas); // V
SymbolZas.typ = S_NF;
SymbolZas.atribcislo = vrchol_zas.atribcislo; Vyjmi_ze_zasobniku(vrchol_zas) ; Pridej_do_zasobniku(SymbolZas); break;
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1) Implementace
OOOOO OOO OOOOOOOOOOOOO OO OOOOOOOOOOOOO0OOOOOO
Rozhodování mezi pravidly podle tabulky
	n	i	—	+	—	*	/	(	)	$
S'										flCC
s										rO
v				push	push				push	r1
A	r9	r9						r9		
M				r2	r2	push	push		r2	r2
B	push	push						push		
F				r6	r6	r6	r6		r6	r6
n				MO	MO	MO	MO		MO	MO
i			push	r11	r11	r11	r11		r11	M1
—	r5	r5						r5		
+	r3	r3						r3		
—	r4	r4						r4		
*	r7	r7						r7		
/	r8	r8						r8		
(	r5	r5						r5		
)				r12	r12	r12	r12		r12	M2
#		push								
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace
OOOOOOOOOOOOOO0OOOOO
Rozhodování mezi pravidly podle tabulky
	n	i	—	+	—	*	/	(	)	$
S'										acc
s										rO
										
void Akce () {
switch  (vrchol_zas) {
case S_NSC:   if   (symbol.typ == S_ENDOFFILE)   accept (); else error("očekáván konec souboru"); break;
case S_NS:   if   (symbol.typ == S_ENDOFFILE) reduce(O); else error("očekáván konec souboru"); break;
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace ooooooooooooooo»oooo
Rozhodování mezi pravidly podle tabulky
	n	i	—	+	—	*	/	(	)	$
V				push	push				push	r1
case S_NV:  switch  (symbol.typ) {
case S_PLUS:  case S_MINUS:  case S_RZAV:
push () ;
break; case S_ENDOFFILE:
reduce(1);
break; default:
error("symbol  "+VypisHodn(symbol)+" není očekávaného typu "+ VypisTyp(S_PLUS)+ ",   "+VypisTyp(S_MINUS),"+  11 + VypisTyp(S_RZAV)+" nebo konec souboru");
}
break;
atd. pro všechny neterminály
Typy atributů ooooo
Překlad výrazů LL(1) ooo
Implementace ooooooooooooo
Překlad výrazů silný LR(1) oo
Implementace oooooooooooooooo«ooo
Pravidla
	n	i	—	+	—	*	/	(	)	$
n				r10	r10	r10	r10		r10	r10
i			push	r11	r11	r11	r11		r11	r11
										
case S_NUM:
if   (symbol.typ==S_PLUS | ||   symbol.typ==S_DIV | reduce(10); else error(...); break;
case S_ID:  switch  (symbol.typ) {
case S_PLUS: case S_MINUS: case case S_RZAV:  case S_ENDOFFILE:
reduce(11); break; case S_ROVNASE:  push(); break; default:  error (...);
symbol.typ==S_MINUS symbol.typ==S_RZAV
symbol.typ==S_MUL symbol.typ==S_ENDOFFILE)
}
atd. pro všechny terminály
S MUL:  case S DIV:
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1) Implementace
ooooooooooooo ooooooooooooooooo«oo
Ošetření chyb 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);
}
void accept () { konec = true;
}
□ s
=
Typy atributů Překlad výrazů LL(1) Implementace Překlad výrazů silný LR(1) Implementace
ooooo ooo ooooooooooooo oo oooooooooooooooooo»o
Práce se vstupem
int push() {
SymbolZas.typ = symbol.typ
SymbolZas.atribcislo = symbol.atribcislo;
SymbolZas.atribstr=symbol.atribstr;
Pride j_do_zasobniku(symbol.typ);
lex(); // lexikální analyzátor načte další symbol
□ s
-       «    -O °s o
Typy atributů Překlad výrazů LL(1) Překlad výrazů silný LR(1) Implementace
OOO OOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOO*
Inicializace a ukončení
void Init () {
TSymbolZas SymbolZas;
. . . // inicializace vstupu a výstupu
konec = falše; Vytvor_zasobnik() ; SymbolZas.typ = S_HASH;
Pridej_do_zasobniku(SymbolZas);   // symbol konce zásobníku
lex(); // načte symbol ze vstupu do symbol
}
void Done() {
Zlikviduj_zasobnik(); // uvolní paměť  zabranou zásobníkem
}
void Překlad() { Init () ;
while(!konec) Akce(); Done ();
}
uzavření vstupu a výstupu