《编译第四章08本》由会员分享，可在线阅读，更多相关《编译第四章08本（70页珍藏版）》请在金锄头文库上搜索。
1、第四章 自上而下语法分析1、语法分析的地位编译程序的核心部分2、语法分析的任务识别由词法分析得出的单词序列是否是给定 文法的句子3、语法分析的理论基础上下文无关文法和下推自动机4.1 语法分析器的功能4.1 语法分析器的功能语法分析器在编译程序中的地位 语法分析的方式 1）自上而下语法分析v反复使用不同产生式进行推导以谋求与输入符号 串相匹配 2）自下而上语法分析v对输入符号串寻找不同产生式进行归约直到文法 开始符号 注：这里所说的输入符号串指词法分析所识别的单 词4.1 语法分析器的功能4.2 下推自动机模型输入带有限状态控制器输出带下推栈4.2 下推自动机模型注：1） PDA和FA的模型相
2、比，多了一个下推栈2） PDA的动作由三个因素来决定：当前状态、读头所 读向符号、下推栈栈顶符号3) 一个输入串能被PDA所接受，仅当输入串读完，下 推栈变空；或输入串读完，控制器到达某些终态。4）正规文法和有限自动机仅适合于描述和识别高级语 言的各类单词，语句可用上下文无关文法来描述，而下推 自动机又恰好能识别上下文无关文法所能描述的语言，因 此上下文无关文法及其对应的下推自动机就成为编译技术 中语法分析的理论基础1、形式定义：PDA是一个七元组：M=(Q,H,q0,Z0,F)-H :下推栈内字母表-Z0:下推栈的栈始符号，是H中的元素-:Q(e)H到QH*的有限子集映射例： (q,a,Z)
3、=(q1,r1),(q2,r2)(qn,rn),其意义是：设控制器当前状态为q，下推栈顶符号为Z，输入符号为a（可为空）， 则状态转换到序偶集(q1,r1),(q2,r2)(qn,rn)（qi为下一状态，ri为 代替Z的栈顶符号串）-FQ是控制器的终态集4.2 下推自动机模型注：1）由此定义的PDA肯定是不确定的PDA，这给语法分析 会带来不确定性，在构造PDA M的算法的时候，要对PDA做 一些限制2）PDA采用“ ”来表示PDA做了一步动作3）输入串能为PDA所接受，仅当输入串读完，下推栈为 空；或者输入串读完，控制器到达某些终态4）有时，下推自动机还配置输出带，以记录推导或归 约过程所用
4、的产生式编号5）对于形如A w的产生式，有(q,e,A)=(q,w),称为推导(q,a,a)=(q,e)，称为匹配，其中a例：试给出接受语言L=ancbn|n=0的下推自动机解：1、生成L语言相应文法的产生式为S aSb|c2、生成相应的PDA M=(Q, ,H,q0,Z0,F)PDA M=(q, a,b,c,S,a,b,c,q,S,q)其中为：1) (q,a,a)=(q,e)2) (q,b,b)=(q,e)3) (q,c,c)=(q,e)4) (q,e,S)=(q,aSb),(q,c)aacbb#有限状态控制器输出带S#其分析过程：（q,aacbb,S) a(q,aacbb,aSb) (q,
5、acbb,Sb)a (q,acbb,aSbb) (q,cbb,Sbb) b(q,cbb,cbb)(q,bb,bb) (q,b,b) (q,e,e)一、自上而下语法分析定义v从文法的开始符号开始，反复使用不同产生式进 行推导以谋求与输入符号串相匹配。v注：此处的输入符号串是指词法分析结果的一串 二元式二、一般方法试探法：带回溯的自上而下分析法4.3 自上而下分析面临的一般问题1、基本构成设下推栈的初始状态包含两个符号：#S，其 中#为栈底，S为文法开始符号。整个分 析过程在语法分析程序控制下进行，在语法分析 中用到的文法产生式的表，称为语法表。a+b#语法分析程序语法表输出带S#4.3 自上而下
6、分析面临的一般问题2、算法 （1）若栈顶符号X是非终结符，查询语法表，找出一个以X作 为左部的产生式，X出栈，并将其右部反序入栈，且输出带 记下产生式编号推导 （2）若栈顶符号x是终结符，但读头下的符号也是x，则x出 栈，读头指向下一个符号匹配 （3）若栈顶符号x是终结符，但读头下的符号不是x，则匹配 失败，这说明可能前面推导时选错了候选式，退回到上次 推导现场（包括栈顶符号，读头的指针和输出带上的信息 回溯 （4）回溯后选取另一候选式进行推导，若没有候选式可选， 则进一步回溯。若回溯到开始符号又已无候选式可选，则 识别失败 （5）若栈内仅剩下“#”，且读头也指向“#”，则识别成功4.3 自上
7、而下分析面临的一般问题S#例：文法产生式如下，请分析符号串x*y#的过程1）S xAy 2) A * 3) A *x*y#语法分析程序语法表输出带4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1输出带xAy#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1输出带Ay#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S
8、xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1，2输出带*y#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1，2输出带*y#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1输出带Ay#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临
9、的一般问题x * y #语法分析程序语法表 1，3输出带*y#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1，3输出带y#v例：文法产生式如下，请分析符号串x*y#的过 程v 1）S xAy 2) A * 3) A *4.3 自上而下分析面临的一般问题x * y #语法分析程序语法表 1，3输出带#3、带回溯的自上而下分析法的缺陷1)如果文法存在左递归,语法分析会无限循环下去2)若产生式存在多个候选式,选择哪个推导?3)回溯会引起时间和空间的大量消耗4)如果被识别的语句是错的
10、，算法无法指出错误的确切位置4.3 自上而下分析面临的一般问题1、消除左递归1) 什么是左递归?左递归：文法存在产生式 P Pa直接左递归： P Pa间接左递归：P Aa ,A Pb2）消除左递归消除直接左递归消除间接左递归+4.4 LL(1)分析法2、消除直接左递归设有文法G=(VN,VT,P,S),其中产生式P为P Pa|b,aV+,bV+且b不以P开头将它转换为等价式P bP, P aP|e一般地：将 P Pa1|Pa2|Pam|b1|b2|bn转换为：P b1P|b2P|.|bnPP a1P|a2P|amP|e4.4 LL(1)分析法例1：文法G: (1) E E+T|T(2) T T
11、*F|F(3) F (E)|i消除左递归转化为G：(1)E TE E +TE|e(2)T FT T *FT|e(3)F (E) | i例2：文法G：P PaPb| BaP转化为：P BaP P aPbP|e注：只有最左边的P参加变换3、消除左递归算法1) 把文法G的所有非终结符按任意顺序排列 P1P2Pn,然后按此顺序执行步骤2 2) For (i=1,i=n,i+)for (k=1,k=i-1,k+)把形如Pi Pkg的规则改写为Pi 1g| 2g|ng,其中Pk 1|2|n消除Pi规则的直接左递归；3) 删去从文法开始符号不可达的非终结符产生式3、消除左递归算法说明如下：1) 此算法适用于
12、消除不含形如P P的产生式，也不含以e 为右部的产生式的文法。2) 这第二步所做的工作是：a)若产生式出现直接左递归则用消除直接左递归的方法消除 掉。b)若产生式右部最左符号是非终结符且序号大于左部的非终 结符，则不处理。c)若序号小于左部的非终结符，则将这序号小的非终结符用 其右部串来取代，然后消除新的直接左递归。例：对下面的文法消除左递归（1） S Qc|c (2) Q Rb|b (3) R Sa|a解：1）对非终结符重新排序：R,Q,S2）对R：S的序号大于R的序号，不处理对Q：R的序号1小于Q的序号2，所以改写Q Rb|b ,将R Sa|a的右部取代R，得到：Q Sab|ab|b,记为
13、（2）式：此时S的序号大于Q的序号，不再处 理对S：Q的序号2小于S的序号3，所以改写S Qc|c,将Q Sab|ab|b的右部取代Q,得到S Sabc|abc|bc|c;出现直接左递归，变换为：S (abc|bc|c)S S abcS|e由于 R Sa|a和Q Sab|ab|b中的R,Q对开始符号S来说 都是不可达非终结符，所以删除它们.故最后消除左递归后文法为：S (abc|bc|c)SS abcS|e注：1) 若非终结符排列顺序不同，改写后的文法也 不同，但它们是等价的。2) 开始符号不能改变左递归左递归消除回溯 1)产生回溯的原因进行推导时，若产生式存在多个候选式，选择 哪个候选式进行
14、推导存在不确定性。 2)消除回溯的基本原则对文法的任何非终结符，若能根据当前读头下 的符号，准确的选择一个候选式进行推导，那么 回溯可以消除。 注：之所以会产生回溯是因为在推导匹配过程中存 在虚假匹配。4.4 LL(1)分析法消除回溯的方法：-预测与提左因子 1.预测根据读头下符号选择候选式，使其第一个符号 与读头下符号相同，或该候选式可推导出的第一 符号与读头下符号相同，这相当于向前看了一个 符号，称为预测。注：使用了预测之后,选择候选式不再是盲目的了，所以也就无需回溯4.4 LL(1)分析法消除回溯-求候选式的终结首符集令G是一个不含左递归的文法，对G的所有非终 结符的各候选式a可求出它的终结首符First(a) First(a)=a|a a,aVT特例：若a e，那么eFirst(a)即：First(a）集合包括了a的所有可能推导的开 头终结符或可能的e* *4.4 LL(1)分析法1、求串a的终结首符集First(a) a) 定义 假定a是文法G的一个符号串，aV*，则First(a)=a|a a.
