大三下课程编译原理

12式语言与自动机第3章词法分析 第4章语法分析 ——自上而下分析第5章语法分析 ——自下而上分析6中间代码生成78码优化Ch4Ch4语法第4章语法分析(Syntax——自上而下分析LL(1)分析法与LL(1)分析2Ch4Ch4语法分 语法分析程序综语法分析综上而下分析下而上3Ch4语法分 语法分析程序综

语法分析程序的功源程序

语法分析 yzer

源程源程

源程序语法分语法分

分析语义分中语义分中间代码Ch4Ch4语法分 语法分析程序综 给给定文法G和字符串(∈VT*)，检查、判定∈L(G)？即检查、判定是否是文法G所能产生的合法的句子告和处5源程序串（L1）源语言的文法

Ch4语法分 语法分析程序综 Ch4语法分 语法分析程序综 6Ch4Ch4语法分 语法分析程序综上而下分析下而上7Ch4语法分 语法分析程序综 语法分析方.非终结符进行替换(推导)，逐步推导出r。式进行推导，逐步使推导结果与r8Ch4Ch4语法分 语法分析程序综 语法分析方例 设有文法G和输入rG：S→A→BaA|B→+|–|*| 分析方式1(推导S=>aA=>aBaA=> =>=> => =r9CCh4 分析树的从左到右叶结点=r，则r∈L(G)S→A→BaA|B→+|–|*|

r10Ch4Ch4语法分 语法分析程序综上而下分析下而上11Ch4语法分 语法分析程序综 语法分析方式进行匹配，直到归约到G的S为止。12Ch4语法分 语法分析程序综 语法分析方.非终结符进行替换(推导)，逐步推导出r。式进行推导，逐步使推导结果与r匹配13Ch4语法分 语法分析程序综 语法分析方二.自下而上语法分析式进行匹配，直到归约到G的S为止。14 G：S→aAA→BaA|B→+|-|*|

SABAABAB上A下Ar *a+aCh4Ch4语法分 语法分析程序综 语法分析方15 G：S→aAA→BaA|B→+|–|*| 分析方式2(推导r=a*a+a<=<=aBaBaε<=<=aBaA<=aA<=

SAAABAB *a+aABABCh4Ch4语法分 语法分析程序综 语法分析方16Ch4语法分 4.1语法分析程序综 语法分析两大类方自上而下分析法； r(一般、递归下降、自下而上分析法rReduceS(一般S-R、OPG、 17Ch4Ch4语法第4章语法分析(Syntax——自上而下分析LL(1)分析法与LL(1)分析18Ch4Ch4语法分析 不确定的自上而下分析19例

S→A→ab

r=Ch4语法分析Ch4语法分析 不确定的自上而下分析法 一般自上而下分析 20S→S→A→ab

a

r=Ch4Ch4语法分析 不确定的自上而下分析法 一般自上而下分析 分析的本质是一种带回溯的自上而下分析,21Ch4Ch4语法分析 不确定的自上而下分析法 一般自上而下分析 I→I0r：按照自按照自上而下分析输入串r产生分析树，对终结符的替换使分析休止的延伸，使自析陷入死循环 …22…Ch4Ch4语法分析 不确定的自上而下分析23不确定性的假匹 回G的左递 无止境的匹提 因

消除G的左递24一.消除文法的 A +假定关于非终结符P 其中，不以P不分析：P→P不P→PP→P′→假定关于非终结符P 其中，不以P把P的规则改写成如下等价的非直接左PPP′→27例 设有简单表达式文法E→E+E|E*E|（E）|对G(E)消除二义性后，得到文法G'(E)E→E+T|T→T*F|F→(E)|E→TE′EE→TE′E′→+TE′|εT→FT′T′→*FT′|εF→(E)|i假定关于非终结符PP→P1|P2|…|Pn|β1|β2|…其中，每个i不等于 ,…,βn不以PPPP′→1P′|2P′|…|29例 设有文法I→I0|Ia|Ib|a|对左递归文法G改写后的文法G′II→aI'|bII'→0I'|aI'|bI'30间接左递归的消除：A→Ba|B→Cb|C→Ac|经若干步推导替换，有A=>Ba=>Cba=>B=>Cb=>Acb=>C=>Ac=>Bac=>31用消除直接左递归的方法改写P+>P的推导）且不含以ε为右部的产生式32算法4.1除文法左递给定文法①对文法Ｇ的所有非终结符按任一种顺序排列例如A1，A2，…，An。消除A1中的直接左递②for(i=1;i=n;i++{for(j=1;j=i-1;j++{Ai其中Aj→δ1│δ2│……│δk是关于Aj的全部规}消除Ai规则中的直接左递归③简34 令文法G(A)的非终结符排序为C，B，A对于C，不存在直接左递归，把C代入BB的规G(A):A→Ba|B→Cb|C→Ac|代换后的B不含直接左递归，将其代入的规则变A→A存在直接左递归，消除A的直接左递A→dAbaA′|caA′|bBA′A′→cbaA′|ε35文法G(A)改写A→dAbaA′|caA′|bBA′A′→cbaA′|εBCC→Ac|无左递归的等价文法G′(A)为A→dAbaA′|A′→B36 对于B，候选式中不包含A不存在直接G(A):A→Ba|B→Cb|C→Ac|将A，B带入C，代换后的C的规则变为C→C→C存在直接左递归，消除C的直接左递C→cacC′|bBcC′|dAC′C′→bacC′|ε37→Ba|→Cb|C→cacC′|bBcC′|dAC′C′→bacC′|ε二.消除P→1|2|…| 当前前输入ai匹配成功则替换，否则选2，依此类39定义FIRST()={a|>a……，a∈VT,则ε∈FIRST()不带回溯的条件：(充分非必要式，设为： A→1|2|…|n如果它的每个候选式i均不存在i的情况而且FIRST(i)两两彼此互不相40式设为：A→1|2|…|满足不带回溯则据当前扫描单词a，若a∈FIRST(i)其中i是1…n中之一，选取A→进行41计算FIRST(X)(XV)的算法描述为构造FIRST(X)可反复应用如下规1、若X是终结符,则2、若X是非终结符，且XX1X2Xk是一个产生式②若对于某个i，aFIRST(Xi)且X1X2Xi－1，则③若对于所有的j＝1，2，，k，FIRST(Xj)将加到FIRST(X)42计算FIRST()(V*)的算法描设=X1X2Xk1、FIRST(X1)中的所有终结符号加到FIRST()2、若对于某个i，aFIRST(Xi)且X1X2Xi－1，43计算FIRST(X)(XV)的算法描述为构造FIRST(X)可反复应用如下规1、若X是终结符,则、X的、X的FIRST为其所有候选式的FIRST集合的并集44例

设有文法S→Ap|A→a|B→b|对 FIRST(Ap∩对 FIRST(a∩对 FIRST(b∩45若给出r=cap,则有S

r:capr:

S→Ap|A→a|B→b| r:46对非终结符A的多个候选式的FIRST(i)的相互两若有文法A→δβ1|δβ2|…|彼此交集≠Φ，一般是因为i中有公共左因子若有文法A→δβ1|δβ2|…|δ(β1|β2|…|可可以使用下面规则改写文法Ｇ为AA′→β1|β2|…|47若文法G2(1|2|…|mA→11|12|…|1n|22(1|2|…|m1(1|2|…|n A→δ1A'A'→β1|β2|…|βn48Ch4Ch4第4章语法分析(Syntax——自上而下分析LL(1)分析法与LL(1)分析49ch4语法分 一个VN的分析程序。(将一个非终结符的文 递归下降分析器对文法要求：LL(1对文法的每个非终结符号，都根据其产50ch4ch4语法分 例 设有文法G(E)E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→(E)|i文法G(Ｅ)的递归51E()主程{E()主程{T;E′({if{n++;T;E’;}F({if(c=‘i’)elseif(c=‘(’{n++;if(c=‘)’)elseelseT→*FT|εF→(E)|ich44.3TT({F;T′({if(c=‘*’){n++;F;T′}cch44.3T→FTT→*FT|εF→(E)|iTTFT

查查ii+i*ipoppopi+i+i*iT匹配E',Push匹配E',Pushcch44.3Ti+Ti+i*i查TTFpop匹配匹配i,popTi+i*iT

i+i*i分析完成匹配T',Push匹配T',PushE→+TE|εT→FTT→*FT|εF→(E)|iTFpopT,匹配i,popT,匹配i,popT

54cch44.3r1=（+iTPushPushT

查查E→+TE|εT→FTT→*FT|εF→(E)|i（+iE'T'E'T'匹配popF,Push)E)TpopE,PushE'TT55ch4语法分 E‘T’）E'（+i查E‘T’)E'T'（+iE→+TE T→FTT→*FT F→(E)|（+i分析完成56—状态状态图构造：为文法G的每个建立1个初态和1个终态(函数返回态为每个产生式Ax1x2xn建立从初态到终态的路径，弧标记为x1，x2…，xn；12**其中12ch4语法分 ch4语法分 E'→+TE'

0

1T 1Tε23ch4ch4语法分 开始处于图的初态t在某状态tT S TSAt当前输入符号为a，分析器扫描指针+1，进入tSAt tttS S若直接进入t状态，扫描指针不变5812通过状态图的化简来化简递归下降分12例如，E 1Tε23E 1Tε23T

0

入E′的FA的开 1T2ε3ch4ch4语法分 0 0 1359ch4ch4语法分 0T10T1+2 3E′代入E+0T1ε2*3F4ε5F：(7E8)9iEE→E'→+TE'|εT→FT′T'→F→（E）|60Ch4Ch4第4章语法分析(Syntax——自上而下分析LL(1)分析法与LL(1)分析61ch4ch4语法分析4.4LL(1)分析法与LL(1)分析LL(1)分析法与LL(1)LL(1)LL(1)关于LL(1)62ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结LL

预测在分析中最多向前看1个输入字扫描模式：自 63ch4ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结LL(1)分析器的逻#X总控（分#X总控（分析表#…输…总控 64ch4ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结分析#S句子界#S句子界符(栈底标志文法开始符65文法的一条产生式规则(候选式唯一出错（空白

文法的 M(A1,a1) …文法

预测分析函ch4ch4语法分析4.4LL(1)分析法与LL(1)4.4.1LL(1)分析器66算法#S初始化工作#S

pa1a2…anch4ch4语法分析4.4LL(1)分析法与LL(1)4.4.1LL(1)分析器的结①X＝ai＝“＃”，表示分析成功，停止分析67ch4语法分析4.4LL(1)分析法与LL(1)4.4.1LL(1)分析器的结若Ｘ∈ＶN，则查分析表。此时对Ｍ(X,①若Ｍ(Ｘ,ai)中为一个产生式规则，则将X从 出)。②若Ｍ(Ｘ,ai)中为空白，表示出错，可法出错处理子程序68例 设有文法E’→+TE’│ε

ch4ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结69 文法G(E)的LL(1)分析+*()#ETFF→返 返回 第701#E步 分析1#E#E#E’T’#E#Eid#E#E#E#E#E’T’#E#E56789

idid

ch4ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结表下71表下ch4ch4语法分析4.4LL(1)分析法与LL(1)分析器4.4.1LL(1)分析器的结表表#E #E #E #E T##分析成#E##分析成72ch4ch4语法分析4.4LL(1)分析法与LL(1)分析LL(1)分析法与LL(1)LL(1)LL(1)关于LL(1)73LL(1)分析LL(1)分析器构造关 分析表的构分析表的构造关 预测函74第一种情式形如A→且没=>ε的情况，则产生对 则A若a∈FIRST()，那么要匹配输入单词a时，Ｍ(A，a)={A→75Ｍ(A，a)前例

设有文法S→Ap|A→a|B→b|对 FIRST(Ap∩对 FIRST(a对B FIRST(b77S→Ap| A→a|对S：FIRST(Ap)={a,c}对A：FIRST(a)={a}

B→b|对B文法G的LL(1)分析abcdpqSAB若有ε∈FIRST()怎么办？此时aFIRST()时并不一定78定义FOLLOW(A)＝｛a|S>…Aa…，a∈VTS*>…A，句型中，能够紧跟着A之后的一切终结符“＃”79构造FOLLOW集方算法对文法的开始符S，令＃∈FOLLOW(S)②若文法G中有形如A→Bβ的规则，且β≠ε，③若G中有形ABABβ的规则80例 设有文法G[S]为S→AB|bCB→ε|aDD→aS|

A→ε|bC→AD|b据算法4.3计算文法G[S]所有VN的FOLLOW#由规则S→AB|bCFOLLOW(S)FOLLOW(B)；FOLLOW(S)FOLLOW(A)；FOLLOW(S)FOLLOW(C)；FIRST(B){}FOLLOW(A)

FOLLOW(B)={#}；81

FOLLOW(B)={#}；

S→AB|bCA→ε|bFOLLOW(B)

B→ε|aDC→AD|bD→aS|由规则C→AD|b得

FOLLOW(B)FOLLOW(C)FOLLOW(D)，FIRST(D){}FOLLOW(A), FOLLOW(B)={#}；FOLLOW(A)={#，a，c}，FOLLOW(C)＝{#}FOLLOW(D)所有的FOLLOW集合无变化 S→AB|A→ε|FOLLOW(B)B→ε|C→AD| |所以上面的即为最后求得的FOLLOW832.构造FOLLOW集方法二——W和。⑵从开始符号S的FOLLOW(S)结点到”#”⑶如果文法中有产生式A→BX,当X∈VN时，则从结点到FIRST(X)结点连一条弧，当X∈VT时，则与X相连⑷如果文法中有产生式A→Bβ,且>,则从FOLLOW(B)结点FOLLOW(A)结点连一条箭则与X1相连;当X1∈VN时,从FIRST(A)到FIRST(X1)结点连一条箭)84

#

S→AB|bCA→ε|bB→ε|aDC→AD|b |c

85 所以分析表的构造A→|且和均不推出ε，则可产生LL(1)分析表的A行对a∈FIRST()，a列即Ｍ(A，a)={A→86设对文法G求出FIRST和FOLLOW，对A1| 如果满则惟一候选为若a∈FIRST(1)M(AaA1；若b∈FIRST(2)或b∈FOLLOW(A)，则置M(AbA2

87分=>…Aa…，a∈ＶT｝b∈FOLLOW(A)则必有=>…Ab…(b∈ＶT S=*>…Ab…由于对文法规则存在A→2，A自动获得匹 中才可能从栈中退掉A。88算法 LL(1)分析表构{ifa∈FIRSTγi)置Ｍ(AaA→γi ε∈FIRST(γifor置Ｍ(AbA→γi}89前例 设有文法E’→+TE’│εF→(E)│i对E：FIRST(TE(，i对T：FIRST(FT’(，i对F：FIRST((E))={( FIRST(i)={i∩=90 对E’：FIRST(TEE→E'→FIRST(ε)={εFOLLOW(E’)={#,)T→T'→ F→（E）|满足：+}ε}∪对T’FIRST(*FT’*FIRST(ε)={ε}FOLLOW(T’)={#,),+}满足：{*}ε}∪91 E'→+TE'|ε:FIRST(+TE’)={+}FIRST(ε)={ε}FOLLOW(E’)={#,)T→FT’:FIRST(FTT'→*FT'|ε:FIRST(*FT’)={*}FIRST(ε)={ε}FOLLOW(T’)={#,),+F→(E)|i FIRST(i文法G(E)的LL(1)分析+*()i#ETFF→92ch4ch44.3r1=（+iE→+TEE→+TE|εT→FTT→*FT|εF→(E)|i（+iE'T )E'T'PushTTE'T'E'T'匹配popF,Push)E)TpopE)TpopE,PushE'popT,PushTT）T93#TF##TF#E#T#T)E（#T)Ech4语法分 文法G(E)的LL(1)分析+*()i#ETFF→r1=（+i 94例 设有文法S→iCtSS’│aS’→eS│εＣ→对S：FIRST(iCtSSiFIRST(a)={a对 FIRST(eS)={e对CFIRST(bbFIRST(ε)={ε} FIRST(eS)∩(FIRST(ε)对CFIRST(bb95S→iCtSS’│a:FIRST(iCtSS’)={i} FIRST(a)={a}S’→eS│ε:FIRST(eS)={e} Ｃ→b: FIRST(b)={b}文法G(S)的LL(1abeit#abeit#SS S’→C C多重

96ch4ch4语法分析4.4LL(1)分析法与LL(1)LL(1)分析法与LL(1)LL(1)LL(