四类文法的定义是通过逐步增加限制条件进行的。即有： 3型文法?2型文法?1型文法?0型文法。 三、例题

判断下列文法类型：

例1：文法G[S]：S →aSYZ S→aYZ aY→ay yY→yy yZ→yz ZY→YZ zZ→zz 0，1

例2：文法G[S]：S →xSYZ S→xYZ xY→x yY→yy yZ→yz ZY→YZ zZ→zz 0，1

例3：文法G[S]：S→aT T→bT|cT|b|c 0，1，2，3

例4：文法G[S]：S→xB|c B→Az A→cS 0，1，2，3

授课顺序：3

教学目的：使学生掌握语法树的构造、句型分析的方法，了解二义性文法的改

造和有关文法实用性的一些说明。

教学重点：句型分析

教学难点：二义性文法的改造、句型分析 授课学时：2学时

教学方式：多媒体讲授 教学内容：

3.4 上下文无关文法及语法树

上下文无关文法有足够的能力来描述现今程序设计语言的语法结构。今后如无特别说明，“文法”一词均指上下文无关文法。 一、语法树

语法树也称推导树，给定文法G=(VN， VT，P，S)，对于文法G的任意一个句型都存在一个相应的语法树，它满足：

(1)树中每一个结点都有一个标记，此标记是V= VN∪VT中的一个符号。 (2)根的标记是S。

(3)苦树的一结点A至少有一个子女，则A∈VN。

(4)如结点A的子女结点从左到右次序为B1，B2...Bn，则必有产生式A→B1B2...Bn。 例：G[S]： S→aAS | a

A→SbA |SS |ba

对句型aabbaa的推导过程可表示为下图所示语法树。

下面两个推导过程均可由上图表示。

(1) S?aAS?aSbAS?aabAS?aabbaS?aabbaa (2) S?aAS?aAa?aSbAa?aSbbaa?aabbaa

这说明同一语法树可以表示对同一句型不同的推导过程。

二、最左(右)推导

1、如果每一步α?β中，都是对α中最左(右)非终结符进行替换， 则称之为最左(右)推导。

2、最右推导称为规范推导，由规范推导所得的句型称为规范句型。 3、同一语法树最多对应唯一的最左(右)推导。 4、一个句型有可能对应着不同的语法树。 例：文法G[E]： E→i | E+E | E*E | (E)，则句型 i*i+i可能对应着下面两个最右推导： (1) E?E+E?E+i?E*E+i?E*i+i?i*i+i (2) E?E*E?E*E+E?E*E+i?E*i+i?i*i+i

三、二义性语法树

1、如果一个文法存在某个句子对应着两棵不同的语法树，则称此文法是二义的。不存在一种算法能在有限步骤内判断一个2型文法是否是二义的。

2、实际应用中，常找出一组无二义性的充分条件来构造无二义性文法。 3、例子

例1：下列简单算术表达式的文法是二义性文法。

E→E+E|E-E|E*E|E/E|(E) |id

引入新的非终结符后可变换为非二义性文法。

E→E+T|E-T|T T→T*F|T/F|F F→(E) |id

例2：If语句的文法G[S]：

S→if E then S S→if E then S else S S→E E→a≠0|a>0|b=1|b=-1|b=0 假设执行下列语句前b=0，有If句子：if a≠0 then if a>0 then b=1 else b=-1 则当a=1时，b=1;当a=-1时，b=-1; 当a=0时，b=0。 通过引入新非终结符、加ε规则进行改造后得文法：

(1)S→U|M|E (2) U→if E then S (3) U→if E then M else U (4) M→if E then M else M (5) M→ S (6) M→ ε (7) E→a≠0|a>0|b=1|b=-1|b=0

课堂作业：为上述改造前和和改造后的文法构造唯一的语法树。

3.6句型的分析

句型的分析就是识别一个符号串是否为某文法的一个句型。本课程介绍的分析算法都是从左到右的分析算法。它们分为两大类：自顶向下分析、自底向上分析 一、自顶向下分析

自顶向下分析：由根向下逐步建立语法树，是一个逐步推导的过程。 例：文法G[S]： S→cAd A→ab |a

对输入串cabd进行识别过程为：S?cAd?cabd，构造语法树步骤如图所示：

识别过程也有可能是S?cAd?cad，此时无法识别出串cabd，需要回溯。

二、自底向上分析

自底向上分析：自叶向上构造语法树，是一个逐步约的过程。自底向上分析法的核心在于寻找“可归约串”。

例：对串cabd归约过程为 cabd?cAd?S，构造语法树步骤如图所示：

归约过程也有可能是cabd?cAbd，此时无法识别出串cabd，也需要回溯。

三、句型分析的有关问题 1、基本概念

（1）令G[S]是一文法，αβδ是文法G的一个句型，如果有：S =*> αAδ，且A =+>β，则称β是句型αβδ相对于非终结符A的短语，如有A?β，则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语(也叫简单短语)。

（2）一个句型的最左直接短语称为该句型的句柄。

注意： 作为短语的β必须是需要分析的句型αβδ的一部分。 2、例子

例1：已知文法G[E]： E→E+T | T T→T*F | F F→(E) | i 对于给定的句型i*i+i，指出该句型的所有短语、直接短语和句柄。 解：将句型改写为i1*i2+i3，则：

1）因 E=+>i1*i2+i3， E=+>i1*i2，故句型相对于E的短语有：i1*i2+i3，i1*i2。 2）因 T=+>i1*i2，T=+>i1，T=+>i3，故句型相对于T的短语有i1*i2， i1， i3。 3）因 F=+>i1，F=+>i2， F=+>i3，故句型相对于F的短语为：i1， i2， i3;且i1， i2， i3均为句型相对于规则F→i 的直接短语，其中i1为句柄。 下面根据语法树进行分析：

例2： G[S]： S→aAS S→ a A→SbA A→ SS A→ ba 要求对句型aabbaa的进行分析。

解：将句型改写为a1a2b1b2a3a4，则：

1）该句型相对于S的短语： a1a2b1b2a3a4和 a4； 2）该句型相对于A的短语： a2b1b2a3和b2a3； 3）该句型相对于Sàa的直接短语： a2，a4； 4）该句型相对于Aàba的直接短语： b2a3； 5）句柄：a2。