吉林大学：《编译原理》课程教学资源（PPT课件讲稿）文法例1

文法例1 文法Gz:Z→D Z→zD D→0|11..9 句子12的推导 Z→ZD→DD→1D→12 Z→ZD→DD→D2→12 D D 2

文法例1 文法Gz：Z → D Z → Z D D → 0 |1 |…|9 句子12的推导： Z  ZD DD 1D 12 Z  ZD DD D2 12 Z Z D D 1 2

文法例2 今文法G=({+,*,i,(,)},[E},E,P,其中P为: E→i E→E+E E→E*E E→(E) 句型i*i+i:

文法例2 ❖文法G=({+,*,i,( ,)},{E},E,P),其中P为： ⚫ E → i ⚫ E → E + E ⚫ E → E * E ⚫ E → ( E ) ❖ 句型i * i + i :

推导1 E→E+E→E*E+E→i*E+E ii +e ki + i 推导2 E→E*E→i*E →i*E+E→i*i+E→i*i+i E E E E 推导1的语法树 推导2的语法树

推导1: E  E + E  E * E + E  i * E + E  i * i + E  i * i + i E + E E E * E i i 推导1的语法树 i E E * E E + E i i 推导2的语法树 i 推导2: E  E * E  i * E  i * E + E  i * i + E  i * i + i

else = if then i f then if then then then else <st f语句的二义性

→if then else →if then → ...... 假设有条件语句 if e1 then if e2 then s1 else s2 则可有下图所示的两棵不同的语法分析树： if语句的二义性 if if then then else e1 e2 s1 s2 if then else if then e1 e2 s1 s1

文法二义性的消除 口二义性文法的判定是递归不可解的 消除二义性的方法: 1.设置一规则,该规则可在产生二义 性的情况下,指出哪一个分析树是正确的 2将文法改变成一个强制正确分析树 的构造格式

文法二义性的消除 ❑二义性文法的判定是递归不可解的 ❑消除二义性的方法： ⚫ 1.设置一规则，该规则可在产生二义 性的情况下，指出哪一个分析树是正确的 ⚫ 2.将文法改变成一个强制正确分析树 的构造格式

表达式的无二义性文法 ●E→T ●E→TE+T E→E+T T→FT*F T→T*F °F→(E) ●F→(E) ●F→

表达式的无二义性文法 ⚫ E → T ⚫ E → E + T ⚫ T → F ⚫ T → T * F ⚫ F → ( E ) ⚫ F → i ⚫ E → T | E + T ⚫ T → F | T * F ⚫ F → ( E ) | i

f语句的无二义性文法定义 Stmt → Matched stmt I Unmatched stmt Matched stmt ife then matched stmt else Matched stmt I other Unmatched stmt ife then stmt ife then matched stmt else unmatched stmt

If语句的无二义性文法定义 Stmt → Matched_stmt | Unmatched_stmt Matched_stmt → if E then Matched_stmt else Matched_stmt | other Unmatched_stmt → if E then Stmt | if E then Matched_stmt else Unmatched_stmt

有关文法实用中的一些说明 ●有关文法的实用限制 有害规则U→>U 多余规则[不可到达的,不可终止的 上下文无关文法中的λ规则A→

有关文法实用中的一些说明 ⚫ 有关文法的实用限制 • 有害规则 U → U • 多余规则{ 不可到达的，不可终止的 } ⚫ 上下文无关文法中的规则 A → 

文法Q]: s→Be )23 B→ce B→)Af A→)Ae 5 A→)e 6) c→Cf 7) C→C 8 D→)f

文法G[s]: 1) S → B e 2) B → C e 3) B → A f 4) A → A e 5) A → e 6) C → C f 7) C → C 8) D → f

求能推出λ的非终极符 s Lambda=[A1|A;→∈Pset 对p∈PSet:A→X1…xn 如果X;∈ S Lambda,0≤isn,则 S Lambda = S Lambda U A. 重复第二步,直至 s Lambda收敛为止

求能推出的非终极符 ⚫ S_Lambda = {Aj | Aj →   PSet}; ⚫ 对pPSet：Ap → X1…Xn, 如果XiS_Lambda, 0in，则 S_Lambda = S_Lambda  {Ap} ⚫ 重复第二步，直至S_Lambda收敛为止