[拼音]：jufa fenxi

[外文]：syntax ysis

判断一个句子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=a1a2…an进行句法分析。具体步骤是构造一个三角形的表 T={tij|1≤i≤n+1-j，j=1,2…,n}，其中 ti1＝｛A|若A─→ai是G的产生式｝，i＝1,…，n，且当 1厄尔利剖析算法

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

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

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

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

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

（5）对Ij-1中每个形如[A─→α·ɑj&gam ;，i]的项目.把[A─→αɑj&gam ;，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)。

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

严正声明：本文由历史百科网注册或游客用户宇姻自行上传发布关于» 句法分析的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：宇姻；本文链接：https://www.freedefine.cn/wenzhan/34453.html