第二章文法和语言
本章讲述目前广泛使用的上下文无关文法。即用上下文无关文法作为程序设计语言语法的描述工具。阐明语法的一个工具是文法。本章将介绍文法和语言的概念。
本章重点：上下文无关文法及其句型分析中的有关问题。
第一节文法的直观概念
当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。
以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。是汉语的一个句子。汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉
〈主语〉∷＝〈代词〉|〈名词〉
〈代词〉∷＝我|你|他
〈名词〉∷＝王明|大学生|工人|英语
〈谓语〉∷＝〈动词〉〈直接宾语〉
〈动词〉∷＝是|学习
〈直接宾语〉∷＝〈代词〉|〈名词〉
“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。
一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉?〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉?〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：
〈句子〉?〈主语〉〈谓语〉
?〈代词〉〈谓语〉
?我〈谓语〉
?我〈动词〉〈直接宾语〉
?我是〈直接宾语〉
?我是〈名词〉
?我是大学生
符号?的含义是，使用一条规则，代替?左边的某个符号，产生?右端的符号串。
显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。
第二节符号和符号串
符号和符号串，在形成语言中和编译技术中是很重要的概念。任何一种语言，都是由许多语言的基本符号组成的符号串的集合。如：英语的基本符号有26个字母和一些标点符号，英语，就是由这些符号所组成的符号串的集合。
（一）字母表和符号串
字母表是元素的非空有穷集合，字母表中的元素称为符号。由字母表中的符号所组成的任何有穷序列称之为“符号串”。
例如：00，01，10 是字母表Σ＝{0，1}上的符号串，又如ab，abc，bc 是字母表Σ＝{a，b，c}上的符号串。还允许有空符号串。空符号串是不包含任何符号的符号串。用ε表示，其长度为0，即|ε|=0。
（二）符号串的运算
相等X＝Y当且仅当组成X的诸符号与组成Y的诸符号依次相等，Σ＝{a，b ，c}
X＝abbc Y＝abbc X＝Y X＝ab Y＝ba X≠Y
①符号串的长度，X是符号串，则其长度用|X|表示。其数值等于组成该符号串的符号个数。
如：X＝STV |X|＝3 而|ε|＝0
②符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串.
如：b是符号串banana的一个前缀.
符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串.
如:nana是符号串banana的一个后缀.
Z＝abc，那么Z的前缀.是ε，a，ab，abc
Z的后缀.ε，c，bc，abc
③符号串的联接，X和Y是符号串，它们的联接XY是把Y的符号写在X的符号之后，得到的符号串。
X＝ST Y＝abu XY＝STabu
|X|＝2 |Y|＝3 |XY|＝5 由于ε的含义
显然有εX＝Xε＝X
④符号串的方幂，X是符号串，把X自身连接几次得到的符号串Z，Z＝XX……XX ，Z＝X n
X0＝ε
X1＝X
X2＝XX
X＝abc X0＝εX1＝abc X2＝abcabc……
n＞0有X n＝XX n-1＝X n-1x
⑤集合的乘积运算
符号串的集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。
AB＝{XY|X∈A，Y∈B}
如：A＝{a，b} B＝{c，d} AB＝{ac，ad，bc，bd}
∵对于任意符号串X总有εX＝Xε＝X
∴{ε}A＝A{ε}＝A
⑥集合A的闭包A*和集合A的正闭包A+
A+＝A1∪A2∪A3……A n∪……
A*＝A0∪A+
A＝{a，b}
A+＝{a，b，aa，ab，ba，bb，aaa，aab……}
A*＝{ε，a，b，aa，ab，ba，bb……}
第三节文法和语言的形式定义
规则，也称重写规则、产生式，是形如α→β或α∷＝β的（α，β）有序对，α是规则的左部，β是规则右部。
α∈V+β∈V* V为某字母表
①定义1 文法G定义为四元组（V N，V T，P，S）。
其中V N为非终结符号集
V T终结符号集非空有穷集
P产生式的集合
S称为识别符号或开始符号，它是一个非终结符，它至少要在一条规则中作为左部出现。
Vn∩V T＝φV＝Vn∪V T V称为文法G的字母表。
②定义2，如α→β是文法G＝（V N，V T，P，S）的规则，γ和δ是V*中的任意符号，若有符号串V，W满足V＝γαδ，W＝γβδ
则说V（应用规则α→β）直接产生W或说W是V的直接推导或说W直接归约到V记作V?W 如，对于G[S] ：S→0S1，S→01
V＝0S1 W＝0011 直接推导：0S1?0011，使用的规则S→01 这里γ＝0 ，δ＝1 V＝S，W＝0S1 直接推导：S→0S1 使用的规则：S→0S1，这里γ＝ε，δ＝ε
③定义3，如果存在直接推导的序列：
V＝Wo?W1?W2……?W n＝W（n＞0）
则称V推导出W或称W归约到V。记作V+?W。
④定义4 若有V+?W，或V＝W，则记作V* ?W
如，对于G[S] S→0S1，S→01存在直接推导序列
V＝0S1?00S11?000S111?00001111＝W，即0S1+?00001111也可记作0S1* ?00001111
⑤定义5，设G[S]是一文法，如果符号串X是从识别符号推导出来的，即S* ?X，则称X是文法G[S]的句型。若X仅由终结符号组成，即S* ?X X∈V T* S：识别符号，则称X是文法G[S]的句子。
⑥定义6，文法G所产生的语言L（G）={X|S* ?X，X∈V T* ，S：识别符号}，即文法G[S]所产生的所有句子的集合。
形式语言理论可以证明如下两点：
A、给定一个文法，就能从结构上唯一地确定其语言G→L（G）
B、给定一种语言，能确定其文法，但这种文法不是唯一的L→G1或G2，……
在此我们用例子说明。
如文法G[Z]：
（1）Z→aZb
（2）Z→ab
由该文法所确定的语言为：
用规则（1）：Z?a Zb?a2Zb2?…?a n-1Zb n-1
用规则（2）：?a n b n
所以，：L（G[Z]）={ a n b n |n≥}。
又如已知语言为：
L（G）={ab n a|n≥1} 可构造其文法G：G：Z→ a B a B→ b B|b
对于上述语言，还可构造文法G′G′：Z→a B a/B→Bb|b
很显然，G不同于G′。对上述语言还可以构造出其他文法。
⑦定义7，若L（G1）＝L（G2）则称文法G1和G2是等价的。
第四节文法的类型
乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
1、设G=（V N，V T，P，S），如果它的每个产生式α→β是这样一种结构：α∈( V N∪V T) *且至少含有一个非终结符，而β∈( V N∪V T) *，则G是一个0型文法。
0型文法也称短语方法。一个非常重要的理论结果是，0型文法的能力相当于图灵机（Turing）。
2、设G=（V N，V T，P，S）为一文法，若P中的每一个产生式α→β均满足| β |≥| α |，| α |指符号串α的长度，仅仅S→ε除外，则文法G是1型或上下文有关的。
3、设G=（V N，V T，P，S），若P中的每一个产生式α→β满足：α是一非终结符，β∈( V N∪V T) * 则此文法称为2型的或上下文无关的。
例G=（｛S，A，B｝，｛a, b｝，P，S），其中P由下列产生式组成：
S→aB A→bAA
S→bA B→b
A→a B→bS
A→aS B→aBB
有时，为书写简洁，常把相同左部的生产式，形如
A→α1
A→α2
.
.
.
A→αn
缩写为：
A→α1|α2|…|αn
这里的元符号“|”读做“或”。
上例的P可写为：
S→aB | bA
A→a |aS| bAA
B→b |bS| aBB
4、设G=（V N，V T，P，S），若P中的每一个产生式的形式都是A→aB或A→a，其中A和B 是非终结符，a是终结符，则G是3型文法或正规文法。
例文法G=（｛S，A，B｝，｛0，1｝，P，S），其中P由下列产生式组成：
S→0A A→1B
S→1B B→1B
S→0 B→1
A→0A B→0
A→0S
显然G是正规文法。
四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文
无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。
第五节上下文无关文法及其语法树
上下文无关文法有足够能力描述现今程序设计语言的语法结构，如算术表达式，各种语句等。
（一）语法树：上下文无关文法句型推导的图解过程
给定文法G＝（V N，V T，P，S）对于G的任何句型都能构造与之关联的语法树。
这棵树满足下列4个条件：
1、每个结点都有一个标记，此标记是V的一个符号。
2、根的标记是S
3、若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在V N中。
4、如果结点n的直接子孙，从左到右的次序是结点n1，n2，…，n k，其标记分别为A1，A2，…，
A K，那么A→A1A2…A K一定是P中的一个产生式。
从一个例子来说明某语法树的构造。
例1 G[S] =（｛S，A｝，｛a, b｝，P，S），其中P为：
（2）A→SbA
（3）A→SS
（4）S→a
（5）A→ba
图2-5-1是G[S]的一棵语法树
图2-5-1的语法树是G[S]的文法的句型aabbaa的推导过程非
常直观自然的描述，从左至右读出图2-5-1的语法树的叶子标记，
得到的就是句型aabbaa。
最左（最右）推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。
最右推导常被称为规范推导。
由规范推导所得的句型称规范句型。例如，
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
（二）递归规则与递归文法
递归的概念在编译技术中是一个很重要的概念。
递归定义是指在定义某事物时，又用到某事物本身。
递归规则，是指在规则的左部和右部具有相同的非终结符号的规则。
在文法中，可以包含有递归规则
如：U→XUY 即为递归规则
若X＝ε则U→UY 左递归
若Y＝ε则U→XU 右递归
X、Y≠ε则U→X∪Y自嵌入
文法的递归性质，若文法中至少包含一条递归规则，
即U?U…，U?…U ，U?…U…则称此文法是直接递归的。
文法具有直接递归还具有间接递归
如：α→βX β→αY|β有α+?αYX
若U+?UYX 间接左递归
U +?YXU 间接右递归
U+?…U…自嵌入
定义递归文法，使得我们能够用有穷的文法去刻划无穷的语言。
例如：有文法G[S]
S→aB|bB
B→a|b
由于该文法是无递归性的，所以由它所描述的语言是有穷的，上述文法所确定的语言为：
L（G[S]）={aa, ab, ba, bb}
例如：文法G[Z]
（1）Z→aZb
（2）Z→ab
由于该文法是递归性的，所以由它所描述的语言是无穷的。由该文法所确定的语言为：
用规则（1）：Z?a Zb?a2Zb2?…?a n-1Zb n-1
用规则（2）：?a n b n
所以，：L（G[Z]）={ a n b n |n≥}。
（三）推导过程与语法树的生成
给定一文法和相应的句子，据文法画出语法树
给定一文法和相应的句子，据推导的定义，推出该文法的句型或句子，这种推导过程，用几何图形表示，就是语法树的生长过程
例1中，对句子aabbaa推导过程可以列举以下3个：
推导过程1：S?aAS?aAa?ASbAa
?aSbbaa?aabbaa
推导过程2：S?aAS?aSbAS?aabAS
?aabbaS?aabbaa
推导过程3：S?aAS?aSbAS?aSbAa
?aabAa?aabbaa
不管是上述第1个还是第2、第3个推导过程，它们相联的语法树都是图2-5-1。
这就是说，一棵语法树表示了一个句型的种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导，但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左（最右）推导呢？不是的。
（四）文法的二义性
如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。
例2文法G[E]
E→E+E|E*E|（E）|i
该文法的V n={E}
V T={+，*，（，），i}
可以看到，i*i+i是该文法的一个句子，因根据文法可以将其推导出来。但是这样的句子可以有两棵语法树，很明显，也存在着两个最右（或最左）推导，见下图。注意：图中结点间连线上的数字，并不表示推导顺序，而是表示归约的顺序。由于该句子对应着两棵语法树，所以该文法是二义性文法。
对于例2的文法G，句型i*i+i就有两个不同的最左推导1和2，它们所对应的语法树分别如图
i*i+i是文法G的一个句子，这个句子可以用完全不同的两种办法生成，在生成过程的第一步，一种办法使用产生式E→E+E进行推导，另一种办法是使用产生式E→E*E。因而i*i+i对应了两棵不同的语法树。
第六节句型的分析
若已有文法，我们就可以用它来推导和产生句子了，但是如若给定一个符号串，如何来确定该符号串是否是文法的句子呢？可用试图按照文法的规则构造推导也可以用语法树，以此识别它是否是该文法的句子
语法分析分为两大类，即自上向下的和自下向上的。所谓自上而下分析法，是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。自下而上的方法，则是从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。从语法树建立的方式可以很好的理解这两类方法的区别。自上而下方法是从文法识别符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端接点符号串正好是输入符号串；自下而上方法则是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。
（一）向上而下的分析方法
以一个简单的例子，说明自上而下分析方法的基本思想。
例3考虑文法G[S]；
（1）S→cAd
（2）A→ab
（3）A→a
识别输入串w = cabd是否该文法的句子。即从根符号S开始如图2-6-1（a）所示，试着为cabd 构造一棵语法树。在构造的第一步，唯一的一个产生式可施用，则构造了直接推导S?cAd，从S向下画语法树如图2-6-1的（b）所示。这棵树的最左叶子标记为c，已和w的第一个符号匹配，考虑下一个叶子，标记A，可用A的第一个候选（产生式（2））去扩展A，则会得到如图2-6-1的（c）所示的语法树，构造的直接推导为cAd?cabd。这时输入符号串w的第二个符号a得到了匹配，第三个输入符号为b，将它与下一叶子标记b相比较，得以匹配，叶子d匹配了第四个输入符号，这
（二）自下而上的分析方法
仍使用上例中的文法来为输入符号串cabd构造推导或语法树，所采用的是自下而上的方法。
首先从输入符号串开始。扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。子串a和子串ab都是合格的，假若我们选用了ab，用产生式（2）的左端A去替代它，即把ab归约到了A，得到子串cAd。构造了一个直接推导cAd?cabd，即从cabd叶子开始向上构造语法树，如图2-6-2的（b）所示。接下去，在得到的串cAd中又找到了子串cAd与产生式（1）的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导S?cAd，形成了图2-6-2的（c）所示的语法树，符号串cabd的推导序列为：
S?cAd?cabd
1、在自上而下的分析过程中，假定被代换的最左非终结符号是V，且有n条规则
V→α1|α1|……αn，那么如何挑选一个正确的呢。
2、在自底向上分析中，在分析每一步都是从当前串中选择一个子串，将它归约到某个非终结符号，这个子串“可归约串”，如何找？这个可归约串，称“句柄”。
但是，如何找出这些句柄呢？若有两条以上的规则，其右部符号串相同，若该符号串又构成句型的句柄时，那么，又将根据哪条规则进行归约呢？
⑧定义8，令G是文法，S是文法的开始符号，αβδ是文法的一个句型，如果有S* ?αAδ且A+?β，则称β是句型αβδ相对于非终结符A的短语。特别，如果A?β则称β是句型αβδ相对于规则A→β的直接短语（简单短语）。一个句型的最左直接短语，称为句型的句柄。
例4定义表达式的无二义文法G[E]：
E→T|E+T
T→F|T*F
F→（E）|i
考虑它的一个句型i*i+i，为了讲授方便，我们将句型写作i1*i2+i3。因为有：
①E*?F* i2+i3且F?i1则称i1是i1*i2+i3的相对于非终结符F的短语，也是相对于规则F→i 的直接短语。
②E*?i1*F+i3且F? i2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则F→i的直接短语。
③E*?i1 * i2+F 且F?i3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则F→i的直接短语。
④E*?T* i2+i3且T+?i1则i1是句型i1*i2+i3的相对于T的短语。
⑤E*?i1* i3+T 且T+?i3则i3是句型i1*i2+i3的相对于T的短语。
⑥E*?T+i3且T+?i1*i2则i1*i2是句型i1*i2+i3的相对于T的短语。
⑦E*?E+i3且E+?i1*i2则i1*i2是句型i1*i2+i3的相对于E的短语。
⑧E*?E 且E+?i1*i2+ i3则i1*i2+i3是句型i1*i2+i3的相对于E的短语。
即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接短语，其中i1是最左直接短语，即句柄。
（四）子树与短语
子树，是由该树的某个结点（称为子树的根）连同它向下射出的部分组成。
利用语法树，我们很容易地找到该句型的短语，直接短语，句柄。
若句型中某些符号，按从左到右顺序，组成某棵小树的末端结点，那么，由这些末端结点所组成的符号串，即是相对于子树根的短语。
第七节有关文法的实用限制
在实用中，我们将限制文法中不得含有有害规则和多余规则，所谓有害规则，是指形为U→U 的产生式。它对描述语言显然是没有必要的。说它有害，是说它只会引起文法的二义性。所谓多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现。一
例5文法G[S]
（1）S→Be（1）S→Be
（2）B→Ce（3）B→Af
（3）B→Af（4）A→Ae
（4）A→Ae（5）A→e
（5）A→e
（6）C→Cf
（7）D→f
对文法G=（V N，V T，P，S）来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件：
1、A必须在某句型中出现。即有S*?αAβ，其中α，β属于（V T∪V N）*。
2、必须能够从A推出终结符号串t来。即A+?t,，其中t∈V* T
若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。
致谢： 2005级周朝丽、丛志环、张云华、周娇、陈亮、陶锌、张世强等同学不仅对讲义的进一步完善提出了宝贵的意见和建议，而且提出的许多富有探讨性的问题，不仅令我进一步思考，同时也令讲义的许多内容进一步丰富，在此，本人、现在已经看到、未来将会看到该讲义的人对各位的“答疑解惑”表示由衷的谢意！ 参考书目： 1.编译原理，Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman著，李建中，姜守旭译。机械工 业出版社，2003 Compilers Principles, Techniques, and Tools（英文版名字） 2.编译原理及实践，（美）Kenneth C. Louden著，冯博琴等译。机械工业出版社，2000 Compiler Construction: Principles and Practice （英文版名字） 3.编译原理习题与解析(第2版)/伍春香编著-.--北京:清华大学出版社,2006 4.编译原理=Compiling Principle/周经野，张继福主编-.--武汉:武汉理工大学出版社,2003 5.程序设计语言编译方法. 肖军模编著. 大连理工大学出版社，2000。 6.程序设计语言编译原理/陈火旺等编.--北京:国防工业出版社,1984 7.编译方法/金成植编.--北京:高等教育出版社,1984 8.编译原理/蒋立源主编.--西安:西北工业大学出版社,1993.8 9.编译原理和技术/陈意云, 马万里编译.--安徽:中国科学技术大学出版社,1989.12 10.编译原理及其习题解答/何炎祥...[等]编著-.--武汉:武汉大学出版社,2004。 11.形式语言与自动机理论 12.FORTRAN语言程序设计，谭浩强、田淑清编著，高等教育出版社，1987年5月。 13.PASCAL程序设计，郗曼丽编著，陕西科学技术出版社。 14.讲义的一些部分来源于互联网上的多种资源，其链接难以一一提供，在此，谨向大家 致以真诚地敬意和诚挚的谢意，感谢大家通过互联网提供的极为有益的帮助和指导。 1
#include
G[5].rightlength=3; G[6].left=103; G[6].right[1]=5; G[6].rightlength=1; printf("·????á·?o?:"); for(i=1;i 编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V 第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。 一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 1、给出算符优先文法的定义，算符优先表是否都存在对应的优先函数给出优先函数的定义。 设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和h三种关系的一种成立，则称G一个算符优先文法。 算符优先关系表不一定存在对应的优先函数 优先函数为文法字汇表中 2、考虑文法G[T]： T→T*F|F F→F↑P|P P→（T）|i 证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。 首先构造T*P↑（T*F）的语法树如图所示。 句型T*P↑（T*F）的语法树 由图可知，T*P↑（T*F）是文法G[T]的一个句型。 直接短语有两个，即P和T*F；句柄为P。 3、文法G[S]为： S→SdT | T T→T 4、目标代码有哪几种形式生成目标代码时通常应考虑哪几个问题 三种形式：可立刻执行的机器语言代码；汇编语言程序；待装配的机器语言代码模块 考虑的问题包括： 每一个语法成分的语义； 目标代码中需要哪些信息，怎样截取这些信息。 5、符号表的作用是什么符号表的查找的整理技术有哪几种 作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。主要技术：线性表，对折查找与二叉树，杂凑技术。 1、实现高级语言程序的途径有哪几种它们之间的区别 计算机执行用于高级语言编写的程序主要有两种途径：解释和编译。 在解释方式下，翻译程序并不对高级语言进行彻底的翻译，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再执行。 在编译方式下，翻译程序先对高级语言进行彻底的翻译并生成目标代码，然后再对目标代码进行优化，即对源程序的处理是先翻译后执行。 从速度上看，编译方式下，源程序的执行比解释方式下快，但在解释方式下，有 《编译原理》课程论文 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上讲，一个编译程序就是一个语言翻译程序。语言翻译程序把一种源语言书写的程序翻译成另一种目标语言的等价程序，所以总的说编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成几个阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程是词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。 编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机工作者的职业生涯中，本书中的原理和技术都会反复用到。在这本书中，向我们介绍了文法的概念，在讲词法分析的章节中讲述了构造一个有穷自动机的方法，以及如何将一个不确定的有穷自动机转化成确定的有穷自动机和有穷自动机的最小化等方法。 词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。 词法分析中的重点是有穷自动机DFA的生成以及DFA和正规式与正规文法的关系。还要熟练掌握NFA转换为DFA的方法及DFA的化简。 词法分析的核心应该是构建DFA，最后维护一个状态转移表。通过转态转移的结果来识别词性。DFA的思想和字典树很像。NFA通过求每个状态的闭包后构造出的自动机与DFA等价。正则表达式闭包，连接，或三种操作都有相应的NFA与其等价。所以正则表达式==NFA==DFA。DFA状态最小化算法化简DFA。LL(1)文法主要就是根据FIRST集判断向哪条路径走，来避免回溯；LR(0)文法构造项 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 作业一 1.已知文法G[A]，写出它定义的语言描述 如：G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 2. 给出生成下述语言的上下文无关文法： （1）{ a n b n a m b m| n，m>=0} (2) { 1n0m 1m0n| n，m>=0} 3. 给出生成下述语言的三型文法： (1){ a n b m|n,m>=1 } (2){a n b m c k|n,m,k>=0 } 4、文法G[E]为：E→E+T|T T→T*F|F F→(E)|i 试给出句型(E+F)*i的短语，简单(直接)短语,句柄。 第3章练习题 一、判断题: 1、编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常 采用二元组的形式。 2、正规式的运算符“|”读作“或“。 3、若两个正规式所表示的正规集相同，则认为二者是等价的。 4、用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。 5、一个确定的有穷自动机DFA M的转换函数f是一个从KⅹΣ到K 的子集的映像。 6、一个非确定的有穷自动机NFA N 的转换函数f是一个从KⅹΣ*到K 的映像。 7、一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 8、终态与非终态是可区别的。 9、对任意一个右线性文法G，都存在一个NFA M，满足L（G）=L（M）。 10、对任意一个右线性文法G，都存在一个DFA M，满足L（M）=L（R）。 二、构造正规式1(0|1)*101相应的DFA. 练习题2 一、判断题： 1、空符号串的集合{ε}={}=ф。 2、设A是符号串的集合，则A0=ε。 3、设G是一个文法，S是开始符号，如果S => x且x∈V T*,则称x是文法G[S]的句型。 4、在形式语言中，最右推导的逆过程也称为规范归约。 5、一个语言的文法是唯一的。 6、若一个语言是无穷集合，则定义该语言的文法一定是递归的。 7、一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。 例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)的分析树 S ( T ) T ， S S T ， S a a (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所示的四种情形。 图 1文法G[Z]可能的几种推导 Z 1 U Z U Z 1 Z 1 Z 1 V 由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、…所以文法描述的语言为{ a n b n c n|n>0}. 例4 构造描述语言L(G[S])={（n）n|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]推导出来的所有终结符号串均为语言的句子. 例5 构造描述语言L(G[S])={a m b n |n>m>0} 的文法。 【解】找出语言的一些典型句子:abb、abbb、…、aabbb、aabbbb、…,语言的句子的特点是仅含有a、b, a在b的左边，b的个数大于a的个数，a的个数至少是1。 单独生成c k, k>1 可用产生式 C→c |Cc 句子中要求b的个数大于a的个数，所以得到文法： 第2章形式语言 1．试分别构造产生下列语言的文法： （1）{a n#b n|n≥0}∪{c n#d n|n≥0}； （2）任何不是以0打头的所有奇整数所组成的集合。 答：(1) 对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S) (2) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9}, {S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S) 2．对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导。 答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb 3．已知文法G[S]: S->(AS)|(b) A->(SaA)|(a) 请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。 答： 因为S 不能? (a), 所以(a)不是文法的句型。没有短语、直接短语和句柄。 因为S ?(AS) ?(A(AS)) ?(A((SaA)S)) ?(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。 短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b) 直接短语：(SaA)，(b) 句柄：(SaA) S ( A S ) ( A S ) ( S a A ) ( b ) 4．试描述由下列文法所产生的语言的特点： （1）S→10S0 S→aA A→bA A→a （2）S→aSS S→a 答：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。 (2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。 附加题：试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 答：因为存在句子：abc，它对应两个最右推导： S ? AB ? Abc ? abc S ? DC ? Dc ? abc 所以，本文法具有二义性。 编译原理课程设计报告 课题名称：编译原理课程设计 C-语言词法与语法分析器的实现 C-词法与语法分析器的实现 1.课程设计目标 （1）题目实用性 C-语言拥有一个完整语言的基本属性，通过编写C-语言的词法分析和语法分析，对于理解编译原理的相关理论和知识有很大的作用。通过编写C-语言词法和语法分析程序，能够对编译原理的相关知识：正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。（2）C-语言的词法说明 ①语言的关键字： else if int return void while 所有的关键字都是保留字，并且必须是小写。 ②专用符号： + - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 注：ID表示标识符，NUM表示数字，letter表示一个字母，digit表示一个数字。 小写和大写字母是有区别的。 ④空格由空白、换行符和制表符组成。空格通常被忽略。 ⑤注释用通常的c语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记)上，且可以超过一行。注释不能嵌套。 （3）程序设计目标 能够对一个程序正确的进行词法及语法分析。 2.分析与设计 （1）设计思想 a.词法分析 词法分析的实现主要利用有穷自动机理论。有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。通过有穷自动机理论能够容易的设计出词法分析器。b.语法分析 语法分析采用递归下降分析。递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 （2）程序流程图 程序主流程图： 词法分析: 语法分析： 编译原理复习题及答案一、选择题 1．一个正规语言只能对应( B ) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是( A ) A 正规文法 B 二型文法 3．下面说法正确的是( A ) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A ) A 必要条件 B 充分必要条件 5．下面说法正确的是( B ) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是( A ) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法( B ) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是( A ) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是( A ) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。 A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序?B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序? C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器?C．表格处理和出错处理 ??? D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n(n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) 课程名称编译原理 设计题目语法分析——规约 目录 一.问题描述 (2) 二．文法及属性文法的描述 (2) 2.1文法描述 (2) 2.2 while-do循环语句的文法 (2) 2.3属性文法描述 (2) 3语法分析方法及中间代码形式的描述 (3) 3.1 语法分析方法 (3) 3.2 中间代码形式描述 (3) 4简要的分析与概要设计 (4) 4.1词法分析 (4) 4.2递归下降翻译器的设计 (4) 4.3语法制导翻译 (5) 5 详细的算法描述 (5) 5.1 文法 (6) 5.2 查错 (6) 三．测试方法和测试结果 (9) 3.1测试方法 (9) 3.2测试结果 (9) 四．设计心得 (10) 一、问题描述 1.1 能够写出一个while-do语句，此语句符合LL（1）的文 法。 1.2 构造词法分析程序对while-do语句进行词法分析。 1.3构造语法分析程序对while-do语句进行语法分析，判断 语法正确性。 1.4 运行程序，要求有正确的语义输出（4地址码）。 二、文法及属性文法的描述： 2.1 文法描述： 基本概念： 文法是对语言结构的定义与描述。即从形式上用于描述和规定语言 构的称为“文法”。 定义：文法G=（V N，V T，P，Z） V N：非终结符号集 V T：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） Z∈V N 其中: 2.2 while-do循环语句的文法 文法G(s)如下： S-->WEDG （意思是while E do G） G-->c=R R-->dTe|d T-->+|-|*|/ E-->aFb F--> >|==|< (id1，id2代表标识符) 2.3 属性文法的描述: 2.3.1属性文法的定义形式: 每个文法符号有一组属性,每个文法产生式A->α有一组产生式 b:=f(c1,c2,……，ck)的语义规则，其中f式函数，b和c1,c2,……， ck式该产生式文法符号的属性。 3．语法分析方法及中间代码形式的描述； 3.1 语法分析方法: 3.1.1本次设计采用LL（1）分析： 预测分析方法概述： 分析钜阵的元素M[A，a]中的下标A为非终结符，a为终结符或句子的结束标记“#”，钜阵元素M[A，a]的内容为一条关于A的产生式。它表明当用非终结符A向下推而当输入符a时，所应该采用的后选式。当钜阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配，因此应该出错处理。 在构造预测分析表时，对每个终结符或“#”号用a表示，则若a∈SELECT （A->a)。令M[A，a]= A->a(一般为了简化,取M[A，a]= a)把所有的无定义的M[A，a]标上ERROR(一般在表中用空白表示)。 3.1.2 此程序预测分析方法： 此设计为非左递归while-do文法,应采用自上而下的预测分析方法。在此设计中，产生式只到E->id1>id2| id1=id2| id1 第3章 文法和语言 第1题 文法G ＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2题 文法G[N]为： N →D|ND D →0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4题 已知文法G[Z]： Z →aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题 已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i * 编译原理复习题 一．简答题： 1) 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。 语言——语言是句子的集合。 或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │S x,x ∈V T *} 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个 开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直 接推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图 归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。 7) 在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG ，AG=（G ，V ，E ）。 其中G 为一个上下文无关文法；V 为属性的有穷集；E 为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 编译程序是一种程序，它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇 编语言的目标程序。 一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段。如果编译生成的目标 程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段。 解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行。 解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程 序，而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不 源程序 产生目标程序。 析阶段、语义分析和中间代码生成阶段、优化阶段和目 标代码生成阶段。词法分析的任务是对构成源程序的字 符串进行扫描和分解，根据语言的词法规则识别出一个 个具有独立意义的单词；语法分析的任务是在词法分析 的基础上，根据语言的语法规则（文法规则）从单词符 号串中识别出各种语法单位并进行语法检查；语义分析 和中间代码生成阶段的任务是首先对每种语法单位进行 静态语义检查，然后分析其含义，并用另一种语言形式 来描述这种语义即生成中间代码；优化的任务是对前阶 段产生的中间代码进行等价变换或改造，以期获得更为 高效（节省时间和空间）的目标代码； 的任务是把中间代码（或经优化处、理之后）变换成特编译程序结构示意图 定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。 形式化的方法：用一整套带有严格规定的符号体系来描述问题的方法。 标识符：以字母打头的字母数字串 字母表：是元素的非空有穷集合。 字符：字母表中的元素称为符号，或称为字符。可以是字母、数字和其他符号。 符号串的运算：符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算、集合A的 正闭包A+与闭包A* 形式语言：字母表上所有的字符按照某种规则所组成的集合。 句子：均对应与字母表中的符号串。 文法：是规则的非空有穷集合（描述语言的文法不唯一） 文法四元组：G[S]=(V N，V T，P，S) V N ：非终结符集V T：终结符集（V N ^ V T=空集） P：产生式集S：文法的开始符号 直接推导：在推导过程中只使用了一个产生式。 推导：经一步到多步推导出结果。（推导：用产生式的右部取代其左部的过程规约：用产 生式的左部取代其右部的过程） 广义推导：经0步到多步推导出结果。 句型：S经0步到多步推导出x且x属于V*（V是V N V T的并集），则x是该文法的一个句型。句子：S经0步到多步推导出x且x属于V T*，则x是该文法的一个句子。句子是一种句型语言：文法G[S]产生的所有句子的集合称为文法G所定义的语言，记为L（G[S]）：L（G[S]）={x|S经一步到多步推导出x且x属于V T*} （文法给定，则语言确定） 最左（右）推导：每步推导都坚持替换当前句型最左（右）边的非终结符。（最右推导也称 规范推导。用规范推导推导出的句型称为规范句型。其逆过程是最左规约，也成为规范规约） 递归规则（产生式递归）：是指在规则的左部和右部具有相同非终结符的规则。 编译原理实验报告 ******************************************************************************* ******************************************************************************* PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下： <程序>::=<分程序>. <分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句> <常量说明> ::=CONST<常量定义>{，<常量定义>}; <常量定义> ::=<标识符>=<无符号整数> <无符号整数> ::= <数字>{<数字>} 】 <变量说明> ::=VAR <标识符>{, <标识符>}; <标识符> ::=<字母>{<字母>|<数字>} <过程说明> ::=<过程首部><分程序>{; <过程说明> }; <过程首部> ::=PROCEDURE <标识符>; <语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空> <赋值语句> ::=<标识符>:=<表达式> <复合语句> ::=BEGIN <语句> {;<语句> }END <条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>} ; <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’ <加法运算符> ::= +|- <乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <条件语句> ::= IF <条件> THEN <语句> <过程调用语句> ::= CALL 标识符 <当循环语句> ::= WHILE <条件> DO <语句> <读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’ <写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’ ￥ <字母> ::= a|b|…|X|Y|Z <数字> ::= 0|1|…|8|9 【预处理】 对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。编译原理知识点汇总
编译原理习题及答案(整理后)
编译原理简答
编译原理论文
编译原理词法分析和语法分析报告+代码(C语言版)
编译原理习题
编译原理第一章练习和答案
编译原理 形式语言题+答案
编译原理课程设计报告C语言词法与语法分析器的实现
编译原理复习题及答案
编译原理-- 语法分析——规约
编译原理第三章答案
编译原理复习题2017(含试卷)
编译原理所有名词解释
编译原理实验-(词法语法分析-附源代码
相关主题
文本预览