32语言和文法 325消除二义性 smt→ if expr then stmt if expr then stmt else stmt I other 句型: if expr then if expr then stmt else stmt 两个最左推导 stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt ifexpr then if expr then stmt else stmt
3.2 语言和文法 3.2.5 消除二义性 stmt → if expr then stmt | if expr then stmt else stmt | other • 句型：if expr then if expr then stmt else stmt • 两个最左推导： stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt
32语言和文法 无二义的文法 stmt→) matched stmt J unmatched stmt matched stmt>if expr then matched stmt else matched stmt l other unmatched stmt->if expr then stmt I if expr then matched stmt else unmatched stmt
3.2 语言和文法 • 无二义的文法 stmt → matched _stmt | unmatched_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then stmt | if expr then matched_stmt else unmatched_stmt
32语言和文法 32.6消除左递归 文法左递归 A→→+Ac 直接左递归 AAaB 串的特点 Ba...a 消除直接左递归 A→BA A→aA
3.2 语言和文法 3.2.6 消除左递归 • 文法左递归 A+A • 直接左递归 A→A |b – 串的特点 b . . . • 消除直接左递归 A → b A A→ A |
32语言和文法 例算术表达文法 E→E+TT (T+T.+T) T→T*FF (F*F.*F) F→(E)id 消除左递归后文法 E→TE E→+TEE T→FT′ T→*FT'8 F→>(E)id
3.2 语言和文法 • 例 算术表达文法 E → E + T | T （ T + T . . . + T ） T → T F | F （ F F . . . F ） F → ( E ) | id 消除左递归后文法 E → TE E → + TE | T → FT T → F T | F → ( E ) | id
32语言和文法 非直接左递归 S→>Aa|b A→Sl|e 先变换成直接左递归 S→>Aa|b A→Aad|bd 再消除左递归 S→Aa|b A→bA|A A→adAy|E
3.2 语言和文法 • 非直接左递归 S → Aa | b A → Sd | • 先变换成直接左递归 S → Aa | b A → Aad | bd | • 再消除左递归 S → Aa | b A → bd A | A A → adA |