上下文无关文法

上下文无关文法的正式定义

上下文无关文法(context-free grammar)，简称文法，由终结符号、非终结符号、一个开始符号、一组产生式组成。

• 终结符号

终结符号是组成串的基本符号。术语“词法单元名”是“终结符号”的同义词。(CRE：终结符号不可再分解)

• 非终结符号

非终结符号是表示串的集合的语法变量。(CRE：非终结符号可以分解)

• 开始符号

一个文法中，一个非终结符号被指定为开始符号。这个符号表示的串集合就是这个文法生成的语言。

• 产生式

一个文法的产生式描述了将终结符号和非终结符号组成串的方法。

推导

将产生式看作重写规则，就可以从推到的角度精确地描述构造语法分析树的方法。从开始符号出发，每个重写步骤把一个非终结符号替换为产生式体。这个推导思想对应自顶向下构造语法分析树的过程，但是推导概念所给出的精确性在讨论自底向上的语法分析过程时尤其有用。

如果S是文法G的开始符号，而S可以通过0步或者多步推导出α，我们说α是G的一个句型(sentential form)。
一个句型可以既可以包含终结符号又可以包含非终结符号，也可以是空串。句子(sentence)是不包含非终结符号的句型。
一个文法生成的语言是它所有句子的集合。可以由文法生成的语言被称为上下文无关语言(context-free language)。

• 最左推导和最右推导

最左推导(left-most derivation)：总是选择每个句型的最左非终结符号。
最右推导(right-most derivation)：总是选择最右边的非终结符号。

语法分析树和推导

语法分析树是推导的图形表示。语法分析树每个内部节点表示一个产生式的应用。

一棵语法分析树的叶子节点的标号可以是非终结符号，也可以是终结符号。从左到右排列这些符号就可以得到一个句型，它称为这棵树的结果(yield)或者边缘(frontier)。

二义性

如果一个文法可以为某个句子生成多颗语法分析树，那么它就是二义性的(ambiguous)。
换句话说，二义性就是对同一个句子有多个最左推导或多个最右推导的文法。

大部分语法分析器都是期望无二义性的。但某些情况下，使用精心选择的二义性文法也可以带来方便。但同时需要使用消二义性规则来抛弃不想要的语法分析树，只留一棵。

※上下文无关语言和正则表达式

文法是比正则表达式表达能力更强的表示方法。

每个可以使用正则表达式描述的构造都可以使用文法描述，但是反之不成立。换句话说，就是每个正则语言都是一个上下文无关语言，反之不成立。

（END）