编译原理第4章课件

第四章语法分析—自上而下分析

4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL（1）分析法4.4递归下降分析程序构造(略)4.5预测分析程序4.6LL（1）分析中的错误处理(略)1§4.１语法分析器的功能1、任务：在词法分析识别出单词符号串的 基础上，分析并判定程序的语法 结构是否符合语法规则。2、语法分析器的地位：单词符号取下一单词符号语法分析树符号表词法分析器语法分析器编译程序后续部分源程序2§4.１语法分析器的功能3、本质：按文法的产生式，识别输入符 号串是否为一个句子。4、语法分析方法分类：

自上而下分析法 自下而上分析法 3§4.2自上而下面临的问题一、基本思想：1、自上而下：从文法的开始符号出发，向下 推导，推出句子2、主旨：对任何输入串，试图用一切可能的 办法，从开始符号出发，自上而下 地为输入串建立一棵语法树。4§4.2自上而下面临的问题二、举例： 自上而下方法的分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。5§4.2自上而下面临的问题SxA

ySxAy**SxAy*例：文法SxAy A**|* 输入串α:x*y6§4.2自上而下面临的问题实现上述带回溯试探发的简单途径： 让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。7§4.2自上而下面临的问题三、困难和缺点1、文法的左递归性问题使自上而下的分析过程陷入无限循环2、回溯问题3、虚假匹配难以消除4、当最终报告分析不成功时,难于知道输入串中出错的确切位置5、采用了一种穷尽一切可能的试探法,效率很低,代价极高8§4.３LL(1)分析法一、左递归的消除：1、规则:（直接左递归消除）PPα｜βPPα１|Pα２|…Pαｍ|β１|β２|…|βｎ PβP’ P’αP’|ℇ Pβ1p’|β2P’|…|βnP’ P’α1P’|α2P’|…|αmP’|ℇ9§4.３LL(1)分析法例题：已经文法：ＥＥ+Ｔ｜Ｔ ＴＴ＊Ｆ｜Ｆ Ｆ(Ｅ)｜ｉＥＴＥ’Ｅ’+ＴＥ’｜ℇＴＦＴ’Ｔ’*ＦＴ’｜ℇＦ(Ｅ)|ｉ10§4.３LL(1)分析法２、消除左递归：（１）把文法Ｇ的所有ＶＮ按任一种顺序排列成P1,P2,…,Pn;按此顺序执行；（２）FORi=1TonDo Begin Forj:=1Toi-1Do 把形如PiPjγ的规则改写成 Piδ1γ|δ2γ|…|δkγ 其中Pjδ1|δ2|…|δk是关 于Pj的所有规则； 消除关于Pi规则的直接左递归性 End11§4.３LL(1)分析法（３）化简由（２）所得的文法,即去除那些从开 始符号出发永远无法到达的非终结符的产 生规则例题:（间接左递归）已知文法G:SQc|c QRb|b RSa|a 试消除其左递归?解答12二、消除回溯,提取左因子§4.３LL(1)分析法１、消除回溯必须保证:

对文法的任何非终结符,当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。即：

若此候选获得成功匹配，那么，这种匹配决不会是虚假的； 若此候选无法完成匹配任务，则任何其它候选也肯定无法完成。13§4.３LL(1)分析法例：Ａα１｜α２｜…｜αｎ

设Ａ所面临的第一个输入符号为ａ，若Ａ能根据不同的输入符号指派相应的候选αｉ作为全权代表去执行任务，那就肯定无需回溯。在这里Ａ已不再是让某个候选去试探性地执行任务，而是根据所面临的输入符号ａ准确地指派唯一的一个候选。14§4.３LL(1)分析法２、当不得回溯时，对文法有什么要求？ ∀非终结符Ａ的各个候选的首符集的交集均为空。分析：Ａαfirst(α)={a|α⇒a…,a∈VT} 若α⇒ℇ,则规定ℇ∈first(α)即:first(α)是α的所有可能推导的开头终结符或可能的ℇ。此时，当要求A匹配输入串时，A根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务；这个候选就是那个终结首符集含a的α. **15§4.３LL(1)分析法3、A、事实上，许多文法均存在这样的非终结符，其所有候选的终结首符集并非两两不相交。 例如：语句if条件then语句else语句 if条件then语句B、任何把一个文法改造成任何非终结符的所有 候选首符集两两不相交呢？提取公共左因子16§4.３LL(1)分析法代价:大量引进新的非终结符和ℇ_产生式例：Aδβ1|δβ2|…|δβn|γ1|γ2|…|γm (其中,每个γ不以δ开头)⇒ AδA’|γ1|γ2|…|γm A’β1|β2|…|βn经过反复提取坐因子,就能把每个非终结符(包括新引进者)的所有候选首符集变成两两不相交.17§4.３LL(1)分析法三、分析条件1、当一个文法不含左递归,并且满足每个非终结符的所有候选首符集两两不相交的条件,是不是就一定能进行有效的自上而下分析了呢?18§4.３LL(1)分析法例：文法 EE+T|T TT*F|F F（E）|i经消去直接左递归后变成 ETE’

E’+TE’|ℇ TFT’ T’*FT’|ℇ F（E）｜iＥTE’ＦＴ’+Ｅ’ Ti ℇ ℇ

FＴ’

ｉℇ输入串：ｉ＋ｉ； 如右图所示19§4.３LL(1)分析法２、由上分析是不是就意味着：当非终结符Ａ面临输入符号ａ，且ａ不属于Ａ的任意候选首符集，但Ａ的某个候选首符集包含ℇ时，就一定可以使Ａ自动匹配？分析：只有当ａ是在文法的某个句型中允许跟在Ａ后的终结符时，才可能允许Ａ自动匹配，否则，ａ在这里的出现是一种语法错误。20§4.３LL(1)分析法Follow(A)={a|A⇒…Aa…,a∈VT}若S⇒…A,则规定#∈follow(A)即:follow(A)是所有句型中出现在紧接A之后的终结符或“＃”。当Ａ面临输入符号ａ，且ａ∉first（A），但ℇ∈first（A），只有当a∈first（A）时，才可能允许A自动匹配。 **21§4.３LL(1)分析法3、构造不带回溯的自上而下分析的文法的条件：（1）文法不含左递归（2）文法中每一个非终结符A的各个产生式 的候选首符集两两不相交即：若Aα1|α2|…αn 则first(αi)∩first(αj)=Φ （ｉ≠ｊ）（３）对文法中的每个非终结符Ａ，若它存在某个候 选首符集包含ℇ，则first(A)∩follow(A)=Φ若一个文法G满足以上条件,则称该文法G为LL(1)文法22§4.３LL(1)分析法4、对LL(1)文法,可对其输入串进行有效的无回溯的自上而下分析：Aα1|α2|…|αn对非终结符A进行匹配,此时面临的输入符号为a(1)若a∈first(αi),则指派αi去执行匹配任务(2)若a不属于任何一个候选首符计,则若ℇ∈first(αi

),且a∈follow(A),则让A与ℇ自动匹配否则,a的出现是一种语法错误23§4.5预测分析程序——即LL(１)分析法介绍一、构造First和Follow1、构造First(x)，x∈VT∪VN连续使用下述规则,直至每一个集合First不再增大为止。规则:(1)若X∈VT,则FIRST(X)={X}。(2)若X∈VN,且有产生式Xa…,则把a加入到FIRST(X)中;若Xℇ也是一条产生式,则把ℇ也加到FIRST(X)中。24§4.5预测分析程序——即LL(１)分析法介绍(3)若XY…是一个产生式且Y∈VN,则把FIRST(Y)中的所有非ℇ—元素都加到FIRST(X)中;若XY1Y2…Yk是一个产生式,Y1,…Yi-1都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有ℇ(即Y1…Yi-1⇒ℇ),则FIRST(Yi)中的所有非ℇ—元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj)均含有ℇ,j=1,2,…,k,则把ℇ加到FIRST(X)中。*25§4.5预测分析程序——即LL(１)分析法介绍2、构造Follow(A)，A∈VN连续使用下述规则,直至每一个集合Follow不再增大为止。规则:(1)对于文法的开始符号S,置#于FOLLOW(S)中;(2)若AαBβ是一个产生式,则把FIRST(β)\{ℇ}加至FOLLOW(B)中;(3)若AαB是一个产生式,或AαBβ是一个产生式而β⇒ℇ(即ℇ∈FIRST(β)),则把FOLLOW(A)加至FOLLOW(B)中。26§4.5预测分析程序——即LL(１)分析法介绍举例:对于文法EE+T|T;TT*F|F;F(E)|i我们可构造出每个非终结符的FIRST和FOLLOW集合:FIRST(E)={(，ｉ} FOLLOW(E)={)，＃｝FIRST(E’)={+，ℇ} FOLLOW(E’)={)，＃}FIRST(T)={（，ｉ} FOLLOW(T)={+，），＃}FIRST(T’)={*，ℇ} FOLLOW(T’)={+，），＃}FIRST(F)={（，ｉ} FOLLOW(F)={*，+，），＃}27§4.5预测分析程序——即LL(１)分析法介绍二、构造分析表构造分析表M的算法是:(1)对文法G的每个产生式A执行第2步和第3步;(2)对每个终结符a∈FIRST(α),把Aα加至M[A,a]中;(3)若ℇ∈FIRST(α),则对任何Bfollow(A)把Aα加至M[A,b]中;(4)把所有无定义的M[A,a]标上“出错标志”。28§4.5预测分析程序——即LL(１)分析法介绍举例：文法EE+T|T;TT*F|F;F(E)|i的 LL(1)分析表如下所示i+*()#EETE’ETE’E’E’+TE’E’ℇE’ℇTTFT’TFT