3.2语言和文法 3.2.5消除二义性 stt→if expr then stmt if expr then stmt else stmt other 。句型：if expr then if expr then stmt else stmt 两个最左推导： stt→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
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
3.2语言和文法 ·无二义的文法 stnt-→natched 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
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
3.2语言和文法 3.2.6消除左递归 ·文法左递归 A→+AC 。直接左递归 A->Aa B -串的特点 Ba...a 消除直接左递归 A→BA' A'→CA'ε
3.2 语言和文法 3.2.6 消除左递归 • 文法左递归 A+A • 直接左递归 A→A |b – 串的特点 b . . . • 消除直接左递归 A → b A A→ A |
3.2语言和文法 ·例算术表达文法 E→E+TT (T+T...+T T→T*FF (F*F,。,*F F→(E)|id 消除左递归后文法 E→TE' E'→+TEe T→FT T′>*FT'|E F→(E)lid
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
3.2语言和文法 ·非直接左递归 S→Aa|b A→Sdε ·先变换成直接左递归 S→Aa|b A→Aad bd|ε 再消除左递归 S→Aa|b A→bdA'A A'-→adA'e
3.2 语言和文法 • 非直接左递归 S → Aa | b A → Sd | • 先变换成直接左递归 S → Aa | b A → Aad | bd | • 再消除左递归 S → Aa | b A → bd A | A A → adA |