句型的分析

上篇讲述了上下文无关文法的推导以及句子的语法树。

本篇继续对句型分析。

开始教程：

对于句子而言，语法树是句子的几何表示形式，把句型形象直观的表示出来了，语法树是句型分析结构分析很好的工具。本篇

所说的句型分析是，给定一个符号串，是否为某文法的句型，也就是给定一串字符串，视图按照某文法的规则为该符号构造推导或

推导树，以此识别他是否是该文法的一个句型，当符号串全部是由非终结符组成的时候，就可以知道他是否是某个文法的句子。

这样根据一个句子得到的树，称为分析树。

句型分析是一个识别输入符号串是否为语法上正确的程序的过程。

我们的分析算法分为：自上而下和自下而上两大类。

自上而下分析算法：

从文法的开始符出发，反复使用各种产生式，寻找“匹配”于输入符号的推导。

自下而上的分析算法：

从输入符号串开始，逐步进行“归约”，直至规归约到文法的开始符号。

从语法树的角度来描述这两种：自上而下是从开始开始推导，使语法树的末端正好是输入符号串。

自下而上是把输入的符号串作为语法树末端的符号串，自底向上的构造语法树。

句型分析的一些说明：

例如：

文法的一些实用性规则：

在实用中，我们限制文法不能含有有害规则和多余规则。

有害规则：形为U——>U的规则。

多余规则：一个句子的归到用不到的规则。

本篇讲述到这里，下一篇讲解词法分析，词法分析的工具--正规式。