第一部分 重点知识回顾
第一章 引论
1．程序语言的定义
(1)程序语言：一个程序语言是一个记号系统。如同自然语言一样，程序语言也是由语法和语义两方面定义的。任何语言程序都可看成是一定字符集（称为字母表）上的一个字符串，合乎语法的字符串才算是一个合式的程序。所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序，这些规则一部分称为词法规则，另一部分称为语法规（或产生规则）。
(2) 词法规则：指单词符号的形成规则。
(3)语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位）。换言之，语法规则是语法单位的形成规则，一般程序语言的语法单位有表达式、语句、分程序、函数、过程和程序等。
语言的词法规则和语法规则定义了程序的形式结构，是判断输入的字符串是否构成一个形式上正确（即合式）的程序的依据。
(4)语义规则：对于一个语言，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题。离开了语义，语言只不过是一堆符号的集合。所谓一个语言的语义是指这样一组规则，使用它可以定义一个程序的意义。 2. 编译程序
编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一般来说，整个过程可以划分成5个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。
第一阶段，词法分析。词法分析的任务是输入源程序，对构成源程序的字符串进行扫描 和分解，识别出一个个单词符号，如基本字、标识符、常数、算符和界符等。在词法分析阶 段的工作中遵循的是语言的构词规则。
第二阶段，语法分析。语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子（语句）”、“程序段”和“程序”。通过语法分解确定整个输入串是否构成一个语法上正确的“程序”。语法分析所遵循的是语言的语法规则。 第三阶段，中间代码生成。这一阶段的任务是对各类不同语法范畴按语言的语义进行初 步翻译的工作。把语法范畴翻译成中间代码所遵循的是语言的语义规则。一般而言，中间代 码是一种独立于具体硬件的记号系统，它与现代计算机的指令形式有某种程度的接近，或者 说能够比较容易地把它变换成现代计算机的机器指令。常用的中间代码有四元式、三元式、 间接三元式和逆波兰记号等。
第四阶段，优化。优化的任务是对前阶段产生的中间代码进行加工变换，以便在最后阶 段能产生出更为高效（节省时间和空间）的目标代码。优化的主要方面有：公共子表达式的 提取、循环优化、算符归约等。优化所遵循的原则是程序的等价变换规则。
第五阶段，目标代码生成。这一阶段的任务是把中间代码（或经优化处理之后）变换成 特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。这个阶段实现了最后 的翻译，它的工作依赖于硬件系统结构和机器指令含义。 如果最终得到的目标代码是绝对指令代码，则这种目标代码可以立即运行；如果目标代 码是汇编指令代码，则这种目标代码需经汇编之后方可运行。目前多数实用编译程序所产生 的目标代码都是一种可重定位的指令代码，这种目标代码必须通过一个连接装配程序把各个
目标模块连接、装配在一起，使之成为一个可以独立运行的绝对指令代码程序。
上述编译过程的5个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这5 个阶段的任务分模块进行设计。
第二章 高级语言及其文法 1上下文无关文法的定义
文法是描述语言的语法结构的形式规则。
一个上下文无关文法G 包括四个组成部分：一组终结符、一组非终结符、一个开始符号 和一组产生式。从形式上说，一个上下文无关文法G 是一个四元式（V,T, S,P)，其中： （1) T是一个非空有限集，它的每个元素称为终结符号；
(2) V是一个非空有限集，它的每个元素称为非终结符号， T∩V=φ； （3）S 是一个非终结符号，称为开始符号； (4）P 是一个产生式集合（有限），每个产生式的形式是P →α; 其中，P ∈V ，α∈（T
*
∪V ）。开始符号至少必须在某个产生式的左部出现一次。 用上下文无关文法定义语言的中心思想是：从文法的开始符号出发，反复连续地使用产 生式，对非终结符实施替换和展开。 2推导与语法树
我们称αΑβ直接推出αγβ，即：
αΑβ=>α γ β
仅当A →γ是一个产生式，且α，β∈ (T ∪V ）。如果α1=>α2=>…＝>αn , 则称这个序列是从丛α1至αn 的一个推导。若存在一个从α1至αn 的推导，则称“α1可推导出αn 。
注意：用α1=>αn , 表示从α1出发，经过0步或若干步可推导出αn ；而用α1=>αn 表示从α1出发，经过一步或若干步可推导出αn 。这里α=>β意味着或者α=β, 或者α=>β.
*
假定G 是一个文法，S 是它的开始符号。如果S=>α，则称a 是一个句型；仅含终结符 号的句型是一个句子。文法G 所产生的句子的全体是一个语言，将它记为L （G ）。
*
L(G)=｛α|S=>α＆α∈T ｝ 我们可以用一张图表示一个推导，这种表示称为语法树。语法树有助于理解一个句子语 法结构的层次。语法树通常表示成一棵倒立的树，树根在上，枝叶在下。 语法树的根结点由开始符号所标记，每一步推导则对应语法树的生长。在一棵语法树生长程中的任何时刻，所有那些没有后代的树叶自左至右全部排列起来就是一句型。 例如，对文法E →E+E|E*E|(E)|i,关于(i*E+E )推导的语法树生长过程如图所示
*
如果一个文法中存在某个句子，它有两个不同的最左（最右）推导。也就是说，该句于 对应两棵不同的语法树，则这个文法是二义的。因此，判断文法是否具有二义性，就是设法 找到该文法下的一个句子．该句子对应两棵不同的语法树。 注意：假定G 是一个文法，则由该文法开始符号出发所进行的每一步推导所对应的语法树的 树叶自左至右排列的全体就是一个句型，仅含终结符号的句型就是一个句子。
此外，对无二义性的文法来说，无论是最左推导还是最右推导，同一个句子最终形成的 语法树都是一样的。
3．乔姆斯基（Chomsky ）文法 乔姆斯基（Chomsky ）把文法分成4种类型，即0型、1型、2型和3型。0型强于1型， 1型强于2型，2型强于3型。
我们说G ＝(T, V , S,P)是一个0型文法，如果它的每个产生式α→β是这样一种
+*
结构：α∈(T∪V) 且至少含有一个非终结符，而β∈(T∪V) 。
如果把0型文法分别加上以下的第(1)条限制，则我们就得到1型文法：
（1) G的任何产生式α→β均满足|α|≤|β|（|α|指符号串α的长度,|ε|=0);
*
(2）G 的任何产生式为A →β，A ∈V, β∈（T ∪V) ：2型文法
(3）G 的任何产生式为A →a B 或A →a, 其中a ∈T ，A, B∈V ：3型文法。
0型文法也称短语文法，0型文法的能力相当于图灵(Turing)机。或者说，任何0型语 言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。 1型文法也称上下文有关文法（简记为CSG ）。这种文法意味着对非终结符进行替换时务 必考虑上下文；并且，一般不允许替换成空串ε。 2型文法也称上下文无关文法（简记为CFG ）。这种文法对非终结符进行替换时无需考虑 上下文。上下文无关文法对应非确定的下推自动机。
3型文法由于形式上类似线性方程，故称右线性文法。由于这类文法等价于正规式，所 以也称正规文法。由正规文法产生的语言叫做正规语言（正规集）。对任何一个3型文法G. 可以设计一个NFA, 它能够而且只能够识别G 的语言。当然，也可以对任何NFA 构造一个 相应的正规文法, 3型文法的另一种形式是左线性文法，其文法G 的产生式为： A--Ba或A →a a∈T,A,B ∈V 注意：左线性文法与右线性文法是相互等价的。 各类语言与各类自动机的对应关系见表3.1。
注意：如果产生式“→”左侧有终结符，刚该文法一定属于0型或者1型文法范畴。0型和1型的区别仅在产生式“→”左、右两侧的符号串长度上；如果文法中所有产生式“→”左部的符号串长度均小工或等于“→”右部的符号串长度，则为1型文法，否则为0型文法。 2型或3型文法的产生式“→”的左侧仅为非终结符，如果产生式“→”的右侧形式上为aB 或（a ∈T,B ∈V ），则为3型文法，否则为2型文法（上下文无关文法）。
第二部分 例题与习题
重点与难点
重点：文法、推导与归约、短语与句柄。
难点：文法、推导、归约、短语、句柄、文法的二义性、用文法表示语言。
基本要求
掌握语言的描述、形式定义、文法、文法分类的概念以及形式文法的应用，了解二义性文法，熟练掌握推导与规约、短语与句柄及用文法描述语言、正则语言、上下文无关文法、语法分析树。
例题解析
例1设有文法G[S]:
S →a|（T ）| T →T,S|S （1） 试给出句子(a,a,a)的最左推导。 （2） 试给出句子(a,a,a)的分析树 （3） 试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约) 的每一步的句柄。 【解】(1) (a,a,a)的最左推导
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a) （2）(a,a,a)的分析树
( a
T ) (3) (a,a,a)最右推导 最左规约每一步的句柄
S=>(T) 句柄为：(T) =>(T,S) 句柄为：T,S =>(T,a) 句柄为：a =>(T,S,a) 句柄为：T,S =>(T,a,a) 句柄为：第一个a =>(S,a,a) 句柄为：S
=>(a,a,a) 句柄为：第一个a
例2已知文法G[Z]:
Z →0U|1V U →1Z|1 V →0Z|0
（1） 请写出此文法描述的只含有４个符号的全部句子。 （2） G [Z]产生的语言是什么？ （3） 该文法在Chomsky 文法分类中属于几型文法？ 【解】（1）0101，0110，1010， 1001
（2）分析G[Z]所推导出的句子的特点：由Z 开始的推导不外乎图1所示的四种情形。
Z 1
Z
1
Z
1
图 1文法G[Z]可能的几种推导
由Z 推导出10或01后就终止或进入递归，而Z 的每次递归将推导出相同的符号串：10或
+
01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01) } (3)该文法属于3型文法。
例3 已知文法G=({A,B,C}，{a,b,c}，P ，A), P由以下产生式组成:
A →abc A →aBbc Bb →bB Bc →Cbcc bC →Cb
aC →aaB aC →aa
此文法所表示的语言是什么？ 【解】
分析文法的规则：
每使用一次Bc →Cbcc ，b 、c 的个数各增加一个；
每使用一次aC →aaB 或aC →aa, a的个数就增加一个； 产生式Bb →bB 、 bC→Cb 起连接转换作用。
由于A 是开始符号，由产生式A →abc 推导得到终结符号串abc ；由产生式A →aBbc 推导得到B 后，每当使用产生式Bb →bB 、Bc →Cbcc 、bC →Cb 、aC →aaB 就会递归调用B 一次，所产生的a 、b 、c 的个数分别增加一个，因此推导所得的终结符号串为abc 、aabbcc 、aaabbbccc 、…
n n n
所以文法描述的语言为{ ab c |n>0}.
n n
例4 构造描述语言L(G[S])={（）|n≥0} 的文法。 【解】(1)找出语言的一些典型句子:
n=0 ε n=1 ( ) n=2 (()) …
所以, L(G[S])={ ε、( ) (())、((()))、…}
(2)分析句子的特点:
只含有(和),(和) 的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。 (3)凑规则:由 S→ε|() 得到ε|()，由 A→ (S) 得到 (())，(()) 是在（）的两边再加上一对（）得到，((()))是在(())的两边再加上一对（）得到，…所以将上述产生式合并为 S →(S) |ε。
(4)得到文法 G[S]: S→(S) |ε
(5)检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言的句子.
m n
例5 构造描述语言L(G[S])={a b |n>m>0} 的文法。
【解】找出语言的一些典型句子:abb、abbb 、…、aabbb 、aabbbb 、…, 语言的句子的特点是仅含有a 、b, a在b 的左边，b 的个数大于a 的个数，a 的个数至少是1。
k
单独生成c , k>1 可用产生式 C→c |Cc
句子中要求b 的个数大于a 的个数，所以得到文法：
G[S]: S→Ab |Sb
A →aAb |ab
检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言L(G[S])的句子.
例6设有文法G[S]:
S →S*S|S+S|(S)|i
该文法是否为二义文法？
【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图2所示. 。
S
S (1)
S
+
i
S *
i
(2)
i
图2句子i*i+i的语法树
例7写一个文法，使其语言是奇数集，且每个奇数不以0开头。 【解】解题思路
首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。 解答：
G(S)：S →CD ｜D C →CB ｜A B →A ｜0
A →2｜4｜6｜8｜D D →1｜3｜5｜7｜9
例8写一个上下文无关文法CFG ，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，…. ｝） 【解】解答：
能被5整除的数从形式上看，是以0,5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为：
G(S)：S →MF ｜5 F →5｜0 M →MD ｜N D →N ｜0
N →1｜2｜3｜4｜5｜6｜7｜8｜9
例9证明下面的文法是二义的：
S →ｉS ｅS ｜ｉS ｜ｉ 【解】解题思路：
根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if ….else …. 结构的（用“i ”代表“if ”或语句集，“e ”代表“else ”）。因此我们就要到if ….else …结构中去找二义性。我们知道，程序语言一般都规定else 部分是和它前面离它最近的没有被匹配的的if 语句进行匹配。而
上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else 前面有两个if （如句子iiiei ），else 和不同的if 进行匹配时就会产生不同的语义。 解答：
考虑句子iiiei ，存在如下两个最右推导： S => iSeS => iSei => iiSei => iiiei S => iS => iiSeS => iiSei => iiiei
例10某程序设计语言的表达式由运算符θ1、θ2、θ3、标识符、（、）组成，其中θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？ 设E 为识别符号，终结符号集={θ1、θ2、θ3、（、）、I}，非终结符号集={E、T 、F}。
a.E →T|Eθ1T|Eθ2T T →F|Tθ3F F →(E)|I
b. E→T|Tθ1E|Tθ2E T →F|Fθ3T F →(E)|I c. E→T|Eθ3T T →F|Tθ1F|Tθ2F F →(E)|I d. E→T|Tθ3 E T →F|Fθ1T|Fθ2T F →(E)|I
【解】对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。
题意要求：θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，因此θ3比 θ1、θ2先推导出来，即应为图3所示的四种情形。
U
1
3(1)
U
U 3(2)
U
U θ 1
2
3(3)
U
U 3(4)
U θ 2
图3可能的文法推导顺序
因此a 和b 不成立。
又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。
U
1(1)
U
θ 1
2(2
U
θ 2
3(3)
θ 3
图4可能的文法递归结构
故c 不成立, 应为d 。
例11 CFG ：由相同个数 a 和 b 组成句子 【解】我们用一个非终结符A 代表一个a(即有A →a), 用一个非终结符B 代表一个b （即有B →b ）；为了保证a 和b 的个数相同，则在出现一个a 时应相应地出现一个B. 出现一个b 时则相应出现一个A 。假定已推导出bA ，如果下一步要推导出连续两个b 时，则应有
bA=>bbAA。也即为了保证b 和A 的个数一致，应有A →bAA ；同理有B →aBB 。此外，为了保证递归地推出所要求的ab 串，应有S →aBS 和S →bAS 。由此得到无二义文法G[S]为：
G[S]：S →aBS|bAS|ε A→bAA|a B→aBB|b
例12下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。
S → S and S|S or S|not S|p|q|(S)
【解】文法G[S]:S→S and S| S or S |not S | p |q | (S)所产生的二义性在于：运算符and 和or 的优先级未确定，并且and, or 运算的结合顺序也未确定。由于优先级的高低在产生式中反映为归约的先后，运算结合顺序是左结合还是右结合在产生式中反映为递归的方向是左还是右。根据通常的约定，单个变量p ，q 及运算符not, 括号（）的优先级最高，and 的优先级次之，最
后是运算符or. 为了体现这种关系，我们引入了新的非终结符。注意，归约是从语法树底层 向上进行的，也即越是底层的优先级越高，层次越往上的优先级越低。体现在产生式中，就 是离开始符越远的优先级越高，反之越低。由此，我们得到无二义的文法G ’[S]如下： G ’[S]：S →S or A|A A →A and B|B B →not B|p|q|(S) 例13 有文法 G ： S → aAcB|Bd A → AaB|c B → bScA|b
（ 1) 试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄； (2) 写出句子 acabcbbdcc 的最左推导过程。
（1) 【解】分别画出对应两句型的语法树如图(a), (b)所示。
对树（a ），直接短语有3个：AaB, b和c ，而AaB 为最左直接短语（即为句柄) 。对树
(b），直接短语有两个：Bd 和c ，而Bd 为最左直接短语。 （2）句子acabcbbdcc 的最左推导如下：
S=>aACB=>aAaBCB=>acaBcB=>aCabCB=>acabcbScA=>acabcbBdCA
=>acabcbbdcA=>acabcbbdcc
第一部分 重点知识回顾
第一章 引论
1．程序语言的定义
(1)程序语言：一个程序语言是一个记号系统。如同自然语言一样，程序语言也是由语法和语义两方面定义的。任何语言程序都可看成是一定字符集（称为字母表）上的一个字符串，合乎语法的字符串才算是一个合式的程序。所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序，这些规则一部分称为词法规则，另一部分称为语法规（或产生规则）。
(2) 词法规则：指单词符号的形成规则。
(3)语法规则：语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位）。换言之，语法规则是语法单位的形成规则，一般程序语言的语法单位有表达式、语句、分程序、函数、过程和程序等。
语言的词法规则和语法规则定义了程序的形式结构，是判断输入的字符串是否构成一个形式上正确（即合式）的程序的依据。
(4)语义规则：对于一个语言，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义，这就是语义问题。离开了语义，语言只不过是一堆符号的集合。所谓一个语言的语义是指这样一组规则，使用它可以定义一个程序的意义。 2. 编译程序
编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一般来说，整个过程可以划分成5个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。
第一阶段，词法分析。词法分析的任务是输入源程序，对构成源程序的字符串进行扫描 和分解，识别出一个个单词符号，如基本字、标识符、常数、算符和界符等。在词法分析阶 段的工作中遵循的是语言的构词规则。
第二阶段，语法分析。语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子（语句）”、“程序段”和“程序”。通过语法分解确定整个输入串是否构成一个语法上正确的“程序”。语法分析所遵循的是语言的语法规则。 第三阶段，中间代码生成。这一阶段的任务是对各类不同语法范畴按语言的语义进行初 步翻译的工作。把语法范畴翻译成中间代码所遵循的是语言的语义规则。一般而言，中间代 码是一种独立于具体硬件的记号系统，它与现代计算机的指令形式有某种程度的接近，或者 说能够比较容易地把它变换成现代计算机的机器指令。常用的中间代码有四元式、三元式、 间接三元式和逆波兰记号等。
第四阶段，优化。优化的任务是对前阶段产生的中间代码进行加工变换，以便在最后阶 段能产生出更为高效（节省时间和空间）的目标代码。优化的主要方面有：公共子表达式的 提取、循环优化、算符归约等。优化所遵循的原则是程序的等价变换规则。
第五阶段，目标代码生成。这一阶段的任务是把中间代码（或经优化处理之后）变换成 特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。这个阶段实现了最后 的翻译，它的工作依赖于硬件系统结构和机器指令含义。 如果最终得到的目标代码是绝对指令代码，则这种目标代码可以立即运行；如果目标代 码是汇编指令代码，则这种目标代码需经汇编之后方可运行。目前多数实用编译程序所产生 的目标代码都是一种可重定位的指令代码，这种目标代码必须通过一个连接装配程序把各个
目标模块连接、装配在一起，使之成为一个可以独立运行的绝对指令代码程序。
上述编译过程的5个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这5 个阶段的任务分模块进行设计。
第二章 高级语言及其文法 1上下文无关文法的定义
文法是描述语言的语法结构的形式规则。
一个上下文无关文法G 包括四个组成部分：一组终结符、一组非终结符、一个开始符号 和一组产生式。从形式上说，一个上下文无关文法G 是一个四元式（V,T, S,P)，其中： （1) T是一个非空有限集，它的每个元素称为终结符号；
(2) V是一个非空有限集，它的每个元素称为非终结符号， T∩V=φ； （3）S 是一个非终结符号，称为开始符号； (4）P 是一个产生式集合（有限），每个产生式的形式是P →α; 其中，P ∈V ，α∈（T
*
∪V ）。开始符号至少必须在某个产生式的左部出现一次。 用上下文无关文法定义语言的中心思想是：从文法的开始符号出发，反复连续地使用产 生式，对非终结符实施替换和展开。 2推导与语法树
我们称αΑβ直接推出αγβ，即：
αΑβ=>α γ β
仅当A →γ是一个产生式，且α，β∈ (T ∪V ）。如果α1=>α2=>…＝>αn , 则称这个序列是从丛α1至αn 的一个推导。若存在一个从α1至αn 的推导，则称“α1可推导出αn 。
注意：用α1=>αn , 表示从α1出发，经过0步或若干步可推导出αn ；而用α1=>αn 表示从α1出发，经过一步或若干步可推导出αn 。这里α=>β意味着或者α=β, 或者α=>β.
*
假定G 是一个文法，S 是它的开始符号。如果S=>α，则称a 是一个句型；仅含终结符 号的句型是一个句子。文法G 所产生的句子的全体是一个语言，将它记为L （G ）。
*
L(G)=｛α|S=>α＆α∈T ｝ 我们可以用一张图表示一个推导，这种表示称为语法树。语法树有助于理解一个句子语 法结构的层次。语法树通常表示成一棵倒立的树，树根在上，枝叶在下。 语法树的根结点由开始符号所标记，每一步推导则对应语法树的生长。在一棵语法树生长程中的任何时刻，所有那些没有后代的树叶自左至右全部排列起来就是一句型。 例如，对文法E →E+E|E*E|(E)|i,关于(i*E+E )推导的语法树生长过程如图所示
*
如果一个文法中存在某个句子，它有两个不同的最左（最右）推导。也就是说，该句于 对应两棵不同的语法树，则这个文法是二义的。因此，判断文法是否具有二义性，就是设法 找到该文法下的一个句子．该句子对应两棵不同的语法树。 注意：假定G 是一个文法，则由该文法开始符号出发所进行的每一步推导所对应的语法树的 树叶自左至右排列的全体就是一个句型，仅含终结符号的句型就是一个句子。
此外，对无二义性的文法来说，无论是最左推导还是最右推导，同一个句子最终形成的 语法树都是一样的。
3．乔姆斯基（Chomsky ）文法 乔姆斯基（Chomsky ）把文法分成4种类型，即0型、1型、2型和3型。0型强于1型， 1型强于2型，2型强于3型。
我们说G ＝(T, V , S,P)是一个0型文法，如果它的每个产生式α→β是这样一种
+*
结构：α∈(T∪V) 且至少含有一个非终结符，而β∈(T∪V) 。
如果把0型文法分别加上以下的第(1)条限制，则我们就得到1型文法：
（1) G的任何产生式α→β均满足|α|≤|β|（|α|指符号串α的长度,|ε|=0);
*
(2）G 的任何产生式为A →β，A ∈V, β∈（T ∪V) ：2型文法
(3）G 的任何产生式为A →a B 或A →a, 其中a ∈T ，A, B∈V ：3型文法。
0型文法也称短语文法，0型文法的能力相当于图灵(Turing)机。或者说，任何0型语 言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。 1型文法也称上下文有关文法（简记为CSG ）。这种文法意味着对非终结符进行替换时务 必考虑上下文；并且，一般不允许替换成空串ε。 2型文法也称上下文无关文法（简记为CFG ）。这种文法对非终结符进行替换时无需考虑 上下文。上下文无关文法对应非确定的下推自动机。
3型文法由于形式上类似线性方程，故称右线性文法。由于这类文法等价于正规式，所 以也称正规文法。由正规文法产生的语言叫做正规语言（正规集）。对任何一个3型文法G. 可以设计一个NFA, 它能够而且只能够识别G 的语言。当然，也可以对任何NFA 构造一个 相应的正规文法, 3型文法的另一种形式是左线性文法，其文法G 的产生式为： A--Ba或A →a a∈T,A,B ∈V 注意：左线性文法与右线性文法是相互等价的。 各类语言与各类自动机的对应关系见表3.1。
注意：如果产生式“→”左侧有终结符，刚该文法一定属于0型或者1型文法范畴。0型和1型的区别仅在产生式“→”左、右两侧的符号串长度上；如果文法中所有产生式“→”左部的符号串长度均小工或等于“→”右部的符号串长度，则为1型文法，否则为0型文法。 2型或3型文法的产生式“→”的左侧仅为非终结符，如果产生式“→”的右侧形式上为aB 或（a ∈T,B ∈V ），则为3型文法，否则为2型文法（上下文无关文法）。
第二部分 例题与习题
重点与难点
重点：文法、推导与归约、短语与句柄。
难点：文法、推导、归约、短语、句柄、文法的二义性、用文法表示语言。
基本要求
掌握语言的描述、形式定义、文法、文法分类的概念以及形式文法的应用，了解二义性文法，熟练掌握推导与规约、短语与句柄及用文法描述语言、正则语言、上下文无关文法、语法分析树。
例题解析
例1设有文法G[S]:
S →a|（T ）| T →T,S|S （1） 试给出句子(a,a,a)的最左推导。 （2） 试给出句子(a,a,a)的分析树 （3） 试给出句子(a,a,a)的最右推导和最右推导的逆过程(即最左规约) 的每一步的句柄。 【解】(1) (a,a,a)的最左推导
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a) （2）(a,a,a)的分析树
( a
T ) (3) (a,a,a)最右推导 最左规约每一步的句柄
S=>(T) 句柄为：(T) =>(T,S) 句柄为：T,S =>(T,a) 句柄为：a =>(T,S,a) 句柄为：T,S =>(T,a,a) 句柄为：第一个a =>(S,a,a) 句柄为：S
=>(a,a,a) 句柄为：第一个a
例2已知文法G[Z]:
Z →0U|1V U →1Z|1 V →0Z|0
（1） 请写出此文法描述的只含有４个符号的全部句子。 （2） G [Z]产生的语言是什么？ （3） 该文法在Chomsky 文法分类中属于几型文法？ 【解】（1）0101，0110，1010， 1001
（2）分析G[Z]所推导出的句子的特点：由Z 开始的推导不外乎图1所示的四种情形。
Z 1
Z
1
Z
1
图 1文法G[Z]可能的几种推导
由Z 推导出10或01后就终止或进入递归，而Z 的每次递归将推导出相同的符号串：10或
+
01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01) } (3)该文法属于3型文法。
例3 已知文法G=({A,B,C}，{a,b,c}，P ，A), P由以下产生式组成:
A →abc A →aBbc Bb →bB Bc →Cbcc bC →Cb
aC →aaB aC →aa
此文法所表示的语言是什么？ 【解】
分析文法的规则：
每使用一次Bc →Cbcc ，b 、c 的个数各增加一个；
每使用一次aC →aaB 或aC →aa, a的个数就增加一个； 产生式Bb →bB 、 bC→Cb 起连接转换作用。
由于A 是开始符号，由产生式A →abc 推导得到终结符号串abc ；由产生式A →aBbc 推导得到B 后，每当使用产生式Bb →bB 、Bc →Cbcc 、bC →Cb 、aC →aaB 就会递归调用B 一次，所产生的a 、b 、c 的个数分别增加一个，因此推导所得的终结符号串为abc 、aabbcc 、aaabbbccc 、…
n n n
所以文法描述的语言为{ ab c |n>0}.
n n
例4 构造描述语言L(G[S])={（）|n≥0} 的文法。 【解】(1)找出语言的一些典型句子:
n=0 ε n=1 ( ) n=2 (()) …
所以, L(G[S])={ ε、( ) (())、((()))、…}
(2)分析句子的特点:
只含有(和),(和) 的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。 (3)凑规则:由 S→ε|() 得到ε|()，由 A→ (S) 得到 (())，(()) 是在（）的两边再加上一对（）得到，((()))是在(())的两边再加上一对（）得到，…所以将上述产生式合并为 S →(S) |ε。
(4)得到文法 G[S]: S→(S) |ε
(5)检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言的句子.
m n
例5 构造描述语言L(G[S])={a b |n>m>0} 的文法。
【解】找出语言的一些典型句子:abb、abbb 、…、aabbb 、aabbbb 、…, 语言的句子的特点是仅含有a 、b, a在b 的左边，b 的个数大于a 的个数，a 的个数至少是1。
k
单独生成c , k>1 可用产生式 C→c |Cc
句子中要求b 的个数大于a 的个数，所以得到文法：
G[S]: S→Ab |Sb
A →aAb |ab
检验:语言所有的句子均可由文法G[S]推导出来, 文法G[S]推导出来的所有终结符号串均为语言L(G[S])的句子.
例6设有文法G[S]:
S →S*S|S+S|(S)|i
该文法是否为二义文法？
【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图2所示. 。
S
S (1)
S
+
i
S *
i
(2)
i
图2句子i*i+i的语法树
例7写一个文法，使其语言是奇数集，且每个奇数不以0开头。 【解】解题思路
首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。 解答：
G(S)：S →CD ｜D C →CB ｜A B →A ｜0
A →2｜4｜6｜8｜D D →1｜3｜5｜7｜9
例8写一个上下文无关文法CFG ，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，…. ｝） 【解】解答：
能被5整除的数从形式上看，是以0,5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为：
G(S)：S →MF ｜5 F →5｜0 M →MD ｜N D →N ｜0
N →1｜2｜3｜4｜5｜6｜7｜8｜9
例9证明下面的文法是二义的：
S →ｉS ｅS ｜ｉS ｜ｉ 【解】解题思路：
根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if ….else …. 结构的（用“i ”代表“if ”或语句集，“e ”代表“else ”）。因此我们就要到if ….else …结构中去找二义性。我们知道，程序语言一般都规定else 部分是和它前面离它最近的没有被匹配的的if 语句进行匹配。而
上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else 前面有两个if （如句子iiiei ），else 和不同的if 进行匹配时就会产生不同的语义。 解答：
考虑句子iiiei ，存在如下两个最右推导： S => iSeS => iSei => iiSei => iiiei S => iS => iiSeS => iiSei => iiiei
例10某程序设计语言的表达式由运算符θ1、θ2、θ3、标识符、（、）组成，其中θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？ 设E 为识别符号，终结符号集={θ1、θ2、θ3、（、）、I}，非终结符号集={E、T 、F}。
a.E →T|Eθ1T|Eθ2T T →F|Tθ3F F →(E)|I
b. E→T|Tθ1E|Tθ2E T →F|Fθ3T F →(E)|I c. E→T|Eθ3T T →F|Tθ1F|Tθ2F F →(E)|I d. E→T|Tθ3 E T →F|Fθ1T|Fθ2T F →(E)|I
【解】对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。
题意要求：θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，因此θ3比 θ1、θ2先推导出来，即应为图3所示的四种情形。
U
1
3(1)
U
U 3(2)
U
U θ 1
2
3(3)
U
U 3(4)
U θ 2
图3可能的文法推导顺序
因此a 和b 不成立。
又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。
U
1(1)
U
θ 1
2(2
U
θ 2
3(3)
θ 3
图4可能的文法递归结构
故c 不成立, 应为d 。
例11 CFG ：由相同个数 a 和 b 组成句子 【解】我们用一个非终结符A 代表一个a(即有A →a), 用一个非终结符B 代表一个b （即有B →b ）；为了保证a 和b 的个数相同，则在出现一个a 时应相应地出现一个B. 出现一个b 时则相应出现一个A 。假定已推导出bA ，如果下一步要推导出连续两个b 时，则应有
bA=>bbAA。也即为了保证b 和A 的个数一致，应有A →bAA ；同理有B →aBB 。此外，为了保证递归地推出所要求的ab 串，应有S →aBS 和S →bAS 。由此得到无二义文法G[S]为：
G[S]：S →aBS|bAS|ε A→bAA|a B→aBB|b
例12下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。
S → S and S|S or S|not S|p|q|(S)
【解】文法G[S]:S→S and S| S or S |not S | p |q | (S)所产生的二义性在于：运算符and 和or 的优先级未确定，并且and, or 运算的结合顺序也未确定。由于优先级的高低在产生式中反映为归约的先后，运算结合顺序是左结合还是右结合在产生式中反映为递归的方向是左还是右。根据通常的约定，单个变量p ，q 及运算符not, 括号（）的优先级最高，and 的优先级次之，最
后是运算符or. 为了体现这种关系，我们引入了新的非终结符。注意，归约是从语法树底层 向上进行的，也即越是底层的优先级越高，层次越往上的优先级越低。体现在产生式中，就 是离开始符越远的优先级越高，反之越低。由此，我们得到无二义的文法G ’[S]如下： G ’[S]：S →S or A|A A →A and B|B B →not B|p|q|(S) 例13 有文法 G ： S → aAcB|Bd A → AaB|c B → bScA|b
（ 1) 试求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄； (2) 写出句子 acabcbbdcc 的最左推导过程。
（1) 【解】分别画出对应两句型的语法树如图(a), (b)所示。
对树（a ），直接短语有3个：AaB, b和c ，而AaB 为最左直接短语（即为句柄) 。对树
(b），直接短语有两个：Bd 和c ，而Bd 为最左直接短语。 （2）句子acabcbbdcc 的最左推导如下：
S=>aACB=>aAaBCB=>acaBcB=>aCabCB=>acabcbScA=>acabcbBdCA
=>acabcbbdcA=>acabcbbdcc