《编译原理(第2版)第五章》由会员分享，可在线阅读，更多相关《编译原理(第2版)第五章（70页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 LL(1)文法及其分析程序,5.1 自上而下的语法分析 5.2 预测分析程序 递归下降子程序 表驱动的预测分析程序 5.3 LL(1)分析程序的生成 LL(1)文法 FIRST和FOLLOW集 定义和计算 5.4 非LL(1)文法的改造,2,5.1自上而下的语法分析,1语法分析概念 2自上而下的语法分析的一般过程 3自上而下的语法分析面临的问题,3,（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。,4,语法树推导的几何表示,句型aabbaa的可能推导序列和语法树,例: GS: SaAS ASbA ASS Sa Aba,S
2、 a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,5,语法分析,在语言的编译实现中，把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,6,分析算法分类,分析算法可分为： 自上而下分析法： 从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。
3、 自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,7,两种方法反映了语法树的两种构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串 自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,8,自上而下分析,对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的过程。,9,自上而下的语法分析的一般过程,例：文法G： S cAd A ab A a 识别输入串w
4、=cabd是否为该文法的句子,S S S c A d c A d a b 推导过程：S cAd cAd cabd,10,自上而下的语法分析的一般过程 (1)S cAd (2) A ab (3) A a 识别输入串w=cad是否为,该文法的句子 1.S cAd 2.后选择(2)扩展A，得到推导S cAd cabd 这时 w的第二个符号可以与叶子结点a得以匹配，但第三个符号d却不能与下一叶子结点b匹配 怎么办？-查看A有无另一个选择，有！回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）构造推导S cAd cad,识别输入串w=caa的过程： 1.S cAd 2.选择(2)
5、扩展A，得到推导S cAd cabd 3.回溯回到推导S cAd 4.选择(3)扩展A，得到推导S cAd cad 5. A没有选择了！回溯到推导S cAd 6.再回溯S有无另一个选择？没有！ 宣告分析失败。 （请思考 若有 (4) S cB (5) B aa 会怎样? ）,11,自上而下的语法分析面临的问题-实现考虑,回朔 文法的左递归性 SSa,12,自上而下分析对文法的要求,例文法G0S: (1) SSa (2) Sb 分析baa是不是文法的句子 按照自上而下的分析思想 选用产生式(1)来推导SSa 语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa 此时语法树末端结点
6、最左符号仍为非终结符，所以选用（1）继续推导SSaSaa Saaa 问题试图用S匹配输入串时，出现：在没有读入任何输入符 号的情况下，又得重新要求S去进行新的匹配 原因文法含有左递归，,13,自上而下的语法分析左递归规则,GS: SSa Sb L=ban | n1 W=baaa S b S S a S a,14,左递归 关于非终结符P的规则,直接左递归 若 P P | 、 V*且、不以P开头 一般 左递归 若 P =* P SAa ASb ,15,自上而下分析的进一步讨论,自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明
7、输入串是给定文法的句子，否则表明该输入不是给定文法的句子。 自上而下分析对文法的要求文法不能含有左递归规则。 自上而下分析又可分为确定的和不确定的两种 不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法 确定的分析方法需对文法有一定的限制,16,消除文法中左递归规则,消除直接左递归 形如：P P | 非， ，不以P打头 改写为：P Q Q Q| 其中Q为新增加的非终结符,17,消除文法中左递归规则,例:E E+T|T T T*F|F F (E)| a G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F
8、(E) (8) F a,18,消除一般左递归要求文法: 1.无回路(A(=+(A) 2.无空产生式,（1） .以某种顺序将文法非终结符排列A1 ,A2 An （2） for i:=1 to n do begin for j:=1 to i-1 do 用Ai1| 2r| k r替代 形如Ai Ajr的规则,其中 Aj 1| 2| k是关于Aj的全部产生式; 消除Ai规则的直接左递归; end; （3）化简由2得到的文法,19,回溯的原因,例GS: SxAy Aaba 若当前输入串为xay，首先构造的推导SxAy 匹配 进一步推导对A可选择Aab替换，得SxAy xaby xay xaby 匹配
9、xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式Aa进行试探， SxAy xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。 由于相同左部的产生式的右部开始符号相同而引起回溯。,20,在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？-什么信息用于Parser做正确选择?(输入串,文法特点),21,可预测的试探推导过程,例 文法GS: S pA |qB A cAd|a B d B |c 识别输入串w= pcc
10、add是否是G1S的句子 可预测的试探推导过程： S pA pcAd pccAddpccadd 试探成功。,22,PL/0语言的EBNF,程序=分程序. 分程序=常量说明部分变量说明部 分过程说明部分语句 常量说明部分=CONST常量定义部分，常量 定义； 变量说明部分=VAR标识符，标识符； 过程说明部分= PROCEDURE 标识符分程序 ；过程说明部分； 语句= 标识符：=表达式 |IF 条件 then语句|CALL|READ|BEGIN 语句；语句 END|WHILE|,23,PL/0分析语句的子程序片断,begin(*statement*) if sym=ident then (*p
11、arsing ass.st.*) begin getsym; if sym=becomes then getsym else error(13); expression(fsys); end else if sym=readsym then (* parsing read st.*),begin getsym; if symlparen then error(34) else repeat getsym; if sym ident then error(35) else getsym until symcomma; if symrparen then error(33); end,24,例：递
12、归子程序实现 表达式的语法分析,表达式的EBNF 表达式=+|-项（+|-）项 项=因子（*|/）因子 因子=ident|number|（表达式）,25,表达式=+|-项（+|-）项,int expression(bool* fsys, int* ptx, int lev) if(sym=plus | sym=minus) /* 开头的正负号*/ getsym; term(nxtlev, ptx, lev); /* 处理项 */ else /* 此时表达式被看作项的加减 */ term(nxtlev, ptx, lev); /* 处理项 */ while (sym=plus | sym=min
13、us) getsym; term(nxtlev, ptx, lev); /* 处理项 */ ,26,项=因子（*|/）因子,int term(bool* fsys, int* ptx, int lev) factor (nxtlev, ptx, lev);/* 处理因子 */ while(sym=times | sym=slash) getsym; factor (nxtlev, ptx, lev); ,27,因子=标识符|无符号整数|（表达式）,int factor(bool* fsys, int* ptx, int lev) if(sym = ident) /* 因子为常量或变量 */ g
14、etsym else if(sym = number) /* 因子为数 */ getsym else if (sym = lparen) /* 因子为表达式 */ expression(nxtlev, ptx, lev); if (sym = rparen) getsym; else error(22); /* 缺少右括号 */ else error( ) ,28,5.2 预测分析程序（Predictive parser）无回溯的自顶向下分析程序,特征根据下一个(几个）输入符号为当前要处理 的非终结符选择产生式 要求文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归（下降）子程序 2 表驱动分析程序,29,例：递归下降子程序ParseFunction(),
