文档介绍：第三章上下文无关文法与上下文无关语言
上下文无关文法的重要性:
拥有足够强的表达力来表示大多数程序设计语言的语法
可以构造有效的分析算法来检验一个给定的字符串是否是由某个上下文无关文法产生。
上下文无关语言在实践中有重要意义:
1)定义程序设计语言:
BNF(巴克斯-诺尔范式);
2)描述文档格式:
XML,HTML;
3)使语法分析概念形式化;
4)简化程序设计语言的翻译:
语法分析器的设计;
给定文法G,如果对于G中的任意产生式ν→ω,而ν只是一个非终结符,即A→ω,A∈V,ω∈(∑UV)*,则称文法G为上下文无关文法(简称无关文法)。如果一个语言能由一个无关文法产生,则称这个语言是上下文无关语言(简称无关语言)。
定义3-1 线性的无关文法
若无关文法G=(∑,V,S,P) 的
所有产生式都是下列形式之一:
A→uBv 或 A →w;
其中:A,B∈V;u,v∈∑+;w∈∑*。
该文法称为线性的无关文法。
注意: u,v可以有一个为空串ε。
特别地,
如果u=ε,称为左线性的(无关)文法;
如果v=ε,称为右线性的(无关)文法。
从定义可以看出,线性的无关文法是受限制的无关文法;本身一定还是无关文法。
化简的上下文无关文法
左线性文法和右线性文法是线性文法中
特殊的两类。
定理3-2 G=(∑,V,S,P)是一个上下文无关文法,产生式的一般形式为A→w,其中: w∈(∑UV)* ,
则存在另一个等价的线性的无关文法G1,而G1中产生式的形式为;
A→a 或 A→aβb。
其中: A∈V;a,b∈∑U{ε} ;β∈V+。
证明:
读者自己完成。
定理3-3 G=(∑,V,S,P)是一个上下文无关文法,产生式的一般形式为A→w,其中:w∈(∑UV)*,则存在另一个等价的无关文法G1,而G1中产生式的形式为;
A→a 或 A→aB 或 A→aBC。
其中:A ,B,C∈V;a∈∑{ε} 。
证明: 读者自己完成。
消除无关文法中的无用非终结符号
定义3-4 文法中的无用符号
一个无关文法G,符号Y∈V,如果不出现在任何形如S=>*uYv=>*uwv的推导之中,称Y为文法G的无用非终结符。
其中:u ,w ,v ∈∑*。