上下文元关文法和正则表达式 CFG的表达能力更强 每个正则表达式都可以用一个上下文无关文法来描述, 反之不成立 ●每个正则语言都是一个上下文无关语言,反之不成立 正则表达式(ab)*ab等价于文法 A0→aA0|bAo|aA1 A b a A,→bA A
上下文无关文法和正则表达式 CFG的表达能力更强 每个正则表达式都可以用一个上下文无关文法来描述， 反之不成立 每个正则语言都是一个上下文无关语言，反之不成立 正则表达式(a|b)*abb等价于文法 21 Ａ０→ａＡ０｜ｂＡ０｜ａＡ１ Ａ１→ｂＡ２ Ａ２→ｂＡ３ Ａ３→ε
为NFA构造等价文法 1)对于NFA的每个状态i,创建一个非终结符号A; 2)如果状态i有一个在输入a上到达状态j的转换,则加入产生式A→a4。如果状态i在输 入∈上到达状态j,则加入产生式A→4。 3)如果i是一个接受状态,则加入产生式A→∈。 4)如果i是自动机的开始状态,令A;为所得文法的开始符号。 start b b b 22
为NFA构造等价文法 22
上下文无关文法和正则表达式 正则表达式魔下文无关文法√ 上下文无关文法则表达式? L={a"bn>=} ●描述该语言的文法? ●可以用正则表达式描述该语言吗?
上下文无关文法和正则表达式 正则表达式 上下文无关文法 ✔ 上下文无关文法 正则表达式 ？ L={a nb n|n>=1} 描述该语言的文法？ 可以用正则表达式描述该语言吗？
文法及其生成的语言 语言是由文法的开始符号出发,能够推导得到的所有句子 的集合。 文法G:S→aSab, L(G)=a'(a b), i>=o) 文法G:S→ asb ab L(G)={ab,n>=} 文法G:S→(S)S|e L(G)={所有具有对称括号对的串} ●如何验证文法G所确定的语言L 证明G生成的每个串都在L中 证明L中的每个串都能被G生成 实质上回归到了原始的定义,证明采用数学归纳法
文法及其生成的语言 语言是由文法的开始符号出发，能够推导得到的所有句子 的集合。 文法G: S → aS|a|b, L(G)={a i (a|b), i>=0} 文法G：S → aSb|ab L(G)={a nb n , n>=1} 文法G：S → (S)S|ε L(G)={所有具有对称括号对的串} 如何验证文法G所确定的语言L 证明G生成的每个串都在L中 证明L中的每个串都能被G生成 实质上回归到了原始的定义，证明采用数学归纳法 24
文法的设计 ●在进行高效的语法分析之前,需要对文法做以下处理 ●消除二义性 文法的二义性:文法可以为一个句子生成多颗不同的树 消除左递归 左递归:文法中一个非终结符号A使得对某个串a,存在一个 推与A≥A,则称这个文法是左递归的 提取左公因子
文法的设计 在进行高效的语法分析之前，需要对文法做以下处理 消除二义性 文法的二义性：文法可以为一个句子生成多颗不同的树 消除左递归 左递归：文法中一个非终结符号A使得对某个串α，存在一个 推导 ，则称这个文法是左递归的。 提取左公因子 25