Překladače

3. blok: Syntaktická analýza, úvod do atributových gramatik (motivace)

Metody syntaktické analýzy LL a LR byly detailně studovány v první třetině kurzu IA006.

Přednášky:

Shlédněte přednášku, která je tématicky rozdělena do 3 částí: část 1. se týká výhradně syntaktické analýzy, další části jsou de facto motivačním úvodem k atributovým a překladovým atributovým gramatikám.

1. Úkoly syntaktického analyzátoru (SyAn), jeho komunikace s ostatními moduly kompilátoru,

principy syntaktické analýzy metodou rekurzivního sestupu (recursive descent parsing).

PA008_Synt_analyza_cast_1.mp4

2. Zavedení pojmu překladové (bezkontextové) gramatiky a její využití pro možnou konstrukci (kódu) AST.

Příklad: formální překlad (vstupního) infix výrazu E a na ekvivalentn (výstupní) postfix (jako postfix kód AST).

PA008_Synt_analyza_cast_2.mp4

3a. Příklad: doplnění pravidel (standardní) CFG o funkce konstrukce AST v jednom průchodu při analýze zdola (motivace pro následnou definici atributových gramatik - vizte další blok).

PA008_Synt_analyza_cast_3.mp4

Sumarizující foto tabule k výše uvedené přednášce lze nalézt v učebních materiálech předmětu, sekce

Záznamy přednášek nebo též zde:

PA008_Synt_analyza_cast_3_vytvor_AST_zdola.jpg

3b. Příklad: doplnění pravidel CFG o funkce konstrukce AST v jednom průchodu při analýze shora (motivace pro následnou definici atributových gramatik - vizte další blok).


Studium:

K těmto přednáškám doporučuji doplňkově prostudovat ze skript M.Češka a kol.: Překladače tyto části: (za předpokladu, že jste absolvovali kurs IA006 nebo samostatně dostudovali jeho 1. třetinu.

K vlastní syntaktické analýze pak navíc z uvedených skript (dále jen skripta):

  • sekci 3.2.5 (str. 41-44) "Analýza rekurzívním sestupem"; možno též najít řadu odkazů pod názvem "Recursive descent parsing". Jedná se pouze o jinou implementaci LL analýzy, a to nikoli pomocí PDA. ale pomocí tzv. "Recursive Finite State Machines" (vzájemně rekurzivních konečně stavových automatů - vzájemně rekurzívních procedur). Poznámka: (Vzájemně) rekurzívní deterministické konečné automaty (DFA) rozpoznávají tutéž třídu jazyků jako deteterministické zásobníkové automaty (DPDA).
  • orientačně se seznámit s použitím generátoru syntaktických analyzátorů yacc v sekci 3.5.1. (s. 93-100)
K překladovým gramatikám ze skript sekci 4.1 "Základní pojmy teorie překladu".
Předchozí
Následující