基本概念

实例解析

基本概念

最左推导：若x和y是符号串α中有两个以上的非终结符号时，对推导的每一步坚持把α中的最左非终结符号进行替换，称为最左推导。

推导：x和y是x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导)，记为x y。

归约：推导的逆过程称之为归约。

实例解析

对于一给定的文法来说，从其开始符号到某一句型，或从一个句型到另一句型间的推导序列可能不惟一。例如对句型i+i*i可以有如下几个推导序列：

E=> E+T=>E+T*F=>T+T*F=> T+T*i=> F+T*i=>i +T*i=>i+F*i=>i+i*i 式子(2-3)

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i 式子(2-4)

E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i 式子(2-5)

为了使句型或句子能按一种确定的推导序列来产生，通常我们可仅考虑最左推导或最右推导。所谓最左 (右)推导，是指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左 (右)非终结符号。例如，在上面的各推导序列中，式(2?4)和式(2?5)就分别是最左和最右推导。形式上，设有符号串α到符号串β的一个推导序列

α ， *xUy ， xuy ， *β

其中，xUy，xuy表示这个推导序列中的任一步直接推导，若总有x∈V*T，则此推导序列为最左推导；而总有y∈V*T时则为最右推导。通常，我们把能由最左 (右)推导推出的句型称为左 (右)句型。另外，也常把最右推导称为规范推导，而把右句型称为规范句型。

然而，应当指出，对于文法中的每一句子都必定有最左和最右推导，但对一句型来说则不尽然，例如，对于上述文法G2[E]中的句型T*i+T而言，仅有惟一的推导

E=>E+T=>T+T=>T*F+T=>T*i+T

显然，推导E=>T*i+T既非最左推导亦非最右推导，故句型T*i+T既不可能是左句型也不可能是规范句型。

对于一个给定的终结符号串w，若采用自顶向下的语法分析来判明w是否为某一语言L(G)中的句子，通常的做法乃是： 试图为w建立一个从G的开始符号S到w的最左推导。显然，在建立此种推导序列的某一步，若当前被替换的非终结符号U是由若干个候选式定义的，即有U→α1|α2|…|αn，那么，就必然会出现如何选用候选式α1,α2,…,αn的问题。一种办法是逐个用这些候选式进行试探，以期获得正确的选择，即若用某一个αi替换U能使分析进行下去，则沿此路径继续前进；若一旦发现此选择有错，则废弃由此选择已做过的分析工作，并回退到出错点再用下一个αi+1继续进行试探，如此等等。因为使用这种方法需反复地回退到出错点进行试探，故称为带回溯的自顶向下的分析方法。由于回溯，将使语法分析的效率大大降低，故应设法予以避免。在第4章中，我们将介绍解决这一问题的途径和方法。

下面再简略地谈谈自底向上的语法分析。概括地说，自底向上的分析也就是从已给的符号串w出发，试图以相反的方向，为w建立一个规范推导。例如，对于文法G2[E]，我们需要判明符号串w0=i+i*i是否为L(G2)中的一个句子。为此，从左至右扫视w0中的各个符号，目的是要在w0中找到一个和G2中某一产生式的右部相同的最左子串，因为w0的最左符号为i，而G2中仅有惟一的产生式F→i其右部为i，故须用此产生式的左部符号F去替换w0的最左子串i，从而就得到新的符号串w1=F+i*i。通常我们将这一操作称为：利用产生式F→i把w0直接归约为w1。类似地，可写出后续的归约过程如表2-1所示。

这里，我们经过了8步最左直接归约，将符号串i+i*i归约为G2[E]的开始符号E，从而再一次证实了它是L(G2)中的一个句子。同时，容易看到，如果我们把上述归约过程的各步所得的各个符号串按归约过程的逆序写出 (也就是按上述过程的逆序来使用所使用过的产生式)，那么，实际上我们就得到了形如式(2?5)的最右推导。由此可见，最右 (左)推导的逆过程是最左 (右)归约，反之亦然。因此，通常我们也将最左归约称为规范归约。至于直接归约、归约以及最左 (右)归约的形式定义我们就不再赘述了，读者不难仿照定义2?2和2?3给出。

此外，再看表21中所列的第5步直接归约。此时的符号串为E+T*i，除了按产生式F→i把此符号串约为E+T*F外，还可考虑按产生式E→E+T或E→T分别将E+T*i归约为E*i和E+E*i。但是，如果把后两个符号串继续进行归约，当分别得到符号串E*E和E+E*E时，显然已无法再进行归约。也就是说，对符号串E+T*i而言，i是惟一可被归约的最左子串。于是，我们自然会提出这样的问题，对于规范归约的每一步，如何确定符号串中当前应被归约的最左子串?这一问题，我们将在2?3?3中进行讨论。