当前位置：文档之家 › 编译原理第2章

编译原理第2章

  • 格式：ppt
  • 大小：1.40 MB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

2021-2022学年编译原理之形式语言基础(2)

2021-2022学年编译原理之形式语言基础(2)

2.4 两种特性文法
设有文法：G(Z)=(VN,VT,Z,P)
2.4.1 递归文法
【定义】
设 若
AA∈=+V>N，xAxy,，y：∈称(V文N+法VT)具*，有则递;归性;
特别： 若 A -> A ，称文法具有直接左递归性； A -> A ，称文法具有直接右递归性。
如：G1(S): S -> S b | a --- 直接左递归文法；
∵ S->a(A|)bc
∴ S->aAbc|abc
∵ A->d(A|)(B|)e ∴ A->dABe|dBe|dAe|de
∵ B->(A|)
∴ B->A
※ 综合 G`(S) ： S->aAbc|abc|bS A->dABe|dBe|dAe|de B->A|b
2.5.2 文法变换方法3
Ⅲ 常用的三种文法变换方法：
D -> f ; G -> b ;
⒊ 删除不可用产生式: ∵ VUS={ S,B,A }; ∴ 应删除 D,G(连同其产生式)
※ 整理后得：G``(S):
S -> Be A -> Ae | e B -> Af
2.5.2 文法变换方法2
Ⅱ 删除 产生式
※假定 文法 G(Z) ; 【算法】
∈ L(G)
2.5.2 文法变换方法
在实际工作中，人们总是希望定义一种语言的 文法尽可能地简单。另外，某些常用的语法分析技 术也会对文法提出一定的要求或限制；为了适应上 述要求，有时需要对文法进行必要的改写。当然改 写后的文法要与原文法等价—通常称为文法变换。
这里重点介绍三类变换：
⑴ 删除无用的产生式（文法的化简）； ⑵ 删除ε产生式； ⑶ 常用的三种文法变换方法：

编译原理第二版作业答案_第2章

编译原理第二版作业答案_第2章

第二章 文法和语言p48 4、6（6）、11、 12（2）（6）、18（2）4 证明文法G=（{E,O}，{(，)，+，*，v ，d}，P ，E ）是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明：因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v=〉EOv+v =〉E*v+v =〉v*v+v ， 句子v*v+v 有两棵不同的语法树所以文法G 是二义的。

问题：1）只有文字说明，比如v*v+v 有两棵语法树，但没有画出语法树或者最左（最右）推导过程2）给出的是不同句子（v*v+d v+v*d ）的语法树 6、已知文法G ：EEEE OO v*v+ vE EE E O O v+v* v〈表达式〉∷=〈项〉|〈表达式〉+〈项〉〈项〉∷=〈因子〉|〈项〉*〈因子〉〈因子〉∷=（〈表达式〉）| i试给出下述表达式的推导及语法树（6）i+i*i推导过程：〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F=〉〈表达式〉+〈项〉* i =〉E+ T*i=〉〈表达式〉+ 〈因子〉* i =〉E+F*i=〉〈表达式〉+ i* i =〉E+i*i=〉〈项〉+ i* i =〉T +i*i=〉〈因子〉+ i* i =〉F +i*i=〉i +i*i =〉i +i*i 共8步推导语法树：〈表达式〉+〈因子〉〈项〉i 〈因子〉i〈项〉〈项〉〈因子〉i*11、一个上下文无关文法生成句子abbaa的推导树如下：（1）给出该句子相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语、简单短语、句柄。

（1）最左推导：S=〉ABS=〉aBS=〉aSBBS=〉aBBS=〉abBS=〉abbS =〉abbAa=〉abbaa最右推导：S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa（2）该文法的产生式集合P可能有下列元素：S→ABS | Aa|εA→a B→SBB|b（3）因为字符串中的各字符有相对的位置关系，为了能相互区别，给相同的字符标上不同的数字。

(完整word版)编译原理课后答案

(完整word版)编译原理课后答案

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

编译原理第二章 文法和语言资料

编译原理第二章 文法和语言资料

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

编译原理教程(第二版)胡元义课后答案第二章

编译原理教程(第二版)胡元义课后答案第二章

第二章 词法分析 对图2-21的DFA进行最小化。首先将状态分为非终态 集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集 可知，对于状态3、6、7，无论输入字符是a还是b的下一 状态均为终态集，而状态4在输入字符b的下一状态落入 非终态集，故将其化为分 {0,1,2,5}, {4}, {3,6,7} 对于非终态集，在输入字符a、b后按其下一状态落 入的状态集不同而最终划分为
重新命名
图2-9 习题2.5的状态转换矩阵
第二章 词法分析
a 0 a 1 b 2
b b 3
a a 4
图2-10 习题2.5的最简DFA
第二章 词法分析 2.6 有语言L={w|w∈(0,1)+，并且w中至少有两个
1，又在任何两个1之间有偶数个0}，试构造接受该语
言的确定有限状态自动机(DFA)。
M′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图
2-3所示。
第二章 词法分析 表2-2 状态转换矩阵
f 状态 0 1 2 字符
a 2 — 2
b 1 2 2
第二章 词法分析 将图2-3所示的DFA M′最小化。首先，将M′的状 态分成终态组{1,2}与非终态组{0}。其次，考察{1,2}，
0 0 0 1 1 0 2 0 3 1 4 0 5 1 0 0 6
图2-13 习题2.6的最简DFA
第二章 词法分析 2.7 已知正规式((a|b)*|aa)*b和正规式(a|b)*b。
(1) 试用有限自动机的等价性证明这两个正规式
是等价的；
(2) 给出相应的正规文法。 【解答】 图2-14所示。 (1) 正规式((a|b)*|aa)*b对应的NFA如

编译原理第二章习题答案

编译原理第二章习题答案

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D……D3.已知文法G[S]:Sf dAB Af aA|a B|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法? [答案]正规式是daa*b* ；相应的正规文法为(由自动机化简来):G[S]:S —dA A —a|aB B —aB|a|b|bC C —bC|b也可为(观察得来):G[S]:S —dA A —a|aA|aB B —bB| &4.已知文法G[Z]:Z->aZb|ab写出L(G[Z])的全部元素。

[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}5.给出语言｛a n b n c1 n>=1,m>=0｝的上下文无关文法。

［分析］本题难度不大，主要是考上下文无关文法的基本概念。

上下文无关文法的基本定义是：A-> B ,A € Vn ,B€( VnU Vt) *,注意关键问题是保证a n b n的成立，即“ a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。

［答案］构造上下文无关文法如下：S->AB|AA->aAb|abB->Bc|c［扩展］凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。

基本思路是这样的：要求符合a n b n c m，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而c m做为另一个单位，初步产生式就应写为S->AB,其中A推出a n b n，B推出c m。

《编译原理》第2章 编译基础-形式语言与有穷自动机

《编译原理》第2章 编译基础-形式语言与有穷自动机
整理课件
句型、推导
G[E]： E→E+T|T T→T*F|F F→(E)|a
对于句子a+a*a 有不同 的推导
EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a
EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a
整理课件
例：奇偶测试器
0
0
1
q0
q1
∈
1
自动机：Ｍ＝（Q，∑ ，δ ，q0，Z）
Q＝｛ q0, q1}
∑ ={0,1}
q0=q0 Z={q1}
整理课件
映射函数：
δ（ q０,０)= q０ 0
0
δ（ q０,１)= q１
1
δ（ q1,０)= q１ q0
q1
δ（ q1,１)= q０
1
例：０００１１０００１
整理课件
第四节 正规文法与有穷自动机 1、正规文法 产生的语言的推导 例：文法 G=（VN，VT，P，S） 其中： VN={A，B，C}
VT={a,b,c} S=A P:A →aB A →aA
B →bB B →bC C →cC C →c
整理课件
A=>aA=>aaA=>…..=>aa…aB =>aa…abB=>aa…abb…bC =>aa…abb…bcC=> aa…abb…bccC => aa…abb…bcc…c
D→ε
Aa→bD
自然语言属于上下文有关文法
整理课件
文法的类型

编译原理第二章词法分析

编译原理第二章词法分析


1
5
6

7
a
8
b
9
2.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} 状态 A
2.3 有 限 自 动 机
2.3.1 不确定的有限自动机（简称NFA）
• • • • •
一个数学模型，它包括: 状态集合S； 输入符号集合； 转换函数move : S ({}) P(S)； 状态s0是开始状态； F S是接受状态集合。 a
识别语言 (a|b)*ab 的NFA 开始
子集构造法 • DFA的一个状态是NFA的一个状态集合 • 读了输入a1 a2 … an后， NFA能到达的所有状态：s1, s2, …, sk，则 DFA到达状态{s1, s2, …, sk} a 开始
0
b
a
1
b
2
2.3 有 限 自 动 机
2.3.3 NFA到DFA的变换
• DFA是NFA的特例，对于每个NFA M都存在一个DFA M’ ，使L(M)=L(M’)。 • 定义对状态集合I的两个运算：
2.3.2 确定的有限自动机（简称DFA) 一个数学模型，包括：
• 状态集合S； • 输入字母表； • 转换函数move : S S； • 唯一的初态 s S； b • 终态集合F S； 识别语言 (a|b)*ab 的DFA
开始 0 a
b b a
1
2
a
2.3 有 限 自 动 机
0
0
开始
1
1
2
3
4
2.3 有 限 自 动 机
• 例：识别 ={0,1}上能被能5整除的二进制数

编译原理讲义(第二章文法与语言)

编译原理讲义(第二章文法与语言)

整理ppt
9
文法和语言的定义（文法）
• 文法：文法G[Z]是一组有穷非空的重写 规则的集合。其中Z称为识别符号。G为 文法名字
• 文法例子：P22, 例子2.10。
• 所有的规则都是基于同一个符号表V。符 号表又可分划非终结符号集合VN和终结 符号结合VT。
整理ppt
10
• 〈句子〉::= <主语><谓语><状语> • <主语>::=<名词> • <名词>::=Peter | Berry | River • <谓语>::=<动词> • <动词>::=Swims • <介词>::= in • <状语>::= <介词> <名词>
=> 123
整理ppt
17
语言的定义（句型,句子）
• 对于文法G[Z]，x称为G的一个句型如果：
Z =>* x 识别符号是最简单的句型。 • G[Z]的一个句型x被称为句子，如果：
xVT* 也就是说句子是全部由终结符号组成的 句型。
整理ppt
18
语言的定义（短语，简单短语）
• 短语：对于文法G[Z]，如果Z =>* xUy， U=>+ u。显然，w=xuy是一个句型。我
• 句柄：一个句型的最左简单短语称为该 句型的句柄。
• 定义句柄的原因：在自底向上识别一个 符号串时，总是规约这个句柄。
整理ppt
20
语言的定义（文法的语言）
• 文法的语言：一个文法G[Z]的语言，用 L(G[Z])表示，定义如下：
L(G[Z]) = {x | Z=>* x 并且 x VT+} • 一个文法的语言就是该文法的所有的句子的

编译原理(龙书)习题答案(chap2-3)

编译原理(龙书)习题答案(chap2-3)

状态
a
b
-A{0}
B
A
B{0,1}
B
C
C{0,2}
B
D
+D{0,3}
E
D
+E{0,1,3} E
F
+F{0,2,3} E
D
DFA的状态图：
1） a(a | b) * a
以a开头和结尾且至少包含两个字符的a,b字符串的集合
2） (( | a)b*)*
由a和b组成的任意字符串的集合
3） (a | b)*a(a | b)(a | b)
倒数第三个字符为a的任意的a,b字符串的集合
4） a*ba*ba*ba*
包含3个b的a,b字符串的集合
5）(aa | bb)*((ab | ba)(aa | bb)*(ab | ba)(aa | bb)*)*
由相同数目的a和b组成的字符串的集合，或者空串
5） S a | S S | S S | S| ( S )
以a为变量，包括+，连接，*和括号四种运算的表 达式的集合
2.2.3 练习2.2.2中哪些文法具有二义性？ 3） 4） 5）具有二义性。 以5）为例进行说明： 给定字符串 a+a+a ，对应着两棵分析树：
DFA的转换表：
状态
ห้องสมุดไป่ตู้
a
b
+A{0,1,2,3,5,6,7,9,10,11} B
C
+B{1,2,3,4,5,6,7,9,10,11} B
C
+C{1,2,3,5,6,7,8,9,10,11} B
C
DFA的状态图：
4） (a | b)*abb(a | b)*

编译原理

编译原理

2.3.1 上下文无关文法

通常，用 1 n 表示：从1出发，经过一步或
定义：称A直接推出，即
A
仅当A 是一个产生式，且， (VT VN)* 。
如果1 2 n，则我们称这个序列是 从1到n的一个推导。若存在一个从1到n的推 导，则称1可以推导出n 。
对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i)
可见,集合A的正闭包表示A上元素a,b构成 的所有符号串的集合；
集合A的闭包比集合A的正闭包多含一个空 符号串。
2.3.1 上下文无关文法
文法： 描述语言的语法结构的形式规则 例如：He gave me a book.
<句子> <主语><谓语><间接宾语><直接宾语> <主语> <代词> <谓语> <动词> <间接宾语> <代词> <直接宾语> <冠词> <名词> <代词> He <代词> me <名词> book <冠词> a <动词> gave
例如，设X＝ABC，Y＝10A 则XY＝ABC10A，YX＝ 10AABC
注意：对任意一个符号串x， 我们有 εx ＝ xε ＝ x。
符号串的运算
3. 符号串的幂运算
设x是符号串, 则x的幂运算定义为：
x0= x1= x x2= xx
注意：x0≠ 1
x3= xxx …
xn= xx … x=x xn-1(n>0)

编译原理第二章-课后题答案

编译原理第二章-课后题答案

编译原理第二章-课后题答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第二章3.何谓“标志符”，何谓“名字”，两者的区别是什么答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。

4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。

（1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。

（2）优先顺序为↑、+、*，同级优先采用右结合。

答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256（2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=86.令文法G6为N-〉D|NDD-〉0|1|2|3|4|5|6|7|8|9（1）G6的语言L（G6）是什么（2）给出句子0127、34、568的最左推导和最右推导。

答：（1）由0到9的数字所组成的长度至少为1的字符串。

即：L（G6）={d n|n≧1,d∈{0,1,…,9}}（2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>01270127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127（其他略）7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。

答：G（S）：S->+N|-NN->ABC|CC->1|3|5|7|9A->C|2|4|6|8B->BB|0|A|ε［注］：可以有其他答案。

［常见的错误］：N->2N+1原因在于没有理解形式语言的表示法，而使用了数学表达式。

8.令文法为E->T|E+T|E-TT->F|T*F|T/FF->(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。

编译原理第二章_文法与语言

编译原理第二章_文法与语言
表示A上所有有穷长串的集合 例如：A={ab，c}，AA={…… }， AAA={…… } A+ = A* A = AA*
（8）符号串集合的自反闭包
设符号串集合为A，则A的自反闭包记为A* ，定义为： A* = A0 ∪ A1 ∪ A2∪… ∪ An
即A* = A0 ∪ A+ = {ε} ∪ A+ 例如： A= {a,b}，则 A*={ε, a, b, aa, ab, ba, bb, aaa, …… }
AB={xy|x∈A,y∈B} 如：若A={ab,c}, B={d,efg},则AB={abd,abefg,cd,cefg} 特别地，有：{ε}A=A{ε}=A
• 空集φ 表示不含任何元素的空集{ }。 有： φA=A φ= φ
<注>请区别： ε，{}，{ε}三种表示方法的含义
12
（5） 符号串的方幂
a1 an 表示：从a1出发经过一步或若干步，可推导出an 。
定义2.5 长度为n（n≥0）的推导 a1 an 表示：从a1出发经过0步（ a1 ＝an ）或若干步，可推导
出an 。
22
2.2.3 句型、句子、语言
1.句型：设G[S]是一个文法，S是它的开始符号，若S α , 则称α是文法G[S]的句型。
5
（1） <句子>::= <主语> <谓语>
推导过程(3/5)
（2） <主语>::= <代词> | <名词> （3） <代词>::= 我 | 你 | 他 （4） <名词>::=王明| 大学生|工人|英语
（5） <谓语>::=<动词> <直接宾语>

《编译原理》.第二章形式语言与自动机理论基础（ＰＤＦ）

《编译原理》.第二章形式语言与自动机理论基础（ＰＤＦ）
(2) (r)(s) (3) ( r )* (4) ( r )
正规表达式表达的语言 {}， {} {a} L( r ) , L(s) L( r ) L(s) L( r ) L(s) ( L( r ))* L( r )
9
2、有关正规式及正规集的说明
注意：
定义中的括号主要用于规定运算顺序。
一般规定优先级从高到低依次为 *, • , |， 可省略某些括号
A→x A→y 21
例子： 求正规式(a|b)(a|b|0|1)*对应的正规文法 G[S]:
S→aA|bA A→aA|bA|0A|1A|ε
22
练习： 求正规式a(a|d)*对应的正规文法
G[S]:
S→aA A→aA|dA|ε
23
正规式与有限自动机
ƒ定理2.4
⑪ 字母表∑上的确定的有限自动机M所接受的语言 L(M)是∑上的一个正规集；
正规文法转换成正规式
对于Ｇ = (ＶT，ＶN，S，P)，存在一个Σ=ＶT上的正规 式r：L(G)=L(r)
步骤：
利用转换规则将每条产生式改写成正规式 用代入法解正规式方程组，最后剩下一个开始符号定义的正
规式，其中不含非终结符
文法产生式 正规式
规则1 规则2
A→xB B→y
A→xA|y
A=xy A=x*y
G[S]:
S→aA|a A→aA|dA|a|d
对应的正规式：
a(a|d)*
20
正规式转换成正规文法
步骤：
构造产生式S →r，并将S定义为G的开始符号
不断利用如下规则做变换，直到每个产生是最多含 有一个终结符为止
规则1
规则2 规则3
正规式 A=xy
A=x*y A=x|y

编译原理 第二章习题答案

编译原理 第二章习题答案

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素。

[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}==============================================2. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D===============================================3.已知文法G[S]：S→dAB A→aA|a B→ε|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案]正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε===================================================================== ==========4.已知文法G[Z]：Z->aZb|ab写出L(G[Z])的全部元素。

[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}===================================================================== =========5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。

编译原理 第二章 第二部分

编译原理 第二章 第二部分
附加题以班级姓名学号.doc为文件名 发至邮箱
§2.3 句型的分析
• 句型的分析是指构造一种算法，用以判断所给符号串是否为某一文 法的句型(或句子) 。 • 分两类方法： • 自顶向下分析：从开始符推导出句子或句型 • 自底向上分析：从句子或句型归约出开始符
例：用以下文法推导出句子i+i*i
• E → E+T|T • T → T*F|F • F →(E)|i
语法树的应用——语法分析（自顶向下分析，自底向上分析） 定义2.8短语:对于句型η的一棵语法树，若它的一棵子树的根结点标 记为A，且将此子树的末端结点标记自左至右排列起来所形成的符 号串为β，则β是句型η(相对于A)的一个短语； 定义2.8‘直接短语:对于句型η的一棵语法树，若它的一棵子树的根结 点标记为A，且将此子树的末端结点标记自左至右排列起来所形成 的符号串为β，若此子树为直接子树，则β是句型η(相对于产生式 A—>β)的直接短语。 定义2.9 句柄:最左直接短语. • 对于无二义性文法，可保证句柄归约的唯一性。
任给的前后文无关文法是否具 有二义性是不可判定的。
• 存在一些检查文法二义性的充分条件 ， 如含有既是左递归又是右递归的非终结 符的文法必是二义性文法。 • 对某些具体文法可判断其二义性或无二 义性，如LL(1),LR()等文法。 • 存在先天二义性语言：用于定义语言的 一切文法都是二义性的。
3. 短语和句柄
2.语法树和二义性（cont.）
•语法树与推导序列间为1对多关系，但一语法树只对应于唯一的最 左推导和最右推导。 •如果L(G)的某个句子(句型)可能对应不只一个最左推导和最右推导， 称这样的文法G树，则称此文法为 无二义性的。
•例如：G(E):E → E+E | E*E | (E) | i

现代编译原理－－第二章（语法分析之LR（1））

现代编译原理－－第二章（语法分析之LR（1））

现代编译原理－－第⼆章（语法分析之LR（1）） （转载请表明出处）前⾯已经介绍过LL（1），以及如何使⽤LL（1）⽂法。

但是LL（K）⽂法要求在看到K个字母的情况下必须做出预测，这相⽐于LR（K）⽂法⽽⾔就逊⾊很多。

LR（K）⽂法的定义是：从左⾄右分析，最右推导，超前查看K个单词。

先看⼀个例⼦，来对LR⽂法有个⼤致的印象。

以上就是使⽤LR⽂法对源码进⾏分析的例⼦。

注意到在LR⽂法中只有三个动作：移进，规约和接受，这三个动作也是通过查表来得到的。

任何时候如果都是唯⼀确定这三个动作中的⼀个，我们就能让LR⽂法正确的运⾏。

为了更好的理解LR（K）⽂法，我们先介绍以下最简单的LR（0）⽂法。

因为动作是根据表来确定，所以，表的构建依然是我们构建的重点，先来看看⼀个表的最终形式： ⾸先要说明的是，构建这张表的时候，我们使⽤到了状态机，⾏标就代表状态。

列标由两部分组成，分别是终结符，和⾮终结符。

s代表移进，r代表规约，g代表跳转，a代表接受，他们后⾯跟着的数字，除了r以外，都是状态的标号，只有r后⾯的数字指的时规约到第⼏个产⽣式。

所有空的地⽅都代表出现错误。

可见在⾮终结符下只有跳转。

为了构建这个表，我们⾸先构建状态机。

我们从⼀个基本的⽂法开始，⽂法如下： 我们向产⽣式中添加⼀个点，形成这种形式，称为项。

这个点的位置告诉我们当前在状态是什么。

点每移动⼀次，我们跳转⼀个状态。

点前⾯的字符串表⽰我们已经读取的历史，点后⾯的字符串表⽰我们希望得到的。

也就是这种表达⽅式，既可以展望未来，也可以回顾过去。

上⾯这个起始项中，我们希望得下⼀次得到⼀个S⾮终结符，可以看出1和2产⽣式是S的等价形式，如果我们得到1和2产⽣式的右部，我们就相当于得到了⾮终结符S，所以，我们的起始状态为： 我们称第⼀个产⽣式为核⼼项，其他为普通项。

这个状态我们称为状态1，所有的状态都是由这个状态中每个项的点的移动得到的。

例如，状态1吃掉⼀个终结符x时，状态1的第⼆个项中的点要向右移动⼀位。

计算机程序编译原理 第2章 形式语言概论

计算机程序编译原理 第2章 形式语言概论

文法举例
例2.6 1型文法G6=（VN ，VT ，P，S），其中VN={S，X，Y，Z}， VT={x ， y ， z} ， P={S→xSYZ|xYZ, xY→xy, yY→yy, yZ→yz, ZY→YZ, zZ→zz} 例2.7 2型文法G7=（VN，VT，P，S），其中VN={S，T}，VT={a， b，c, d}，P={S→aTd, T→bT|cT|b|c } 例2.8 2型文法G8=（VN，VT，P，B），其中VN={B}，VT={(，) }， P={B→(B)|BB|( )} 例2.9 2型文法G9=（VN，VT，P，S），其中VN={S}，VT={0，1 }， P={S→0S1, S→01} 例2.10 正规文法G10=（VN，VT，P，A），其中VN={A, B, C, D}， VT={x, y, z }，P={A→xB|yC, B→zB|y|yC, C→xD, D→yD|x }
文法和语言的几点说明
(1) 文法中某些非终结符不在任何规则的右部出现，该非 终结符称为不可到达的； (2) 文法中某些非终结符，由它不能推出终结符号串来， 称为不可终止的（无用非终结符）； (3)可空终结符,可以用于消除左递归； (4)一个文法，如果它的一个句子有两棵或两棵以上的语法 树，则称该句子具有二义性。如果一个文法含有二义性的 句子，则该文法具有二义性。形如U→U的产生式。会引起 文法的二义性。
推导
定 义 2.3 G= （ VN, VT, P, S ） ， α→β 是 文 法 G 的 产 生 式 ， γ,δ∈V* ， 若 有 v, w 满 足 ： v=γαδ, w= γβδ, 则 说 ： v （应用规则α→β）直接产生w 或说：w是v的直接推导 或说：w 直接归约到v 记作 v ⇒w。 例 G[S]：S→0S1， S→01 直接推导： 0S1⇒0011 （v=0S1，w=0011，使用规则S→01，γ=0，δ=1） S ⇒0S1 （v=S，w=0S1，使用规则S→0S1，γ=ε，δ= ε ） 0S1⇒00S11 （v=0S1，w=00S11，使用规则S→0S1，γ=0，δ=1） 定义2 定义2.4 v⇒+u 若存在v =α0 =>α1=>…=>αn=u, (n>0) 则称u为u的一个推导，记为v⇒+u。 定义2 定义2.5 v⇒*u 表示v⇒+u 或 v=u

编译原理第二章(2-构造文法)

编译原理第二章(2-构造文法)

直接推导举例
例1 文法G[E]： E →E+T|T T →T*F|F F →（E）|i
* T F * T*F F
例2 见P14
2.3.3 和语言有关的几个概念
2. 推导
设α0、α1、…αn均为(VT∪VN)*中的符号串，且有 α0α1α2…αn-1αn 则称以上序列是长度为n的推导，即α0可经过n步推导得到αn。

符号串的方幂 设x是符号串，xn 是x自身连结n次。并且x0＝ ε 则 x1＝ x x2＝ xx xn＝ xx……x= x xn-1 n个 例如, 设 x=abc，则 x1＝ abc x2＝ abcabc ……

符号串集合的方幂 A是符号串的集合， An 是集合A自身n次相乘， 并且A0＝ {ε} 则 A 1＝ A A2＝ AA An＝ AA……A= A An-1 (n>0) n个A 例1 A={a,b} A0＝ {ε} A1 ＝ {a,b} A2＝ {aa,ab,ba,bb} A3＝ {aa,ab,ba,bb}· {a,b} ＝ { aaa,aab,aba,abb,baa,bab,bba,bbb }
2.3.2文法的形式定义
文法是产生式的有穷非空的集合。 文法G是一个四元组，G[S]=（VT，VN，P，S）。 VT——终结符号集。 VN——非终结符号集。 S ——开始符号。至少要在一条产生式中作为左部出现。 P ——表示产生式的有穷非空的集合。
例1
定义标识符的文法
G[<标识符>]=（{ A,B,…,Y,Z,0,1,…,9}， {<标识符>,<字母>,<数字>}，P，<标识符>） P 定义为： <标识符>→<字母>|<标识符><字母>|<标识符><数字> <字母>→A|B|C|D|E|F|G|……|U|V|W|X|Y|Z

《编译原理》第2章 文法和语言的基本知识

《编译原理》第2章 文法和语言的基本知识
第2章
文法和语言的基本知识
教学目标
1. 本章是编译原理课程的理论基础，要求掌握形 式语言的基本术语和概念,重点掌握短语、直接 短语、句柄、素短语、规范推导、规范归约。 2. 掌握文法和语言的定义，文法的二义性与递归 性的判断方法及句型的分析方法，文法分类。 3. 熟练使用文法定义程序设计语言的单词和语法 成分。 4. 对形式语言的理论有一个初步认识。
2013年8月16日
符号串集合的闭包运算
设A是符号串集合，定义 A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪…… 称为集合A的正闭包。 A*＝ A0 ∪A＋ 称为集合A的闭包。 例：A={x,y} A＋＝？ {x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
A1 A A A2 A A3 A
2013年8月16日
文法的直观概念：以汉语中的“我是大学生”为例。
①一组终结符号 采用BNF来表示汉语句子的构成规则为： （语言的基本符号） 〈句子〉：：=〈主语〉〈谓语〉 ②一组非终结符号 〈主语〉：：=〈代词〉|〈名词〉 （语法单位） ③一个开始符号 〈代词〉：：=我|你|他 文法的四部分 （一个特殊的非终结 〈名词〉：：=王明|大学生|工人|英语 符号，最感兴趣的语 〈谓语〉：：=〈动词〉〈直接宾语〉 法单位） 〈动词〉：：=是|学习 ④一组规则（也称产 生式或产生规则） 〈直接宾语〉：：=〈代词〉|〈名词〉 根据上述规则，“我是大学生”的构成符合上述规则，而“我 大学生是”不符合，我们说它不是句子。这些规则成为我们判别 句子结构合法与否的依据。换句话说，这些规则看成是一种元语 言，用它描述汉语。这种的语言描述成为文法。
说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。 (2) 从一组规则可推出不同的句子，如以上规则还可推出 “大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例： ‚变量是一个算术表达式；若E和E2是算术表达式， 则E1＋E2,E1*E2和（El）也是算术表达式。‛ 对于这个定义，若用产生式来描述，则可将它写成： E→i E→E＋E E→E * E E→（E) E：表示‚算术表达式‛ i：表示‚变量‛

一个上下文无关文法G是一个四元式 （VT,VN,S,ρ)， 其中 VT是一个非空有限集，它的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符 号，VT∩VN＝φ S是一个非终结符号，称为开始符号； ρ是一个产生式集合（有限），每个产生式的形式 是P→α，其中，P€ VN， α €(VT∪VN)* 。开始 符号S至少必须在某个产生式的左部出现一次。
注意，文法的二义性和语言的二义性是
两个不同的概念。我们可能有两个不同 的文法G和G‘．其中一个是二义的而另一 个是无二义的，但是却有L(G)=L(G’）， 也就是说，这两个文法所产生的语言是 相同的。
在文法(2.1)中，假若规定了运算符‘十’
与‘*’的优先顺序和结合规则．比方说， 让‘*’的优先性高于‘＋’，且它们都 服从左结合，那么，就可以构造出一个 无二义文法： E→T | E十T T →F | T*F F→（E) | i
例题与习题解答
[例2.1]： 试构造生成语言L={anbnci|n1, i 0}的文法
分析：要求a和b的个数一样多，并至少为一个，而c 的个数为0个以上即可，所以可以用一个终结符去 生成anbn串，用另一个非终结符去生成ci 。 G(Z): ZAB A aAb|ab B cB|
[例2.2]： 已知语言L={anbbn| n 1}, 写出产生L的文法。 [解]： G[S]: S aAb A aAb|b [例2.3]： 已知文法G=({A,B,C},{a,b,c},A,P) 其中产生式P由以下组成： A abc A aBbc Bb bB Bc Cbcc bC Cb aC aaB aC aa 问：此文法表式的语言是什么？
作为描述程序语言的上下文无关文法，对它有几点限 制。 第一，文法中不含任何下面形式的产生式 P→P 因为，这种产生式除了引起二义性外没有任何用处。 第二，每个非终结符P必须都有用处。这一方面意味着， 必须存在含P的句型；也就是，从开始符号S出发， 存在推导 S =>αPβ 另一方面意味着，必须存在终结符串γ€VT*，使得P =>γ,也就是，对于P不存在永不终结的回路。

对于多个左部相同的产生式：
P→α1 P→α2 …… P→αn 可写为： P→α1| α2…… αn 其中每个αi称为是P的一个候选式。 → 读为‚定义为‛， | 读为‚或‛。
一般，用大写字母A,B,C…或汉语词组
（如，算术表达式）代表非终结符号， 用小写字母a,b,c…代表终结符，用α、 β、γ等代表由终结符和非终结符组成 的符号串。
例如，
∑＝{a,b}，则 ∑﹡={ε,a,b,aa,ab,ba,bb,aaa,…｝。 Ф表示不含任何元素的空集｛｝。 注意：要注意空字ε、{}和{ε}的区别。
2、∑﹡的子集U和V的（连接）积 UV＝｛αβ|α∈U&β∈V} 即集合UV中的符号串是由U和V的符号串连接 而成的。 注意，一般而言，UV≠VU，但(UV)W=U(VW）。 3、V自身的n次（连接）积： 记为 Vⁿ=VV……V 规定：V°={ε} 令 V﹡= V0∪V¹ ∪V²∪V ³∪…… 称V*是V的闭包。记V﹢=VV*，称V+是V的正则闭 包。

语义
一个语言的语义是指这样的一组规则，使用
它可以定义一个程序的意义。这些规则称为 语义规则。
2.2 高级语言的分类
一、强制式语言 二、应用式语言 三、基于规则的语言 四、面向对象语言
2.3 程序语言的语法描述
重点讨论上下文无关文法、语法分析树，以
及文法的二义性问题。最后还将对形式语言 进行简单概述。 设Σ是一个有穷字母表，它的每个元素称为 一个符号。 1、Σ上的一个符号串：是指由Σ中的符号所 构成的一个有穷序列。不包含任何符号的序 列称为空字，记为ε。用Σ﹡表示Σ上的所 有符号串的全体，空字ε也包括在其中。
例： G = ({E}, {i, +, *, (, ) } , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的语法树： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) (2) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)
语法分析树与二义性
用一张图表示一个句型的推导，这种表示
称为语法分析树，或简称为语法树。 一棵语法树表示了一个句型种种可能的 （但未必是所有的）不同推导过程，包括 最左（最右）推导。 如果一个文法存在某个句子对应两棵不同 的语法树，则称这个文法是二义的。也就 是说，若一个文法中存在某个句子，它有 两个不同的最左（最右）推导，则这个文 法是二义的。
语法分析树:用一种图示化的方法来表示这种推导
句子 主语 谓语 间接宾语 直接宾语
代词
动词
代词
冠词
名词
He
gave
me
a
book
上下文无关文法描述
一个上下文无关文法G包括四个组成部分：一
组终结符号，一组非终结符号，一个开始符 号，以及一组产生式。 终结符号乃是组成语言的基本符号，在程序 语言中就是以前屡次提到的单词符号，如基 本字、标识符、常数、算符和界符等。从语 法分析的角度来看，终结符号是一个语言的 不可再分的基本符号。

词法规则是指单词符号的形成规则。
语言的单词符号是由词法规则所确定的。
词法规则规定了字母表中哪样的字符串是 一个单词符号。 单词符号一般包括：各类型的常数、标识 符、基本字、算符和界符等。
语言的语法规则规定了如何从单词符号形成更大的 结构（即语法单位），换言之，语法规则是语法单 位的形成规则。 一般程序语言的语法单位有：表达式、语句、分程 序、函数、过程和程序等等。 语言的词法规则和语法规则定义了程序的形式结构， 是判断输人字符串是否构成一个形式上正确（即合 式）程序的依据。

＜句子＞ ==> ＜主语＞＜谓语＞＜间接宾语＞＜直接宾 语＞ ==> ＜代词＞＜谓语＞＜间接宾语＞＜直接宾语＞ ==> He＜谓语＞＜间接宾语＞＜直接宾语＞ ==> He＜动词＞＜间接宾语＞＜直接宾语＞ ==> He gave＜间接宾语＞＜直接宾语＞ ==>He gave＜代词＞＜直接宾语＞ ==> He gave me＜直接宾语＞ ==> He gave me＜冠词＞＜名词＞ ==> H gave me a＜名词＞ ==> He gave me a book

其中1型文法也称上下文有关文法。这种文法
意味着，对非终结符进行替换式务必考虑上 下文并且一般不允许替换成空串。 ※2型文法也称上下文无关文法，注意其语言定 义： G的任何产生式为A→β，A∈VN， β∈ （VN∪VT)* 表明凡出现在产生式左边的符号都是 非终结符。
※3型文法也称右线性文法。 3型文法还有另一种形式，称左线性文法： 一个文法G为左线性文法，如果G的任何产生 式为 A→B 或A→ ，其中∈VT* , A、B ∈ VN 由于3型文法等价于正规式所以 也称正规文法。
设有文法G S→P|aPPb P →ba|bQa Q →ab 求语言L(G). 解： L(G)={ba,baba,abab,ababab… } 例2。3 构造一个文法G3使 L(G3)={anbn|n≥1} 解; S→aSb|ab
最左(最右)推导
所谓最左推导指：Βιβλιοθήκη 何一步a => β都是对α中 的最左非终结符进行替换的。 同样，可定义最右推导。 （i*i＋i)的最右推导： E =>(E) =>(E＋E) =>(E＋i) =>(E*E＋i) =>(E*i＋i) =>(i*i＋i)
第二章 高级语言及其语法描述
主要内容
2.1 程序语言的定义 2.2 高级语言的分类 2.3 程序语言的语法描述
2.1 程序语言的定义
一个程序语言是一个记号系统。程序语言主
要由语法和语义两个方面定义。
语法
任何语言程序都可看成是一定字符集（称为字母表） 上的一字符串（有限序列）。但是，什么样的字符 串才算是一个合式的程序呢？ 所谓一个语言的语法是指这样的一组规则，用它可 以形成和产生一个合式的程序。 这些规则的一部分称为词法规则，另一部分称为语 法规则（或产生规则）。
上下文无关文法
文法是描述语言的语法结构的形式规则
（即语法规则）。 上下文无关文法所定义的语法范畴（或语 法单位）是完全独立于这种范畴可能出现 的环境的。 上下文无关文法不宜于描述任何自然语言， 但对于现今的程序语言来说，上下文无关 文法基本上是够用了。
从一个具体英文例句的分析出发，引进有关上下文无关文法的 基本概念。比如，我们写了这样一个句子： He gave me a book． 这是一个语法上正确的句子，因为它满足英语中的基本语法规则。 有下面语法规则： ＜句子＞→＜主语＞＜谓语＞＜间接宾语＞＜直接宾语＞ ＜主语＞→<代词> ＜谓语＞→<动词> ＜间接宾语＞→＜代词＞ ＜直接宾语＞→＜冠词＞＜名词＞ <代词＞→He ＜代词＞→me ＜冠词＞→a ＜动词>→gave ＜名词＞→book

假定G是一个文法，S是它的开始符号。
如果S => α，则称α是一个句型。仅含 终结符号的句型是一个句子。 文法G所产生的句子的全体是一个语言， 将它记为L(G) L(G) =｛α|S => α&α∈VT﹡｝