終結符與非終結符

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

終結符[編輯]

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

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 （頁面存檔備份，存於網際網路檔案館）