编译原理张晶版 第二章 文法和语言.ppt

2.4语法树与文法的二义性一、语法树 3.语法树中的概念 （4）短语：子树的末端符号自左至右连成串，相对于子树树根而言称为短语。 简单短语（直接短语）：若短语是某子树根经过1步推导得到的，则称之为该子树根的简单短语。 句型的短语：该句型中哪些符号串可以构成某子树根的短语。 第二章 编译基础（78） （5）定义:任一句型的最左简单短语称为该句型的句柄 给定句型找句柄的步骤： 短语 简单短语 句柄 注：句柄是最左归约时要寻找的简单短语 注意：短语、简单短语是相对于句型而言的，一个句型可能有多个短语、简单短语，句柄只能有一个。 第二章 编译基础（80） ( 3 ) 子树与短语 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。 定理 只需画出句型的语法树，然后根据子树找短语→简单短语→句柄。 第二章 编译基础（81） S back a B a B B b b S b A a 句柄 第二章 编译基础（82） 无符号整数= 数字串 = 数字串 数字 = 数字0 = 10 数字串 数字串 数字串 数字串 数字串 数字 (1) (2) (4) (3) (5) 数字串 数字 数字串 数字 数字串 数字 数字串0 数字串0,0 0 0 数字,0 数字0 , 数字,0 数字0 数字 1 1,0 10 ,1,0 10 = 数字串0 句型 短语 简单短语 句柄 第二章 编译基础（83） ( 4 ) 树与推导 句型推导过程==句型语法树的生长过程 由推导构造语法树 1 从识别符号开始，自左向右建立推导序列。 由根结点开始，自上而下建立语法树。 第二章 编译基础（84） 由语法树构造推导 2 自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。 从句型开始,自右向左地逐步进行归约，建立归约序列。 归约 第二章 编译基础（85） 2.4 语法树与文法的二义性二、文法的二义性 1.句子的二义性： --如果文法的一个句子存在对应的两棵或两棵以上的语法树，则该句子是二义的。 2.文法的二义性： --包含二义性句子的文法就是二义文法。 第二章 编译基础（86） 2.4语法树与文法的二义性二、文法的二义性 例如：文法G=({E}，{+,*,(,),i}, P, E) 其中P: E E+E|E*E|(E)|i 对于句子(i*i+i)有几种最左推导。 1）E （E） （E+E） （E*E+E） （i*E+E） （i*i+E) (i*i+i) 2) E （E） （E*E） （i*E） （i*E+E） （i*i+E) (i*i+i) 第二章 编译基础（87） E ( E ) E E + E ( E ) E * E i E * E i i