补充资料：句法分析

    　　判断一个句子x是否符合给定句法的过程,也是检验x是否属于给定文法G所生成语言L(G)的过程。句法分析又称剖析。一类模式由文法G所描述也就是对x表示的模式的识别过程。因此，各种句法分析方法均可作为模式识别手段。当G为正则文法时,句法分析一般借助于有限自动机，看 x是否为相应的自动机所接受（见语言识别器）。当G为上下文无关文法时,实现句法分析可用各种剖析算法，其中主要的有自上而下的剖析、自下而上的剖析、CYK剖析算法和厄尔利剖析算法等。但G为上下文敏感文法或 O型文法时，还没有高效率的句法分析方法（见短语结构文法）。
　　
　　自上而下的剖析 　这种剖析是"面向目标"的，从起始符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₁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≤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，其步骤如下：
　　
　　① 令j=0。对P 中每个形如s─→α 的产生式,把项目[s-→·α,0]添加到I₀中。
　　
　　② 若[B─→β·，i]在 I_j中,则对 I_i中每个形如[A─→α·Bγ，k]的项目,把[A─→αβ·γ，k]添加到I_j中，这里 i≤j。
　　
　　③ 若[A─→α·Bγ，i]在I_j中,则对P中每个形如B─→β的产生式,把项目[B─→·β，j]添加到I_j中。
　　
　　④ 重复第2步和第3步，直到没有新项目可添加到I_j中为止。然后，若j=n则终止，否则用j＋1代替j并执行下一步。
　　
　　⑤ 对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)。
　　
　　对于模式识别来说，句法分析是对输入模式的识别过程，也是对输入模式的结构进行分析的过程。由于它的重要性，除了上述方法外，不少研究者针对不同形式的文法进行了大量的工作，并已取得了不少有益的成果。
　　
　　参考书目
　　　A.V.Aho and J.D.Ullman，The Theory of Parsing, Tranlation　and　Compiling，Vol.1，Prentice-Hall, Englewood Cliffs, N.J., 1972.