22b - Precedenční tabulka

• jedna z metod pro syntaktickou analýzu zdola nahoru - pro vyhodnocování výrazů

Mějme nějakou gramatiku s počátečním neterminálem E a terminály i, +, *, ( a )…
G_expr2 = (N, T, P, E), kde N = {E}, T = {i, +, *, (, )},
Tato gramatika nám Poskytuje nám tyto pravidla:
P = { 1: E → E+E, 2: E → E*E, 3: E → (E), 4: E → i}

K této definici nám ještě přibývá priorita operátorů, jelikož by gramatika byla nedeterministická (derivační strom by šel sestrojit různými způsoby - za uplatnění pravidel v různém pořadí … (viz. kapitola o GKJ))

1. svislé popisky nám udávají, jaký znak je na vrcholu zásobníku
2. vodorovné popisky nám udávají, jaký znak nám právě přišel (vstupní token)

1. $ na zásobníku - určuje dno zásobníku
2. $ na vstupu - určuje konec

Nyní budeme do políček v tabulce psát symboly >, < nebo = podle zadaných pravidel…

• pro sestavení tabulky budeme muset nejprve porovnat priority jednotlivých operátorů
• v našem příkladě máme operátory + a * … * má větší prioritu jak +

Není dobré si představovat symboly < a > jako větší a menší, ale spíše jako závorky (, ).

1. V prvním případě nám říkají, že pokud přijde + a my máme na vrcholu zásobníku *, „ukončíme závorku >“, tedy je třeba vyhodnotit nejprve výraz, který už na zásobníku je… Případně si můžete představit, že * > +.
2. V druhém případě máme na vrcholu zásobníku + a přijde nám *. Jelikož * má větší prioritu, začínáme nový výraz s větší prioritou vyhodnocení, dáme < („začátek závorky“). Případně + < *.

• určuje pořadí, v jakém budeme vyhodnocovat operátory se stejnou prioritou
  1. levě asociativní - a * b * c = (a * b) * c
  2. pravě asociativní - a * b * c = a * (b * c)

Jelikož náš příklad používá levě asociativní výrazy, vyhodnotíme prvně výraz, který je na zásobníku - „ukončíme tedy závorku“. Případně se dá říci, že op. na zásobníku > vstupní op.

• jediné pravidlo, které máme s identifikátorem i, je 4: E → i.

1. Pokud tedy přijde situace, kdy znak na zásobníku je i, je třeba i vyhodnotit („uzavřít závorku“) - převést i na E.
2. Pokud máme situaci, že i je jako vstupní token, je třeba vyřešit prioritně i, jelikož i kdybychom tam např měli +, nemůžeme udělat E+i - musíme podle pravidel nejprve převést i na E. Proto tedy „začneme závorku“, jelikož i má větší prioritu.
3. Výjimkou jsou kombinace i(, ii a )i.

• závorky nám v našem případě slouží k upravení priority vyhodnocování

1. Hned na začátek specialita - pár závorek se rovná, jelikož () bychom mohli klidně zredukovat/odstranit.
2. Pokud nám přijde levá závorka, znamená to, že se snažíme změnit prioritu vyhodnocování - chceme začít nějaký více prioritní výraz, proto „začínáme závorku“.
3. Pokud nám přijde pravá závorka, končíme výraz - tedy žádáme o jeho vyhodnocení. „Končíme tedy závorku.“
4. Nepovolené kombinace jsou opět i( a )i a nově )(, ($ a $)

• jak již bylo zmíněno, určují nám buď dno zásobníku nebo konec vstupu

1. V pravidlech, kde $ je na zásobníku, má každý vstupní znak větší prioritu. Nemáme na zásobníku co vyhodnotit, takže „začínáme hlavní závorku.“
2. Pokud nám dolar přijde jako konec řetězce, končíme čtení a musíme „dovyhodnotit zbytek“. „Končíme tedy hlavní závorku.“
3. Nepovolené kombinace jsou $), ($ a nově $$ (nemůže být prázdný výraz).

Máme vstupní řetězec i+i*i$