Zpracování aritmetického výrazu, gramatiky

• Úlohy
  • Kalkulačka
• Co jsme dnes probrali
  • Zápis aritmetického výrazu
    • Infixový zápis
    • Postfixový zápis
    • Prefixový zápis
  • Zpracování výrazu
    • Abstraktní syntaktický strom
    • Lexer
    • Parser
  • Gramatika
  • Příklad parsování

Úlohy

Kalkulačka

Napište program, který na vstupu přijme aritmetický výraz (s operátory sčítání, násobení a odčítání) v postfixové (RPN) notaci. Na výstup vypíše hodnotu výrazu.

Můžete předpokládat, že čísla a operátory budou oddělené právě jednou mezerou.

Co jsme dnes probrali

Zápis aritmetického výrazu

Infixový zápis

• Běžně používaný zápis, operátory jsou mezi čísly: 1 + 2 + 3.
• Víceznačný, ze syntaktického hlediska nejde poznat, v jakém pořadí vyhodnocovat.
  • (1 + 2) + 3 nebo 1 + (2 + 3)?
  • Pro sčítání je to jedno, protože je asociativní. Můžeme si tedy dovolit psát prostě 1 + 2 + 3.
  • Pro odčítání to jedno není.
  • Abychom nemuseli psát tolik závorek, zadefinujeme, že odčítání má asociativitu zleva.
  • 1 - 2 - 3 tedy interpretujeme jako (1 - 2) - 3.
  • Obdobně mocnění má asociativitu zprava: 2 ^ 3 ^ 4 je 2 ^ (3 ^ 4).
  • Dále samozřejmě hraje roli priorita operátorů: 1 + 2 * 3 je 1 + (2 * 3).
• V programovacích jazycích je operátorů více, jejich priorita je určena tabulkou.
  • Menší prioritu než sčítání má například porovnání <=, ještě menší logická spojka &&.

Postfixový zápis

• Operátor je až za svými operandy.
• Pro počítače jednodušší na zpracování.
• Nepotřebujeme závorky, asociativitu ani prioritu.
• Pozice operátorů ve výrazu přesně určuje pořadí vyhodnocování.
  • 1 2 3 * + je 1 + (2 * 3).
  • 1 2 + 3 * je (1 + 2) * 3.
• Dá se vyhodnocovat pomocí zásobníku (pole, kde přidáváme pouze na konec a odebíráme pouze z konce).
  • Čteme zleva doprava.
  • Pokud narazíme na číslo, přidáme ho na zásobník.
  • Pokud narazíme na operátor, vyjmeme poslední dvě čísla ze zásobníku, provedeme na nich operaci a výsledek přidáme zpět na zásobník.
• Existují algoritmy, které umí infixový zápis převést na postfixový.
  • Shunting-yard

Prefixový zápis

• Podobné vlastnosti jako postfixový, jenom je operátor před svými operandy.
• Znáte jej jako volání funkcí.
  • add(1, multiply(2, 3)) odpovídá + 1 * 2 3, tedy 1 + (2 * 3).
• Hojně využívaný v rodině programovacích jazyků LISP

Zpracování výrazu

Abstraktní syntaktický strom

• AST
• Výraz můžeme reprezentovat pomocí stromu.
  • Každý operátor má dva syny, levý a pravý operand.
  • Na konci každé větve je číslo.
• Přesně určuje pořadí vyhodnocování.
• Používá se také například pro reprezentaci programů v překladači.
  • hezký příklad

Lexer

• Dostaneme výraz jako textový řetězec, chceme jej zpracovat.
• Jako první krok jej musíme rozdělit na čísla a operátory.
• Těmto syntaktickým jednotkám říkáme tokeny.
• Mohlo by se zdát, že stačí rozdělit řetězec podle mezer.
  • Mezer však může být více, někde nemusí být vůbec.
  • Čísla chceme mít jako celek a rovnou je převést z textu na číslo.
• Při zpracování výrazu se tokenizace může zdát zbytečná.
  • Výhodou ovšem je, že se tokenizace nezajímá o význam, takže infixový i postfixový zápis můžeme zpracovávat stejně.
  • Například u zpracování kódu je tokenizace prakticky nutná.
• Části programu, která se stará o tokenizaci, říkáme lexer.

Parser

• Lexer nám rozdělil výraz na tokeny, teď je potřebujeme zpracovat.
• Výsledkem bude AST.
• Parser dodává význam tokenům, infixový a postfixový zápis se zpracovávají jinak.

Gramatika

• Formální popis struktury a významu textu.
• Vytvoříme gramatiku pro výraz, který používá sčítání a násobení.

E => S
S => S + P
S => P
P => P * N
P => N
N => number

• Zavedeme proměnné (neterminály), které budou popisovat celky výrazu.
  • E bude celý výraz.
  • S bude součet několika prvků.
  • P bude součin několika prvků.
  • N bude prvek s danou hodnotou.
• Poté zavedeme pravidla, která popisují, z jakých částí se neterminály skládají.
  • E => S, výraz bude vždy součet, jinými slovy nemáme operátory s menší prioritou než sčítání.
  • S => S + P, pokud máme součet, můžeme k němu přičíst další prvek. Tímto prvkem je součin.
  • S => P, umožňujeme výraz, kde není sčítání.
  • P => P * N, pokud máme součin, můžeme jej vynásobit dalším prvkem. Tímto prvkem je číslo.
  • P => N, umožňujeme výraz, kde není násobení.
  • N => číslo, neboli N sestává z několika číslic.
• Tuto formální definici výrazu můžeme použít pro napsání programu, který výraz zpracuje.
• Pokud bychom psali program ručně, hodí se využít asociativity a pravidla poupravit na S => P + S, P => N * P.
  • Jinak by vznikla neukončená rekurze.

Příklad parsování

Pojďme zkusit rozparsovat výraz 1 + 3 + 2.

1. Tento výraz je E.
2. Aplikujeme pravidlo E => S.
3. Pro první + aplikujeme S => S + P
   • Číslo 1 transformuje jako S => P => N => number
   • Číslo 3 transformuje jako P => N => number
   • Máme (1 + 3)
4. Pro druhé + aplikujeme S => S + P
   • Levou stranu máme: (1 + 3)
   • Pravá strana, číslo 2, se transformuje jako P => N => number
   • Tím dostaneme ((1 + 3) + 2)

Poznámka: závorky nejsou symboly z gramatiky, znázorňují pouze postup parsování (a asociativitu sčítání z něj plynoucí).