3.2语言和文法 3.2.7提左因子 ·有左因子的文法 A-→cp,|Cxf3 ·提左因子 A→CA1 A'→E1E2
3.2 语言和文法 3.2.7 提左因子 • 有左因子的文法 A →b1 | b2 • 提左因子 A → A A → b 1 | b 2
3.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
3.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 |
3.2语言和文法 3.2.8非上下文无关的语言构造 ·L,={wcww属于(a|b)} 标识符的声明应先于其引用的抽象 。L2={abmcndm|n≥0，m≥0 形参个数和实参个数应该相同的抽象 ·L3={abcn|n≥0} 早先排版描述的一个现象的抽象 b￡g1卫：5个字母键，5个回退键，5个下划线键
3.2 语言和文法 3.2.8 非上下文无关的语言构造 • L1 = {wcw | w属于(a | b) * } –标识符的声明应先于其引用的抽象 • L2 = {a nb mc nd m | n 0, m 0} –形参个数和实参个数应该相同的抽象 • L3 = {a nb nc n | n 0} –早先排版描述的一个现象的抽象 b e g i n：5个字母键，5个回退键，5个下划线键
3.2语言和文法 ·L,'={wCwR|w∈(4b)} S→aSa bSb|c ·L2'={abmcmd|n≥1，m≥1} S-→aSd aAd A→bAc|bc ·L2"={a"bmemdm n≥1，m≥1 S→AB A→Abb B→cBdcd
3.2 语言和文法 • L1 = {wcwR | w(a|b) * } S → aSa | bSb | c • L2 = {a nb mc md n | n 1, m 1} S → aSd | aAd A → bAc | bc • L 2 = {a nb nc md m | n 1，m 1} S → AB A → aAb | ab B → cBd | cd
3.2语言和文法 。L3'={abm|n≥1} S→aSb|ab ·L3'是不能用正规式描述的语言的一个范例 若存在接受L3'的DFAD,状态数为k个 设D读完8，a,aa,,ak分别到达状态S,S1,,S 至少有两个状态相同，例如是s,和s,则b属于 标记为d-的路径 标记为a的路径 标记为b的路径 So
3.2 语言和文法 • L3 ={a nb n | n 1} S → aSb | ab • L3 是不能用正规式描述的语言的一个范例 – 若存在接受L3 的DFA D，状态数为k个 – 设D读完, a, aa, …, a k 分别到达状态s0 , s1 , …, sk –至少有两个状态相同，例如是si和sj，则a jb i属于 L3 si … f s0 标记为a i的路径 标记为b i的路径 标记为a j − i的路径 … …