编译原理第二章(430KB).pptVIP

* 2.5 语法树与文法二义性 一. 语法树的定义 二. 如何画出语法树 三. 子树 四. 二义性文法的定义 五. 在构造编译程序中如何处理 二义性文法 * 设文法G=（VN，VT，P，S）,G的一棵语法（分析）树满足如下条件： 1. 每一个结点有一个标记，此标记是VT∪VN∪{ε}中的符号。 2．根的标记是S。 3．如果一个结点至少有一分支节点，则该节点标记一定是非终结符。 4．如果结点A有K个分支结点A1,A2,…,Ak，则A?A1A2…Ak必须是P中的产生式。 一.分析树的定义 * G=(VN,VT,P,S), 其中 P: S?aAS?a A ?SbA ?SS ?ba 对句型aabbaa 例2.5 * 根据推导序列，对每步推导画相应分枝 A S a S b S A a a b a ?aSbAS ?aabAS ?aabbaS ?aabbaa ?aAS S 二. 如何画出语法树 (1.自顶向下） * 根据归约序列，对每步归约画相应分枝 A S a S b S A a a b a ?aAa ?aSbAa ?aSbbaa ?aabbaa ?aAS S 二. 如何画出语法树 (2.自底向上） * 1. 一个句型推导或分析用一棵树结构图示 出来，它反应了一个句子语法结构的层次。 2. 对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。语法树并未描述推导过程。 3. 在书中，用画语法树的过程解释语法分析过程，用语法树图解语法结构。 语法树是推导的图形表示。 关于语法树的几点说明 * 一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如： S A b S a S b a A a a 三. 子树 简单子树的概念： 只有单层分支的 子树 * 短语：子树的末端节点形成的符号串是相对于子树根的短语。 直接短语：简单子树的末端节点形成的符号串是相对于简单子树树根的直接短语。 句柄：最左简单子树的末端节点形成的符号串是句柄。 例如，对表达式文法G[E]和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。 用子树解释短语，直接短语，句柄: * 描述一个句子的文法不是唯一的； 2. 对于一个句子的分析应是唯一的。 考虑表达式下面的文法 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*a E ?E*E ?E+E*E ?a+E*E ?a+a*E ?a+a*a 四. 文法的二义性 * E?E+E ?a+E ?a+E*E ?a+a*E ?a+a*a E ?E*E?E+E*E ?a+E*E?a+a*E ?a+a*a E E + E E * E a a a E E * E + E E a a a 最左推导 例(1) * E?E+E ?E+E*E ?E+E*a ?E+a*a ?a+a*a E ?E*E?E*a ?E+E*a?E+a*a ?a+a*a E E + E E * E a a a E E * E + E E a a a 最右推导 例(2) * 如果一个文法的句子存在两棵语法树,那么该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的; 否 则，该文法是无二义性的。几点说明： 1 . 一般来说，程序语言存在无二义性文法， 对于表达式来说，文法（2 .1）是无二义性的。对于条件语句，经常使用二义性文法描述它：S? if b S ?if b S else S ? A 二义性的句子: if b if b A else A 四. 二义性（歧义性，ambiquity)的定义: * 下面是 S?mathed_s ? unmathed_s mathed_s ?if expr then mathed_s else mathed_s ?other unmathed_s ?if expr then S ? if expr then