高级语言及其语法描述-有限自动机理论资料.ppt

* 3. 语法分析树与二义性 语法树(推导树Parse Tree) 作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树 * 语法树的相关概念 结点：每个树的结点对应于一个符号。结点的名字就是该符号。 边：两个结点之间的连线。 根结点：没有边进入的结点。 分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点） 子树：语法树的某个结点和它向下射出的部分 末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。 * 语法树的概念 定义：语法树的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。 引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。 * 语法树的特征 给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征： 1、根结点的标记是开始符号S； 2、每个结点的标记都是V中的一个符号； 3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么 A → A1A2..AR一定是P中的一条规则； 4、若一标记为A的结点至少有一个除它以外的子孙，则A∈VN 5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。 * 从推导构造语法树 方法：把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。 例如：推导 S ?AB ?AcBd ?Accdd ?abccdd S B B d b a A c d c * 语法树的构造过程 S ?AB ?AcBd ?Accdd ?abccdd S S B A S B B d A c S B B d A c d c S B B d b a A c d c （1） （2） （3） （5） （4） * 从语法树构造推导 方法：从分支建立直接推导，然后从语法树中剪去之这个分支，直到无分支可剪。 语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。 一棵语法树可能对应不止一种推导。 一棵语法树是不同推导过程的共性抽象。 * 从语法树构造推导的过程 例如文法G[S]： S → AB A → aAb|ab B → cBd|cd 存在下面的推导可能： S ?AB ?AcBd (4) (3) ?Accdd ?abccdd (2) (1) S ?AB ?abB ?abcBd ?abccdd （从后往前看） S B B d b a A c d c (1) (2) (3) (4) * 文法G：E→E+E|E×E|（E）|i 句子 i×i+i 对应的语法树 两个不同的最左推导： 推导1：E ? E+E ? E×E+E ? i×E+E ? i×i+E ? i×i+i 推导2：E ? E×E ? i×E ? i×E+E ? i×i+E ?i×i+i i E E + E E E × i i E E E × i E E + i i 文法的二义性(Ambiguity) * 定义 如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。 二义性文法存在某个句子,它有两个不同的最左（右）推导 * 例 设if语句S的文法G=({E，A，S}，{if，then，else}，S，P)，其中P为： S?if E then S （1） S ?if E then S else S （2） S?A （3） 证明该文法是二义的。 由文法有推导：S ? if E then S ? if E then if E then S else S 同样也有推导：S ? if E then S else S ? if E then if E then S else S 对于同一个句型if E then if E then S else S，由于应用规则的顺序不同，得到了两个不同的推导，所以该文法是二义文法。 * 为什么要避免文法产生二义性？ 二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处