[拼音]：jufa fenxi

[外文]：syntax analysis

判断一个句子x是否符合给定句法的过程,也是检验x是否属于给定文法G所生成语言L(G)的过程。句法分析又称剖析。一类模式由文法G所描述也就是对x表示的模式的识别过程。因此，各种句法分析方法均可作为模式识别手段。当G为正则文法时,句法分析一般借助于有限自动机，看 x是否为相应的自动机所接受（见语言识别器）。当G为上下文无关文法时,实现句法分析可用各种剖析算法，其中主要的有自上而下的剖析、自下而上的剖析、CYK剖析算法和厄尔利剖析算法等。但G为上下文敏感文法或 O型文法时，还没有高效率的句法分析方法（见短语结构文法）。

这种剖析是“面向目标”的，从起始符S出发，利用产生式再写句型中的非终止符,以尝试逐步地匹配输入符号串x。若对某一阶段的子目标（x的一个前缀）匹配失败，就必须回溯，再进行其他尝试。如果一切尝试都已失败，则可断言x不属于 L(G)。例如，设G由产生式：

（1）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），故称自下而上的剖析方法。

这种算法是J.科克(Cocke)、D.H.杨格 (Younge)和 T.卡萨米(Kasami)三人于1967年前后各自独立地发现的，并以他们的姓的第一个字母命名。当上下文无关文法G 处于乔姆斯基范式，即产生式的形式为A ─→BC和A ─→α 时，可用CYK算法对输入符号串x=a₁a₂…a_n进行句法分析。具体步骤是构造一个三角形的表 T={t_ij|1≤i≤n+1-j，j=1,2…,n}，其中 t_i1＝｛A|若A─→a_i是G的产生式｝，i＝1,…，n，且当 1<j≤n时,t_ij＝｛A|若有某个k,1≤k≤j使B∈t_ik ,C∈t_i+k，_j-k,且A─→BC是G的产生式｝，1≤i≤n＋1-j。在构造好表T 以后，由起始符S 是否属于t_1n来确定x是否属于L(G)。例如,设G由产生式s─→As，s─→b，A─→sA，A─→a规定,且输入符号串x=abab,则表T 如图4。因s∈t₁₄，故x∈L(G)。

这种算法是J.厄尔利于1968年提出的，是对一切上下文无关文法G=(N，∑，P，S)都适用的高效率句法分析方法。当输入符号串x=a₁a₂…a_n时,先构造剖析表列I₀，I₁，…，I_n，其步骤如下：

（1）令j=0。对P 中每个形如s─→α 的产生式,把项目[s-→·α,0]添加到I₀中。

（2）若[B─→β·，i]在 I_j中,则对 I_i中每个形如[A─→α·Bγ，k]的项目,把[A─→αβ·γ，k]添加到I_j中，这里 i≤j。

（3）若[A─→α·Bγ，i]在I_j中,则对P中每个形如B─→β的产生式,把项目[B─→·β，j]添加到I_j中。

（4）重复第2步和第3步，直到没有新项目可添加到I_j中为止。然后，若j=n则终止，否则用j＋1代替j并执行下一步。

（5）对I_j-1中每个形如[A─→α·ɑ_jγ，i]的项目.把[A─→αɑ_jγ，i]添加到I_j中。转到第2步。在剖析表列I₀，I₁，…,I_n构造完毕后,由项目[S─→α·,0]是否属于I_n来确定x是否属于L(G)。例如,设G由产生式S─→SA，S─→A，A─→ɑA，A─→b规定且输入符号串x=bab,则其剖析表列是

I₀　　　　　　　　　　 I₁

[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]

I₂　　　　　　　　　　 I₃

[A-→a·A,1] [A-→b·,2]

[A-→·ɑA,2]　　　　[A-→ɑA·,1]

[A-→·b,2]　　　　 [S-→SA·,0]因[S─→SA·,0]属于I₃，故x属于L(G)。

对于模式识别来说，句法分析是对输入模式的识别过程，也是对输入模式的结构进行分析的过程。由于它的重要性，除了上述方法外，不少研究者针对不同形式的文法进行了大量的工作，并已取得了不少有益的成果。

参考书目

1. A.V.Aho and J.D.Ullman，The Theory of Parsing, Tranlation　and　Compiling，Vol.1，Prentice-Hall, Englewood Cliffs, N.J., 1972.