当前位置：文档之家 › 编译原理 习题1

编译原理 习题1

  • 格式：doc
  • 大小：29.50 KB
  • 文档页数：2

习题

a. 以a开头和结尾的所有小写字母串。

a(a|b|c|…|z)*a

表达的语言：{aa,aaa,aba,aca,…}

串a也符合要求

故最后的正则表达式为：a| a(a|b|c|…|z)*a

c.第1个不为0的所有数字串。

正则表达式为：(1|2|3|…|9)(0| 1|2|3|…|9)*

e.每个2均在每个9之前的所有数字串。（有二义性）

理解1：形如 29, 1298 , 3329442955

(0|1|3|4|5|6|7|8)*29（0|1|3|4|5|6|7|8)*

((0|1|3|4|5|6|7|8)*29(0|1|3|4|5|6|7|8)* )*

最后写成：(0|1|3|4|5|6|7|8)*29（0|1|3|4|5|6|7|8)*((0|1|3|4|5|6|7|8)*29(0|1|3|4|5|6|7|8)* )*

理解2：形如29, 1298 , 3329442955, 523495, 523495523495

(0|1|3|4|5|6|7|8)*2(0|1|3|4|5|6|7|8)*9(0|1|3|4|5|6|7|8)*

((0|1|3|4|5|6|7|8)*2(0|1|3|4|5|6|7|8)*9（0|1|3|4|5|6|7|8)* )*

最后写成：

(0|1|3|4|5|6|7|8)*2(0|1|3|4|5|6|7|8)*9(0|1|3|4|5|6|7|8)*((0|1|3|4|5|6|7|8)*2(0|1|3|4|5|6|7|8)*9（0|1|3|4|5|6|7|8)* )*

g.包含单数个a或/和单数个b的所有a串和b串。

所有a串和b串，形如：ab , aab, abb, aabb, abb, aabb, aaabb,…..

正则表达式: aa*bb*

包含单数个a的所有a串和b串。

正则表达式: a(aa)*bb*

包含单数个b的所有a串和b串。 正则表达式: aa*b(bb)*

包含单数个a或单数个b的所有a串和b串。

正则表达式: a(aa)*bb*| aa*b(bb)*

包含单数个a和单数个b的所有a串和b串。

正则表达式: a(aa)* b(bb)*

包含单数个a或/和单数个b的所有a串和b串。

正则表达式: a(aa)*bb*| aa*b(bb)*| a(aa)* b(bb)*

i. a和b数目相等的所有a串和b串。

形如：ab, aabb, aaabbb, aaaabbbb

正则表达式可写成 aa*bb* 但不能保证a与b的数目相等。

在程序设计时可以加以限定，如设置一个栈，每获得1个a压栈每获得1个b从栈中弹出1个a，当栈为空时，串得到识别。

合集下载

编译原理习题习题资料

编译原理习题习题资料

6、写一个文法，使其语言是奇数集，且每一个奇数不以零开头。

13、给出下面语言的相应文法：

L1={anbnci|n≧1,i≧0}L2={aibncn|n≧1,i≧0}L3={anbnambm|m,n≧0}L4={1n0m1m 0n|m,n≧0} 答：(1) S->AB A->aAb|ab B->Bc|ε (2) S->AB B->bBc|bc A->Aa|ε

(3) S->AA A-> aAb|ε (4) S->1S0|A A-> 0A1|ε

16、给出下面的正规表达式。

（1）以01结尾的二进制数串; 正规式 (0|1)*01 或 (0*1*)*01

(2) 能被5整除的十进制整数;

(0|1|2|3|4|5|6|7|8|9)*(0|5)或(0*1*2*3*4*5*6*7*8*9*)*(0|5)或(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)

(3)包含奇数个1或者奇数个0的二进制串; 0*1(0|10*1)* 正规式0*1(0|10*1)*

|1*0(1|01*0)*

20、考虑下面文法G1：S → a | ∧ | （T） T → T，S | S

（1）消去G1的左递归；

S → a | ∧ | （T） T → ST’ T’ → ，S T’ |ε

（2）经改写后的文法是否是LL(1)文法，给出预测分析表。

FIRST(a)∩ FIRST(∧) ∩FIRST((T))=中

FIRST(, S T’ )∩ FIRST(ε)= 中 FIRST(T’ )∩ FOLLOW(T’ )=中

经改写后的文法满足3个条件，所以是LL(1)的

22、对下面的文法G

E→TE' E'→+E|ε T→FT' T'→T|ε F→PF' F'→*F'|ε P→(E)|a|b|∧

编译原理习题

编译原理习题

编译原理习题

一、是非题

1．编译程序是对高级语言程序的解释执行。( )

2．一个有限状态自动机中，有且仅有一个唯一的终态。()

3．两个正规集相等的必要条件是他们对应的正规式等价。 ( )

4. 对任何正规表达式e，都存在一个DFA M，满足L(M)＝L(e)。

二、选择题

1．词法分析器的输出结果是_____。

A．( ) 记号 B．( ) 相应条目在符号表中的位置

C．( ) 记号和属性二元组 D．( ) 属性值

2． 正规式 M 1 和 M 2 等价是指_____。

A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等

C．( ) M1和M2所识别的语言集相等 D．( ) M1和M2状态数和有向边条数相等

3．语言是

A．句子的集合 B．产生式的集合

C．符号串的集合 D．句型的集合

4．编译程序前三个阶段完成的工作是

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成

D．词法分析、语法分析和代码优化

5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即

A． 字符 B．单词 C．句子 D．句型

6．构造编译程序应掌握______。

A．( )源程序 B．( ) 目标语言

C．( ) 编译方法 D．( ) 以上三项都是

7．词法分析的任务是

A．识别单词 B．分析句子的含义

C．识别句子 D．生成目标代码

三、填空题

1．计算机执行用高级语言编写的程序主要有两种途径：（ ）和 （ ）。

编译原理习题 2

编译原理习题 2

试卷一

一、是非题(下列各题，你认为正确的，请在题干的括号内打“ √”，错的打“×”。每题1分， 共5分)

1、算符优先关系表不一定存在对应的优先函数。………………………………………（ ）

2、数组元素的地址计算与数组的存储方式有关。………………………………………（ ）

3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。…………………………（ ）

4、每个文法都能改写为LL(1)文法。 ……………………………………………………（ ）

5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 ……………………（ ）

二、填空题(每题2分，共20分)

1、从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。

2、扫描器的任务是从（ ）中识别出一个个（ ）。

3、所谓最右推导是指：（ ）。

4、语法分析最常用的两类方法是（ ）和（ ）分析法。

5、一个上下文无关文法所含四个组成部分是（ ）。

6、所谓语法制导翻译方法是（ ）。

7、符号表中的信息栏中登记了每个名字的有关的性质，如（ ）等等。

8、一个过程相应的DISPLAY表的内容为（ ）。

9、常用的两种动态存贮分配办法是（ ）动态分配和（ ）动态分配。

10、产生式是用于定义（ ）的一种书写规则。

三、名词解释(每题2分，共10分)

1、遍－－

2、无环路有向图(DAG)－－

3、语法分析－－

4、短语－－

5、后缀式－－

四、简述题(每题4分，共24分)

1、考虑下面程序

…………

Var a：integer；

Procedure S(X)；

Var X：integer；

Begin

a：＝a＋1；

X：＝a＋X

End；

Begin

a：＝5；

编译原理习题 3

编译原理习题 3

1 一、名词解释

1.正规文法

2. 编译程序

3. 文法的推导

4.子树

5. LL(1)文法

6. 文法的句子

7. LR（0）文法

8. 请写出四种参数传递的方式

二综合题

1. 请写出编译程序的五个步骤。

2. 给定文法G：（0）S→aAcBe （1）A→b

（2）A→Ab （3）B→d

若有句型 aAbcde，试问b是它的直接短语吗？它的短语是什么？句柄是什么？

3. 设有文法:S->aSbS|bSaS|ε

通过为句子abab建立两个最左推导来说明该文法是二义文法。

4. 写出下列语言的上下文无关文法：0,|)(mnGLcbamnn

5. 写出下列语言的上下文无关文法：L(G)={anbncmdm, n, m≥0}。

6. 令文法G：S aS

Sa | b

给出句子aaaab 的最左推导。

7. 证明下面的文法是有二义性的。

E→-EE

E→-E

E→a|b|c

8. 文法G为： E→E+T|T

T→T*F|F

F→(E)|i

（1）画出句型(E+F)*i的语法树；

（2）给出句型(E+F)*i短语，简单(直接)短语,句柄。

9. 设字母表∑={a,b}，给出∑上的正则式R=（a | ba）*

（1）构造NFA M，使得L（M）=L（R）。

（2）将NFA M确定化、最小化，得到minDFA M。

（3）求右线形文法G，使得L（G）=L（M）

10. 设字母表∑={0,1}，给出∑上的正则式R=0（0 | 1）*1

（1）构造NFA M，使得L（M）=L（R）。

（2）将NFA M确定化，最小化，得到minDFA M。