• Lekce 12
  • Úlohy
  • Co jsme dnes probrali

Lekce 12

Úlohy

Postfix (5b)

V složce této lekce na GitLabu máte parser implementovaný v Pythonu. Infixový parser už hotový je, ale programátor byl líný, a na implementaci toho postfixového zapomněl. Doimplementujte ho za něj.

Na tyto úkoly máte dva týdny, tedy do 12. 12. 2024.

Závorky (6b)

• Přidejte do programu podporu pro závorky.
  • Nápověda: Přidejte pravidlo N => (E).
  • Prvně je samozřejmě potřeba přidat nové tokeny a rozpoznat je v lexeru.

Proměnné (9b)

• Přidejte do programu podporu pro proměnné.
  • Vedle pravidla N => číslo tak vznikne nové pravidlo N => proměnná.
  • Stačí podporovat jednopísmenné proměnné.
  • Opět bude potřeba nový token a rozšíření lexeru.
• Program již nebude načítat vstup z argumentu, ale z konzole.
  • Bude pracovat interaktivně, tedy načte řádek, zpracuje ho, vypíše výsledek a čeká na další řádek.
  • Prázdný řádek ukončí program.
• Řádek může obsahovat pouze výraz, pak jej program vyhodnotí.
• Také může být řádek ve formátu x = výraz, poté do proměnné x uloží výsledek výrazu.
  • Toto nemusíte rozpoznávat v lexeru, stačí ručně rozdělit řádek podle =.
• Hodnoty proměnných budete muset předat do funkce compute.

Co jsme dnes probrali

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í).