电子科技大学：《形式语言与自动机》第三章 上下文无关文法与上下文无关语言

第三章 上下文无关文法与上下文无关语言 ●上下文无关文法的重要性: ●拥有足够强的表达力来表示大多数程序设计语 言的语法 ●可以构造有效的分析算法来检验一个给定的字 符串是否是由某个上下文无关文法产生

第三章 上下文无关文法与上下文无关语言 ⚫ 上下文无关文法的重要性： ⚫ 拥有足够强的表达力来表示大多数程序设计语 言的语法 ⚫ 可以构造有效的分析算法来检验一个给定的字 符串是否是由某个上下文无关文法产生

上下文无关语言在实践中有重要意义: ●1)定义程序设计语言: ●BNF(巴克斯-诺尔范式); 2)描述文档格式: ●XML,HTML; ●3)使语法分析概念形式化; ●4)简化程序设计语言的翻译: 语法分析器的设计;

⚫ 上下文无关语言在实践中有重要意义： ⚫ 1）定义程序设计语言: ⚫ BNF（巴克斯-诺尔范式）； ⚫ 2）描述文档格式: ⚫ XML，HTML； ⚫ 3）使语法分析概念形式化； ⚫ 4）简化程序设计语言的翻译: ⚫ 语法分析器的设计；

●给定文法G,如果对于G中的任意产生式v→>, 而v只是一个非终结符,即A→U,A∈V U∈(∑UV)’,则称文法G为上下文无关文法(简 称无关文法)。如果一个语言能由一个无关文法 产生,则称这个语言是上下文无关语言(简称无 关语言)

⚫ 给定文法G，如果对于G中的任意产生式ν→ω， 而 ν 只 是 一 个 非 终 结 符 ， 即 A→ω ， A∈V ， ω∈(∑UV）* ，则称文法G为上下文无关文法（简 称无关文法）。如果一个语言能由一个无关文法 产生，则称这个语言是上下文无关语言（简称无 关语言）

定义3-1线性的无关文法 ●若无关文法G=(∑,VS,P)的 所有产生式都是下列形式之一: A→UBv或A→W; 其中:A,B∈V;u,V∈∑+;w∈∑。 该文法称为线性的无关文法。 ●注意:u,V可以有一个为空串E

定义3-1 线性的无关文法 ⚫ 若无关文法G=(∑,V,S,P) 的 所有产生式都是下列形式之一： ⚫ A→uBv 或 A →w； ⚫ 其中:A，B∈V；u，v∈∑+；w∈∑* 。 ⚫ 该文法称为线性的无关文法。 ⚫ 注意： u，v可以有一个为空串ε

●特别地, 如果U=E,称为左线性的(无关)文法; 如果v=ε,称为右线性的(无关)文法 从定义可以看出,线性的无关文法是受 限制的无关文法;本身一定还是无关文 法

⚫ 特别地， 如果u=ε，称为左线性的(无关)文法； 如果v=ε，称为右线性的(无关)文法。 ⚫ 从定义可以看出，线性的无关文法是受 限制的无关文法；本身一定还是无关文 法

化简的上下文无关文法 ●左线性文法和右线性文法是线性文法中 特殊的两类

化简的上下文无关文法 ⚫ 左线性文法和右线性文法是线性文法中 特殊的两类

●定理32G=(∑,V,S,P)是一个上下文 无关文法,产生式的一般形式为A→W,其中 W∈(xUV)·, 则存在另一个等价的线性的无关文法G1,而 G1中产生式的形式为; A>a或A-aβb 其中:A∈v;a,b∈∑u{e};β∈v

⚫ 定理3-2 G=（∑，V，S，P）是一个上下文 无关文法，产生式的一般形式为A→w，其中： w∈（∑UV）* ， ⚫ 则存在另一个等价的线性的无关文法G1，而 G1中产生式的形式为； ⚫ A→a 或 A→aβb。 ⚫ 其中: A∈V；a，b∈∑U{ε} ；β∈V+

●证明: 读者自己完成

⚫ 证明： ⚫ 读者自己完成

定理33G=(∑,V,s,P)是一个上下文 无关文法,产生式的一般形式为A→W,其 中:w∈(∑Uv)‘,则存在另一个等价的无 关文法G1,而G1中产生式的形式为; A→a或A→aB或A→aBC。 其中:A,B,cev;a∈∑{} ●证明:读者自己完成

⚫ 定理3-3 G=（∑，V，S，P）是一个上下文 无关文法，产生式的一般形式为A→w，其 中：w∈（∑UV）* ，则存在另一个等价的无 关文法G1，而G1中产生式的形式为； ⚫ A→a 或 A→aB 或 A→aBC。 ⚫ 其中：A ，B，C∈V；a∈∑ {ε} 。 ⚫证明： 读者自己完成

3.1消除无关文法中的无用非终结符号 定义3-4文法中的无用符号 个无关文法G,符号Y∈V,如果不出 现在任何形如S=>uY=>uW的推导 之中,称Y为文法G的无用非终结符。 其中:u,W,V∈∑

3.1 消除无关文法中的无用非终结符号 ⚫ 定义3-4 文法中的无用符号 ⚫ 一个无关文法G,符号Y∈V,如果不出 现在任何形如S=>*uYv=>* uwv的推导 之中，称Y为文法G的无用非终结符。 ⚫ 其中：u ，w ，v ∈∑*