《编译原理》第章自上而下语法分析.pdf

编译原理 武汉大学计算机学院 编译原理课程组 第5章 自上而下语法分析 · 基本思想 · 存在的问题 · 解决方法 · LL(1)方法 · 递归子程序法 5.0 语法分析的功能及基本思想 1. 语法分析的功能 依据语法规则，逐一分析词法分析时得到的单词，把单词串 分解成各类语法单位，即确定它们是怎样组成说明和语句，以及 说明和语句又是怎样组成程序的。分析时如发现有不合语法规则 的地方，便将出错的位置及出错性质打印报告给程序员；如无语 法错误，则用另一种中间形式给出正确的语法结构，供下一阶段 分析使用。 5.0 语法分析的功能及基本思想 2． 自上而下语法分析的基本思想 从识别符号出发，不断建立直接推导，试图构造一个最左推导 序列，最终由它推导出与输入符号串相同的符号串。从语法树的角 度看，自顶向下分析过程将以识别符号为根结点，试图向下构造一 棵语法树，其末端结点符号串正好与输入符号串相同。 相应于高级语言的编译过程，自上而下语法分析就是从该高 级语言文法的开始符号——程序 出发，试图推导得到该文法的 句子—— 源程序或与其等价的单词串。 5.0 语法分析的功能及基本思想 3. 自上而下语法分析遇到的问题 如果文法中存在如下形式的产生式 A →α | α |…| α 1 2 n 那么在自上而下的语法分析过程中，当要对A展开时，应按哪 一个后选式展开呢？即如何确定替换A的αi 。如果选择错误， 将导致回溯。 在分析的过程中，匹配失败后，必须退回到出错点，选择 其它可能的产生式重新推导，这个过程称为回溯。 5.0 语法分析的功能及基本思想 3. 自上而下语法分析遇到的问题 当文法中出现左递归时（存在非终结符号U ，对于它有 U →U…或U + U… ），会使分析过程陷入无限循环。 ⇒ 例如对文法G[S]： S →AB A →bB|Aa B →Sb|a 5.0 语法分析的功能及基本思想 4.自上而下语法分析中问题的解决方法 · 避免回溯 · 消除左递归 5.1 消除左递归的方法 1．直接左递归的消除 •采用扩充BNF表示 [x]——x可以出现零次或一次 {x}——x可以出现零次到多次 x(y|z)——等价于 xy 或 xz 5.1 消除左递归的方法 1．直接左递归的消除 •采用扩充BNF表示 •引进新的非终结符号，将左递归改写为右递归。 设有产生式 U →Ux |Ux |…|Ux |y |y |…|y 1 2 m 1 2 n 其中y (i=1 ，2 ，…，n)均不以符号U为首，增加新非终结符号U′， i 将上述产生式变换为 U →y U′|y U′|…|y U′ 1 2 n U′→x U′|x U′|…|x U′| ε 1 2 m 5.1 消除左递归的方法 2．间接左递归的消除 ⑵执行循环语句： FOR i:=1 TO n DO BEGIN ①FOR j:=1 TO i-1 DO 将产生式规则P →P γ改写