编译原理课件：第四章 语法分析 (2).pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 上节复习 例 E ? E + E | E ? E | (E ) | ? E | id 最左推导 E ? lm ?E ? lm ?(E) ? lm ?(E + E) ? lm ?(id + E) ?lm ?(id + id) 最右推导 E ? rm ?E ? rm ?(E) ? rm ?(E + E) ? rm ?(E + id) ?rm ?(id + id) 上节复习 二义性 E ? E ? E E ? E + E ? id ? E ? E ? E +E ? id ? E + E ? id ? E + E ? id ? id + E ? id ? id + E ? id ? id + id ? id ? id + id 两棵不同的语法树 E E E * + E E id id id E E id E * + E E id id 上节复习 正则式和上下文无关文法的比较 正则式 (a|b)*ab 文法 A0 ? a A0 | b A0 | a A1 A1 ? b A2 A2 ? ? 1 2 开始 a 0 a b b 4.2 语言和文法 4.2.6 消除左递归 消除左递归 A ? A α | β A ? β R R ? α R | ε 4.2 语言和文法 4.2.6 消除左递归 文法左递归 A?+Aa 直接左递归 A?Aa |b 串的特点 ba . . . a 消除直接左递归 A ? b A? A?? a A? | ? 4.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 4.2 语言和文法 非直接左递归 S ? Aa | b A ? Sd | ? 先变换成直接左递归 S ? Aa | b A ? Aad | bd | ? 再消除左递归 S ? Aa | b A ? bd A? | A? A? ? adA? | ? 4.2 语言和文法 4.2.7 提左因子 有左因子的文法 A ???1 | ??2 提左因子 A ? ? A? A? ? ?1 | ?2 4.2 语言和文法 例 悬空else的文法 stmt ? if expr then stmt else stmt | if expr then stmt | other 提左因子 stmt ? if expr then stmt optional_else_part | other optional_else_part ? else stmt | ? 4.2 语言和文法 4.2.8 非上下文无关的语言构造 L1 = {wcw | w属于(a | b)*} 标识符的声明应先于其引用的抽象 L2 = {anbmcndm | n ? 0, m ? 0} 形参个数和实参个数应该相同的抽象 L3 = {anbncn | n ? 0} 早先排版描述的一个现象的抽象 b e g i n：5个字母键，5个回退键，5个下划线键 4.2 语言和文法 L1?= {wcwR | w?(a|b)*} S ? aSa | bSb | c L2? = {anbmcmdn | n ? 1, m ? 1} S ? aSd | aAd A ? bAc | bc L 2?? = {anbncmdm | n ? 1，m ? 1} S ? AB A ? aAb | ab B ? cBd | cd 4.2 语言和文法 L3? ={anbn | n ? 1} S ? aSb | ab L3?是不能用正则式描述的语言的一个范例 若存在接受L3? 的DFA D，状态数为k个 设D读完?, a, aa, …, ak 分别到达状态s0, s1, …, sk 至少有两个状态相同，例如是si和sj，则ajbi属于L3? si … f s0 标记为ai的路径 标记为bi的路径 标记为aj ? i的路径 … … 4.2 语言和文法 4