编译 第三章 语法分析.ppt

第三章 语法分析语法分析 2 语法分析方法 自下而上分析法 自上而下分析法 自下而上是指: 根据文法,对输入字串进行归约,若能正确地归约 为文法的初始符号,则表示输入字串是合法的. 典型方法是算符优先分析法. 自上而下是指: 从文法的初始符号进行推导,若能推导出与输入 字串相同的句子,则表示输入字串是合法的. 典型方法是递归下降分析法. 语法分析概述 3 3.1分析器的作用 一、语法分析的任务: 把单词符号作为基本单位,根据文法,分析源程序 (字 符串)是否为合法的程序. 同时报告语法错误并进行错误的恢复，使后面的分析 能够进行下去。 分析器在编译器模型中的位置 源程序 词法 分析器 分析器 符号表 记号 取下一个 记号 前端的 其余部分 分析树中间表示 4 二、语法错误的处理 程序的错误有各种不同的性质。例如，错误可能是： n(1)詞法错误，如标识符、关键字或算符的拼写错误 n(2)语法错误，如算术表达式的括号不配对 n(3)语义错误，如算符作用于不相容的运算对象 n(4)逻辑错误，如无穷的递归调用。 大多数错误的诊断和恢复集中在语法分析阶段，原因如下： (1)大多数错误是语法错误 (2)诊断语法错误比诊断语义错误和逻辑错误容易得多。 分析器出错处理的基本目标是： (1)清楚而准确地报告错误的出现； (2)迅速从每个错误中恢复过来，以便诊断后面的错误 (3)不应使正确程序的处理速度降低太多。 5 三、错误恢复策略 (1)紧急方式恢复：发现错误时，分析器每次抛弃一个输入记号 ，直至输入记号属于某个指定的同步记号集合为止。 同步记号一般是定界符，如分号或end。 优点：方法简单，不会陷入死循环。 适用于一个语句中很少出现多个错误的情况。 (2)短语级恢复：发现错误时，分析器对剩余输入作局部纠正， 用可以使分析器继续分析的输入串来代替剩余输入的前缀。 如：用分号代替逗号、删除多余的分号、插入遗漏的分号。 这种替换可用于纠正任何输入串，已经用于几个错误修复编 译器，首先是用于自上而下的分析方法。它的主要缺点是很 难应付实际错误出现在诊断点以前的情况。 (3)出错产生式：如果对经常遇到的错误了解得很清楚 ，就可以 扩充语言的文法，增加产生错误结构的产生式，用此扩充的 方法来构造分析器。 (4)全局纠正： 在处理不正确的输入串时，作尽可能少的修改。 6 3.2 上下文无关文法 文法：是描述语言的语法结构的形式规则(即语法规则) 形式描述：用一组数学符号和规则来描述语言的方式。 形式语言：形式描述所用的数学符号和规则。 形式：指仅考虑数学符号间的推演,而不涉及符号的具体含义。 上下文无关文法是这样一种文法: 它定义的语法单位,独 立于该语法单位可能出现的环境,不必考虑上下文关系. 自然语言不是上下文无关文法; 程序语言是上下文无关文法. 程序设计语言的许多结构包含固有的递归性，可用上下文 无关文法定义。 例：如果s1和s2是语句，e是表达式，则 “if e then s1 else s2”是语句。 使用语法变量stmt表示语句类，用expr表示表达式类，上述语句 可用文法产生式方便地表示为： stmtif expr then stmt else stmt 7 1. 上下文无关文法定义 上下文无关文法 g 是一个四元组: g =(vt,vn,s,p) vt ： 是一个非空有限集,每个元素称为终结符. 程序设计语言的文法中记号是终结符的同义词。 例如：if,then,else,while,do,等都是终结符。 vn：是一个非空有限集,每个元素为非终结符,代表了一种 语法单位. 且 vt vn=. 例如:表达式,短语,语句等。 s: 是一个非终结符，称为开始符号,s vn. s 是文法g 的最高层次的语法单位. 在程序语言中, s代表了程序这一语法概念. p: 是产生式的有限集合。一条产生式定义了一个非终结 符，产生式形式如下: a (a vn , (vt vn ) * ) 称a定义为 . ( 有时也会用:=代替) (vt | vn ) * 8 n例：文法(id,+,-,*,/,(,),expr,op,expr,p)定 义了简单的算术表达式，p是由下列产生式组成的有限 集合： nexprexpr op expr nexpr(expr) nexpr-expr nexprid nop+ nop- nop* nop/ nop 9 2 文法的几点约定 a) 若 a 1 a 2 a k 则简写为: a 1|2| |k b) 用英文大写字母表前面的字母、字母s、小写字母串 代表非终结符; 英文小写字母表前面的字母、数字、运算符号、标 点符号、黑体字代表终结符; 希腊字母 、大写字母后面的字母、小写字目表后 面的字母串等代表由vt,vn组成的符号串; 即: , (vt vn) * . c) 一个文法,可以仅用开始符号及产生式代替. 例如:表达式的文法可以定义如下: e e+e|e-e|e*e|e/e|(e) e 为文法的开始符号, + - * / ( ) 为终结符. 10 例如：考虑一个文法g1: ns ba na |a n aa 它定义了一个什么样的语言呢？ ns是开始符号，是非终结符 na是非终结符 n是终结符与非终结符组成的字符串 nb是终结符 na是终结符 n 结论：s baa* 11 3 文法 g 与语言l(g)的关系及术语 从文法初始符开始,反复用产生式右部替换左部的非终结符, 直到推出的符号串全部由终结符组成.得到g所定义的各种句子. 例如:e=e+e=e*e +e=i * e + e= i * i + e = i * i + i 定义: 若b,经产生式 b替换后得到 ,称b直接 推出. , , (vt vn) *,用=表示直接推出. 若存在1= 2 = 3= n ,称1可推出n; 1= n表示经一步或若干步1可推出n. 1= n表示经零步或若干步1可推出n. 定义:设s 是g的开始符号,若 s=, (vt vn) *, 则称 是 g的一个句型;若 vt *,则称是 g的一个句子. 如果两个文法产生同样的语言，则这两个文法等价。 + * * 12 例如： e=e+e=e*e +e=i * e + e= i * i + e = i * i + i ne是我们的开始符号，也是非终结符 n+、-、*、/是终结符 ni是终结符 ne+e、e*e +e、i * e + e、 i * i + e是句型 ni*i+i是句子 ne=e+e、 e+e =e*e +e、 e*e +e =i * e + e、 i * e + e = i * i + e是经一步推导出-直接推导 ne = i * i + i是经多步推导出-可推导出 13 定义: 文法 g 所产生的句子的全体,为g所描述的语言,记为 l(g)= |s=, vt * + 文法 g 正规式 v g: 描述句子结构; v:描述单词结构; l(g):g的全体句子; l(v):v的全体单词. 一个句型到另一个句型的推导有两种方式:最左推导和最右 推导: 最左推导是指每次直接推导,对句型的最左非终结符实行替 换; 最右推导是指每次直接推导,对句型的最右非终结符实行替 换. 14 例如：有文法g: e=e+e|e*e|e/e|e-e|i n最左推导： ne=e+e ne+e=e*e +e ne*e +e=i * e + e ni * e + e= i * i + e ni * i + e = i * i + i n最右推导： ne=e+e ne=e+i ne=e*e+i ne=e * i + i ne = i * i + i 15 4 语法树与文法的二义性 语法树可以表示句型的推导及句型的层次结构. 语法树是一棵倒立树,根结点表示了文法的初始符号,每进行一 步推导,树的叶结点构成的有序序列构成一个句型. 例如:e=e+e=e*e +e=i * e + e= i * i + e = i * i + i 可表示为: 语法树可以表示同一 句型的多种推导,是多种推 导的共性抽象.但未必代表 了同一句型的所有推导: e=e*e=e*e +e =i * e + e = i * i + e = i * i + i e ee+ ee* ii i 语法树 e ee* ee+ ii i 16 定义: 若文法 g 的某个句型存在两个不同的语法树表示,称该文法 是二义文法. 因此,文法 e 是二义文法. 二义性导致了i * i + i 的两种不同运 算结果: (i*i)+i 以及 i*(i+i). 编译中应避免二义文法. e 文法的 二义性是因为没有规定*,+ 运算符的优 先顺序,改进 e 后,得到: et|e+t tf|t*f f(e)| i e为表达式, t 为项, f 为因子 该文法对于句子i * i + i的各种 推导,对应的语法树是唯一的. e et+ tf t * i fi f i 17 3.3 语言和文法 1、文法的优点： n文法给出了精确的、易于理解的语言语法说明。 n某些文法类可以自动产生高效的分析器，分析器的构造过程 可以揭示出语法的二义性和其他难于分析的结构。 n设计的漂亮的文法把结构加于程序设计语言，这些结构对于 把源程序翻译成为正确的目标代码和错误诊断都是很有用的 n语言也是逐渐完善的，需要补充新的结构和完成附加的任务 。如果存在以文法为基础的语言的实现，这些新结构的加入 就更方便。 但是不是所有的语言都可以用上下文无关文法来描述， 例如：我们变量的使用就要求先定义后使用，后面的使用就 的根据前面的类型和属性来决定。即：程序语言也有一定的 语言环境。因此我们强调语法分析器的输出结果。 本章介绍语法分析，是分析语法结构，使用文法；而前 一节词法分析，是分析我们的词法规则，使用正规式；他们 有什么区别、联系、相似之处。 18 2、正规式和上下文无关文法的比较 正规式所描述的每一种结构都可以用上下文无关文法来描述。 例如：正规式(a|b)*abb和上下文无关文法 a0 aa0|ba0|aa1 a1 ba2 a2 ba3 a3 描述同样的语言。 既然上下文无关文法可以跟正规式等价，那么，我们为什么 不在词法分析阶段不介绍正规式，而仅仅介绍上下文无关文法 ？ （1）语言的词法规则非常简单，不必要功能更强大的上下文 无关文法来描述它。 （2）对于记号，正规式比上下文无关文法提供了更见解和易 于理解的符号表式。 （3）从正规式可以自动地构造出比从其他文法更有效的词法 分析器。 （4）把语言的语法结构分成词法和非词法两部分，为编译器 前段的模块化分提供了方便的途径。 19 3. 文法的表式及产生的语言 例如 文法：s(s)s| 推导我们的文法产生式，每一次推导得到的终结符为（ ）或则 ，（）成对出现，而是空串，所以此文法描述的 语言是所有的配对括号组合。 例如 文法：s if expr then stml a a else b| b s|stml stml s| stml | 推导文法产生式，可以得到我们的if语句的语法结构， 包括if的嵌套结构，描述所有的if语句。 例如 文法：s while expr do stml stml stml | 推导文法产生式，得到该文法描述的是我们所有的 while循环语句。 20 例如 设expr和term为非终结符，用以表式不同的优先级，终 结符为id、括号、运算符等，facter为产生表达式的基本单位 。则： 文法一 facter id|(expr) term term*facter|term/facter|facter expr expr+term|expr-term|term 这个表达式文法是无二义性的，句子id+id+id和id+id*id的分 析树如下： expr expr expr term term term facter facter facter id id id + + expr exprterm termterm facter facter facter id idid + * 21 文法二： facter id|(expr) term term+facter|term-facter|facter expr expr*term|expr/term|term 对于文法二，就具有二义性，优先级于我们的语法结构不 能对应，我们再分析id+id*id，得到语法树： term facterterm term facterfacter id id id + * facter expr term expr * expr term facter id term term facter facter id id + 22 4. 消除二义性 从上面例题可以看出，消除文法的二义性，可以重写文 法的产生式，来使我们的算符优先级、算符结合性与我们的 语法树相对应。 例如 文法：stml if expr then stml | if expr then stml else stml | other 这里other代表任何语句，按照这个文法，复合的 条件语句：if e1 then s1 else if e2 then s2 else s3 stml stml ifstmlstml exprelsethen e1s1 ifstml exprelsethen e2s2s3 23 stml if exprthen e1 stml stml ifstml exprelsethen e2s1s2 stml stml ifstml exprelsethen e1s2 if exprthen stml s1 e2 每个else和最 近的还没有配对 的then配对 但是以上是二义文法，因为串if e1 then if e2 then s1 else s2有两棵语法树 24 可以使用下面的文法消除二义性，思想是每个then和else 之间的语句必须是配对的，配对是不包括不配对语句的“if then-else”结构的，文法： stml matched_stml|unmatched_stml matched_stml if expr then matched_stml else unmatched_stml|other unmatched_stml if expr then stml| if expr then matched_stml else unmatched_stml 分析以上文法，对于复合的条件语句：if e1 then s1 else if e2 then s2 else s3 表示同样的意义，但对于if e1 then s1 else if e2 then s2 却限定了只有一种分析。 25 5. 消除左递归 文法是左递归的，如果它有非终结符a，对于串a，存在 着推导a aa，至上而下的分析方法不能处理左递归文法 ，因此需要消除二义性，左递归的产生式a aa|，可以用 非左递归的产生式： a a a aa| 来代替，他们没有改变从a推导出的串集。 n例如：考虑下面的算术表达是文法： e e+t|t t t*f|f f (e)|id 消除e和t的直接左递归（形式为a aa 的产生式），可 以得到： + 26 e te e +te| t ft t *ft| f (e)|id 不管有多少a的产生是，我们都可以用下面的技术消除直 接左递归。首先把a的产生式组在一起： a aa1|aa2|aam| 1| 2| n 其中i都不以a开头，ai都非空，由产生式： a 1a| 2a| na a a1a | a2a |ama| 代替。 以上变换可以删除左递归，但不能消除两步或多步推导 形成的左递归。 n例如 考虑文法： s aa|b a ac|sd| 27 非终结符s式左递归的，因为s aa sda，但它不是直 接左递归。用s产生式替换a sd中的s，得到下面的文法： s aa|b a ac|aad| bd | 删除其中的直接左递归，产生如下的文法： s aa|b a bda |a a ca| ada | 例如：是消除下列文法的直接左递归： g1s: s sa|ab|b|c a bc|a b sb|b g2s: s a|(t) t t.s|s 28 n解答：采用引进新的非终结符的方法，将g1s改为： s abs|bs|cs s as| a bc|a b sb|b 采用扩充的bnf范式描述的方法，可以得到g1s的无 直接递归文法如下： s aba|ba|ca a bc|a b sb|b 29 n采用引进新的非终结符的方法，将g2s改为： s a|(t) t st t .st| n采用扩充的bnf范式描述的方法，可以得到g2s的无直接递 归文法如下： s a|(t) t s.s n例如 已知文法ga: a ab|b b bc|c c d|d d (a)|i 其中“ ”表式“非”运算，试构造该文法的等价的无左递归文法 ： 30 解答：这题实际上是要消除文法的左递归。既可用扩充的bnf范 式，也可用引进新的非终结符号的方法。 n采用扩充的bnf范式描述的方法，可得无左递归文法如下： ga: a b b b c c c d|d d (a)|i 例如 消除下列文法的左递归。 s sap|sf|p p qbp|q q csd|e 解答：该文法的左递归为直接左递归。 31 n采用引进新的非终结符号的方法，将文法改为： s ps s aps|fs| p qbp|q q csd|e n采用扩充的bnf范式描述的方法，可得无直接左递归文法如 下： s pf|pap p qbp|q q csd|e 32 6. 提左因子 提左因子也是一种文法变换，它用于产生适合预测分析 的文法。当我们不清楚应该用两个选择的哪一个来替换非终 结符a时，可以重写a产生式来推迟这种决定，直到看见足够 多的输入，能正确决定所需选择为止。 例如，有两个产生式 stml if expr then stml else stml|if expr then expr 看见输入记号if的时候，不能马上决定用哪个产生式来扩 展stml，一般地，如果a a1| a2是a的两个产生式，输入 串是由从a推导出的非空串开始的，我们不知道是用a1扩展a 还是用a2去扩展它。然而，可以通过先扩展a到aa来推迟这 个决定然后，看完了从a推出的输入后，再扩展a到1或2 ，这就是提左因子，原来的产生式成为： a aa a 1|2 33 例如：下面的文法是从悬空else问题中抽象出来的： s iets|ietses|a e b 这里的i，t和e分别代表if，then和else，e和s是表达式 和语句提左因子后语法成为： s ietss|a s es| e b 这样，如果输入是i，扩展s到ietss，等到iets都看见后， 再决定扩展s到es还是 当然，由于文法是二义的，对于输 入e，为s取哪个选择是不清楚的以后讨论解决这个困难的 办法 34 例如：抽象语言：l1=wcw |w属于（a|b）*. n l1的前后是相同的字符串w，即：a和b组成的字符串， 中间由c隔开，例如：aabcaab，这个例子可以很好地说明程 序中标识符的申明应先于它的引用。 7.非上下文无关文法的语言结构 n例如：语言l2= 分析得a和c的个数相同，b和d的个数相同，类似于前面 的例子，他也可以代表我们程序中的过程申明时的形式参数 的个数应该与过程调用时的实际参数的个数相等。 我们前面说过，程序设计语言都是上下文无关的，对吗 ？我们程序设计语言的文法也不全是上下文无关的，那么类 是于l1、l2的文法都不是上下文无关的吗？先看下面的例子 。 35 n例如：l1=wcwr|w （a|b）*是上下文无关的，其中 wr代表逆序的w，他可由下面的文法产生： sasa|bsb|c n例如：语言l2= ，也是 上下文无关的，文法是： s asd|aad a bac|bc n例如：语言l3= ，也是上下文无关的 ，文法是： s asb|ab 思考：语言l3= ，有限自动机能不 能接受语言l3 36 8 乔姆斯基文法分类 定义:若g =(vt,vn,s,p)的每一个产生式型如: , (vt vn) * , 且 至少含有一个非终结符, 称 g 为 0 型文法; , (vt vn) * , 至少含有一个非终结符, 且满足 | , 称 g 为 1 型文法; a a vn , (vt vn) * , 称 g 为 2 型文法(上下文无关文法); a b 或a , a,b vn , vt * , 称 g 为 3 型文法(正则文法). 37 3.4 算符优先分析法 算符优先分析法是一种简单实用的自下而上分析方法,本节 将详细介绍该方法,包括 介绍 什么是算符优先文法,优先关系表 构造,可归约串的刻画与寻找方法,算符优先分析算法等内容. 1 算符优先文法 定义1: 若一个文法 g 的任何产生式右部,都不含两个相继出现的 非终结符, 则称 g 为算符文法. 38 定义2: 设 g 是一个算符文法,任何相继出现的终结符对之间存在 如下三种归约优先顺序: 1) a b 当且仅当 g 中含有型如 p ab 或 p aqb的产生式; 2) a b 当且仅当 g 中含有型如 p ar, 且 r b 或 r qb ; 3) a b 当且仅当 g 中含有型如 p rb, 且 r a 或 r aq. 优先关系可以用矩阵表示,称为优先关系表. + = + = + = + 39 定义3: 若文法 g 的任何相继终结符对至多只满足以上关系之一, 称该文法为算符优先文法. 2 优先关系表的构造 给定一个算符优先文法,求各终结符对间的优先关系. 定义: firstvt(p)=a | p a, 或 p qa lastvt(p)=a | p a,或 p aq = + = + = + = + 对每个非终结符求出这两个集合后,可按如下规则求出各终 结符对之间的优先关系: 1) 对每一条产生式,若存在型如 pab或 paqb ,则令 a b; 该关系表示 a b 同时归约. 40 2) 对每一条产生式,若存在型如 paq的产生式,对 所有 b firstvt(q) , 令 a b; 该关系表示 b 应先于 a 归约为 q. 示例: 设文法 g 为: ee+t|t tt*f|f f (e)|i 根据定义1,这是一个算符文法. 41 对每个非终结符,求出: firstvt(f)= ( , i lastvt(f)= ) , i firstvt(t)= * , ( , i lastvt(t)= * , ) , i firstvt(e)= + , * , ( , i lastvt(e)= + , * , ) , i 优先关系表如下: +*()i + i 根据定义3,该 文法是算符优先文 法 42 3 可归约串 在算符优先分析法中,用最左素短语描述可归约串. 定义:素短语是一个短语,它至少含有一个终结符,且除自身之外不 含更小的素短语. 一个句型的最左素短语即为可归约串. 例如:设文法 g 为: ee+t|t 句型 为: f*f+i tt*f|f f (e)|i 根据短语的定义,f*f+i 有如下四个短语: 其中,素短语有: f*f, i 两个, 最左素短语为: f*f e e e f*f+i e e+i e f*f e f*f+t t i e t*f+i t f = * = * = * = * = + = + = + = + 43 4 寻找最左素短语 根据定义,算符优先文法的句型必为如下形式: n1a1n2a2nmamnm+1 其中 ai vt ni vn ni可有可无. 定理: 一个算符优先文法 g 的任何句型的最左素短语,为满足 如下条件的最左子串: 最左素短语 = niainjajnj+1 且满足 ai -1 ai ai ai +1 aj aj aj+1 45 示例: 设文法 g 为: ee+t|t tt*f|f f (e)|i +*()i + i 优先关系表如右, 分析表达式 i+i*i 是 否为合法的表达式 i+i*i# # +i*i# #i +i*i# #n i*i# #n+ 移入 归约 移入 移入 46 *i# # n+i *i# #n+n i# # n+n* 归约 移入 移入 # # n+n* i 归约 # # n+n* n 归约 # # n+n 归约 # # n 为合法句子 算符优先分析过程中,产生式以及非终结符名已不再起作用, 只有优先关系表决定了分析过程. 47 3.5 递归下降分析法 递归下降分析法是一种自顶向下分析方法,从文法开始符号 自左向右进行推导,若能推出一个与输入串相等的句子,说明输入 串是合法的句子. 1 递归下降分析法存在的问题 递归下降分析法本质上是一种最左推导,根据输入串选择相应 产生式进行推导. 48 例如: 设文法为 g : sa | ict输入串为: icta ttses | ts 推导如下: s icta 根据输入字 i ict icta 根据输入字 t ictses icta 根据输入字 a ictaes icta 不匹配 t 有两个候选产生式,如果选择第二个候选推导,则 s icta 根据输入字 i ict icta 根据输入字 t icts icta 根据输入字 a icta icta 匹配 = = = = = = 49 从上面分析可知: 若允许 p a |a 的产生式,则输入字 a 面临多个产 生式可选择用于推导,这种情况下,推导只能试探性的进行,一旦后 续推导中不能匹配,再回过头( 回溯 ) 选择下一个产生式候选进行 推导. 这种方式效率低, 因此,应消除回溯. 另外,递归下降分析中,不允许有如下的左递归推导: p p 这种左递归推导,会导致不匹配任何输入字而无止境的 推导(死循环). 因此,递归下降分析法中存在两个主要问题: 1) 文法的左递归 2) 文法的回溯 = + 50 2 无回溯递归下降分析 对文法的要求 要做到无回溯分析, 实际上就是要求文法无回溯及左递归. 定义: 设 a 1| 2 | m , a vn , i (vt vn) * ; 令 first(i ) = a | i a, a vt 若 i ,则 first(i ) (i 可能推出的所有首终结符的集合) 定义: 设 s为 g的开始符, 令 follow(a)=a | s aa, a vt 若 s .a ,则 # follow(a) ( 从 s 开始的推导中,所有可能紧跟在 a 之后的终结符) = * = * = + = + 51 定义: 设 a 1| 2 | m , 且有 1) first(i ) first(j )= ,i j ; 2) 若 first(i ),则对任意 i ( 1im) 满足 first(i ) follow(a) = ; 若文法 g 满足上面条件,则 g 就是无回溯文法,也称为 ll(1) 文法. 换句话说,只要根据输入的一个字,就能唯一地确定产生式 候选,进行最左推导. 一个文法是ll(1) 文法,且不含左递归,就可以进行无回溯 的递归下降分析. 52 3 消除文法的左递归 1) 直接左递归的消除 若 文法 g 中含有型如 pp | 的产生式, 称 g 含有直接 左递归. 可将直接左递归改写为等价的不含左递归的产生式: p p p p | 这两组产生式都可推导出: *; 一般而言,若产生式为: pp 1 | p 2 | |p m| 1 | 2 |.| n 则可改写为如下等价的产生式: p 1 p | 2 p |.| n p p 1 p | 2 p | | m p | 53 2) 间接左递归的消除 若 文法 g 中含有型如 p p 的推导, 称 g 含有间接 左递归. 间接左递归可通过如下算法消除: a) 令 vn =p1 ,p2 ,., pn b) for i:=1 to n do for j:=1 to i-1 do 把型如pipj 的规则改写为: pi 1 | 2 |.| k 其中 pj 1 | 2 |.| k 消除关于pj的直接左递归 c) 消除无用非终结符. = + 54 4 消除回溯 造成回溯的原因是公共左因子. 1) 直接左因子的消除 若 文法 g 中含有型如 pa1| a2| ak 的产生式, 称 g 含有直接左因子. 可将直接左因子改写为等价的不含左因子的产生式: p a p p 1| 2| k ; 2) 间接左因子的消除 若 文法 g 中含有型如 p a1| a2| ak 的推导, 称 g 含有间接左因子. 消除方法同上. = + 55 5 递归下降分析程序的实现 为每一个非终结符编写一个子程序. 设文法 g 为: ee+t|t tt*f|f 消除左递归后 f (e)|i 左递归的文法 et e e +t e| tf t t*ft | f (e)|i ll(1) 且无左递归 56 procedure e; t;e ; procedure e; if sym=+ then advance; t;e ; procedure t; f;t ; procedure t; if sym=* then advance; f;t ; procedure f; if sym=i then advance else if sym=( then advance; e; if sym=) then advance else error else error ; et e e +t e| tf t t*ft | f (e)|i 57 6. 非递归的预测分析器 n 显式地维持一个状态栈；同时根据产生式推导出各种非终 结符号的可能推导（分析表）；再从输入字符串入手，进行 分析，查阅分析表，选择产生式。 预测分析程序 输入 a + b 栈 x y z 分 析 表 输出 例如 ： 58 n分析器的工作过程：程序根据栈顶当前的符号x和输入串中的 输入符号a决定分析器的动作，有4种可能： （1）如果x=a=，分析器宣告分析成功完成而停机。 （2）如果x=a，分析器弹出栈顶符号x，推进输入指针 ，指向下一个符号。 （3）如果x式终结符而不是a，则报告出错，调用错误恢复 例程。 （4）如果x是非终结符，程序访问分析表m