上下文無關文法與推導

起始符號(start symbol)

每個故事都有第一句話,每個推導都有第一個符號。起始符號是你在生成字串時「總是」從之開始的那個被指定的佔位符。沒有它,你不會知道該先套用哪些規則;有了它,整個文法就從單一種子萌發。

形式上,在上下文無關文法 (V, Σ, R, S) 中,起始符號 S 是變數集合 V 中一個被選定的元素。要生成語言中的任何字串,你都從單獨的 S 開始,套用產生式規則直到只剩終端符號。依一般慣例,起始符號命名為 S;當文法寫成規則清單時,它就是最最開頭那條規則左側的變數。文法的語言被定義為恰好是「從 S」可推導出的終端字串所成的集合——從任何其他變數開始的推導不算入該語言。

選擇起始符號很重要,因為它確定了「一個完整程式」或「一個完整表達式」的意義:它應該是其範疇即你想生成的整體的那個非終端符號(對程式語言而言,類似 Program)。在證明與構造中(例如把文法化為喬姆斯基正規形式時)有個有用的技巧:引入一個全新的起始符號 S0 並加上規則 S0 → S,使起始符號永不出現在任何右側——這能避開麻煩的特例。

在 S → a S a | b S b | ε 中,起始符號是 S。每個推導都從 S => ... 開始;例如 S => aSa => abSba => abba,所以「abba」在語言中。從 S 以外的任何符號開始的推導都不能定義該語言。

起始符號是每個推導生長所自的單一種子;語言就是從它可推導出的字串。

起始符號永遠是變數(非終端符號),絕非終端符號。語言是相對於它而定義的:從其他變數可推導出的字串不屬於該文法的語言。

又稱
start variablesentence symbol起始變數開始符號