发表于: 更新于: 浏览: 22

上下文无关文法

上下文无关文法是指一种语法范畴独立于环境的文法。例如，自然语言中很多句子都需要根据语境分析意思，而数学语句不需要。
在计算机语言学科中，一般提到文法，指的就是上下文无关文法。

上下文无关文法的形式表示

上下文无关文法 G 的四元表达式：

G=(V,Σ,P,S)

文法生成的语言表示为 L(G)，是一系列称为句子的符号串集合。
V 是一组非终结符的集合，\Sigma 是一组终结符的集合，P 是一个起始符号，S 是一组生成式。
非终结符可以理解为文法在生成句子时使用的中间符号。
句子是由文法生成的只包终结符的符号串，而包含了非终结符的符号串则称为句型。
起始符号属于非终结符，是文法推导的起点。
生成式是一种推导规则，左边是一个非终结符，右边是由非终结符和终结符组合成的符号串（也可以是空串 \epsilon）。
在研究中，习惯上我们使用大写字母 A,B,... 表示非终结符，小写字母 a,b,... 表示终结符。
举个例子:

S→A\\ A→aA|B\\ B→bB|\epsilon

这个文法能生成 \{a^nb^m|n,m\geq0\} 其中，B→bB|\epsilon 可以表示 B→bB 和 B→\epsilon 的组合。
为了对句子的结构进行确定性分析，推导时我们往往只考虑最左推导和最右推导。最左推导指的是在推导过程中，每次只对符号串的最左侧非终结符进行替换。最右推导则是从最右侧。

语法分析树

在文法推导时，可以用一张树形图表示推导过程。这种树形图被称为语法分析树，或者语法树。

         S
        / \
       A   B
      /   / \
     a   C   d
         |
         b

文法的二义性

如果一个文法 G，在它生成的语言 L(G) 中，有一个句子，能够通过两个及以上不同的推导得到，那么就说文法 G 具有二义性，文法 G 是一个二义文法。
对于一个程序语言，我们一般希望它的文法是无二义的。因为我们一般需要一个句子有唯一的解析方法。
然而，人们已经证明，无法通过算法在有限步内证明一个文法是否具有二义性，即文法的二义性不可判定。我们能做的只有为无二义性寻找一组充分条件，并依据他们构造文法：

  1. 文法不包含 P->P 这种形式的产生式
  2. 每个非终结符 P 都有作用，即一定存在一个句型包含 P，也就是从起始符号 S 开始，有推导 S\stackrel{*}{\implies}\alpha P\beta。
  3. 每个非终结符 P 都存在一个终结符串 \lambda 使得 P\stackrel{+}{\implies}\lambda。

正规文法

正规文法是一种特殊的文法，要求文法满足：
任何产生式都形如 A → B\alpha 或 A → \alpha (A → \alpha B 或 A → \alpha)。
其中生成式形如 A → B\alpha 或 A → \alpha 的正规文法称为左线性正规文法，另一种则是右线性文法.
正规文法的句子可以用正规式表达。