《编译原理精品课件第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)=
