痤疮王编译原理

2021年1月19日发(作者：6450)
1
、

给出如图所示
NFA
等价的
DFA








思路：子集划分方法。参考答案（矩阵表示）



a

{ i,1,2}

S

{1,2,3}

A

{1,2,3}

A

{1,2,3,5,6,f}

C

{1,2,4}

B


*
{1,2,3,5,6,f}

C
{1,2,3,5,6,f}

C

*
{1,2,4,5,6,f}

D
{1,2,3,6,f}

F

{1,2,4,6,f}

E
*
{1,2,3,6,f}

F

{1,2,3,6,f}

F
*
{1,2,3,5,6,f}

C

2
、

构造正规式
1(1|0)
*
101
相应的
DFA.

b

{1,2,4}

B

{1,2,4}

B

{1,2,4,5,6,f}

D

{1,2,4,6,f}

E

{1,2,4,5,6,f}

D

{1,2,4,5,6,f}

D

{1,2,4,6,f}

E

3
、

为正规式（
ab
）
*
a(a|b)
构造
NFA
、
DFA
。




解题思路：正则式无非是连接< br>/
或
/
星闭包几个运算表达的串，
FA
是状态和弧构成的图， 知
道他们的映射关系，还是比较简单的，先画
NFA
，再确定化。建议仿照
2
，自己联系一
下。


为什么插不进去？？？
4
、

（
1
）考虑正规表达式
L(r)
的一个正规文法。

（
2
）考虑如图所示的
NFA N,
构造可以生成语言
L(N)
的

一个正规文法
.

解题思路：（
1
）自动机、正规文法、正 则式是对正规语言的三种描述方式，从描述语言的
角度，三者是等价的。这个同第
2
题 。

1
（
1|0
）
*
101
，构造可以生 成语言

正则式到正则文法，一定要知道，正则文法形式上是左端是一个非终结符，右端全部是 一
个终结符紧跟一个非终结符（或全部是一个非终结符紧跟一个终结符）的串，怎么看呢？
眼睛 放大看，再长的串，用一个非终结符表示的方法看，也一定知道，既然是正则式，那
么一定可以用自动机 或和正则文法表示的。当然可以借助中介自动机完成该题。


这里采用中介，看题
2
的图，有：
S-->1A, A-->0A|1B, B-->0C|1B, C-->0A|1D, D-->1B|0C



5
、考虑如下文法
G
：


S-->1S|0S|1A


A-->0B|1B


B-->
e (
空串
)

(1)

试构造语言为
L(G)
的一个正规表达式。

(2)

试构造语言为
L(G)
的一个有限自动机。



主要考虑大家思维广阔点，不要拘泥，知道要干什么，很关键

解题套路：（
1
），不需要多高深的技术，逐层带入，假设
a=
（
0|1
），则< br>S=aS|a,
大致可以
想象描述怎样的串吧？！（
0|1
）
+;(2)
6
、构造产生如下语言的上下文无关文法：

（
1
）
{a
n
b
n
|n>0}

（
2
）
{wcw
R
|w
由
a,b
组成的任意串
}

（
3
）
{ww
R
|w< br>由
a,b
组成的任意串
}

（
4
）
{w|w
由
a,b
组成的任意串且
w
与其逆串相等
}

(5)

{
w|w
由
a,b
组成的任意串且
w
中
a
的个数是
b
个数的
2
倍
}

参考答案：（
1
）
S-->aSb|ab;

(2) S-->aSa|bSb|c














(3) S-->aSa|bSb|e(e--
空串
)












(4) S-->aSa|bSb|a|b|e













(5)--> e|Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSa a|baSa|baaS

7
、考虑下面的文法：



S-->aS|aSbS|e



e
是空串的意思

这个文法是二义的，试给出串
a a b
的两个不同的：

（
1
）

分析树。

（
2
）

最左推导。

（
3
）

最右推导。

8
、

已知文法
G[S]:


S-->MH|a


H-->LS|e
e
是空串的意思


M-->K|MBL


K-->dML


L-->bHf
























判断
G
是否是
LL(1)
文法，如果是，构造
LL(1)
分析表。

9
、

已知文法
G[S]:


S-->MBf


M-->BbS|a


B-->dMg|e
e
是空串的意思


< br>判断
G
是否是
LL(1)
文法，如果是，构造
LL(1)分析表。

10
、

对于文法
G[V]:


V-->N|N[E]


E-->V|V+E


N-->i





(1)

构造
G[V]< br>的优先关系表，判断
G[V]
是否为算符优先文法。


(2)

分析输入串
i[i+i+i]
是否是
G[V]
的句子。

11
、某语言的文法
G(E)
为：


E-->aTd|e
e
是空串的意思


T-->Eb|ac|e



（
1
）

请证明
G
（
E）不是
LR(0)
文法而是
SLR(1)
文法，请给出该文法的分析表。

（
2
）

给出输入串
aabdbd #
的分析过程，并说明是否是
G(E)
的句子。

12
、

对于文法
G[S]:

S-->a|^|(T)

T-->T,S| S









构造文法
G[S]
的算法优先关系矩阵，并判断该文法是否是算符优先文法。

13
、划分下列程序的所有基本块，画出程序的流图。

（
1
）

read x
（
2
）

read y

（
3
）

r:=x mod y

（
4
）

if r=0 goto (8)

（
5
）

x:=y

（
6
）

y:=r

（
7
）

goto (3)

（
8
）

write y

（
9
）

halt

14
、已知四元式的代码序列如下：

（
1
）

read a

（
2
）

read b

（
3
）

h
：
=1

（
4
）

f
：
=1

（
5
）

if f>3 goto (18)

（
6
）

g
：
:=1

（
7
）

c
：
=a

（
8
）

d
：
=b

（
9
）

if g>2 goto (14)

（
10
）

c
：
=c*c

（
11
）

d
：
=d*d

（
12
）

g:
：
=g+1

（
13
）

goto (9)

（
14
）

f
：
=f+1

（
15
）

e
：
=c+d

（
16
）

h
：
=h*e

（
17
）

goto (5)

（
18
）

write h

（
19
）

halt

完成一下任务：

（
1
）

划分为基本块并画出其流程图。

（
2
）

求每个每个结点的必经结点集。

（
3
）

求流图的回边。

（
4
）

找出流图中的循环。

15
、已知四元式的代码序列如下
:

(1)

j
：
=1

(2)

write j

(3)

writeln

(4)

R[j]
：
=1

(5)

i
：
=1

(6)

if i>12 goto (22)

(7)

i
：
=i+1

(8)

k
：
=1

(9)

if k>4 goto (18)

(10)k
：
=k+1

(11)j
：
=j+1

(12)if j14 goto (14)

(13)j
：
=j+1

(14)if R[j]
1 goto (9)

(15)j
：
=j+1

(16)if j
14 goto (14)

(17)goto (13)

(18)write j

(19)writeln

(20)R[j]
：
=1

(21)Goto (6)

(22)Halt

1
、

划分的基本块并画出其流图；

2
、

求每个结点的必经结点集；

3
、

求流图中的回边；

4
、

找出流图中的所有循环。