Ch4语法分析自上而下分析.ppt

编译原理,第四章 语法分析- 自上而下分析,程 序 设 计 语 言,2,本章在编译程序中的地位,表 格 管 理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出 错 处 理,3,回顾：语法分析,任务：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位，如“短语”、“句子”、 “子句”、“程序段”等，为语法正确的输入构造语法树(或分析树)。 语法分析依据的是语言的语法规则，即描述程序结构的规则，通过语法分析确定整个输入串是否构成一个语法上正确的程序。 语法规则通常用上下文无关文法描述。 语法分析方法有自上而下和自下而上两类。 本章和下一章将介绍编译程序构造中的一些典型的语法分析方法。,2019/7/11,Ch4.语法分析-自上而下分析,4,典型的语法分析方法,自上而下语法分析方法 第四章介绍 递归子程序法 预测分析法，即LL(1)法 自下而上语法分析方法 第五章介绍 算符优先分析法 规范归约法 LR方法：LR(0)、SLR(1)、LR(1)、LALR(1),5,CH.4 语法分析-自上而下分析,掌握：消除文法左递归，消除回溯，计算FIRST集、FOLLOW集，LL(1)分析条件， LL(1)文法的概念，预测分析表的构造。 了解理解：自上而下分析方法的基本思想, 自上而下分析的过程。 教学内容： 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序的构造 4.5 预测分析程序 *4.6 LL(1)分析中的错误处理,6,4.1 语法分析器的功能,语法分析是编译程序的核心部分。 它的任务是在词法分析识别出单词符号串的基础上，分析并判定一串单词符号的语法结构是否符合语法规则, 是否文法的一个句子。 分析判定的方法： 建立输入串n的从文法开始符号S出发的推导 S1n 即建立以S为根的与输入串n相匹配的语法树 图4.1表明语法分析器在编译程序中的地位,2019/7/11,Ch4.语法分析-自上而下分析,7,4.2 自上而下分析面临的问题,本节主要是通过例子 1.说明自上而下分析方法的思想和步骤 2.认识自上而下分析时所遇到的主要困难 自上而下分析的主要困难是: 文法的左递归性，使分析陷入无限循环 回溯的不确定性，要求将已经完成工作推倒重来 为解决这些问题，考虑要消除文法左递归和避免回溯。,8,自上而下分析方法的思想,从文法的开始符号出发，向下推导，试图推出句子，匹配输入符号串，寻找输入串的最左推导，并按与最左推导相对应的顺序，自上而下从左到右地建立输入串的语法分析树。 推导过程中，试图根据当前的输入符号判断使用非终结符的哪个候选式去替换。 分析过程是一种穷尽一切可能的试探过程；是反复使用不同产生式谋求匹配输入串的过程。 用例子说明，P67.例4.1,9,自上而下分析(1),例4.1 文法： SxAy A* A* 输入串 =x*y，分析是否文法的句子？,10,自上而下分析(2),11,自上而下分析(3),12,自上而下分析：说明,注: 自上而下分析过程是带回溯的试探过程 遇非终结符标记的结, 就试图用某个候选式展开, 期望此候选能匹配输入串, 若不能匹配, 则要回溯。 遇终结符号的结，就进行匹配，然后移动输入串指针ip指向下一个符号。 回溯是一项复杂而费时的工作，须废弃已做的许多工作，恢复到前面的某一情况，效率很低。 下面讨论自上而下分析法存在的困难和缺点 左递归、回溯、虚假匹配、当报告分析不成功时难于知道输入串中出错的确切位置，等,13,文法的左递归问题,文法的左递归性 直接左递归：文法存在产生式 P P 间接左递归：存在推导 P + P 文法具有左递归性，采用自上而下方法分析，可能会陷入无限循环，分析不下去。,例如：文法有左递归产生式 AAx 分析中会遇到试图展开A，却又立即遇到A，并将永远循环下去。在没有识别任何输入符号的情况下又得重新要求A去进行新的匹配-消左递归！,14,候选式的确定与回溯问题,自上而下分析是一种反复用可能的候选式去进行试探的过程，不能预知本次试探是否会成功，若不成功则需要回溯。 例如文法： SxAy A*|* 判定句子x*y是否该文法定义的语言的句子。 希望：当要进行关于某个非终结符的推导时，能够根据当前输入符号确定候选式，避免回溯。,15,虚假匹配问题,虚假匹配：当一个非终结符用某一候选式匹配成功时，这种成功可能仅是暂时的、虚假的。 例如：文法 S xAy A *|* 识别输入串 =x*y 是否为该文法的句子 自上而下的语法分析中，若在 SxAy 后选择用 * 替换 A，则 S xAy x*y 。 的第二个符号可以与叶结点*得以匹配，但第三个符号却不能与下一叶结点y匹配。 于是分析失败，意味着不能为串x*y 构造语法树，即 x*y 不是句子。错误的结论。 失败的原因在于错误的选择了A的产生式 - 用最长匹配方法解决。,16,4.3 LL(1) 分析法,下面将集中讨论不带回溯的自上而下分析法 4.3 LL(1)分析法 消除文法左递归 提左因子、避免回溯 LL(1)分析条件、LL(1)文法 4.4 递归下降分析程序构造 实现 LL(1)分析的简单方法 4.5 预测分析程序 实现 LL(1)分析的有效方法,17,4.3.1 左递归的消除,无法对左递归文法进行有效的自上而下分析，因此必须消除文法的左递归。 直接左递归 有产生式 AA 间接左递归 没有产生式 AA , 但有推导 A+A 消除直接左递归的方法：引入新的非终结符号P，将关于P的如下产生式 PP| (非且不以P打头) 替换为 PP P P,2019/7/11,Ch4.语法分析-自上而下分析,18,例4.2 表达式文法直接左递归的消除,E E + TT T T * FF F ( E )i,E T E E + T E| T F T T* F T F ( E )i,消左,问题：可否不用E、T，而用其他非终结符号？,2019/7/11,Ch4.语法分析-自上而下分析,19,文法直接左递归消除：练习,消除下面文法的左递归 ： (1) G(H): H H;M|M M d|aHb,解: 消除左递归后的文法： (1) G(H): H MH H ;MH| M d|aHb,(2) G(A): AaAb1|a BBb|d,(2) G(A): A aAb1|a BdB BbB|,20,消除直接左递归的一般方法,一般而言，假定关于P的全部产生式是： PP1| P2| Pm| 1| 2 | | n 其中, 每个都不等于, 而每个都不以P开头 消除P的直接左递归就是把这些规则改写成： P 1 P| 2 P| n P P 1P| 2P| | mP| 直接左递归和间接左递归的消除方法均在必须掌握之列。P70.有一个消除任何左递归的算法，下面先举例说明消除间接左递归的方法。,21,消除间接左递归,间接左递归的消除: 先将间接左递归变为直接左递归，再按消直接左递归的方法消除。 例1：文法 (1) A Bb 有间接左递归 (2) B Ac (3) B d 先将(1) 代入(2)得：BBbc，于是 B Bbc|d 再消除直接左递归，得到的文法不含左递归: A Bb B dB B bc B | ,22,消除间接左递归：例1,例1：有间接左递归文法： (1) A Bb (2) B Ac (3) B d 也可以先将(2)(3)代入(1)得: A Acb|db 再消直接左递归, 得到不含左递归的文法: A dbA A cb A| B现在是无用符号, 把B及其产生式删除。 说明：代入方法不同，得到的不含左递归的文法可能是不一样的，但它们等价。消左以后，可能会出现无用符号，应把它们去掉。,23,间接左递归的消除：例2,例2：有间接左递归的文法： SAc|c ABb|b BSa|a (1) 将B的定义代入A的产生式得：ASab|ab|b (2) 将A的定义代入S的产生式得: SSabc|abc|bc|c (3) 消除其直接左递归：SabcS|bcS|cS SabcS| (4) 删除“多余的”产生式：ASab|ab|b 和 BSa|a 结果： SabcS|bcS|cS SabcS|,24,消除左递归的算法(P70.),消除左递归要求文法: 1. 无回路(无形如 P + P 的推导)； 2. 无产生式 算法 (1) 以某种顺序将文法非终结符排列 P1 , P2 , Pn (2) For i:=1 to n do begin for j:=1 to i-1 do 把形如 Pi Pj 的规则改写为 Pi 1|2| k 其中, Pj 1| 2| k 是关于Pj的全部产生式; 消除Pi规则的直接左递归; end; (3) 化简由(2)得到的文法, 去掉无用的非终结符号。,25,消左递归算法：例4.3,解：将非终结符排序为 R、Q、S。 对于R不存在直接左递归，把R代入Q的候选式： Q Sab|ab|b 现在Q也不含直接左递归，把Q代入S的候选式： S Sabc|abc|bc|c 经消除S的直接左递归后，得到整个文法： S abcS|bcS|cS S abcS| Q Sab|ab|b R Sa|a 由于关于 Q, R 的规则是多余的, 则可化简得到： S abcS|bcS|cS S abcS|,消除文法 SQc|c Q Rb|b R Sa|a 的左递归。,26,消左递归算法：注意,注意: 非终结符排序不同, 消左递归的结果不同; 不要改变文法的开始符号。 消左还有一个方法 - 扩充的巴科斯范式(P75.)。 例如，例4.3的文法： SQc|c Q Rb|b R Sa|a 如果将非终结符排序为 S 、Q、 R 则得到无左递归的文法： (参见P70.) S Qc | c Q Rb | b R bcaR|caR| aR R bcaR| ,27,4.3.2 消除回溯、提左因子,强调: 实现有效的自上而下分析，要求文法不得含左递归，并且不得回溯。现在左递归已经解决。 接下来讨论: 1. 在不得回溯的情况下进行自上而下分析，对于文法有什么要求。 2. 如何改写文法使满足消除回溯的要求。 需要引入: 符号串的终结首符集 FIRST() 非终结符A的后随终结符集 FOLLOW(A),28,为避免回溯对文法的要求,回溯的产生是由于文法中存在非终结符A有n个候选式： A 1| 2| | n 在自上而下分析中展开A时，穷尽A的一切可能的候选式去谋求与输入串相匹配。 如果能够: 根据当前的输入符号a，能准确地指出其匹配的某个候选式i，而不需要从1开始逐个试探。并且若 i 匹配输入串成功，那么这种匹配决不会是虚假的；若 i 无法完成匹配任务，那么其他候选式也肯定不能完成。i 是A的全权代表， i 的工作成效完全代表了A。,29,为避免回溯引入FIRST()集,回溯的产生是由于文法中存在非终结符A有n个候选式： A 1| 2| | n 在面临当前输入符号a时要能准确指出唯一可使用的候选式i去代表A谋求与输入串相匹配，显然要求各i的终结首符号互不相同。 引入符号串的终结首符集FIRST()，上述要求即： FIRST(i )FIRST(j)= ij，i,j=1,2,n 显然，当输入符号aFIRST(i)时, 可以确定用候选式i去谋求匹配。,30,FIRST()集合及作用,令G是一个不含左递归的文法, 符号串VTVN* 定义的终结首符集为： FIRST()= a| * a 且 aVT 特别是，若 * ，则规定 FIRST()。 FIRST集合的作用: 如果非终结符A 的任何两个不同的候选i和j有： FIRST(i) FIRST(j) = 那么，当要求A匹配输入串时，A 就能根据它所面临的当前输入符号a，准确地指派某个候选前去执行任务, 这个候选就是那个终结首符集合含a 的i。,2019/7/11,Ch4.语法分析-自上而下分析,31,例1：文法: SaA A Sd AbAS FIRST(S)=a,d FIRST(bAS)=b FIRST(A)=,b FIRST()= 例2：文法: SAa A Sd AbaS FIRST(S)=b, a, d FIRST(Aa)=a,b FIRST(A)=,b,计算FIRST集合: 例,2019/7/11,Ch4.语法分析-自上而下分析,32,练习：文法 EE+T | T TT*F | F F(E) | i 计算: FIRST(E)=? FIRST(i)=? FIRST(T*F)=? FIRST(F)=? FIRST(E)=?,计算FIRST集合: 练习,解: FIRST(E)= ( FIRST(i)= i FIRST(T*F)= (, i FIRST(F)= (, i FIRST(E)= (, i ,33,如何把一个文法改造成所有候选式的终结首符集两两不相交呢？ 其办法是提取公共左因子。 例如，假定关于A 的规则是: A 1| 2| |n | 1| 2| |m (其中每个不以开头) 那末，可以引进新的非终结符, 把这些规则改写成： A A| 1| 2| |m A 1 | 2 | | n,改写文法避免回溯: 提左因子,1| 2| |n = (1| 2| | n),34,例1: 有产生式 B bBcA|b 由于FIRST(bBcA) FIRST(b) =b 则需要对B bBcA|b提取公共左因子b 将产生式改写成：B bB B BcA|,提左因子：例,例2: 有文法 S cAd|b A ab|a 由于FIRST(ab) FIRST(a) =a 则需要对A ab|a提取公共左因子a 将文法改写成：S cAd|b A aA A b|,2019/7/11,Ch4.语法分析-自上而下分析,35,练习1: 有文法 S iBtS|iBtSeS|a B b 提取公共左因子改写文法。,提左因子：练习1,解: 提取公共左因子，将文法改写为 S iBtSS|a S |eS B b,2019/7/11,Ch4.语法分析-自上而下分析,36,练习2: 有文法 A aAB1|a B Bb|d 改写文法, 使其不含左递归, 能避免回溯。,改写文法：练习2,解: 将文法改写为: A aA A AB1| B dB B bB|,37,4.3.3 LL(1)分析条件,设文法满足: 不含左递归; 若有 A1|2| |n, 则 FIRST(i)FIRST(j)= ij 是否就能进行有效的自上而下分析呢? 例4.4 P69.(4.2)的算术表达式文法 E TE E +TE| T FT T *FT| F (E) | i 该文法不含左递归, 候选式的FIRST集合两两不交 考察识别输入串 i+i # (#是句末符, #不属于VT),38,LL(1)分析条件的提出(1),E只有一个候选TE, E替换为 TE T只有一个候选 FT, T替换为 FT,F有两个候选, iFIRST(i) F替换为 i, i 得到匹配, 移动 ip指+ T有两个候选, +不属于任一候选的 FIRST集; 但有 T ,认为 T 自动匹配 注意：+号并不读进！,E TE E +TE| T FT T *FT| F (E)|i,39,LL(1)分析条件的提出(2),E有两个候选, +FIRST(+TE), 故E替换为 +TE 。+得到匹配, 移动 ip 指下一个 i 。T只有一个候选, T展开为 FT。F展开为 i。i 得到匹配， 移动 ip 指 #。#不属于T任一候选的 FIRST集， 但有 T , 认为T 自动匹配。 #不属于E任一候选的 FIRST集， 但有 E , 认为E 自动匹配。,E TE E +TE| T FT T *FT| F (E)|i,40,LL(1)分析条件的提出(3),问题: 是不是一旦非终结符A面临输入符号a, 且a不属于所有FIRST(i), 但属于某个FIRST(j), 就一定可以使A自动匹配呢? 答案是不一定。在一定的条件下才可以。否则错误。 条件是a 允许跟在A的紧后面 例如上例中，+可跟在T后，#可跟在T、E后面。 下面定义可跟在非终结符后的终结符号的集合FOLLOW。,41,非终结符的后随终结符集FOLLOW,假定S是文法G的开始符号，对于任何非终结符A，定义： FOLLOW(A) = a | S* Aa且 aVT 特别是, 若S*A, 则规定 #FOLLOW(A) ( #是句末符号) 也就是说，FOLLOW(A)是所有句型中，出现在紧接A之后的终结符或#。 例： SaA A Sd AbAS FOLLOW(S)=#,a,d FOLLOW(A) = a,d,# SaAabASabbASS,2019/7/11,Ch4.语法分析-自上而下分析,42,计算FOLLOW集合：例,例：P69.(4.2)表达式文法 ETE E+TE| TFT T*FT| F(E)|i FOLLOW(T)= #, +, ), ETE T FT 有 #号 E TE T+TE FT+TE 有+号 E TE T FT (E)T (TE)T (T)T (FT)T 有 ) 号,2019/7/11,Ch4.语法分析-自上而下分析,43,LL(1)分析条件：3个,(1) 文法不含左递归。 (2) 对于文法中每个非终结符A的各个候选式的终结首符集两两不相交。即，若 A 1 | 2 | n 则： FIRST(i) FIRST(j) = ( i j ) (3) 对文法中每一个非终结符A，若它存在某个候选式的终结首符集包含，则 FIRST(A) FLLOW(A)= 特别注意第3个条件：当空字属于非终结符的某个候选式的终结首符集时的条件!,44,LL(1)文法,一个文法G若满足上述LL(1)分析的三个条件，则称该文法G为LL(1)文法。 LL(1)文法: 第一个 L 表示从左到右扫描输入串 第二个L 表示语法分析欲构造输入串的最左推导 括号里的 1 表示分析时, 每步只需向前查看一个符号 LL(1)文法是无二义文法, 上述三个条件是LL(1)文法无二义的充分条件。 对LL(1)文法，可以对其输入串进行有效的无回溯的自上而下分析。,2019/7/11,Ch4.语法分析-自上而下分析,45,LL(1)文法：自上而下分析过程,对LL(1)文法，假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为： A 1 | 2 | n (1) 若aFIRST(i ), 则指派 i 执行匹配任务。 (2) 若a不属于任何一个候选式的终结首符集, 则: 若属于某个FIRST(j )且aFOLLOW(A), 则让A与自动匹配; 否则, a的出现是一种错误。 根据LL(1)文法的条件, 每一步这样的工作都是确信无疑的。,46,LL(1)文法：例,例4.2文法(P69.) 不是LL(1)文法, 有左递归 例4.2消左以后的文法P69.(4.2)是LL(1)文法 满足LL(1)分析的三个条件 例1 文法G: S iA A :i=e|=e 是LL(1)文法 满足LL(1)分析的三个条件: 1. 不含左递归 2. FIRST(:i=e)= : , FIRST(=e)=, 不交 3. 候选式的FIRST集都不含,2019/7/11,Ch4.语法分析-自上而下分析,47,LL(1)文法: 例2,例2 文法G: S LU L i:| U i=e 因为: 1. 不含左递归 2. L的各个候选的FIRST集合互不交 3. L有个候选式的FIRST集合含, 再求得 FIRST(L)= i, FOLLOW(L)= i , 是相交的 所以G不是LL(1)文法。,2019/7/11,Ch4.语法分析-自上而下分析,48,4.4 递归下降分析程序构造,当一个文法满足LL(1)条件时，就可以为该文法构造一个不带回溯的自上而下分析程序： 这个分析程序由一组递归过程组成； 每个递归过程对应文法的一个非终结符号，完成该非终结符号所对应的语法成分的分析和识别任务。 这样一个自上而下语法分析程序称为递归下降分析器。,2019/7/11,Ch4.语法分析-自上而下分析,49,递归下降分析程序构造： 过程和变量,先设定一些过程和变量，作为递归下降分析程序的基本成分。 过程ADVANCE：调整ip指向下一个输入符号, 读入ip指向的输入符号到SYM中。 变量SYM：表示ip当前所指的那个输入符号。 过程ERROR：出错诊察处理。,50,递归下降分析程序构造： 非终结符对应的递归过程的结构, A1| 2| n =X1X2Xm Xi(VTVN) XiVT XiVN, IF ELSE IF ELSE 结构 顺序结构 IF SYM=Xi THEN ADVANCE ELSE ERROR 调用Xi对应的递归过程,2019/7/11,Ch4.语法分析-自上而下分析,51,例: 算术表达式的递归下降分析器(1),的子程序 ETE procedure E; begin T; 的过程调用 E E的过程调用 end;,的子程序 E+TE| procedure E; IF SYM=+ THEN begin ADVANCE; T; T的过程调用 E E的过程调用 end;,2019/7/11,Ch4.语法分析-自上而下分析,52,例: 算术表达式的递归下降分析器(2),T的子程序 TFT procedure T; begin F; F的过程调用 T T的过程调用 end;,T的子程序 T*FT| procedure E; IF SYM=* THEN begin ADVANCE; F; F的过程调用 T T的过程调用 end;,2019/7/11,Ch4.语法分析-自上而下分析,53,例: 算术表达式的递归下降分析器(3),F的子程序 Fi|(E) procedure F; IF SYM=i then ADVANCE ELSE IF SYM=( then,BEGIN ADVANCE; E; E的过程调用 IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,54,扩充巴科斯范式定义系统,对前面的产生式(巴科斯范式)进行扩充 ： (1) 用花括号表示闭包运算*。 (2) 用0n表示可以任意重复0次至n次, 00= 0=。 (3) 用方括号表示01，即表示的出现可有可无, 等价于 |。 这样, 使得产生式右部的形式像正规式一样, 这种定义形式称扩充巴科斯范式定义系统。 例如, P75. “实数”的扩充巴科斯范式定义 Decimalsigninteger.digitexponent,55,使用扩充BNF定义系统的好处(1),(1)直观易懂: 如表示不超过10位的无符号整数 90,(2)便于表示消除左递归和提取左因子消除回溯 例, 消除左递归，不用引入新的非终结符和产生式,56,使用扩充BNF定义系统的好处(2),(3)便于构造自上而下分析程序, 过程是: 关于非终结符A的产生式 写为扩充BNF定义形式 画出其语法图 转换为A对应的程序 非终结符号的语法图 类似于表示正规式的状态转换图，所以也称为文法的状态转换图。 结点 - 文法符号 有向边 - 文法符号的排列顺序,|或 分支 回路 .连接 顺序,57,用语法图描述语言的文法: 例(P75.),58,例: 简单算术表达式的 递归下降分析器(P76.)E,ET+T 的子程序, 请与P74.的程序对照 procedure E; begin T; 的过程调用 while SYM=+ do 当前符号等于时 begin ADVANCE; 处理终结符 T 的过程调用 end end; SYM：当前符号,59,例: 简单算术表达式的 递归下降分析器(P76.)T,TF*F 的子程序, 请与P74.的程序对照 procedure T; begin F; 的过程调用 while SYM=* then 当前符号等于时 begin ADVANCE; 处理终结符 F 的过程调用 end end;,60,总结递归子程序法,1.构造文法。 2.改写文法：消除二义性、消除左递归、提取公共左因子。 3.求每个候选式的FIRST集和非终结符的FOLLOW集。 4.检查是不是 LL(1)文法,是否满足LL(1)分析的三个条件。 5.若是LL(1)文法，为该文法的每个非终结符画出语法图。 6.按照语法图，为每个非终结符编写一个递归子程序。,2019/7/11,Ch4.语法分析-自上而下分析,61,4.5 预测分析程序,实现LL(1)分析的另一种有效方法是使用一张分析表和一个分析栈进行联合控制。直接根据当前的非终结符号以及当前输入符号，确定进行分析所需的候选式。 本节要介绍的预测分析程序就是属于这种类型的LL(1)分析器。 本节要掌握: 1.对给定文法构造符号串的FIRST集合和非终结符的FOLLOW集合的方法。 2. 构造预测分析表的方法。,2019/7/11,Ch4.语法分析-自上而下分析,62,4.5.1 预测分析程序工作过程,系统维持一张分析表和一个分析栈，直接根据当前的输入符号，选择当前非终结符(处于栈顶)的候选式进行推导，希望找到相应输入符号串的最左推导。 预测分析程序的逻辑结构： 1.一个通用的控制程序 2.一个统一形式的分析表M 不同文法使用内容不同的分析表 3.一个分析栈，#为栈底符号 4.一个输入缓冲区，#为输入串结束符,2019/7/11,Ch4.语法分析-自上而下分析,63,预测分析器模型 P77.图4.4,.a#,x . . . #,总控程序 见P77.,预测分析表M 见P76.表4.1,输出,分析栈,输入缓冲区,预测分析表是预测分析器的核心,64,预测分析程序的逻辑结构,1.一个输入串, “#”号为输入串结束符,#不属于VT。 2.一个统一形式的预测分析表M。 行: 所有的非终结符A 列: 所有的终结符号a, 包括“#”号 元素MA,a: 产生式或错误,概括了文法的全部信息。例, P76.表4.1文法(4.2)的预测分析表 3. 一个分析栈STACK，随着分析过程的进行而不断变化,分析开始时栈底先放一个“#”号,分析结束时,若栈底只剩下“#”号,则分析成功。 4.一个通用的统一的控制程序,分析的每一步都根据分析表、分析栈及输入串的当前符号进行控制。,2019/7/11,Ch4.语法分析-自上而下分析,65,表达式文法的预测分析表(P76.),66,预测分析程序的工作过程(1),在系统启动时，输入指针指向输入串的第一个符号，分析栈中存放着栈底符号#和文法的开始符号。 分析的每一步都根据栈顶符号X和当前输入符号a查看分析表MX,a,以决定相应的动作。 对任何(X,a),执行三种可能的动作之一： (1) 若 X=a=#，则分析成功,停止分析。 (2) 若 X=a#，则将X从STACK栈逐出,让a指向下一个输入符号，当前输入符号得到匹配。,2019/7/11,Ch4.语法分析-自上而下分析,67,预测分析程序的工作过程(2),(3)若XVN ,则查分析表项 MX,a: 若MX,a中存放的是XX1X2Xk,则将X从栈顶逐出,让 X1,X2,Xk反序进栈。 若MX,a中存放的是X,则将X逐出,不推什么进栈。 若MX,a中存放的是出错, 则调用ERROR进行错误处理。 预测分析程序的总控程序的形式描述(见P77.),68,预测分析程序的工作过程(P78.),例4.6文法(4.2),输入串为i*i+i,分析步骤： 分析栈 输入串 所用产生式 动作,#E i*i+i# 查表ME,i,出入栈 #ET i*i+i# ETE 查表MT,i,出入栈 #ETF i*i+i# TFT 查表MF,i,出入栈 #ETi i*i+i# Fi 匹配,i出栈,调指针 #ET *i+i# 查表MT,*,出入栈 #E TF* *i+i# T*FT 匹配,*出栈,调指针 #ETF i+i# 查表MF,i,出入栈 #ETi i+i# Fi 匹配,i出栈,调指针,#ET +i# 查表MT,+,出入栈 #E +i# T 查表ME,+,出入栈 #ET+ +i# E+TE 匹配,+出栈,调指针 #ET i# 查表MT,i,出入栈 #ETF i# TFT 查表MF,i,出入栈 #ETi i# Fi 匹配,i出栈,调指针 #ET # 查表MT,#,出入栈 #E # T 查表ME,#,出入栈 # # E,所用的产生式序列形成了最左推导对应的分析树,分析栈 输入串 所用产生式 动作,#ETi i+i# Fi 匹配,i出栈,调指针,70,4.5.2 预测分析表的构造,预测分析法步骤: 1)构造文法，消除二义性； 2)消除左递归、提取左因子； 3)求每个候选式的FIRST集和非终结符的FOLLOW集； 4)检查是不是 LL(1)文法； 若不是 LL(1),说明文法的复杂性超过LL(1)分析法的分析能力； 5)构造预测分析表； 6)实现预测分析器。,2019/7/11,Ch4.语法分析-自上而下分析,71,FIRST集和FOLLOW集,前面定义了: 对于(TN)* , 的终结首符号集 FIRST()=a|*a，aT * 特别的，若*，则FIRST()。 对于AN , A的后随终结符号集： FOLLOW(A)=a|S*Aa，aT 特别的, 若S* A,则#FOLLOW(A)。 下面介绍构造集合FIRST和FOLLOW的算法,72,求FIRST(X)的算法(P78.),设文法符号XTN (1) 若 XT，则 FIRST(X)=X； (2) 若 XN，取FIRST(X)的初值： a|Xa X FIRST(X)= a|Xa X 第(2)条的要点是查看X的产生式! (3) 下页,73,(3) 若XN，重复如下过程，直到其FIRST集不再增大: 若 XY，且YN，则 FIRST(X)= FIRST(X)(FIRST(Y)-) 若 XY1Yk ,且Y1Yi-1* 即FIRST(Yn), 其中 n=1到i-1, 则 FIRST(X)= FIRST(X)(FIRST(Yn)-) 若 Y1Yk*,即任何FIRST(Yi), 其中i=1到k,则 FIRST(X)=FIRST(X) 第(3)条的要点仍然是查看X的产生式，对产生式右部的一个个符号，计算符号的FIRST集合，检查是否含, 以决定是否继续计算!,求FIRST(X)的算法,74,设符号串=X1X2Xn，构造FIRST(),重复如下过程，直到其FIRST集不再增大: (1) 首先置 FIRST()= FIRST(X1)- (2) 若对任何j=1到i-1, 若X1Xi-1*, 则 FIRST()=FIRST()(FIRST(Xj)-) (3) 若 X1Xn*，则 FIRST()= FIRST() 计算FIRST()的要点是从左到右查看的一个个符号，计算符号的FIRST集合，检查是否含, 以决定是否继续计算！,求FIRST()的算法(P79.),75,例4.7 表达式文法符号的 FIRST集,FIRST(F)=(,i FIRST(T)=FIRST(F)=(,i FIRST(E)=FIRST(T)=(,i FIRST(E)=+， FIRST(T)=*, FIRST(+)=+ FIRST(*)=* FIRST()=( FIRST()=) FIRST(i)=i FIRST(+TE)=+ FIRST(ETF)=(,i FIRST(ETF)=+,*,(,i FIRST(ET)=+,*,文法(4.2): ETE E+TE| TFT T*FT| F(E)|i,76,计算FIRST集：例,例1 文法GS: SLU LUi:| Ue=i| FIRST(S)=e,i, FIRST(L)=e,i, FIRST(U)=e, FIRST(LU)=e,i, FIRST(Ui:)=e,i FIRST(e=i)=e,例2 文法GE: EE+T|T TT*F|F F(E)|i FIRST(E)=(,i FIRST(T)=(,i FIRST(F)=(,i FIRST(E+T)=(,i FIRST(T*F)=(,i FIRST(E)=(,77,计算FIRST集：练习,解： FIRST(A)= a FIRST(A)= a, FIRST(B)= d FIRST(B)= b, FIRST(AB1)= a FIRST(AB1)=a,b,1 FIRST(AB)=a,b,文法GA: AaA AAB1| BdB BbB| 计算: FIRST(A),FIRST(A) FIRST(B),FIRST(B) FIRST(AB1) FIRST(AB1) FIRST(AB),78,求FOLLOW(A)的算法(P79.),设文法GS,对G的所有非终结符, 重复作以下计算: (1)将#加入到 FOLLOW(S),#为句子的结束符 (2)若 AB，BN 则 FOLLOW(B)= FOLLOW(B)FIRST() (3)如果 AB 或 AB,且*，AB，则 FOLLOW(B)= FOLLOW(B)FOLLOW(A) 计算FOLLOW(B)的要点 是查看右部符号串包含B的产生式,计算B右边符号串的FIRST集合,若该集合含有,则还要计算FOLLOW(A),若B右边没有符号,也要计算FOLLOW(A)!,2019/7/11,Ch4.语法分析-自上而下分析,79,例4.7 表达式文法符号的FOLLOW集,FOLLOW(E)= ),# FOLLOW(E) = FOLLOW(E)= ),# FOLLOW(T)=+,),# FOLLOW(T) = FOLLOW(T)=+,),# FOLLOW(F)=*,+,),#,文法(4.2) ETE E+TE| TFT T*FT| F(E)|i,2019/7/11,Ch4.语法分析-自上而下分析,80,计算FOLLOW集：例,例1 文法GE: EE+T|T TT*F|F F(E)|i FOLLOW(E)=+,),# FOLLOW(T)=*,+,),# FOLLOW(F)=*,+,),#,例2 文法GS: SLU LUi:| Ue=i| FOLLOW(S)=# FOLLOW(L)=e,# FOLLOW(U)=i,#,2019/7/11,Ch4.语法分析-自上而下分析,81,计算FOLLOW集：练习,解： FOLLOW(A)=d,# FOLLOW(A) = FOLLOW(A)=d,# FOLLOW(B)=1 FOLLOW(B) = FOLLOW(B)=1,文法GA: AaA AAB1| BdB BbB| 计算: FOLLOW(A),FOLLOW(A) FOLLOW(B),FOLLOW(B),82,预测分析表(LL(1)分析表)的 构造算法(P79.),构造分析表M的算法是确定每个表元素，即确定MA,a： (1) 对文法G的每个产生式A, 先计算FIRST(), 若FIRST()含有, 则还要计算FOLLOW(A), 然后执行第步和第步； (2) 对于每个终结符aFIRST()，把A加到MA,a中； (3) 若FIRST() , 则对任何的 bFOLLOW(A), 把A加至MA,b中； (4) 把所有无定义的MA,a标上“出错标志”。,2019/7/11,Ch4.语法分析-自上而下分析,83,例4.8 表达式文法的预测分析表,84,表达式文法预测分析表的构造,对 F(E)| i FIRST(E)=(；FIRST(i)=i 则 确定 MF,(；MF,i,对 ETE FIRST(TE)=(,i 则 M E,( = ME,i= ETE,对 E+TE| FIRST(+TE)=+； FOLLOW(E)=),# 则确定 ME,+; ME,)； ME,#,对TFT FIRST(FT)=(,i；则确定MT,(；MT,i,对T*FT| FIRST(*FT)=*; FORLLOW(T)=+,),# 则确定 MT,*；MT,+；MT,)；MT,#,85,预测分析表与LL(1)文法,上述构造预测分析表的算法可应用于构造任何文法G的预测分析表 M。 但对于某些文法，其 MA，a可能持有若干个产生式，即MA，a是多重定义的。 如果文法G是左递归或二义的，那么，其预测分析表 M 至少含有一个多重定义入口。 可以证明，一个文法G的预测分析表M不含多重定义的入口，当且仅当该文法是LL(1)文法。 例如:(4.2)表达式文法是LL(1)文法,分析表不含多重定义; 而下面例子的文法不是LL(1)文法。,86,构造预测分析表：例,文法: SiCtSS|a SeS| Cb FIRST(iCtSS)=i, FIRST(a)=a FIRST(eS)=e, FOLLOW(S)=e,# FIRST(b)=b,该文法不是LL(1)文法!,87,构造预测分析表：练习,P82.第4题文法, 构造 LL(1)分析表(预测分析表)。 ExprExpr Expr(Expr)|Var ExprTail ExprTailExpr| V