32语言和文法 327提左因子 有左因子的文法 A→>0B1a/2 提左因子 A→aA A→B1|62
3.2 语言和文法 3.2.7 提左因子 • 有左因子的文法 A →b1 | b2 • 提左因子 A → A A → b 1 | b 2
32语言和文法 例悬空ele的文法 stmt-> if expr then stmt else stmt l if expr then stmt I other 提左因子 stmt>if expr then stmt optional else part I 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 |
32语言和文法 328非上下文无关的语言构造 L1={ wCw w属于(a|b)} 标识符的声明应先于其引用的抽象 L2={"b"c"tmn≥0,m≥0} 形参个数和实参个数应该相同的抽象 L3={"b"c"|n≥0} 早先排版描述的一个现象的抽象 begin: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个下划线键
32语言和文法 L1={wew|w∈(ab) S→>aSa|bSb|c L2={ memon|n≥1,m≥1 S→>aSda4d A→ bAc bc L2"={m" bcmd|n≥1,m≥1 S→AB A→4bmb B→>CBd|cd
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
32语言和文法 L3={"b"|n≥1} S→>aSb|ab L3是不能用正规式描述的语言的一个范例 若存在接受L3的DFAD,状态数为A个 设D读完e,a,aa,…,mk分别到达状态sp,s1,…,Sk 至少有两个状态相同,例如是s和s,则ab属于 3 标记为d-的路径 标记为ai的路径 标记为b的路径 ●●
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的路径 … …