文法定义中的“终结符号”和“非终结符号”

文法定义中的“终结符号”和“非终结符号”

这篇文章是个人理解

可能有人看相关书籍时对此有疑惑，什么叫“终结符号”，什么叫“非终结符号”，怎么就终结了，终结了什么，怎么就非终结了，不终结什么

这也是我写这篇文章的目的

上下文无关文法(CFG)

先看一段来自“Compilers Principes, Techniques, & Tools”中译本《编译原理》中对“文法”的定义

文法定义：

一个上下文无关文法(context-free grammar, CFG)由四个元素组成

1. 一个终结符号集合，它们有时也称为“词法单元”。终结符号是该文法所定义的语言的基本符号的集合

2. 一个非终结符号集合，它们有时也称为“语法变量”。每个非终结符号表示一个终结符号串的集合。我们将在后面介绍这种表示方法。

3. 一个产生式集合，其中每个产生式包括一个称为产生式头部或左部的非终结符号，一个箭头，和一个称为产生式体或右部的由非终结符号及非终结符号组成的序列。产生式主要用来表示某个构造的某种书写形式。如果产生式头部非终结符号代表一个构造，那么该产生式体就代表了该构造的一种书写方式。

4. 指定一个非终结符号为开始符号

以上是所有的书面描述，这四条定义都怎么理解呢？

先画个表，文法的所有元素的集合

所谓“开始”符号，只是非终结符号中的一员，因此我们将其归入非终结符号的集合就可以了

其实这里CFG文法的定义中，最重要的概念是“产生式”，它就像（而且作用也类似）外语学习时句子里的谓语，有了谓语，才好理解整个句子的意思

产生式是做什么用的？就是不断把自己左边的东西变成右边的东西

考虑到文章读者基本都是汉语汉字使用者，基本都有英语英文字母基础，所以这里避开使用汉字或者英文字母举例，以避免和现实的状况产生联系

假如定义一个产生式的作用是将日语平假名“产生”成为俄语俄文（这样字形差异比较大），那么我们说如下的形式是一个符合这个定义中的产生式

1

にほんご→японский

那么它的作用就是在文段中不断地替换，将左边的内容替换成右边的内容

左边的这种平假名组成的串都得替换，而右边的这样的西里尔字母串属于转换的目的，就不必再替换了

然而，实际上下面的式子也是一个产生式（当然这里就不太符合这两种语言文字的词法了）

1
2

にほんご→японご
ご→ский

为什么第一个产生式中一个平假名跑到右边去成为了“产生”的结果了呢？“产生”不是将俄语俄文翻译为日语平假名吗

因为只有西里尔字母只能出现在右边，可从来没说过假名不能出现在右边——假名既可以出现在左边，也可以出现在右边

但是为什么呢？

带着这个疑惑，现在聊一聊终结符号和非终结符号

所谓“终结符号”，就是不可再“产生”的符号，就是产生的“目的”，而“非终结符号”，可能是“产生”的开始，也可能是“产生”的中间产物，由于非终结符号到终结符号的关系，或者说翻译规则可能过于复杂，不能直接写出所有非终结符号到终结符号的产生式，只能第一步，先将非终结符号“产生”成为非终结符号和终结符号混在一起的形式，然后在后续的步骤中逐渐将所有的非终结符号替换成为或者说“产生”成为终结符号

最后，定义中所谓的“开始符号”，其实就是一个特殊的非终结符号，因为总得有一个起点，而且也只能从“开始符号变成第一个非终结符号(和/或)终结符号”开始，从这里继续下去去书写其它的产生式

因此，总的来说，要理解什么是“终结符号”和“非终结符号”，首先需要理解什么是“产生式”

先理解了“产生式”这个“谓语”，那么“非终结符号”和“终结符号”这两个“宾语”就好理解了

以上均为个人理解，欢迎勘误

上下文有关文法(CSG)

这一部分是扩展，在2023年4月4日新增。

在词法分析中，只需要使用正规式就足够应对各种工作，对应的自动机模型是有限自动机(有限自动机包括NFA和DFA，需要先设计NFA，再将NFA转化为DFA，并将DFA最小化才可以使用)。

而在语法分析中，仅仅用正规式这样的模型是不足以描述语言的，这时候需要引入文法，进行语法分析时一般使用上下文无关文法(Content Free Grammar)，对应的自动机模型是下推自动机。

这些都与本文的主题无关，与本文主题有关的是，既然定义了“上下文无关文法”，那么一定有与之对应的“上下文有关文法”。

确实如此，虽然不会用它，但是我们得知道那是什么东西。

上文中说，“终结符号”是转换的目的，其实留了一点东西没有提，那就是“有没有情况允许终结符号位于产生式的左边”？

对于上下文无关文法来说，产生式头部，也即左边不允许出现终结符号。

但是对于上下文有关文法，产生式头部是会出现终结符号的，这些终结符号并不会被产生式推导展开，但是，出现在左边的终结符号会影响这个产生式的适用范围，这也是上下文有关文法何以与上下文“有关”。

这里用外语找例子不太好找，只能用字母来进行表示了

引用一下维基百科的例子

正规的非上下文无关语言{ }可由以下上下文有关文法生成:

1
2
3
4
5
6
7
8
9

S → aSBC
S → aBC
CB → HB
HB → HC
HC → BC
aB → ab
bB → bb
bC → bc
cC → cc

这个文法中的a,b,c作为终结符号却出现在了左侧，因此它们就限制了与之组合的、作为产生式头部的非终结符号能够表示含义的场景；

非终结符号B的含义受到了同侧的终结符号a,b的限制；非终结符号C的含义受到了同侧终结符号b,c的限制；

不过这个例子也不是特别地好，待我再找找(搁置中)

总而言之，在文法中，终结符号有时可以出现在左侧，例如短语文法、上下文有关文法中都是可以这么做的

但是，属于文法范畴的上下文无关文法这个种类的文法中，任何情况下都不允许终结符号出现在产生式左侧

Knighthana

2023/03/29