終結符與非終結符

終結符和非終結符在電腦科學和語言學的领域是用來指定推導規則的元素。在某個形式語法之中，終結符和非終結符是兩個不交的集合。

終結符

終結符是一個形式語言的基本符號。就是說，它們能在一個形式語法的推導規則的輸入或輸出字符串存在，而且它們不能被分解成更小的單位。確切地說，一個語法的規則不能改變終結符。例如說，下面的語法有兩個規則：

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 （页面存档备份，存于互联网档案馆）