上下文無關文法與推導

句型(sentential form)

建造字串建到一半時,你手上有個半成品:一部分是真正的符號,一部分仍是待展開的佔位符——就像一個填了些字、又留了些空格的句子範本。沿著推導出現的每個這樣的中間字串,就稱為句型。它是施工進行中的一張快照。

形式上,句型是任何可從起始符號推導出的、由終端符號與變數組成的字串:任何滿足 S =>* w 的 w,其中 w 可同時含有兩種符號。最最開頭的句型是單獨的起始符號 S(零步)。再者,若 w 只含終端符號,則稱它為一個句子(或語言中的一個字串)——那些不剩變數的特殊句型,恰好就是所生成語言的成員。所以「句型」是一般概念,而「句子」是完工的特例。

句型是描述推導步驟(每一步把一個句型變成下一個)以及對文法能產生什麼作歸納證明時,自然要談論的對象。一個細化:「左句型」是出現在最左推導中的句型,「右句型」則是出現在最右推導中的句型;這些受限概念在剖析理論中很重要,那裡由下而上的剖析器處理的是右句型。一個常見的口誤是把含有殘留變數的中間字串稱為「句子」——在每個變數都消失之前,它都只是個句型。

以 S → A B、A → a、B → b,推導 S => AB => aB => ab 經過句型 S、AB、aB 與 ab。其中只有「ab」(全為終端符號)是句子;其餘仍含變數。

句型是任何滿足 S =>* w、含終端符號與/或變數的字串;若 w 只含終端符號便是句子。

句型仍可含變數;只有完全由終端符號組成的句型(即「句子」)才屬於該語言。單獨的起始符號 S 本身就是一個句型(零步的那個)。

又称
句式推導中間形式