上下文無關文法與推導

非終端符號(nonterminal symbol)

如果終端符號是牆上的成品磚塊,那麼非終端符號就是藍圖上的標籤——「這裡放一扇窗」、「那裡放一段牆」。非終端符號是一個佔位符,代表一「整類」尚待填入的子結構,而非任何單一的最終符號。建造字串就是反覆展開這些標籤,直到一個都不剩。

形式上,非終端符號恰好是上下文無關文法 (V, Σ, R, S) 中的變數 V。每個非終端符號都出現在一條或多條產生式規則的左側,說明它可以如何被展開,它也可以出現在右側(包括出現在自己的規則裡,這正是遞迴的來由)。非終端符號永遠不是成品字串的一部分;除非每個非終端符號都被重寫成終端符號,否則推導尚未完成。把每個非終端符號讀成一個有意義的語法範疇會很有幫助:在某語言的文法中,你可能有名為 Expr、Term、Statement、Block 的變數——各自生成所有合法表達式、項、敘述或區塊所成的集合。

依慣例,非終端符號寫成大寫字母(或在 BNF 中寫成帶角括號的名稱如 <expr>),以與終端符號區別。起始符號就是你每次推導都從之開始的那個被指定的非終端符號。設計文法在很大程度上就是選對非終端符號的藝術:每個都應捕捉一種連貫的子片語,而它們之間的遞迴正是讓有限規則集得以描述無限、巢狀語言的關鍵。

在 Expr → Expr + Term | Term、Term → Term * Factor | Factor、Factor → ( Expr ) | id 中,非終端符號是 Expr、Term、Factor;各自命名一個語法範疇,而 Expr 生成所有合法的表達式。

非終端符號是整類子結構的佔位符;字串完成前,每一個都必須被重寫掉。

「非終端符號」、「變數」與「語法範疇」指的是同一件事。非終端符號永不出現在最終生成的字串中——若有殘留,純粹表示推導尚未完成。

又称
nonterminalvariablesyntactic category非終結符變數