语法分析自上而下分析.ppt_第1页
语法分析自上而下分析.ppt_第2页
语法分析自上而下分析.ppt_第3页
语法分析自上而下分析.ppt_第4页
语法分析自上而下分析.ppt_第5页
已阅读5页,还剩66页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

语法分析 自上而下分析 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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论