判斷一個句子x是否符合給定句法的過程,也是檢驗x是否屬於給定文法G所生成語言L(G)的過程。句法分析又稱剖析。一類模式由文法G所描述也就是對x表示的模式的識別過程。因此，各種句法分析方法均可作為模式識別手段。當
自上而下的剖析 這種剖析是“面向目標”的，從起始符S出發，利用產生式再寫句型中的非終止符,以嘗試逐步地匹配輸入符號串x。若對某一階段的子目標（x的一個前綴）匹配失敗，就必須回溯，再進行其他嘗試。如果一切嘗試都已失敗，則可斷言x不屬於 L(G)。例如，設G由產生式：①S→aSbS，②S→aS，③S→c規定,且輸入符號串x=acbc,則對x的自上而下剖析過程如圖1,依次利用產生式①、②、③,就可由 S出發導出x。這相當於自上而下地構成x的派生樹（圖2），剖析方法由此得名。
自下而上的剖析 與自上而下的剖析過程相反，這是從輸入符號串x開始,嘗試用產生式左端的非終止符代換句型中的句柄（即與產生式右端相同的子串），以期逐步達到將x縮為起始符S的目標。若某一階段的嘗試失敗,也需要回溯並進行其他嘗試。如果一切嘗試失敗,就可以斷言x不屬於L(G)。例如,以從左到右的次序代換句型中的句柄，對輸入字符串x=acbc用前述文法進行自下而上的剖析，其過程如圖3。由此可見,依次利用產生式③、②、①，可將x逐步縮減到S。這相當於自下而上地構造x的導出樹（圖2），故稱自下而上的剖析方法。
CYK剖析算法
這種算法是J.科克(Cocke)、D.H.楊格 (Younge)和 T.卡薩米(Kasami)三人於1967年前後各自獨立地發現的，並以他們的姓的第一個字母命名。當上下文無關文法
G 處於喬姆斯基范式，即產生式的形式為
A ─→
BC和
A ─→
α 時，可用CYK算法對輸入符號串
x=
a
1
a
2…
a
n進行句法分析。具體步驟是構造一個三角形的表
T={
tij|1≤
i≤
n+1-
j，j=1,2…,
n}，其中
ti
1＝｛
A|若
A─→
ai是
G的產生式｝，
i＝1,…，
n，且當 1＜
j≤
n時,
tij＝｛
A|若有某個
k,1≤
k≤
j使
B∈
tik ,C∈
ti
+
k，j
-
k,且
A─→
BC是
G的產生式｝，1≤
i≤
n＋1-
j。在構造好表
T 以後，由起始符
S 是否屬於
t
1
n來確定
x是否屬於
L(
G)。例如,設
G由產生式
s─→
As，s─→
b，A─→
sA，A─→
a規定,且輸入符號串
x=
abab,則表
T 如圖4。因
s∈
t
14，故
x∈
L(
G)。
厄爾利剖析算法 這種算法是J.厄爾利於1968年提出的，是對一切上下文無關文法G=(N，∑，P，S)都適用的高效率句法分析方法。當輸入符號串x=a1a2…an時,先構造剖析表列I0，I1，…，In，其步驟如下：
① 令j=0。對P 中每個形如s─→α 的產生式,把項目[s-→·α,0]添加到I0中。
② 若[B─→β·，i]在 Ij中,則對 Ii中每個形如[A─→α·Bγ，k]的項目,把[A─→αβ·γ，k]添加到Ij中，這裡 i≤j。
③ 若[A─→α·Bγ，i]在Ij中,則對P中每個形如B─→β的產生式,把項目[B─→·β，j]添加到Ij中。
④ 重復第2步和第3步，直到沒有新項目可添加到Ij中為止。然後，若j=n則終止，否則用j＋1代替j並執行下一步。
⑤ 對Ij-1中每個形如[A─→α·ɑjγ，i]的項目.把[A─→αɑjγ，i]添加到Ij中。轉到第2步。在剖析表列I0，I1，…,In構造完畢後,由項目[S─→α·,0]是否屬於In來確定x是否屬於L(G)。例如,設G由產生式S─→SA，S─→A，A─→ɑA，A─→b規定且輸入符號串x=bab,則其剖析表列是
I0 I1
[S-→·SA,0] [A-→b·,0]
[S-→·A,0] [S-→A·,0]
[A-→·ɑA,0] [S-→S·A,0]
[A-→·b,0] [A-→·ɑA,1]
[A-→·b,1]
I2 I3
[A-→a·A,1] [A-→b·,2]
[A-→·ɑA,2] [A-→ɑA·,1]
[A-→·b,2] [S-→SA·,0]
因[S─→SA·,0]屬於I3，故x屬於L(G)。
對於模式識別來說，句法分析是對輸入模式的識別過程，也是對輸入模式的結構進行分析的過程。由於它的重要性，除瞭上述方法外，不少研究者針對不同形式的文法進行瞭大量的工作，並已取得瞭不少有益的成果。
參考書目
A.V.Aho and J.D.Ullman，The Theory of Parsing, Tranlation and Compiling，Vol.1，Prentice-Hall, Englewood Cliffs, N.J., 1972.