)句法分析
自上而下的剖析 这种剖析是“面向目标”的，从起始符S出发，利用产生式再写句型中的非终止符,以尝试逐步地匹配输入符号串x。若对某一阶段的子目标（x的一个前缀）匹配失败，就必须回溯，再进行其他尝试。如果一切尝试都已失败，则可断言x不属于 L(G)。例如，设G由产生式：①S→aSbS，②S→aS，③S→c规定,且输入符号串x=acbc,则对x的自上而下剖析过程如图1,依次利用产生式①、②、③,就可由 S出发导出x。这相当于自上而下地构成x的派生树（图2），剖析方法由此得名。
句法分析
句法分析
句法分析CYK剖析算法
这种算法是J.科克(Cocke)、D.H.杨格 (Younge)和 T.卡萨米(Kasami)三人于1967年前后各自独立地发现的，并以他们的姓的第一个字母命名。当上下文无关文法G 处于乔姆斯基范式，即产生式的形式为A ─→BC和A ─→α 时，可用CYK算法对输入符号串x=a1a2…an进行句法分析。具体步骤是构造一个三角形的表 T={tij|1≤i≤n+1-j，j=1,2…,n}，其中 ti1＝｛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 是否属于t1n来确定x是否属于L(G)。例如,设G由产生式s─→As，s─→b，A─→sA，A─→a规定,且输入符号串x=abab,则表T 如图4。因s∈t14，故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.
