编译原理第四章课件

1编译原理主讲教师:雷向东2023/7/212第四章语法分析——自上而下分析4.1语法分析器的功能语法分析器的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的结构是否符合语法规则。语法分析方法可分为两类：一类是自上而下分析法，另一类是自下而上分析法。2023/7/21语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子（“程序”）呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。2023/7/2144.2自上而下分析面临的问题自上而下分析法就是从文法的开始符号出发，向下推导，推出句子。例4.1假设文法G[S]

S→xAy

A→**

A→*

识别输入串α

=x*y是否该文法的句子。2023/7/215

S S S x A y x A y **推导过程：S

xAy

x**y。用非终结符A的第一个候选告失败。应该回溯，使用A的其它候选。自上而下构造α

的语法树。(a)(b)(c)2023/7/216为了回溯，把A的第一个候选所发展的子树注销掉，试探A的第二个候选。

S x A y *匹配成功，证明了α是一个句子。*7上述自上而下分析面临的问题:文法的左递归性质问题一个文法是含有左递归的，如果存在非终结符PPPα

含有左递归的文法将使上述的自上而下分析过程陷入无限循环。例如文法规则：A→AaAAaAa…递归展开。+2023/7/218回溯问题做了很多语义工作，最后必须回头，推倒重来，既麻烦又费时间。虚假匹配现象当最终报告分析不成功，难于知道输入串中出错的确切位置。2023/7/21自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归法，并找出克服回溯的充分必要条件。下面将讨论消除文法左递归和克服回溯的方法。

4.3LL(1)

分析法2023/7/2110消除直接左递归假设关于非终结符P的规则为

P→Pα|β

其中,β不以P打头。把P的规则改写为如下非直接左递归形式：

P→βP

’

P→αP

’|这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。它们推出的符号串都是{β，βα，βαα，βααα，…}。

2023/7/2111例4.2文法G[E]E→E+T|TT→T*F|FF→(E)|i消除直接左递归

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i2023/7/2112消除回溯，提左因子假设关于非终结符A的全部规则为

A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm其中，每个γ不以δ开头。把A的规则改写为如下形式：

A→αA’|γ1|γ2|…|γmA’→β1|β2|…|βn

2023/7/21LL(1)分析条件为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。也就是说，若此候选获得成功匹配，那么，这种匹配决不会是虚假的；若此候无法完成匹配任务，则任何其它候选也肯定无法完成。换句话说，假定现在轮到非终结符A去执行匹配（或称识别）任务，A共有n个候选α1，α2，…，αn，即A→α1|α2|…|αn。A所面临的第一个输入符号为a，如果A能够根据不同的输入符号指派要应的候选αi作为全权代表去执行任务，那就肯定无需回溯了。2023/7/21

在不得回溯的前提下，文法不得含有左递归。令G是一个不含左递归的文法，对G的所有非终结符的每个候选A定义它的终结首符集FIRST(α)为

FIRST(α)={a|α*a,a∈VT,α,∈V*}

特别是，若*=>ε，则规定ε∈FRIST()。2023/7/21换名话说，FIRST(α)是α的所有可能推导的开头终结符或可能的ε。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选i和j

FIRST(α)∩FIRST(β)=那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的α。2023/7/21当非终结符A面临输入符号a，且a不属于A的任意候选首符集，但A的某个候选首符集包含ε时，就一定可以A自动匹配？如果我们仔细来考虑一下的话，就不难发现，只有当a是允许在文法某个句型中跟A后面的终结符时，才可能允许A自动匹配，否则，a在这里的出现就是一种语法错误。2023/7/21假定S是文法G的开始符号，对于G的任何非终结符A，定义FOLLOW(A)={aS*…Aa…且a∈VT}特别是，若S*…A，则规定#FOLLOW(A)。换句话说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或“#”。因此，当非终结符A面临输入符号a，且a不属于A的任意候选首符集但A的某个候选集包含ε时，只有当aFOLLOW(A)，才可能允许A自动匹配。2023/7/21184.4预测分析程序预测分析表的构造FIRST集和FOLLOW集的定义:设G=(VT,VN,S,P)是上下文无关文法

FIRST(α

)={a|α*a,a∈VT,α

,∈V*}

若*=>ε则规定ε∈FRIST()。

FOLLOW(A)={aS*…Aa…且a∈VT}

若S*…A，则#∈FOLLOW(A)。2023/7/2119计算FIRST集方法对于文法符号X1.若XV，则FIRST(X)={X}；2.若XVN，且有产生式Xa…，则把a加入到FIRST(X)中；若X也是一条产生式,则把也加到FIRST(X)中；2023/7/21203.若XY…是一个产生式且YVN，则把FIRST(Y)中的所有非元素都加到FIRST(X)中；若XY1Y2…YK

是一个产生式，Y1,Y2,…,Yi-1都是非终结符，而且，对于任何j,1≤j≤i-1,FIRST(Yj)都含有，则把FIRST(Yj)中的所有非元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)(j=1,2,…,K)均含有，则把加到FRIST(X)中。2023/7/2121计算FOLLOW集方法1.对于文法的开始符号S,置#于FOLLOW(S)中；2.若Ａ→αBβ是一个产生式，则把FIRST(β)\{}加至FOLLOW(B)中；3.若Ａ→αB是一个产生式,或Ａ→

αBβ是一个产生式而β*

(即FIRST(β))，则把FOLLOW(A)，加至FOLLOW(B)中。*2023/7/2122例4.3假设文法G[E]

E→E+T|TT→T*F|FF→(E)|i消除直接左递归

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i

2023/7/2123计算FIRST集和FOLLOW集FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}FOLLOW(E)=FOLLOW(E’)={),#}FOLLOW(T)=FOLLOW(T’)={+,),#}FOLLOW(F)={+,*,),#}2023/7/2124预测分析表构造算法1.对文法G的每个产生式Ａ→执行第二步和第三步；2.对每个终结符aFIRST()，把Ａ→

加至[A,a]中，3.若FIRST()，则对任何bFOLLOW(A)，把Ａ→

加至[A,b]中，4.把所有无定义的[A,a]标上“出错标志”。2023/7/2125i+*()$EE→TE’E→TE’E’E’→+TE’E’→εE’→ε

TT→FT’T→FT’T’T’→ε

T→*FT’T’→ε

T’→ε

FF→i

F→(E)文法G[E]的LL(1)预测分析表2023/7/2126

栈STACK用于存放文法符号。分析开始时，栈底先放一个‘＃’，然后，放进文法开始符号。同时，假定输入串之后也总有一个‘＃’，标志输入串结束。预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a行事的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：(1)若X＝a＝‘＃’，则宣布分析成功，停止分析过程。(2)若X＝a¹‘＃’，则把X从STACK栈顶逐出，让a指向下一个输入符号。*预测分析器的结构2023/7/2127

(3)若X是一个非终结符，则查看分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X逐出STACK栈顶，然后，把产生式的右部符号串按反序一一推进STACK栈（若右部符号为e，则意味不推什么东西进栈）。在把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作（目前暂且不管）。若M[A，a]中存放着“出错标志”，则调用出错诊察程序ERROR。*2023/7/21预测分析器的结构如图所示输入a+b#预测分析控制程序分析表M输出(采选用的产生式)栈XYZ#2023/7/2129预测分析控制程序：置ip指向ω#的第一个符号repeat

令X是栈顶符号,a是ip所指向的符号;ifX

是一个终结符号或#thenifX=athen

把X从栈中弹出,并且更新ipelseerror()else/*X是非终结符号*/ifM[X,a]=XY1Y2....Ykthenbegin

把X从栈中弹出;

把Yk,Yk-1,....,Y1压入栈中,即Y1在顶上;

输出产生式XY1Y2....Yk

endelseerror()untilX=#/*栈为空*/2023/7/2130#E#E’T#E’T’F#E’T’i#E’T’#E’#E’T+#E’T#E’T’F#E’T’id#E’T’F*#E’T’F#E’T’i#E’T’#E’##i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i####E→TE’T→FT’F→iT’→εE’→+TE’T→FT’F→iT’→*FT’F→iT’→εE’→ε符号栈输入串所用产生式字符串i+i*i的分析过程2023/7/2131

若文法G分析表不含多重定义入口，则称其为LL(1)文法。

一个文法是LL(1)文法充分必要条件：一个文法G是LL(1)的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式Ａ→αβ，下面的条件成立：１.FIRST(α)∩FIRST(β)=；２.假若β

，那么，FIRST(α)∩FOLLOW(A)＝。LL(1)文法是无二义的．*2023/7/2132例4.4考虑文法G[S]

S(L)|a

LL,S|S消除左递归后的文法为G[S]

S(L)|a

LSL

L,SL|2023/7/2133构造FIRST

和FOLLOW集合FIRST(S)={(,a}FIRST(L)={(,a}FIRST(L)={,,}FOLLOW(S)={#,)}FOLLOW(L)={)}FOLLOW(L)={)}2023/7/21(),a#SS(L)SaLLSLLSLLLL

,SL构造文法的LL(1)分析表LL(1)分析表2023/7/21354.5递归下降分析将一个非终结符A的文法规则看作识别A的过程的定义。•文法中的每个非终结符号对应一个递归过程。

•根据输入句子的当前单词，确定所用的产生式。当存在多个候选产生式时，采用试探法，试错了则回溯。

•对于产生式右部的终结符号，则将其与输入单词匹配；对于产生式右部的非终结符号，则调用相应的递归过程。

•重复以上过程，构造关于输入句子的最左推导。2023/7/2136例4.5为下述表达式文法构造递归下降程序。

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iprocedureE;beginT;E’end;procedureE’;begin

ifsym=‘+’then

beginadvance;T;E’

endend;2023/7/2137p