Hlavní navigace

Frázové a abstraktní syntaktické stromy

2. 1. 2012 19:09 zboj

Pod článkem o Jisonu se rozvinula zajímavá diskuse, navážu proto na tématiku stručným vysvětlením rozdílu mezi abstraktní a frázovou syntaxí.

Nejprve je třeba ujasnit si terminologii, která je tu mírně zmatená. Frázové stromy se tak nazývají podle frázové gramatiky, která se definuje pro každý formální jazyk. V literatuře je najdete také pod názvem „konkrétní“ stromy (jako protiklad k abstraktním). Abstraktní syntaktické stromy (anglicky Abstract Syntax Tree, odtud často používaná zkratka AST) se odvozují z frázových a lze je přímo použít pro interpretaci jazyka (nebo kompilaci).

Parsingu zpravidla předchází lexikální analýza, jejímž výstupem je seznam tokenů (u programovacích jazyků bývá gramatika jednoznačná). Počet tokenů je stejný jako počet listů frázového stromu. Listy jsou ohodnoceny vstupními tokeny, ostatní vrcholy stromu jsou ohodnoceny neterminály gramatiky, na jejímž základě byl strom vytvořen.

Abstraktní strom obsahuje menší počet vrcholů, je roven nanejvýš počtu tokenů. Převod z frázového na abstraktní strom je plně automatický a není ovlivněn sémantikou jazyka. Každému frázovému stromu přitom odpovídá právě jeden abstraktní, opačně to ale samozřejmě neplatí.

S přihlédnutím k sémantice lze definovat ekvivalenci abstraktních stromů, např. vzhledem k vlastnostem operace sčítání jsou abstraktní stromy pro výrazy (a+b)+c a a+(b+c) ekvivalentní, pro mínus to už ale neplatí. Frázový strom těchto výrazů bude mít 10 vrcholů, abstraktní 5.

Při převodu na abstraktní strom se určuje hlava pravidla, což je většinou operátor nebo jméno funkce (u volání funkce). V příkladu výše by to byl operátor +.

V závislosti na sémantice se abstraktní stromy po parsingu ve fázi optimalizace upravují (některé podstromy např. nejsou potřebné). Interpretace abstraktního stromu je přímočará (fungují tak interprety Javascriptu), při kompilace se používá většinou mezikód, a to buď explicitní (např. bajtkód v .NETu či Javě), nebo implicitní (vnitřní reprezentace kódu, jako např. v LLVM).

Frázové stromy při implementaci interpretu nebo překladače v podstatě nikdy nevidíme, jsou jen jakousi imaginární datovou strukturou, již generuje gramatika, vlastní parser generuje přímo AST. Navíc často splývá syntax a sémantika. Pokud si chcete vyzkoušet, jak se netriviální gramatika implemetuje, doporučuji třeba ANTLR.