编译原理ppt课件二 编译原理第二章.ppt

=(VN,VT,P,S),G的一棵语法(分析)树满足如下条件:,此标记是VT∪VN∪{ε}中的符号。。,则该节点标记一定是非终结符。,A2,…,Ak,则AA1A2…Ak必须是P中的产生式。=(VN,VT,P,S),其中P:SaASaASbASS,对每步推导画相应分枝ASaSbSAaabaaSbASaabASaabbaSaabbaa()4根据归约序列,对每步归约画相应分枝ASaSbSAaabaaAaaSbAaaSbbaaaabbaa(),它反应了一个句子语法结构的层次。(若文法是无二义性的),采用各种推导过程,画出的分析树是一样的。语法树并未描述推导过程。,用画语法树的过程解释语法分析过程,用语法树图解语法结构。语法树是推导的图形表示。关于语法树的几点说明6一棵分析树中一个特有的结点连同它的全部后裔,连接这些后裔的边以及这些结点的标记。例如::只有单层分支的子树7短语:子树的末端节点形成的符号串是相对于子树根的短语。直接短语:简单子树的末端节点形成的符号串是相对于简单子树树根的直接短语。句柄:最左简单子树的末端节点形成的符号串是句柄。例如,对表达式文法G[E]和句子a1+a2*a3,挑选出推导过程中产生的句型中的短语,直接短语,句柄。用子树解释短语,直接短语,句柄:8描述一个句子的文法不是唯一的;。考虑表达式下面的文法G[E],其产生式如下:EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导:EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*E+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导例(1)10