规则句法分析作业文档参考.doc

实验三:句法分析 一． 理论描述： 句法分析是指对输入的单词序列进行语法判断,看其能不能构成合乎语法的句子，并抽取出合乎语法的句子的句法结构,即将输入句子中单词之间的线性词序，变成一个非线性的数据结构，如短语结构树。 不同的语法形式，使用的句法分析算法也不同。现在流行的语法有短语结构语法和依存语法两种，主流的是短语结构语法，特别是上下文无关语法，因其高效句法分析算法得到广泛应用。 一个句法分析可以表述为一个有哪些信誉好的足球投注网站过程，有哪些信誉好的足球投注网站空间是语法规则，有哪些信誉好的足球投注网站过程是检查各种语法规则所有可能的组合方式，目的是最终找到一种组合，其中的语法规则能够生成一棵用来表示句子结构的句法树。 句法分析通常采用的策略有：自顶向下分析法；自底向上分析法；左角分析法；其他策略。所谓自顶向下分析法也就是先构造句法树的根结点，再逐步向下扩展，直到叶结点。自底向上分析法则是和自顶向下分析法完全相反的过程。本次试验采用的是自顶向下分析法。 二． 算法描述： 1.初始当前状态为((s) 1)记为C，候选状态为空 2.当算法未失败，且算法未成功，重复： (1)若C是空字符列且词位置到了句尾，则算法成功，返回。 (2)若当前状态和候选状态都为空，且词未知未到句尾，则算法失败，返回。否则，产生新状态： i. 若C中字符列的第一个字符是句子中下一个词的词类，则从字符列中移去第一个字符，并修改词位置，修改后的状态为当前状态，记为C，转(2)。 ii. 若C中字符列的第一个字符是非终止符β，用语法中能重写β的每个规则产生新状态，产生的第一个状态为当前状态（记为C)，产生的其它状态加入到候选状态的栈顶，转（2）. iii. 否则，回溯，从候选状态中取出栈顶作为当前状态. 三． 详例描述与软件演示： 下面我们用“the boy saw a cat”来进行句法分析。分两种情况。 （1） P包含以下几条重写规则： S→NP VP NP→ART N NP →ART ADJ N VP→V NP ART → the|a N →boy|cat V →saw ADJ →dirty 分析过程如下： 步骤 候选状态 找到S→NP VP 由NP找到NP→ART N， NP →ART ADJ N两条规则 NP →ART ADJ N 由ART找到ART → the|a NP →ART ADJ N 由N找到N →boy|cat NP →ART ADJ N 由VP找到VP→V NP NP →ART ADJ N 由V找到V →saw NP →ART ADJ N 由NP找到NP →ART N NP →ART ADJ N 由ART找到ART → the|a NP →ART ADJ N 由N找到N →boy|cat NP →ART ADJ N 句法分析结果以字符串显示结果为： （2）把上述规则的顺序改为： S→NP VP NP →ART ADJ N NP→ART N VP→V NP ART → the|a N →boy|cat V →saw ADJ →dirty 句法分析过程变为： 步骤 候选状态 找到S→NP VP 由NP找到NP→ART N， NP →ART ADJ N两条规则 NP→ART N 由ART找到ART → the|a NP→ART N 由ADJ找到ADJ →dirty，不符合，回溯，将候选状态中 NP→ART N取出 由ART找到ART → the|a NP→ART N 由N找到N →boy|cat 由VP找到VP→V NP 由V找到V →saw 由NP找到NP →ART ADJ N NP →ART N 由ART找到ART → the|a NP →ART N 由ADJ找到ADJ →dirty 不符合，回溯，从栈中取出NP→ART N 由ART找到ART → the|a 由N找到N →boy|cat 句法分析结果以字符串显示结果为：