编译原理课件_第二章2

《编译原理课件_第二章2》由会员分享，可在线阅读，更多相关《编译原理课件_第二章2（78页珍藏版）》请在金锄头文库上搜索。

1、第二章第二章 前后文无关文前后文无关文 法和语言（续）法和语言（续）上节内容回顾上节内容回顾文法的文法的BNF表示表示字母表和符号串的运算字母表和符号串的运算任意顺序的推导和归约任意顺序的推导和归约任意选择被处理的非终结符选择任意选择被处理的非终结符选择任意选择推导和归约所用的产生式任意选择推导和归约所用的产生式句型和句子句型和句子左递归和右递归的文法左递归和右递归的文法文法的等价条件：语言相同文法的等价条件：语言相同2.3 句型的分析句型的分析句型的分析：句型的分析：指识别输入的指识别输入的符号串是否为某一文法的是否为某一文法的句型 (或句子)的过程的过程一对多关系：一对多关系：句型句型/

2、/句子和推导的关系可能句子和推导的关系可能不是一一对应 的。很可能可以通过的。很可能可以通过不同的推导序列推导推导 出出同一个句型或句子。对文法定义的限制和要求文法定义不是任意的。为满足分析算法的要求， 需要对其进行一定的限制。句型分析的基本方法句型分析的基本方法自顶向下（基于推导）自顶向下（基于推导）从文法从文法GS的开始符号的开始符号S出发，试图推导出发，试图推导 出给定的符号串的过程。出给定的符号串的过程。自底向上（基于归约）自底向上（基于归约）推导的逆过程。即从给定符号串出发，推导的逆过程。即从给定符号串出发， 试图将其逆向归约为开始符号的过程。试图将其逆向归约为开始符号的过程。从语法

3、树的角度看2.3.1 规范推导和规范归约规范推导和规范归约2.3.1.1 推导和归约的顺序推导和归约的顺序 （1）终结符选择顺序）终结符选择顺序任意顺序的推导和归约任意顺序的推导和归约不利于计算机自动地进行推导或归约不利于计算机自动地进行推导或归约因此，通常只考虑因此，通常只考虑最左推导或最右推导最左推导：用于用于自顶向下分析分析最左句型最左句型：最左推导得到的句型：最左推导得到的句型最右推导：最左归约的逆过程，用于的逆过程，用于自 底向上分析分析最右句型（规范句型）最右句型（规范句型）：最右推导得到最右推导得到 的句型的句型后续章节后续章节 的基础的基础最左推导的例子最左推导的例子得到得到i

4、+i*i的最左推导的最左推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i文法G(E): E E+T | T T T*F | F F (E) | iET TF Fi TT*F TF Fi FiEE+T最右推导最右推导EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i文法G(E): E E+T | T T T*F | F F (E) | i最左归约最左归约i+i*i F+i*i T+i*i E+i*i E+F*i E+T*i E+T*F E+T E最左归约是最右最左归约是最右 推导的逆过程推导的逆过程最右推导和最左归约最右推导和最左归约最左推导和最

5、右归约不一定存在最左推导和最右归约不一定存在每个句子都有相应的最左和最右推导，每个句子都有相应的最左和最右推导， 因此，句子即是左句型也是右句型（规因此，句子即是左句型也是右句型（规 范句型）范句型）不是每个句型都有最左/最右推导例如，例如，E +E+i*T即不是左句型，也即不是左句型，也 不是右句型不是右句型最左、最右推导的形式定义最左、最右推导的形式定义形式上，从符号串形式上，从符号串 到符号串到符号串 的推导序列的推导序列 * xUy xuy * 总有总有x VT* (y VT*) 时，称为时，称为最左（右） 推导2.3.1.2 推导和归约的顺序推导和归约的顺序 （2）文法规则的选择）文

6、法规则的选择任意顺序的产生式选择存在不足：任意顺序的产生式选择存在不足：回溯回溯在每个推导和归约步骤，应当如何确定究在每个推导和归约步骤，应当如何确定究 竟哪个产生式可以得到最后的结果？竟哪个产生式可以得到最后的结果？最右推导（归约的逆过程）最右推导（归约的逆过程）E T F iE E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i文法G(E): E E+T | T T T*F | F F (E) | i回溯回溯最右推导（最左归约）中的回溯最右推导（最左归约）中的回溯最左推导中的回溯最左推导中的回溯最左推导最左推导ETFi（失败回溯）（失败回溯）E+TE

7、+T+T失败回溯失败回溯T+TT*F+T失败回溯失败回溯F +T(E)+T失败失败i+T失败失败 i+i*iE E+T | T T T*F | F F (E) | i推导成功推导失败1、如何知道推导失败? 2、能否避免回溯？文法分析算法的设计目标的设计目标文法分析算法文法分析算法 的设计目标的设计目标选择恰当的产生式 推导或归约推导或归约提高效率2.3.1.3 文法规则和分析算法的关系文法规则和分析算法的关系 （1）回顾：语言的表示方法）回顾：语言的表示方法2.2.2.3节给出了语言表示的三种方法节给出了语言表示的三种方法枚举法枚举法规则生成法（定义文法规则）规则生成法（定义文法规则）对应于自

8、顶向下分析对应于自顶向下分析语言识别法（定义自动机）语言识别法（定义自动机）对应于自底向上分析对应于自底向上分析根据什么进 行分析？都需根据都需根据 文法规则 进行设计进行设计2.3.1.3 文法规则和分析算法的关系文法规则和分析算法的关系 （2）与自顶向下分析的关系）与自顶向下分析的关系最左推导最左推导：自顶向下分析的基础2.2节节推导推导语言的全部句子语言的全部句子。编译器的设计目的编译器的设计目的 推导出语言的全部句子？推导出语言的全部句子？ 识别符号串（程序）识别符号串（程序）,进行相关处理进行相关处理!2.3.1.3 文法规则和分析算法的关系文法规则和分析算法的关系 （3）与自底向上

9、分析的关系）与自底向上分析的关系自底向上分析自底向上分析以符号串为基准以符号串为基准符号串的特点符号串的特点归约归约 开始符号开始符号与自顶向下分析的比较与自顶向下分析的比较自顶向下：推导时可以不需要输入的符自顶向下：推导时可以不需要输入的符 号串（程序）号串（程序）自底向上：必须有符号串自底向上：必须有符号串2.3.1.3 文法规则和分析算法的关系文法规则和分析算法的关系 （4）输入字符）输入字符文法规则文法规则推导推导/归约归约当前推导结果当前推导结果文法规则输入字符串输入字符选择 下一步骤要用 的文法规则下步使用的文法规则下步使用的文法规则选择选择自动推导自动推导/归约归约更新结果更新结

10、果输入输入选择依据选择依据2.3.1.3 文法规则和分析算法的关系文法规则和分析算法的关系 （5）其他说明）其他说明避免回溯，提高效率对文法定义加以限制设计高效的算法提高实现的效率2.3.2 语法树和二义性语法树和二义性推导和归约的图形表示推导和归约的图形表示语法树语法树二义性二义性要求：要求：能够根据给定语法和符号串，进行推导和归约能够根据给定语法和符号串，进行推导和归约能够给出其语法树能够给出其语法树能够根据语法树，给出推导和归约过程能够根据语法树，给出推导和归约过程2.3.2.1 语法树的基本概念语法树的基本概念 （1）用途）用途又称具体语法树或分析树图形表示推导或归约过程的图形表示树型

11、数据结构推导或归约结果的计算机存储方式语法分析的结果也可以用推导/归约序列等表示结构化 表示方 法2.3.2.1 语法树的基本概念语法树的基本概念 （2）树型数据结构）树型数据结构语法树是一语法树是一有向树（连通的）1）有且仅有一个无任何前驱的结点，称为根）有且仅有一个无任何前驱的结点，称为根 （S）；）； 2）除根外，每个结点恰有一个直接前驱；）除根外，每个结点恰有一个直接前驱； 3）对于任一结点）对于任一结点m，从根到从根到m可达可达; 4) 每个结点的后继是有序的（从左到右）每个结点的后继是有序的（从左到右）2.3.2.1 语法树的基本概念语法树的基本概念 （2）定义：与文法的关系）定义

12、：与文法的关系设设G=(VN,VT,P,S)是一文法，则满足下述条件是一文法，则满足下述条件 的树称为的树称为语法树： 1）每个结点有一标记）每个结点有一标记X， X V； 2）根的标记为）根的标记为S（开始符）；（开始符）； 3）若结点）若结点X有后继，则有后继，则X VN； 4）A有有k个后继，自左至右为个后继，自左至右为X1, X2, , Xk，则，则 A X1X2Xk P一个语法树的例子一个语法树的例子 赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6中间节点：中间节点： 非终结符非终结符有向边：有向

13、边： 节点派生关系节点派生关系y=x+r*6根节点：根节点： 开始符号开始符号叶子节点：叶子节点： 终结符号终结符号子树：子树： 节点节点 及其全及其全 部子节部子节 点点2.3.2.1 语法树的基本概念语法树的基本概念 （2）语法树的建立过程语法树的建立过程语法树的建立过程语法树的建立过程推导推导/归约的过程归约的过程一对多关系一对多关系语法树可由不同的推导或归约序列形成语法树可由不同的推导或归约序列形成最左和最右推导得到的语法树可能不同最左和最右推导得到的语法树可能不同约定约定通常采用最左推导通常采用最左推导/最右推导（最左归约）最右推导（最左归约）语法树建立和最左推导语法树建立和最左推导

14、i+i*i的最左推导的最左推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iET TF FiTT*FTF Fi FiEE+TE+TTFiET*FFii从左到右从左到右 排列排列自顶向下 最左推导语法树建立和最右推导语法树建立和最右推导 i+i*i的最右推导的最右推导EE+TE+T*FE+T*iE+F*iE+i *iT+i*iF+i*ii+ i*iTT*F Fi TF Fi ET TF FiEE+TE+TTFiET*FFii从左到右从左到右 排列排列自顶向下 最右推导最右推导最右推导EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i最左归约最左归约i+i*i F+i*i T+i*i E+i*i E+F*i E+T*i E+T*F E+T E语法树的建立和最左归约语法树的建立和最左归约E+TTFiETF*Fii句型和语法树的关系句型和语法树的关系句型：句型：在语法树生成过程中，所有叶子节点共在语法树生成过程中，所有叶子节点共 同构成了句型同构成了句型2.3.2.2 二义性二义性 （1）定义）定义定义：二义性文法若一个文法的某句子存在若一个文法的某句子存在两个不同的最右 (最左)推导，则该文法是二义性的，否则是则该文法是二义性的，否则是 无二义性的。无