欢迎光临四川沃锐官网
建筑资质代办一站式服务平台

句法分析

[拼音]: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)SaSbS,②SaS,③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 ─→BCA ─→α 时,可用CYK算法对输入符号串x=a1a2an进行句法分析。具体步骤是构造一个三角形的表 T={tij|1≤in+1-j,j=1,2…,n},其中 ti1={A|若A─→aiG的产生式},i=1,…,n,且当 1<jn时,tij={A|若有某个k,1≤kj使Btik ,C∈ti+kjk,且A─→BCG的产生式},1≤in+1-j。在构造好表T 以后,由起始符S 是否属于t1n来确定x是否属于L(G)。例如,设G由产生式s─→As,s─→b,A─→sA,A─→a规定,且输入符号串x=abab,则表T 如图4。因st14,故xL(G)。

厄尔利剖析算法

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

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

(2)若[B─→β・,i]在 Ij中,则对 Ii中每个形如[A─→αBγ,k]的项目,把[A─→αβγ,k]添加到Ij中,这里 ij

(3)若[A─→αBγ,i]在Ij中,则对P中每个形如B─→β的产生式,把项目[B─→・β,j]添加到Ij中。

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

(5)对Ij-1中每个形如[A─→α��jγ,i]的项目.把[A─→α��jγ,i]添加到Ij中。转到第2步。在剖析表列I0I1,…,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-→SA,0]

[A-→・b,0]     [A-→・��A,1]

[A-→・b,1]

I2           I3

[A-→aA,1] [A-→b・,2]

[A-→・��A,2]    [A-→��A・,1]

[A-→・b,2]     [S-→SA・,0]因[S─→SA・,0]属于I3,故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.

建筑资质代办服务热线:13198516101

赞(0)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《句法分析》
文章链接:https://www.scworui.com/13301.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。
资质代办立即咨询:13198516101

建筑资质代办专业顾问:

赵经理

13198516101