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

语法分析 自上而下分析 w 在第三章，用正规式描述了单词符号的 结构，并研究了如何用有限自动机构造 词法分析器的问题。 w 由于正规式与正规文法是等价的，它们 的描述能力有限，而高级语言的语法结 构适合用上下文无关文法描述，因此， 我们将上下文无关文法用作语法分析的 基础。 w 本章和下一章，我们将介绍编译程序构 造中的一些典型的语法分析方法。 语法分析自上而下分析 w 语法分析器的功能 w 自上而下分析面临的问题 w LL（1）分析法 w左递归的消除 w消除回溯、提左因子 wLL（1）分析条件 w 递归下降分析程序构造 w 预测分析程序 w预测分析程序工作过程 w预测分析表的构造 w 作业 语法分析器的功能 w 语法分析是编译过程的核心部分。它的任务 是在词法分析识别出单词符号串的基础上， 分析并判定程序的语法结构是否符合语法规 则。 w 语言的语法结构是用上下文无关文法描 述的。因此，语法分析器的工作本质上 就是按文法的产生式，识别输入符号串 是否为一个句子。 w 所说的输入串是指由单词符号（文法的 终结符）组成的有限序列。 w 对一个文法，当给你一串（终结）符号 时，怎样知道它是不是该文法的一个句 子（“程序”）呢？这就要判断，看是否 能从文法的开始符号出发推导出这个输 入串。或者，从概念上讲，就是要建立 一棵与输入串相匹配的语法分析树。 w 按照语法分析树的建立方法，我们可以 粗略地把语法分析办法分成两类： w 一类是自上而下分析法， w 另一类是自下而上分析法。 自上而下分析面临的问题 w 自上而下就是从文法的开始符号出发， 向下推导，推出句子。 w 我们首先将简单地介绍自上而下分析的 一般方法。这种方法是带“回溯”的。 w 下一节，将着重讨论一种广为使用的不 带回溯的递归子程序（递归下降）分析 方法。 w 自上而下分析的主旨是，对任何输入串 ，试图用一切可能的办法，从文法开始 符号（根结）出发，自上而下地为输入 串建立一棵语法树。或者说，为输入串 寻找一个最左推导。 w 这种分析过程本质上是一种试探过程， 是反复使用不同产生式谋求匹配输入串 的过程。 w 例4.1 假定有文法 （1）SxAy （2）A*|* （4 .1） 以及输入串x*y (记为）。 为了自上而下构造的语法树，我们首先按文法的开始 符号产生根结 S，并让指示器IP指向输入串的第一个 符号x。然后，用S的规则（此处关于S的规则仅有一 条）把这棵树发展为 S xA y w 非终结符A有两个候选，试着用它的第一个 候选(A*) 去匹配输入串，于是把语法树 发展为 S xA y * 子树A的最左子结和IP所指的符号*相符，然后我们再把IP调 为指向下一符号并让A的第二个子结进入工作。但A的第二 子结*和当前所指的符号y不一致。因此，A告失败。这意味 着A的第一个候选此刻不适用于构造的语法树。这时应该回 头（回溯），看A是否还有别的候选。 w 为了这种回溯，我们一方面应把A的第一 候选所发展的子树注销掉，另一方面应 把IP恢复为进入A时的原值，也就是让它 重新指向第二个输入符号，。现在我们 试探A的第二个候选（ A* ），即考虑 如下的语法树： S xA y * w 由于子树A只有一个子结，而且它和IP 所指的符号相一致，于是，A完成了匹 配任务。在A获得匹配后，指示器IP应 指向下一个未被触及符号y。 w 在S的第二子结A完成匹配后，接着就轮 到第三个子结y进行工作。 w 由于这个子结和最后一个输入符号相符 ，于是，我们完成了为构造语法树的 任务，证明了是一个句子。 w 实现这种自上而下的带回溯试探法的一 个简单途径是让每个非终结符对应一个 递归子程序。 w 每个这种子程序可作为一个布尔过程。 一旦发现它的某个候选与输入串相匹配 ，就用这个候选去扩展语法树，并返回“ 真”值；否则，保持原来的语法树和IP值 不变，并返回“假”值。 但是，自上而下分析法存在许多困难和缺点 w 首先，是文法的左递归性问题。 w 一个文法是含有左递归的，如果存在非终结 符 P w P + P w 含有左递归的文法将使上述的自上而下的分 析过程陷入无限循环。即，当试图用P去匹配 输入串时，我们会发现，在没有识别任何输 入符号的情况下，又得重新要求P去进行新的 匹配。因此，使用自上而下分析法必须消除 文法的左递归性。 w 其次，由于回溯，就碰到一大堆麻烦事 情。如果我们走了一大段错路，最后必 须回头，那么，就应把已经做的一大堆 语义工作（指中间代码产生工作和各种 表格的簿记工作）推倒重来。这些事情 既麻烦又费时间， w 应设法消除回溯。 w 第三，在上述的自上而下分析过程中，当一 个非终结符用某一候选匹配成功时，这种成 功可能仅是暂时的。 w 例如，就文法(4.1)而言，考虑输入串x*y。若 对A首先使用第二个候选式，A将成功地把它 的唯一子结*匹配于输入串的第二个符号。但 S的第三个子结Y与第三个输入符号*不匹配。 因而，导致了无法识别输入串x*y是一个句 子的事实。 w 然而，若A首先使用它的第一个候选*，则整 个输入串即可获得成功分析。 w 这意味着，A首先使用第二个候选所得的成功 匹配是虚假的。 w 由于这种虚假现象，我们需要更复杂的回溯 技术。一般说，要消除虚假匹配是很困难的 。 w 但若从最长的候选开始匹配，虚假匹配的现 象就会减少一些。 w 第四，当最终报告分析不成功时，我们 难于知道输入串中出错的确切位置。 w 最后，由于带回溯的自上而下分析实际 上采用了一种穷尽一切可能的试探法， 因此，效率很低，代价极高。严重的低 效使得这种分析法只有理论意义，而在 实践上价值不大 。 w 下面将集中讨论不带回溯的自上而下分 析法。 LL（1）分析法 w 自上而下分析方法不允许文法含有任何 左递归。 w 为构造不带回溯的自上而下分析算法， 首先要消除文法的左递归性，并找出克 服回溯的充分必要条件。 w 本节，我们将讨论消除左递归和克服回 溯的方法。在后两节，将分别研究递归 子程序分析算法及其变种一预测分析法 。 左递归的消除 w 直接消除见诸于产生式中的左递归是比较容 易的。假定关于非终结符P的规则为：PP| 其中，不以P开头。那么，我们可以把P的规则 改写为如下的非直接左递归形式： PP PP| w 这种形式和原来的形式是等价的，也就是说 ，从P推出的符号串是相同的。 例4.2：文法G: (1 )E E + T | T (2) T T * F | F (3) F ( E ) | i 经消去直接左递归后转化为G: (1) E TE (2) E +TE| (3) T FT (4) T *FT| (5) F (E) | i w 消除直接左递归 一般地，假定关于P的全部产生式是 将P P 1| P 2|. |P m|1| 2|.| n 其中,每个都不等于，而每个都不以P开头， 那么消除P的直接左递归性为 P 1P| 2 p| n P P 1P| 2P| mP| w 使用这个办法，我们容易把见诸于表 面上的所有直接左递归都消除掉，也 就是说，把直接左递归都改成直接右 递归。但这并不意味着已经消除整个 文法的左递归性。例如文法 ： 虽不具有直接左递归，但S,Q,R都是 左递归的，例如有 S Q c R b c S a b c S Qc | c Q Rb | b R Sa | a w 如果一个文法不含回路（形如PP的推导） ，也不含以为右部的产生式，那么，执行 下述算法将保证消除左递归（但改写后的文 法可能含有以为右部的产生式）。 1）把文法G的所有非终结符按任意顺序排列成 P1,P2,Pn,然后按此顺序执行步骤2。 2） for (i=1,ij) 3) 对文法中的每个非终结符A,若它存在某个候选首 符集包含 ，则 First(A) Follow(A)= 如果一个文法G满足以上条件，则称该文法G为 LL(1)文法。其中: 第一个L表示从左到右扫描输 入串，第二个L表示最左推导，1表示分析时每一 步只需向前察看一个符号。 w不带回溯的自上而下分析 对一个LL(1) 文法，假设要用非终结符A进行匹配 ，面临的输入符号为a，A的所有产生式为 A 1| 2|. | n 1) 若a First( i) ,则指派 i去执行匹配任务 2) 若a不属于任何一个候选首符集，则： 若 属于某个First( i) 且a Follow(A)，则 让A与自动匹配； 否则，a的出现是一种语法错误。 根据LL(1)文法的条件，每一步这样的工作都是确 信无疑的。 例：判断下面文法是不是LL(1)文法： S if E then S else S | if E then S | other E b 解：首先对文法进行改造，消除文法左递归和提 取公共左因子；文法改写为： S if E then S S|other S else S| E b 第2步：求首符集和随符集 First(S)=if,other, First(S)=else, First(E)=b Follow(S)= Follow(S)=else,# Follow(E)=then 第3步：根据定理判定文法是不是LL(1)文法。 因为：1) First(if E then S S) First(other)= First(else S) First()= 但2) First(else S) Follow(S)=else不为空集 故此文法不是LL(1)文法。 递归下降分析程序的构造 w 是进行语法分析的一种方法 w 要求文法是LL(1)文法 w 实现思想： 识别程序由一组过程组成。每个过程对应 于文法的一个非终结符号。 每一个过程的功能是：选择正确的右部， 扫描完相应的字。在右部中有非终结符号 时，调用该非终结符号对应的过程来完成 。 基本架构(1) w 对于每个非终结符号的产生式Uu1|u2|un处理的方 法如下： U( ) ch保存当前符号sym; if(ch是u1符号串的第一个符号) 处理u1 else if(ch是u2符号串的第一个符号) 处理u2 else error() 由于无回溯的文法保证选择是唯一的。 当存在时，可以将error()替代为return;这样 可以较晚发现错误。 约定：进入这个过程时，已读入U的第一个符号到当 前符号。离开这个过程时，下一个符号已经被读到 当前符号。 基本架构(2) w 对于U的每个右部ui=x1x2xn的处理架构如下 ： 处理x1的程序； 处理x2的程序； 处理xn的程序； w 如果右部为空，则不处理。 基本架构(3) w 对于右部中的每个符号xi w 如果xi为终结符号： if(x= 当前输入符号串中的符号) NextCh()； else 出错处理 w 如果xi为非终结符号，直接调用相应 的过程： xi() w 给出以下文法的递归子程序： E TE E +TE | T FT T *FT | F (E) |i / 主程序 PROGRAM MAIN ; BEGIN ADVANCE; E; IF SYM = # THEN ACCEPT ELSE ERROR END; PROCEDURE E; BEGIN T ; E END; PROCEDURE T; BEGIN F ; T END; PROCEDURE E ; BEGIN IF SYM = + THEN BEGIN ADVANCE; T ; E END END; PROCEDURE T ; BEGIN IF SYM = * THEN BEGIN ADVANCE; F ; T END END; PROCEDURE F; / F (E) |i BEGIN IF SYM = i THEN ADVANCE ELSE IF SYM = ( THEN BEGIN ADVANCE; E; IF SYM = ) THEN ADVANCE ELSE ERROR END ELSE ERROR; END; / 提前报错，检测FRIST 集 PROCEDURE E; BEGIN IF SYM IN FRIST(T) THEN BEGIN T ; IF SYM IN FRIST(E ) THEN E ELSE ERROR; END ELSE ERROR END; / 提前报错，检测FOLLOW集 PROCEDURE E ; / E +TE | BEGIN IF SYM = + THEN BEGIN ADVANCE; T ; E END ELSE IF SYM IN FOLLOW(E) THEN 空语句 ELSE ERROR END; 预测分析程序 w 递归下降分析法：采用递归过程。因此实 现分析程序所使用的高级语言必须支持递 归过程才行。 w 预测分析法是自顶向下分析的另一种方法 。 w 使用下推自动机的方式实现。 w 使用一个二维分析表和栈联合进行控制来 实现分析。 表驱动预测分析器模型 预测分析程序 预测分析表M abcaab # 输出带 X # stack 输入带 文法（4.2）的预测分析表 i + * ( )# EETEETE EE +TE EE TTFTTFT TTT *FT TT FF iF (E) w 预测分析程序算法描述 设栈顶符号为X，读入符号为a，则 1)若X=a=#，则表示识别成功，退出分析程序； 2)若X=a#，则表示匹配，弹出栈顶符号X，读头 前进一格，让读头指向下一个符号，以读入下一个 符号；若X是终结符，但Xa，则调用error处理； 3)若XVN，则查预测分析表M。若MX,a中存放 着关于X的产生式，则弹出X，且将相应产生式右 部以自右向左的顺序压入栈，在输出带上记下产生 式编号；若MX,a中存放着出错标记，则调用相应 Error处理。 w 预测分析程序形式化描述 BEGIN 首先把#然后把文法开始符号推入栈；把第一个输入符 号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,a=X X1X2XK THEN 把XK，X K-1,X1一一推进栈 ELSE ERROR END OF WHILE; STOP/*分析成功，过程完毕* END 预测分析过程 w 下面用预测分析方法对输入串i+i*i# 进行 分析，给出栈的变化过程如下： 步骤分析栈剩余输入 串 所用产生式 1#Ei+i*i#ETE 2#ETi+i*i#TFT 3#ETFi+i*i#Fi 4#ETii+i*i#i匹配 5#ET+i*i#T 6#E+i*i#E+TE 步骤分析栈剩余输入串所用产生式 7#ET+i*i# +匹配 8#ETi*i#TFT 9#ETFi*i#F i 10#ETii*i#i匹配 11#ET*i#T *FT 12#ETF*i#*匹配 13#ETFi#F i 14#ETii#i匹配 15#ET#T 16#E#E 17# #接受 构造预测分析表 w 从前面的论述我们看到，预测分析过程 的总控程序是固定的。对于某个文法， 分析表是分析过程的核心。 w 表中MA,a=AX1X2Xn表示对应于 X1X2Xn串的首终结符可以是a。就是说 X1X2Xn=aw。可以通过这个方式来确 定分析表中的值。(即：求首终结符) 预测分析表的构造算法 w 对文法的每个文法符号X构造First(X) w 对文法的每个非终结符A构造Follow(A) w 对于每一产生式 A, 对于每个终结符aFIRST(),将A填入 MA,a； 如果FIRST()，则对任何元素 bFOLLOW(A) ，将A填入MA,b； w 将所有无定义的 MA,a 标上错误标志。 如果文法是LL(1)文法，其预测分析表中没 有多重定义的元素，可以进行确定的分析 。 LL(1) 分析中的错误处理 发现错误 v 栈顶的终结符与当前输入符不匹配 v 非终结符A于栈顶，面临的输入符为a，但分析表M 的MA,a为空 “应急”恢复策略 跳过输入串中的一些符号直至遇到“同步符号”为止。 同步符号的选择 把FOLLOW(A)中的所有符号作为A的同步符号。跳 过输入串中的一些符号直至遇到这些“同步符号”， 把A从栈中弹出，可使分析继续 把FIRST(A)中的符号加到A