第三章 上下文无关文法与上下文无关语言 ●上下文无关文法的重要性: ●拥有足够强的表达力来表示大多数程序设计语 言的语法 ●可以构造有效的分析算法来检验一个给定的字 符串是否是由某个上下文无关文法产生
第三章 上下文无关文法与上下文无关语言 ⚫ 上下文无关文法的重要性： ⚫ 拥有足够强的表达力来表示大多数程序设计语 言的语法 ⚫ 可以构造有效的分析算法来检验一个给定的字 符串是否是由某个上下文无关文法产生
上下文无关语言在实践中有重要意义: ●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=ε，称为右线性的(无关)文法。 ⚫ 从定义可以看出，线性的无关文法是受 限制的无关文法；本身一定还是无关文 法