Poslední aktualizace: 26. října 2011

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

LR(k) prˇeklady Sˇa´rka Vavrecˇkova´ ´ stav informatiky, FPF SU Opava U [email protected]

Poslednı´ aktualizace: 26. rˇ´ıjna 2011

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

LR(k) prˇeklady Vy´znam LR L left-to-right, R right-parse, k nejvy´sˇe k znaku˚ ze vstupu potrˇebujeme pro rozhodova´nı´.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

LR(k) gramatika Definice (LR(k) gramatika

(1))

Gramatika je typu LR(k), jestlizˇe ji lze pouzˇ´ıt pro deterministickou syntaktickou analy´zu metodou zdola nahoru (vytva´rˇ´ıme pravy´ rozklad) a prˇi rozhodova´nı´ mezi pravidly potrˇebujeme zna´t nejvy´sˇe k symbolu˚ ze vstupu. Jazyk je typu LR(k), pokud je generova´n LR(k) gramatikou.

Definice (LR(k) gramatika

(2))

Necht’ G = (N, T, P, S) je bezkontextova´ gramatika. G je LR(k) gramatika pro neˇjake´ cele´ neza´porne´ cˇı´slo k, jestlizˇe v prˇ´ıpadeˇ existence dvou pravy´ch derivacı´ S ⇒∗ αAx ⇒ αγx S ⇒∗ βBy ⇒ βγy takovy´ch, zˇe FIRSTk (x) = FIRSTk (y), vzˇdy platı´ αA = βB.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

LR(k) gramatika Definice (LR(k) gramatika

(1))

Gramatika je typu LR(k), jestlizˇe ji lze pouzˇ´ıt pro deterministickou syntaktickou analy´zu metodou zdola nahoru (vytva´rˇ´ıme pravy´ rozklad) a prˇi rozhodova´nı´ mezi pravidly potrˇebujeme zna´t nejvy´sˇe k symbolu˚ ze vstupu. Jazyk je typu LR(k), pokud je generova´n LR(k) gramatikou.

Definice (LR(k) gramatika

(2))

Necht’ G = (N, T, P, S) je bezkontextova´ gramatika. G je LR(k) gramatika pro neˇjake´ cele´ neza´porne´ cˇı´slo k, jestlizˇe v prˇ´ıpadeˇ existence dvou pravy´ch derivacı´ S ⇒∗ αAx ⇒ αγx S ⇒∗ βBy ⇒ βγy takovy´ch, zˇe FIRSTk (x) = FIRSTk (y), vzˇdy platı´ αA = βB.

Prˇ´ıklady

LR prˇeklady

  LL LR 

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Vztah mezi LL a LR jazyky

  CF  

pro neˇktere´ jazyky existujı´ oba typy gramatik – LL i LR

trˇ´ıda jazyku˚ typu LL(1) je vlastnı´ podmnozˇinou trˇ´ıdy jazyku˚ typu LR(1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Srovna´nı´ LL a LR analy´zy LR

LL vstup cˇteme zleva

vstup cˇteme zleva

derivacˇnı´ strom od korˇene k listu˚m

derivacˇnı´ strom od listu˚ ke korˇeni

leva´ derivace, v simulaci ve smeˇru sˇipek

prava´ derivace, v simulaci proti smeˇru sˇipek

rozhodujeme se mezi pravidly se stejnou levou stranou (pro tenty´zˇ netermina´l)

rozhodujeme se mezi pravidly se stejny´m podrˇeteˇzcem na prave´ straneˇ

v rozkladove´ tabulce expanze podle pravidel

v rozkladove´ tabulce redukce podle pravidel

stacˇı´ FIRST a FOLLOW

dalsˇ´ı mnozˇiny pro testy

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Rozsˇ´ırˇenı´ gramatiky Definice (Rozsˇ´ırˇena´ gramatika) Necht’ G = (N, T, P, S) je bezkontextova´ gramatika. Rozsˇ´ırˇena´ gramatika ke gramatice G je gramatika G0 = (N 0 , T0 , P0 , S0 ), kde je N 0 = N ∪ {S0}, S0 ∈ / N, T0 = T ∪ {#}, P0 = P ∪ {S0 → #S}.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

a

a

Zásobník b

$

#

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

push

a

a

Zásobník b

$

a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

push

a

a

Zásobník b

$ b a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

a

a

redukce podle 4

Zásobník b

$ A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

push

a

a

Zásobník b

$ a A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

a

a

redukce podle 3

Zásobník b

$ A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

push

a

a

Zásobník b

$ a A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

a

a

redukce podle 3

Zásobník b

$ A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

push

a

a

Zásobník b

$ b A a #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova abaab Vstup a

b

a

a

redukce podle 1

Zásobník b

$

S #

(abaab$, #, ε) ` (baab$, #a, ε) ` (aab$, #ab, ε) ` (aab$, #aA, 4) ` (ab$, #aAa, 4) ` (ab$, #aA, 4, 3) ` (b$, #aAa, 4, 3) ` (b$, #aA, 4, 3, 3) ` ($, #aAb, 4, 3, 3) ` ($, #S, 4, 3, 3, 1)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

b

a

Zásobník $

#

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

b

a

Zásobník $

push a #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

push

b

a

Zásobník $

a a #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

b

a

redukce podle 5

Zásobník $ B a a #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

b

a

Zásobník $

redukce podle 2 S #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

push

b

a

Zásobník $

a b B a a #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Gramatika S → aAb aaBba A → Aa b B→ε

1 2

, 3 4

, 5

Vy´pocˇet slova aaba Vstup a

a

b

a

Zásobník $

redukce podle 2 S #

(aaba$, #, ε) ` (aba$, #a, ε) ` (ba$, #aa, ε) ` (ba$, #aaB, 5) ` (a$, #aaBb, 5) ` ($, #aaBba, 5) ` ($, #S, 5, 2)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Pomocne´ mnozˇiny Definice V gramatice G = (N, T, P, S) je funkce BEFORE(A) pro A ∈ N definova´na takto: BEFORE(A)  = ∗ ∗ = X ∈ (N ∪∗ T) S ⇒ αXAβ,∗ α, β ∈ (N ∪ T) ∪ ∪ # S ⇒ Aβ, β ∈ (N ∪ T)

Vlastnosti: nerozlisˇujeme varianty pro ru˚zna´ cˇı´sla k parametrem je vzˇdy netermina´l, zpracova´va´me paralelneˇ pro vsˇechny netermina´ly za´rovenˇ pocˇı´ta´me s tı´m, zˇe je pouzˇ´ıva´na prava´ derivace

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Pomocne´ mnozˇiny Definice V gramatice G = (N, T, P, S) je funkce BEFORE(A) pro A ∈ N definova´na takto: BEFORE(A)  = ∗ ∗ = X ∈ (N ∪∗ T) S ⇒ αXAβ,∗ α, β ∈ (N ∪ T) ∪ ∪ # S ⇒ Aβ, β ∈ (N ∪ T)

Vlastnosti: nerozlisˇujeme varianty pro ru˚zna´ cˇı´sla k parametrem je vzˇdy netermina´l, zpracova´va´me paralelneˇ pro vsˇechny netermina´ly za´rovenˇ pocˇı´ta´me s tı´m, zˇe je pouzˇ´ıva´na prava´ derivace

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Postup pro (rozsˇ´ırˇenou) gramatiku G = (N, T, P, S) 1

# ∈ BEFORE(S)

2

Pro kazˇde´ pravidlo B → αXAβ, A, B ∈ N, X ∈ (N ∪ T), α, β ∈ (N ∪ T)∗ : X ∈ BEFORE(A) Do mnozˇin jednotlivy´ch netermina´lu˚ zarˇadı´me vsˇechny symboly (termina´lnı´ i netermina´lnı´), ktere´ jim prˇ´ımo prˇedcha´zejı´ v neˇktere´m pravidle.

3

Pro kazˇde´ pravidlo B → Aβ, A, B ∈ N, β ∈ (N ∪ T)∗ : BEFORE(B) ⊆ BEFORE(A) Pokud se neˇktery´ netermina´l (zde A) nacha´zı´ na zacˇa´tku rˇeteˇzce pravidla, pak cely´ obsah mnozˇiny BEFORE prˇepisovane´ho netermina´lu (zde B) prˇida´me do BEFORE symbolu A (ve smeˇru sˇipky pravidla). Tento krok prova´dı´me rekurzı´vneˇ tak dlouho, dokud docha´zı´ ke zmeˇna´m.

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklad S0 → #S S → aABb A → cAdB Sb ε B → aBS c SdA BEFORE(S0 ) = {#} BEFORE(S) = {#, B, a, c, d, A} BEFORE(A) = {a, c, d} BEFORE(B) = {A, d, a}

Silne´ LR(k) gramatiky

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Definice V gramatice G = (N, T, P, S) pro rˇeteˇzec α ∈ (N ∪ T)∗ pro funkci EFFk (α) platı´  EFFk (α) = w ∈ T∗ w ∈ FIRSTk (α) a pro pravou derivaci ∗ α ⇒∗ β ⇒ wx existuje take´ jiny´ prˇ´ıpad nezˇ β = Awx

Vlastnosti: vycha´zı´me z mnozˇin FIRSTk u kazˇde´ho prvku mnozˇiny zkouma´me derivaci, dı´ky ktere´ byl do FIRSTk zarˇazen pokud se do FIRSTk (α) mohl dostat jen takovou derivacı´, kde je nutne´ na nejleveˇjsˇ´ı symbol slova (netermina´l) pouzˇ´ıt ε-pravidlo, pak tento prvek vyrˇadı´me z EFFk (α)

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

Definice V gramatice G = (N, T, P, S) pro rˇeteˇzec α ∈ (N ∪ T)∗ pro funkci EFFk (α) platı´  EFFk (α) = w ∈ T∗ w ∈ FIRSTk (α) a pro pravou derivaci ∗ α ⇒∗ β ⇒ wx existuje take´ jiny´ prˇ´ıpad nezˇ β = Awx

Vlastnosti: vycha´zı´me z mnozˇin FIRSTk u kazˇde´ho prvku mnozˇiny zkouma´me derivaci, dı´ky ktere´ byl do FIRSTk zarˇazen pokud se do FIRSTk (α) mohl dostat jen takovou derivacı´, kde je nutne´ na nejleveˇjsˇ´ı symbol slova (netermina´l) pouzˇ´ıt ε-pravidlo, pak tento prvek vyrˇadı´me z EFFk (α)

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklad S0 → #S S → aAB ε A → ACbA ε B → bBc Sm C → ABc d ε

BEFORE(S0 ) = {#} BEFORE(S) = {#, A, b} BEFORE(A) = {a, b, A} BEFORE(B) = {A, b} BEFORE(C) = {A}

FIRST(aAB) = {a} EFF(aAB) = {a}

FIRST(ACbA) = {b, a, m, d} EFF(ACbA) = ∅

FIRST(ABc) = {b, a, m} EFF(ABc) = ∅

FIRST(C) = {b, a, m, d, ε} EFF(C) = {d}

Procˇ? ACbA ⇒ · · · ⇒ Axxxxxxx ⇒ xxxxxxx (symbolu A na zacˇa´tku slova se lze zbavit jen ε-pravidlem)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklad S0 → #S S → aAB ε A → ACbA ε B → bBc Sm C → ABc d ε

BEFORE(S0 ) = {#} BEFORE(S) = {#, A, b} BEFORE(A) = {a, b, A} BEFORE(B) = {A, b} BEFORE(C) = {A}

FIRST(aAB) = {a} EFF(aAB) = {a}

FIRST(ACbA) = {b, a, m, d} EFF(ACbA) = ∅

FIRST(ABc) = {b, a, m} EFF(ABc) = ∅

FIRST(C) = {b, a, m, d, ε} EFF(C) = {d}

Procˇ? ACbA ⇒ · · · ⇒ Axxxxxxx ⇒ xxxxxxx (symbolu A na zacˇa´tku slova se lze zbavit jen ε-pravidlem)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklad S0 → #S S → aAB ε A → ACbA ε B → bBc Sm C → ABc d ε

BEFORE(S0 ) = {#} BEFORE(S) = {#, A, b} BEFORE(A) = {a, b, A} BEFORE(B) = {A, b} BEFORE(C) = {A}

FIRST(aAB) = {a} EFF(aAB) = {a}

FIRST(ACbA) = {b, a, m, d} EFF(ACbA) = ∅

FIRST(ABc) = {b, a, m} EFF(ABc) = ∅

FIRST(C) = {b, a, m, d, ε} EFF(C) = {d}

Procˇ? ACbA ⇒ · · · ⇒ Axxxxxxx ⇒ xxxxxxx (symbolu A na zacˇa´tku slova se lze zbavit jen ε-pravidlem)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklad S0 → #S S → aAB ε A → ACbA ε B → bBc Sm C → ABc d ε

BEFORE(S0 ) = {#} BEFORE(S) = {#, A, b} BEFORE(A) = {a, b, A} BEFORE(B) = {A, b} BEFORE(C) = {A}

FIRST(aAB) = {a} EFF(aAB) = {a}

FIRST(ACbA) = {b, a, m, d} EFF(ACbA) = ∅

FIRST(ABc) = {b, a, m} EFF(ABc) = ∅

FIRST(C) = {b, a, m, d, ε} EFF(C) = {d}

Procˇ? ACbA ⇒ · · · ⇒ Axxxxxxx ⇒ xxxxxxx (symbolu A na zacˇa´tku slova se lze zbavit jen ε-pravidlem)

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Silne´ LR(k) gramatiky

Pomocne´ mnozˇiny

Prˇ´ıklady

Silne´ LR(k) gramatiky Definice (Silna´ LR(k) gramatika

(1))

Silna´ LR(k) gramatika je takova´ gramatika, pro kterou je mozˇne´ vytvorˇit syntakticky´ analyza´tor vykona´vajı´cı´ syntaktickou analy´zu zdola nahoru, ktery´ vyuzˇ´ıva´ pouze informace o nejblizˇsˇ´ıch k symbolech v neprˇecˇtene´ cˇa´sti vstupnı´ho rˇeteˇzce.

LR prˇeklady

LR(0) gramatiky

Silne´ LR(k) gramatiky

Pomocne´ mnozˇiny

Definice (Silna´ LR(k) gramatika

(2))

Bezkontextova´ gramatika G = (N, T, P, S) je silna´ LR(k) gramatika, jestlizˇe pro rozsˇ´ırˇenou gramatiku G0 = (N ∪ {S0 }, T ∪ {#}, P0 , S0 ), kde P0 = P ∪ {S0 → #S}: 1 Pro kazˇdou dvojici pravidel v P0 ve tvaru (a) A → αX, B → βX, (b) A → αX, B → ε, kde X ∈ BEFORE(B), (c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B), 2

platı´ FOLLOWk (A) ∩ FOLLOWk (B) = ∅. Pro kazˇdou dvojici pravidel v P0 ve tvaru (a) A → αX, B → βXγ, (b) A → ε, B → βXγ, kde X ∈ BEFORE(A), (c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),

platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

Silne´ LR(k) gramatiky

Pomocne´ mnozˇiny

Definice (Silna´ LR(k) gramatika

(2))

Bezkontextova´ gramatika G = (N, T, P, S) je silna´ LR(k) gramatika, jestlizˇe pro rozsˇ´ırˇenou gramatiku G0 = (N ∪ {S0 }, T ∪ {#}, P0 , S0 ), kde P0 = P ∪ {S0 → #S}: 1 Pro kazˇdou dvojici pravidel v P0 ve tvaru (a) A → αX, B → βX, (b) A → αX, B → ε, kde X ∈ BEFORE(B), (c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B), 2

platı´ FOLLOWk (A) ∩ FOLLOWk (B) = ∅. Pro kazˇdou dvojici pravidel v P0 ve tvaru (a) A → αX, B → βXγ, (b) A → ε, B → βXγ, kde X ∈ BEFORE(A), (c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),

platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → E + T E − T T T → T ∗ F T/F F F → n i (E)

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

Prˇ´ıklady

FOLLOW(S) = {$} FOLLOW(E) = {+, −, ), $} FOLLOW(T) = {∗, /, +, −, ), $} FOLLOW(F) = {∗, /, +, −, ), $}

BEFORE(S) = {#} BEFORE(E) = {(, #} BEFORE(T) = {+, −, (, #} BEFORE(F) = {∗, /, +, −, (, #}

Je silna´ LR(1)? 1

Pro kazˇdou dvojici pravidel ve tvaru (a) A → αX, B → βX,

musı´ platit FOLLOWk (A) ∩ FOLLOWk (B) = ∅. Testujeme pravidla E → E + T, E → E − T: FOLLOW(E) ∩ FOLLOW(E) 6= ∅

Nenı´ silna´ LR(1).

LR prˇeklady

LR(0) gramatiky

Pomocne´ mnozˇiny

Silne´ LR(k) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

FOLLOW(S) = {$} FOLLOW(E) = {+, −, ), $} FOLLOW(A) = {n, i, (} FOLLOW(T) = {∗, /, +, −, ), $} FOLLOW(B) = {n, i, (} FOLLOW(F) = {∗, /, +, −, ), $}

BEFORE(S) = {#} BEFORE(E) = {(, #} BEFORE(A) = {(, #} BEFORE(T) = {A} BEFORE(B) = {A} BEFORE(F) = {B}

EFF(+ · FOLLOW(A)) = {+} EFF(E · FOLLOW(S)) = ∅ EFF(E) · FOLLOW(F)) = ∅ EFF(T · FOLLOW(E)) = ∅ EFF(AT · FOLLOW(E)) = ∅ EFF(BF · FOLLOW(T)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

1

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(a) A → αX, B → βX, (b) A → αX, B → ε, kde X ∈ BEFORE(B), (c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B), platı´ FOLLOWk (A) ∩ FOLLOWk (B) = ∅. 1

(a) Nenı´ co testovat, zˇa´dna´ dveˇ pravidla nekoncˇı´ stejneˇ.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

1

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(a) A → αX, B → βX, (b) A → αX, B → ε, kde X ∈ BEFORE(B), (c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B), platı´ FOLLOWk (A) ∩ FOLLOWk (B) = ∅. 1

(b) Nenı´ co testovat, na konci zˇa´dne´ho pravidla se nevyskytujı´ prvky mnozˇiny BEFORE(A) ani BEFORE(B).

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

1

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(a) A → αX, B → βX, (b) A → αX, B → ε, kde X ∈ BEFORE(B), (c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B), platı´ FOLLOWk (A) ∩ FOLLOWk (B) = ∅. 1

(c) Nenı´ co testovat, mnozˇiny BEFORE(A) a BEFORE(B) majı´ pra´zdny´ pru˚nik.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(a) A → αX, B → βXγ, platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(a) A → αX, B → βXγ, platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

S → E, A → E+ S → E, A → E− S → E, F → (E) E → AT, B → T∗ E → AT, B → T/

FOLLOW(S) ∩ EFF(+ · FOLLOW(A)) = ∅ FOLLOW(S) ∩ EFF(− · FOLLOW(A)) = ∅ FOLLOW(S) ∩ EFF( ) · FOLLOW(F)) = ∅ FOLLOW(E) ∩ EFF(∗ · FOLLOW(B)) = ∅ FOLLOW(E) ∩ EFF(/ · FOLLOW(B)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(b) A → ε, B → βXγ, kde X ∈ BEFORE(A), platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(b) A → ε, B → βXγ, kde X ∈ BEFORE(A), platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

A → ε, S0 → #E FOLLOW(A) ∩ EFF(E · FOLLOW(S)) = ∅ A → ε, F → (E) FOLLOW(A) ∩ EFF(E) · FOLLOW(F)) = ∅ B → ε, E → AT FOLLOW(B) ∩ EFF(T · FOLLOW(E)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B), platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

2

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Pro kazˇdou dvojici pravidel v P0 ve tvaru

(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B), platı´ FOLLOWk (A) ∩ EFFk (γ · FOLLOWk (B)) = ∅.

A → ε, S → #E A → ε, E → AT B → ε, T → BF

FOLLOW(A) ∩ EFF(#E · FOLLOW(S)) = ∅ FOLLOW(A) ∩ EFF(AT · FOLLOW(E)) = ∅ FOLLOW(B) ∩ EFF(BF · FOLLOW(T)) = ∅

Prˇ´ıklady

LR prˇeklady

LR(0) gramatiky

S → #E E → AT A → E+ E− ε T → BF B → T∗ T/ ε F → n i (E)

Pomocne´ mnozˇiny

FL(S) = {$} FL(E) = {+, −, ), $} FL(A) = {n, i, (} FL(T) = {∗, /, +, −, ), $} FL(B) = {n, i, (} FL(F) = {∗, /, +, −, ), $}

Silne´ LR(k) gramatiky

BEF(S) = {#} BEF(E) = {(, #} BEF(A) = {(, #} BEF(T) = {A} BEF(B) = {A} BEF(F) = {B}

Je to silna´ LR(1) gramatika.

EFF(+ · FL(A)) = {+} EFF(E · FL(S)) = ∅ EFF(E) · FL(F)) = ∅ EFF(T · FL(E)) = ∅ EFF(AT · FL(E)) = ∅ EFF(BF · FL(T)) = ∅

Prˇ´ıklady