Дерево вывода: различия между версиями

'''Дерево вывода''' (''[[Derivation tree, parse tree, syntax]]'') - способ представления множества ''выводов'' одной и той же ''[[цепочка|цепочки]]'' в ''[[контекстно-свободная грамматика|контекстно-свободной грамматике]]'', различающихся лишь порядком применения правил.

(2) если <math>D_1,\ldots,D_k</math> --- [[поддерево|поддеревья]], корнями которых являются [[сын|сыновья]] корня <math>D</math>, помеченные символами <math>X_1, \ldots, X_k</math> соответственно,

то <math>A\longrightarrow X_i\ldots X_k</math> --- правило из множества <math>P</math>. Каждое <math>D_i</math> должно либо быть деревом вывода в [[грамматика|грамматике]] <math>G(X_i)=(N,\Sigma,P,X_i)</math>, если <math>X_i</math> - нетерминал, либо состоять из единственной вершины, помеченной символом <math>X_i</math>, если <math>X_i</math> --- [[терминал]];

(3) если корень дерева имеет единственного сына, помеченного <math>e</math>, то этот сын образует дерево, состоящее из единственной вершины, и <math>A\longrightarrow e</math> --- правило из

Другие названия --- ''[[Дерево разбора]], [[Синтаксическое дерево]].''

''[[(Абстрактное) синтаксическое представление|Абстрактное синтаксическое представление]].''

[Ахо-Ульман],  

[Касьянов/95],  

 

[Касьянов-Поттосин],