【教学课件】第四章自顶向下的语法分析.ppt
《【教学课件】第四章自顶向下的语法分析.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第四章自顶向下的语法分析.ppt(55页珍藏版)》请在三一办公上搜索。
1、第四章 自顶向下的语法分析,School of Computer Science&Technology Harbin Institute of Technology,重点:自顶向下分析的基本思想,预测分析器总体结构,预测分析表的构造,递归下降分析法基本思想,简单算术表达式的递归下降分析器。难点:FIRST 和 FOLLOW 集的求法,对它们的理解以及在构造LL(1)分析表时的使用。递归子程序法中如何体现分析的结果。,2023/8/7,2,第4章 自顶向下的语法分析,4.1 语法分析概述 4.2 自顶向下的语法分析面临的问题 与文法的改造 4.3 预测分析法 4.4 递归下降分析法 4.5 本章
2、小结,2023/8/7,3,语法分析的功能和位置,语法分析(syntax analysis)是编译程序的核心部分,其任务是检查词法分析器输出的单词序列是否是源语言中的句子,亦即是否符合源语言的语法规则。,图4.1语法分析器在编译器中的位置,2023/8/7,4,4.1 语法分析概述,递归子程序法自顶向下 预测分析法(LL(1)算符优先分析法自底向上 LR(0)、SLR(1)、LR(1)、LALR(1),Top Down,Bottom Up,从文法产生语言的角度,从自动机识别语言的角度,从根开始,逐步为某语句构造一棵语法树,相反,将一句子归约为开始符号,问题:解决确定性问题!假定文法是压缩的:即
3、删除了单位产生式和无用产生式。,2023/8/7,5,4.2 自顶向下的语法分析面临的问题与文法的改造,自顶向下语法分析的基本思想从文法的开始符号出发,寻求所给的输入符号串的一个最左推导。从树根S开始,构造所给输入符号串的语法树例:设有G:SxAy A*|*,输入串:x*y,SxAy,x*y,S,2023/8/7,6,4.2.1 自顶向下分析面临的问题,1.二义性问题对于文法G,如果L(G)中存在一个具有两棵或两棵以上分析树的句子,则称G是二义性的。也可以等价地说:如果L(G)中存在一个具有两个或两个以上最左(或最右)推导的句子,则G是二义性文法。如果一个文法G是二义性的,假设wL(G)且w存
4、在两个最左推导,则在对w进行自顶向下的语法分析时,语法分析程序将无法确定采用w的哪个最左推导。Gexp:EE+T|E-T|TTT*F|T/F|FFFP|P Pc|id|(E)解决办法:改造文法,引入新的文法变量,2023/8/7,7,4.2.1 自顶向下分析面临的问题,2.回溯问题文法中每个语法变量A的产生式右部称为A的候选式,如果A有多个候选式存在公共前缀,则自顶向下的语法分析程序将无法根据当前输入符号准确地选择用于推导的产生式,只能试探。当试探不成功时就需要退回到上一步推导,看A是否还有其它的候选式,这就是回溯(backtracking)。Ge:ET EE+T EE-T TF TT*F T
5、T/F F(E)Fid 例如:考虑为输入串id+id*id建立最左推导,2023/8/7,8,4.2.1 自顶向下分析面临的问题,2.回溯问题ET(4.1)ETF(4.2)ETF(E)(4.3)ETFid(4.4)ETT*F(4.5).4.2.2节我们将采用提取左因子的方法来改造文法,以便减少推导过程中回溯现象的发生,当然,单纯通过提取左因子无法彻底避免回溯现象的发生。,2023/8/7,9,4.2.1 自顶向下分析面临的问题,3.左递归引起的无穷推导问题假设A是文法G的某个语法变量,如果存在推导A A,则称文法G是递归的,当=时称之为左递归;如果A A至少需要两步推导,则称文法G是间接递归的
6、,当=时称之为间接左递归;如果文法G中存在形如AA的产生式,则称文法G是直接递归的,当=时称之为直接左递归。Ger:ET EE+T EE-T TF TT*F TT/F F(E)Fid 考虑为输入串id+id*id建立一个最左推导 EE+TE+T+TE+T+T+T,2023/8/7,10,4.2.2 对上下文无关文法的改造,1.消除二义性改造的方法就是通过引入新的语法变量等,使文法含有更多的信息。其实,许多二义性文法是由于概念不清,即语法变量的定义不明确导致的,此时通过引入新的语法变量即可消除文法的二义性。if then|if then else|other(4.7)根据if语句中else与th
7、en配对情况将其分为配对的语句和不配对的语句两类。上述if语句的文法没有对这两个不同的概念加以区分,只是简单地将它们都定义为,从而导致该文法是二义性的。,2023/8/7,11,4.2.2 对上下文无关文法的改造,引入语法变量来表示不配对语句,表示配对语句|if then else|other if then|if then else,2023/8/7,12,4.2.2 对上下文无关文法的改造,2.消除左递归直接左递归的消除(转换为右递归)引入新的变量A,将左递归产生式AA|替换为AA A A|EE+T|T TT*F|F F(E)|id替换为:ETE E+TE|TFT T*FT|F(E)|id
8、 一般地,假设文法G中的语法变量A的所有产生式如下:AA1|A2|An|1|2|m其中,i(i=1,2,m)不以A打头。则用如下的产生式代替A的所有产生式即可消除其直接左递归:A1A|2A|mA A1A|2A|nA|,2023/8/7,13,4.2.2 对上下文无关文法的改造,算法4.1 消除左递归。输入:不含循环推导和-产生式的文法G;输出:与G等价的无左递归文法;步骤:1将G的所有语法变量排序(编号),假设排序后的语法变量记为A1,A2,An;2for i1 to n 3for j1 to i-1 4用产生式Ai1|2|k代替每个形如AiAj的产生式,其中,Aj1|2|k是所有的当前Aj产
9、生式;5 6 消除Ai产生式中的所有直接左递归7,2023/8/7,14,4.2.2 对上下文无关文法的改造,3.提取左因子对每个语法变量A,找出它的两个或更多候选式的最长公共前缀。如果,则用下面的产生式替换所有的A产生式A1|2|n|1|2|n,其中1,2,n表示所有不以开头的候选式:AA|1|2|nA1|2|n其中,A是新引入的语法变量。反复应用上述变换,直到任意语法变量都没有两个候选式具有公共前缀为止。请读者自行给出这个变换的算法。,2023/8/7,15,4.2.3 LL(1)文法,问题:什么样的文法对其句子才能进行确定的自顶向下分析?确定的自顶向下分析首先从文法的开始符号出发,每一步
10、推导都根据当前句型的最左语法变量A和当前输入符号a,选择A的某个候选式来替换A,并使得从推导出的第一个终结符恰好是a。当A有多个候选式时,当前选中的候选式必须是惟一的。第一个终结符是指符号串的第一个符号,并且是终结符号,可以称为首终结符号。在自顶向下的分析中,它对选取候选式具有重要的作用。为此引入首符号集的概念。,2023/8/7,16,4.2.3 LL(1)文法,1.假设是文法G=(V,T,P,S)的符号串,即(VT)*,从推导出的串的首符号集记作FIRST():FIRST()=a|a,aT,(VT)*。2.如果,则FIRST()。3.如果文法G中的所有A产生式为A1|2|m,且FIRST(
11、1)FIRST(2)FIRST(n)且对i,j,1i,jm;ij,均有FIRST(i)FIRST(j)=成立,则可以对G的句子进行确定的自顶向下分析,2023/8/7,17,4.2.3 LL(1)文法,如果存在A这样的产生式,则需定义FOLLOW(A)A定义A的后续符号集为:1.FOLLOW(A)=a|S Aa,aT,(VT)*2.如果A是某个句型的最右符号,则将结束符#添加到FOLLOW(A)中3.如果j,则如果对i(1im;ij),FIRST(i)FOLLOW(A)=均成立,则可以对G的句子进行确定的自顶向下分析,2023/8/7,18,4.2.3 LL(1)文法,如果G的任意两个具有相同
12、左部的产生式A|满足下列条件:1.如果、均不能推导出,则FIRST()FIRST()=;2.和至多有一个能推导出;3.如果,则FIRST()FOLLOW(A)=则称G为LL(1)文法。第一个L代表从左向右扫描输入符号串,第二个L代表产生最左推导,1代表在分析过程中执行每步推导都要向前查看一个输入符号,2023/8/7,19,LL(1)文法的判定,算法4.2 计算FIRST(X)。输入:文法G=(V,T,P,S),X(VT);输出:FIRST(X);步骤:1FIRST(X)=;2if(XT)then FIRST(X):=X;3if XV then begin4if(XP)then FIRST(X
13、):=FIRST(X)a|XaP;5if(XP)then FIRST(X):=FIRST(X)a|XaPend6对X,重复如下的过程7-10,直到所有FIRST集不变为止。7if(XYP and YV)then FIRST(X):=FIRST(X)(FIRST(Y)-);8if(XY1YnP and Y1.Yi-1)then 9for k=2 to i do FIRST(X):=FIRST(X)(FIRST(Yk)-);10if Y1.Yn then FIRST(X):=FIRST(X);,2023/8/7,20,LL(1)文法的判定,算法4.3 计算FIRST()。输入:文法G=(V,T,P
14、,S),(VT)*,=X1Xn;输出:FIRST();步骤:1计算FIRST(X1);2FIRST():=FIRST(X1)-;3k:=1;4while(FIRST(Xk)and kn)do begin5 FIRST():=FIRST()(FIRST(Xk+1)-);6 k:=k+1 end7if(k=n and FIRST(Xk)then FIRST():=FIRST();,2023/8/7,21,例 表达式文法的语法符号的FIRST 集,FIRST(F)=(,idFIRST(T)=FIRST(F)=(,id FIRST(E)=FIRST(T)=(,id FIRST(E)=+,FIRST(T
15、)=*,FIRST(+)=+,FIRST(*)=*FIRST(()=(FIRST())=)FIRST(id)=id,ETE E+TE|TFT T*FT|F(E)|id,2023/8/7,22,LL(1)文法的判定,算法4.4 计算FOLLOW集。输入:文法G=(V,T,P,S),AV;输出:FOLLOW(A);步骤:1对XV,FOLLOW(X):=;2FOLLOW(S):=#,#为句子的结束符;3对XV,重复下面的第4步到第5步,直到所有FOLLOW集不变为止。4若ABP,则FOLLOW(B):=FOLLOW(B)FIRST();5若AB或ABP,且,AB,则FOLLOW(B):=FOLLOW
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 第四 向下 语法分析
链接地址:https://www.31ppt.com/p-5665258.html