习题课(第十三周).ppt

习题课 语法分析方法 自上而下分析 LL（1）分析法 递归下降分析法 预测分析法 自下而上分析 算符优先分析法 LR分析法 2. E→TE; E→+E | ? ; T→FT ; T →T | ? ; F→PF ; F→ *F |? ; P→(E)|a|b|? FIRST(E) = FIRST(E) = FIRST(T) = FIRST(T) = FIRST(F) = FIRST(F) = FIRST(P) = FIRST(TE) = FIRST(+E) = FIRST(FT) = FIRST(PF) = FIRST(*F) = FIRST((E)) = 2. E→TE; E→+E | ? ; T→FT ; T →T | ? ; F→PF ; F→ *F |? ; P→(E)|a|b|? FIRST(E) = { (, a,b, ? }; FIRST(E) = { +, ?} FIRST(T) = { (, a,b, ? }; FIRST(T) = { (, a,b, ?, ?}; FIRST(F) = { (, a,b, ? }; FIRST(F) = { *, ?} FIRST(P) = { (, a,b, ? }; 该文法： （1）不存在左递归； （2）非终结符的各个产生式的候选首符集两两不相交； （3）计算FIRST(A)∩ FOLLOW(A) ： FIRST(E) ∩ FOLLOW(E) = { +, ?} ∩{ # , ) }= Φ FIRST(T) ∩ FOLLOW(T) = { (, a,b, ?, ?} ∩ {+, # , ) } = Φ FIRST(F) ∩ FOLLOW(F) = { *, ?} { (, a,b, ?, +, # , ) } = Φ 满足LL(1)文法的三个条件，所以该文法G为LL(1)文法。 第五章 作业 P133 1 2 3 5(1)(2) 1. G1（E）: E→E+T│T T→T*F│F F→ i │(E) 证明E+T*F是它的一个句型，指出该句型的所有短语，直接短语和句柄 G2：S→a│ ? │(T) T →T,S│S (1)(a,(a,a)) S ?(T) ?(T,S) ?(a,S) ?(a,(T)) ?(a,(T,S)) ?(a,(S,S)) ?(a,(a,S)) ?(a,(a,a)) S ?(T) ?(T,S) ?(T,S) ?(S,(T)) ?(S,(T,S)) ?(S,(T,a)) ?(S,(S,a)) ?(S,(a,a)) ?(a,(a,a)) G2：S→a│ ? │(T); T →T,S│S (((a,a), ?,(a)),a) FIRSTVT主程序: BEGIN FOR 每个非终结符P和终结符a DO F[P,a] := FALSE; FOR 每个形如P→a… 或P→Qa … 的产生式 DO INSERT (P, a); WHILE STACK非空 DO BEGIN 把STACK 的顶项 (Q, a) 弹出; FOR 每条形如P→Q … 的产生式 DO INSERT (P, a); END OF WHILE; END 构造优先关系表算法 FOR 每条产生式P→X1X2…Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置Xi = Xi+1 IF i?n-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置Xi = Xi+2； IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置 Xi a； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 a Xi+1 END 输入串(a,(a,a))的算法优先分析过程 5. 文法G(S)： S→AS|b A→SA|a 该文法的LR(0)项目有： 1. S→·AS 2. S→A