《编译原理精品课件第6章自上而下的语法分析》由会员分享,可在线阅读,更多相关《编译原理精品课件第6章自上而下的语法分析(31页珍藏版)》请在金锄头文库上搜索。
1、第六章 语法分析(1),定义:设 GS = (VT ,VN , S , P) 是上下文无关文法,则 FIRST(x) = a|x ay,a VT,x,y V* 若x ,则规定FIRST(x) 实际上, FIRST(x)是指由符号串x出发能够推导出来的所有符号串中,处于串头的终结符号的集合。,6.1 常用终结符号集,6.1.1 FIRST集(首符号集),*,定义:设 GS = (VT ,VN , S , P) 是上下文无关文法,AVN , 则 FOLLOW(A)=a|S Aa ,aVT 若S A,则规定 #FOLLOW(A) 实际上, FOLLOW(A)是指文法GS 的所有句型中, 紧跟在非终结
2、符A后的终结符号的集合。 #作为输入串的结束符,或称为句子括号,如:abc#,6.1.2 FOLLOW集(后继符号集),FOLLOW(A)可采用以下算法求得: 1.对于文法GS的开始符号S,有#FOLLOW(S); 2.若文法GS中有形如UxA的规则,其中xV,则 FOLLOW(U)FOLLOW(A) 3.若文法GS中有形如UxAy的规则,其中xV,yV, 当y 时, FIRST(y)FOLLOW(A) 当y 时, FIRST(y) FOLLOW(A) FOLLOW(U)FOLLOW(A),6.1.4 FIRSTVT集和LASTVT集,定义:设上下文无关文法GS = (VT ,VN , S ,
3、 P)不含产生式,且任何产生式右部都不含有两个相继(并列)的非终结符号,AVN , 则 FIRSTVT(A)=a|A a或A Qa,a VT,Q VN LASTVT (A)=a|A a或A aQ,a VT,Q VN,6.2 语法分析方法概述,6.2.1 自顶向下分析方法,自顶向下分析是从文法的开始符号出发,通过一次次直接推导,试图推导出待分析符号串的过程。 由于自顶向下分析是试图通过一次次直接推导得到待分析符号串,所以推导的每一步都可能面临产生式的选择问题。整过推导过程,都存在推导路径的选择问题。 所谓待分析符号串,实际上是指源程序经词法分析后的单词串,为了简便起见,这种单词串常用形如abcd
4、#的符号串表示。,一、自顶向下分析方法 1.带回溯的自顶向下分析 所谓带回溯的自顶向下分析,实际上是指在推导过程中,总是试图用尽一切可能的方法进行推导。 2.确定的自顶向下分析 所谓确定的自顶向下分析方法,是指若输入串是文法的句子,则从文法的开始符号出发,每一步直接推导都只有唯一的规则可以选择。 条件: 对于文法,要能够进行确定的自顶向下分析,当且仅当对文法的任意非终结符号A,其所有的规则AX1|X2|Xn满足: SELECT(AXi) SELECT(AXj)= 其中i,j=1,2, ,n,且ij.,二、与自顶向下分析方法有关的文法变换 1.SELECT集相交时的候选式提取左公因子; 只有当文
5、法的每一非终结符的所有的规则SELECT集两两不相交时,才能进行确定的自顶向下分析。当文法不满足确定自顶向下分析的条件时,则须改造文法,即对SELECT集相交的候选式提取左公因子。 2.消除文法的左递归; 当采用最左推导的自顶向下的分析方法,如果文法具有左递归,将使分析过程陷入无限循环。在左递归文法中,对于左递归的非终结符,其规则的SELECT集必然相交。因此消除左递归,是进行确定的自顶向下分析的必然。,6.2.2 自底向上分析方法,自底向上的分析方法(即移进_规约法),是从待分析符号串开始,通过不断的在当前符号串中寻找可规约串,用相应的产生式左部替换可规约串,试图最终规约到文法开始符号的过程
6、。由于总是从左到右扫描输入串,因此寻找的可规约串是最左可规约串。,6.3 递归子程序法,递归子程序法也称为递归下降分析法,是一种简单直观易于构造的自顶向下分析方法,起方法思想是:对文法的每一个非终结符号编制一个处理子程序,而处理子程序的代码结构则由相应的非终结符号的规则右部所决定:规则右部的终结符号应与输入符号匹配,规则右部的非终结符号与相应的子程序调用相对应。,6.4 LL(1)分析法,定义:所谓LL(1)分析,是指从左到右扫描输入源程序,同时采用最左推导,且对每次直接推导只需向前查看一个输入符号,便可以确定当前所应选择的规则。 理解: 第一个L表示:自顶向下分析是从左向右扫描输入串。 第二
7、个L表示:分析过程中将用最左推导。 1表示:只需向右看一个符号便可决定如何推导(即选择哪个产生式进行推导)。,6.4.1 LL(1)分析器的逻辑结构,6.4.2 LL(1)分析表的构造,LL(1)分析表MA,a实际上是要表明要由A推导出终结符a所应采用的产生式。我们可以利用SELECT集来构造LL(1)分析表,具体构造算法如下: 设有文法GS=(VN,NT,P,S), VN=A1,A2,Am,令i=1 1.若关于Ai的规则有: Ai x1|x2|xn 则求的各规则的SELECT集。 2.若a SELECT(Aixj),则 MAi ,a= Aixj 3.i=i+1,重复1、2,直到im,即对文法
8、的所有的非终结符号求完为止。,6.4.3 LL(1)文法,1. LL(1)文法的判定 定义:对文法GS,如果其LL(1)分析表M不含多重定义元素,则称该文法是LL(1)文法。 等价定义:对文法GS,若其每个非终结符号的所有的规则的SELECT集都两两不相交,则称该文法是LL(1)文法。 2. 非LL(1)文法到LL(1)文法的变换,例:文法GS是否是LL(1)文法: SaA Sd AbAS A 分析: SELECT(SaA) =a SELECT(Sd) =d SELECT(AbAS)=b SELECT(A) =a,d,# SELECT(SaA) SELECT(Sd)=ad= SELECT(Ab
9、AS)SELECT(A)=ba,d,#= 所以该文法是LL(1)文法。,LL(1)文法的判别,求出能推出的非终结符 计算FIRST集 计算FOLLOW集 计算SELECT集 判别是否是LL(1)文法,例:设文法GS 为: SAB SbC A Ab B BaD CAD Cb DaS Dc 判断它是否是LL(1)文法。,1.能够推出的非终结符号有:S、A、B 2.计算FIRST集 FIRST(S)=(FIRST(A)-)FIRST(B)-)b=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c FIRST(AB)=a,b, FIRST(
10、AD)=a,b,c,SAB SbC A Ab B BaD CAD Cb DaS Dc,SAB SbC A Ab B BaD CAD Cb DaS Dc,3.计算FOLLOW集 FOLLOW(S)=#FOLLOW(D) FOLLOW(A)=aa,cFOLLOW(S) FOLLOW(B)=FOLLOW(S) FOLLOW(C)=FOLLOW(S) FOLLOW(D)=FOLLOW(B)FOLLOW(C),FOLLOW(S)= # FOLLOW(A)= a,c,# FOLLOW(B)= # FOLLOW(C)= # FOLLOW(D)= #,4.计算SELECT集,SAB SbC A Ab B Ba
11、D CAD Cb DaS Dc,FIRST(S)=a,b, FIRST(A)=b, FIRST(B)=a, FIRST(C)=a,b,c FIRST(D)=a,c FIRST(AB)=a,b, FIRST(AD)=a,b,c,SELECT(SAB)=a,b,# SELECT(SbC)=b SELECT(A)=a,c,#, SELECT(Ab)=b SELECT(B)=#, SELECT(BaD)=a SELECT(CAD)=a,b,c SELECT(Cb)=b SELECT(DaS)=a SELECT(Dc)=c,FOLLOW(S)= # FOLLOW(A)= a,c,# FOLLOW(B)=
12、 # FOLLOW(C)= # FOLLOW(D)= #,该文法不是LL(1)文法。,某些非LL(1)文法到LL(1)文法的等价变换,提取左公共因子 消除左递归,A|导致SELECT(A) SELECT(A),因此非LL(1)文法。 等价变换为A(|),然后: A A A | A1|2|n 变换为A(1|2|n) ,然后: AA A 1|2|n,提取左公共因子,例:文法GA为: Aad ABc BaA BbB,1.化为: Aad AaAc AbBc BaA BbB,2.化为: Aa(d|Ac) AbBc BaA BbB,3.化为: AaA AbBc Ad AAc BaA BbB,结果是LL(1
13、)文法。,GE: E E+T | T T T*F | F F i | ( E ),E TE E +TE | T FT T *FT | F i | ( E ),判断文法GE是否为LL(1)文法? 1.消除左递归:,E TE E +TE | T FT T *FT | F i | ( E ),2.可推出 的非终结符表:,3.各非终结符的FIRST集和FOLLOW集:,FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T
14、)= + , ) , # FOLLOW(T)= + , ) , # FOLLOW(F)= * , + , ) , # ,E TE E +TE | T FT T *FT | F i | ( E ),E TE E +TE | T FT T *FT | F i | ( E ),SELECT(E TE) = ( , i SELECT(E +TE ) = + SELECT(E ) = , ) , # SELECT(T FT) = ( , i SELECT(T *FT ) = * SELECT(T ) = , + , ) , # SELECT(F ( E ) = ( SELECT(F i) = i ,FIRST(E)= ( , i FIRST(E)= + , FIRST(T)= ( , i FIRST(T)= * , FIRST(F)= ( , i ,FOLLOW(E)= ) , # FOLLOW(E)= ) , # FOLLOW(T)= + , ) , # FOLLOW(T)=