集合,兩種符號,分類,程式文法,
集合
為了從數學上進行分析，可以把一種語言看成是由有限個字母按照一定的文法規則從左到右線性排列組成的鏈的集合。這有限個字母組成字母表∑。由∑中的符號（字母）可能形成的所有的鏈的集合(包括長度為0的鏈)用∑*表示。既然一種語言是由一定的文法所產生,它只能是∑*的一個子集。考察英文句子“The girl walksgracefully“，從句法上分析,可以看成由下列步驟所形成：
〈句子〉─→〈名詞短語〉〈動詞短語〉─→〈冠詞〉〈名詞〉〈動詞短語〉─→ The〈名詞〉〈動詞短語〉─→The girl〈動詞短語〉─→The girl〈動詞〉<副詞>─→The girl walks<副詞>─→The girl walksgracefully 其中“─→”的意思是“能夠重寫”，即用“─→”右邊的符號代替“─→”左邊的符號。從符號〈句子〉出發，使用一系列重寫規則可得到所需要的句子。對於上面的例子，重寫規則是
〈句子〉─→〈名詞短語〉〈動詞短語〉
〈名詞短語〉─→〈冠詞〉〈名詞〉
〈動詞短語〉─→〈動詞〉〈副詞〉
〈冠詞〉─→The
〈名詞〉─→girl
〈動詞〉─→walks
〈副詞〉─→gracefully
兩種符號
這裡用了兩種不同性質的符號，帶有〈·〉的符號在最後的句子中並不出現，因此它們所組成的集合稱為非終止符集N，N={〈句子〉,〈名詞短語〉,〈冠詞〉,〈名詞〉，〈動詞〉，〈副詞〉}，而在最後句子中出現的符號組成的集合稱為終止符集,亦即字母表∑，∑={The,girl,walks,gracefully}。非終止符集中的〈句子〉在導出整個句子的過程中有特殊的意義,稱為起始符S。因此產生一種語言的文法G可以用四元組表示，即G={∑，N，P，S}，其中P 是形式為α ─→β的重寫規則或稱產生式規則的集合。產生式規則中的α 和β是由非終止符和終止符所組成的鏈，但α 中至少包含N 中的一個符號。
分類
按照產生式α─→β的不同形式,可把文法分成四種類型。產生式的兩端無任何限制的為0型文法，產生0型語言或稱遞歸可數語言。在產生式兩端加上一些限制，又可分為三類文法：①上下文敏感文法(1型)α1Aα2─→α1βα2，只有當非終止符A的前後為α1、α2的條件下,A才可以改寫成β。②上下文無關文法（2型）,產生式的形式是 A─→β,左端為一個非終止符,右端沒有限制。前面所述七條產生式規則就是這種文法的例子。上下文無關文法通過導出樹產生句子。產生“The girl walks gracefully”的導出樹（見圖）。③有限狀態文法或正則文法（3型）,產生式規則為A─→ɑB和A─→a兩種形式。其中A,B為非終止符,a是終止符。從0型文法到3型文法，在產生式規則上的限制形式是逐步增加的，所以它們所對應的語言有包含關係,即0型文法所產生的遞歸可數集真包含上下文敏感語言，上下文敏感語言真包含除了空鏈以外的上下文無關語言,上下文無關語言真包含3型文法產生的正則集。這四種類型的文法所產生的語言可被相應的自動機所接受（見語言識別器）。
程式文法
此外為了增加上下文無關文法的描述能力而又避免在用上下文敏感文法時所存在的分析上的困難，又提出上下文無關文法的改型文法──上下文無關程式文法和上下文無關附標文法。程式文法的特點是在導出過程中對中間鏈用了一個產生式後，下一次再用哪一條產生式要受到限制，因此每個產生式都有一個標號，一個作為核心的重寫規則以及稱為成功區和失敗區的兩個標號集合。假使在導出過程中使用某條產生式成功，就要從該產生式的成功區中去找使用下一條產生式的標號，如果該產生式不能用於該鏈，就要從它的失敗區中去找下一個產生式的標號。這種上下文無關程式語言是上下文敏感語言的真子集，且真包含上下文無關語言。附標文法是通過引入附標產生式的有限集來擴大上下文無關文法的描述能力的。附標文法所對應的語言真包含上下文無關語言而且是上下文敏感語言的一個真子集。
把模式的產生和描述與語言的產生和描述加以比較，借鑑語言的句法結構對模式進行處理和識別，從而在短語結構文法的基礎上，便發展形成模式識別的一個重要分支──句法模式識別（見結構模式識別）。
