@17 Definice AST přímo plyne z toho převodu. Ten se definuje tak, že ve frázovém stromě dojde ke kontrakci hran mezi vrcholem reprezentovaným hlavou aplikovaného pravidla a výsledným neterminálem. Po kontrakci všech takových hran dostaneme AST a z postupu přímo plyne, že různé frázové stromy mohou dát stejný AST (u jednoznačné gramatiky to je ovšem 1:1). Ono se to asi lépe vysvětluje na přirozeném jazyce, klasický příklad Chomského s neterminály S, N, V, NP, VP, Det má např. pravidlo VP -> V NP, u kterého je hlavou V. Proto ve frázovém stromě kontrahujeme hranu mezi V a VP (V je preterminál a ten by se měl ještě kontrahovat s odpovídajícím listem). Podobně u pravidla S -> NP VP je hlavou VP a kontrahuje se tedy hrana mezi S a VP. Nakonec tedy dostaneme strom, jehož vrcholy jsou ohodnoceny původními listy a hrany mezi nimi představují závislosti (např. u prog. jazyka ve výrazu sčítání závisí operandy na vrcholu ohodnoceném operátorem, jenž je hlavou příslušného pravidla). Celý tento proces je nezávislý na konkrétním jazyce, k dalším transformacím už dochází s přihlédnutím k sémantice.
ČLÁNKY DO MAILU