终结符与非终结符

终结符和非终结符在计算机科学和语言学的领域是用来指定推导规则的元素。在某个形式语法之中，终结符和非终结符是两个不交的集合。

终结符

终结符是一个形式语言的基本符号。就是说，它们能在一个形式语法的推导规则的输入或输出字符串存在，而且它们不能被分解成更小的单位。确切地说，一个语法的规则不能改变终结符。例如说，下面的语法有两个规则：

x -> xa
x -> ax

在这种语法之中，a是一个终结符，因为没有规则可以把a变成别的符号。不过，有两个规则可以把x变成别的符号，所以x是非终结符。一个形式语法所推导的形式语言必须完全由终结符构成。

非终结符

非终结符是可以被取代的符号。一个形式文法中必须有一个起始符号；这个起始符号属于非终结符的集合。

在上下文无关文法中，每个推导规则的左边只能有一个非终结符而不能有两个以上的非终结符或终结符。并非所有的语言都可以被上下文无关文法产生。

推导规则

一种语法的定义由推导规则构成。每个规则规定什么词位可以重写为什么别的词位。这些规则可以用来剖析字符串，也可以用来产生字符串。每个规则有左边和右边。左边有可以被取代的字符串，而右边有可以取代左边的字符串。规则的写法一般为左边 $\rightarrow$ 右边。比如，z0 → z1 这个规则规定 z0 可以重写为 z1。左边为一个非终结符，但是右边不一定是个终结符。

例子

下面的形式文法代表一个整数。整数可能是有符号，就是说，可能是负数。下面使用巴科斯范式的变种来表示：

<integer> ::= ['-'] <digit> {<digit>}
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

在这个例子之中，符号 (-,0,1,2,3,4,5,6,7,8,9) 都是终结符，而 <digit> 和 <integer> 都是非终结符。

参见

引用

参考文献

Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Section 2.2 (beginning on p. 42). Note that this section only discusses context-free grammars.
http://osr507doc.sco.com/en/tools/Yacc_specs_symbols.html （页面存档备份，存于互联网档案馆）