编译原理作业题.docx
- 文档编号:7496092
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:23
- 大小:405.33KB
编译原理作业题.docx
《编译原理作业题.docx》由会员分享,可在线阅读,更多相关《编译原理作业题.docx(23页珍藏版)》请在冰点文库上搜索。
编译原理作业题
第二章
2.1设字母表A={a},符号串x=aaa,写出下列符号串及其长度:
x0,xx,x5以及A+和A*.
x0=(aaa)0=ε|x0|=0
xx=aaaaaa|xx|=6
x5=aaaaaaaaaaaaaaa|x5|=15
A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}
A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}
2.2令∑={a,b,c},又令x=abc,y=b,z=aab,写出如下符号串及它们的长度:
xy,xyz,(xy)3
xy=abcb|xy|=4
xyz=abcbaab|xyz|=7
(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12
2.3设有文法G[S]:
S∷=SS*|SS+|a,写出符号串aa+a*规范推导,并构造语法树。
S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
2.4已知文法G[Z]:
Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。
Z=>U0=>Z10=>U010=>1010
Z=>U0=>Z10=>V110=>0110
Z=>V1=>Z01=>U001=>1001
Z=>V1=>Z01=>V101=>0101
2.5已知文法G[S]:
S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。
A∷=aA︱ε描述的语言:
{an|n>=0}
B∷=bBc︱bc描述的语言:
{bncn|n>=1}
L(G[S])={anbmcm|n>=0,m>=1}
2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i,写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。
开始符号:
E
Vt={+,-,*,/,(,),i}
Vn={E,F,T}
2.7对2.6题的文法,写出句型T+T*F+i的短语、简单短语以及句柄。
短语:
T+T*F+iT+T*F
ii
TT*F
简单短语:
iT*F
T
句柄:
T
2.8设有文法G[S]:
S∷=S*S|S+S|(S)|a,该文法是二义性文法吗?
根据所给文法推导出句子a+a*a,画出了两棵不同的语法树,所以该文法是二义性文法。
2.9写一文法,使其语言是奇正整数集合。
A:
:
=1|3|5|7|9|NA
N:
:
=0|1|2|3|4|5|6|7|8|9
2.10给出语言{anbm|n,m≥1}的文法。
G[S]:
S:
:
=AB
A:
:
=aA|a
B:
:
=bB|b
第三章
3.1有正则文法G[Z]:
Z:
:
=Ua|Vb,U:
:
=Zb|b,V:
:
=Za|a,画出该文法的状态图,并检查句子abba是否合法。
解:
该文法的状态图如下:
句子abba合法。
3.2状态图如图3.35所示,S为开始状态,Z为终止状态。
写出相应的正则文法以及V,Vn和Vt。
解:
左线性文法G[Z]:
右线性文法G’[S]:
Z:
:
=Ab|bS:
:
=aA|b
A:
:
=Aa|aA:
:
=aA|b
V={Z,A,a,b}V={S,A,a,b}
Vn={Z,A}Vn={S,A}
Vt={a,b}Vt={a,b}
3.3构造下列正则表达式相应的NFA:
1(1|0)*|0
1(1010*|1(010)*1)*0
解:
正则表达式:
1(1|0)*|0
1、
2、
3、
4、
正则表达式:
1(1010*|1(010)*1)*0
3.4
将图3.36的NFAM确定化
解:
a
b
q0={0}
{0,1}
{1}
q1={0,1}
{0,1}
{1}
q2={1}
{0}
Φ
DFA:
3.5将图3.37的DFA化简。
解:
划分
a
b
{0,1}
{1}
{2,4}
{2,3,4,5}
{1,0,3,5}
{3,5,2,4}
划分
a
b
{0,1}
{1}
{2,4}
{2,4}
{0,1}
{3,5}
{3,5}
{3,5}
{2,4}
q0={0,1}q1={2,4}q2={3,5}
化简后的DFA:
第四章
4.1对下面文法,设计递归下降分析程序。
S→aAS|(A),A→Ab|c
解:
首先将左递归去掉,将规则A→Ab|c改成A→c{b}
非终结符号S的分析程序如下:
非终结符号A的分析程序如下:
过程A
INPUTSYM=’c’
INPUTSYM=下一个符号
Y
INPUTSYM=’b’
N
错误
INPUTSYM=下一个符号
Y
出口
N
4.2设有文法G[Z]:
Z∷=(A),A∷=a|Bb,B∷=Aab
若采用递归下降分析方法,对此文法来说,在分析过程中,能否避免回溯?
为什么?
解:
若采用递归下降分析方法,对此文法来说,在分析过程中不能避免回朔。
因为规则A∷=a|Bb和规则B∷=Aab构成了间接左递归,不满足实现没有回溯的递归下降分析方法的条件
(1)(书P67),且规则A:
:
=a|Bb,FIRST(a)={a},FIRST(Bb)={a},即此规则候选式的首符号集有相交,不满足实现没有回溯的递归下降分析方法的条件
(2)(书P67),在分析过程中,将造成回溯。
改写文法可避免回溯:
将规则B∷=Aab代入规则A∷=a|Bb得:
A∷=a|Aabb,再转换成:
A∷=a{abb},可避免回溯。
4.3若有文法如下,设计递归下降分析程序。
<语句>→<语句><赋值语句>|ε
<赋值语句>→ID=<表达式>
<表达式>→<项>|<表达式>+<项>|<表达式>-<项>
<项>→<因子>|<项>*<因子>|<项>/<因子>
<因子>→ID|NUM|(<表达式>)
解:
首先,去掉左递归
<语句>→<语句><赋值语句>|ε改为:
<语句>→{<赋值语句>}
<表达式>→<项>|<表达式>+<项>|<表达式>-<项>改为:
<表达式>→<项>{(+|-)<项>}
<项>→<因子>|<项>*<因子>|<项>/<因子>改为:
<项>→<因子>{(*|/)<因子>}
则文法变为:
<语句>→{<赋值语句>}
<赋值语句>→ID=<表达式>
<表达式>→<项>{(+|-)<项>}
<项>→<因子>{(*|/)<因子>}
<因子>→ID|NUM|(<表达式>)
非终结符号<语句>的分析程序如下:
非终结符号<赋值语句>的分析程序如下:
非终结符号<表达式>的分析程序如下:
非终结符号<项>的分析程序如下:
<因子>→ID|NUM|(<表达式>)
非终结符号<因子>的分析程序如下:
因子
INPUTSYM=’ID’
Y
出口
INPUTSYM=’NUM’
INPUTSYM=下一个符号
N
Y
N
INPUTSYM=’(’
INPUTSYM=下一个符号
Y
表达式
INPUTSYM=’)’
错误
N
Y
错误
N
4.4有文法G[A]:
A:
:
=aABe|ε,B:
:
=Bb|b
(1)求每个非终结符号的FOLLOW集。
(2)该文法是LL
(1)文法吗?
(3)构造LL
(1)分析表。
解:
(1)FOLLOW(A)=First(B)∪{#}={b,#}
FOLLOW(B)={e,b}
(2)该文法中的规则B:
:
=Bb|b为左递归,因此该文法不是LL
(1)文法
(3)先消除文法的左递归(转成右递归),文法变为:
A:
:
=aABe|ε,B:
:
=bB’,B’=bB’|ε,该文法的LL
(1)分析表为:
更常用且简单的LL
(1)分析表:
a
e
b
#
A
A→aABe
A→ε
A→ε
B
B→bB’
B’
B’→ε
B’→bB’
4.5若有文法A→(A)A|ε
(1)为非终结符A构造FIRST集合和FOLLOW集合。
(2)说明该文法是LL
(1)的文法。
解:
(1)FIRST(A)={(,ε}
FOLLOW(A)={),#}
(2)
该文法不含左递归;
FIRST((A)A)={(},FIRST(ε)={ε},FIRST((A)A)∩FIRST(ε)=Φ,
且FOLLOW(A)={),#},FIRST((A)A)∩FOLLOW(A)=Φ,
因此,该文法满足LL
(1)文法的条件,是LL
(1)文法。
4.6利用分析表4-1,识别以下算术表达式,请写出分析过程。
(1)i+i*i+i
(2)i*(i+i+i)
解:
(1)i+i*i+i
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#E
i+i*i+i#
POP,PUSH(E’T)
E→TE’
2
#E’T
i+i*i+i#
POP,PUSH(T’F)
T→FT’
3
#E’T’F
i+i*i+i#
POP,PUSH(i)
F→i
4
#E’T’i
i+i*i+i#
POP,NEXTSYM
5
#E’T’
+i*i+i#
POP
T’→ε
6
#E’
+i*i+i#
POP,PUSH(E’T+)
E’→+TE’
7
#E’T+
+i*i+i#
POP,NEXTSYM
8
#E’T
i*i+i#
POP,PUSH(T’F)
T→FT’
9
#E’T’F
i*i+i#
POP,PUSH(i)
F→i
10
#E’T’i
i*i+i#
POP,NEXTSYM
11
#E’T’
*i+i#
POP,PUSH(T’F*)
T’→*FT’
12
#E’T’F*
*i+i#
POP,NEXTSYM
13
#E’T’F
i+i#
POP,PUSH(i)
F→i
14
#E’T’i
i+i#
POP,NEXTSYM
15
#E’T’
+i#
POP
T’→ε
16
#E’
+i#
POP,PUSH(E’T+)
E’→+TE’
17
#E’T+
+i#
POP,NEXTSYM
18
#E’T
i#
POP,PUSH(T’F)
T→FT’
19
#E’T’F
i#
POP,PUSH(i)
F→i
20
#E’T’i
i#
POP,NEXTSYM
21
#E’T’
#
POP
T’→ε
22
#E’
#
POP
E’→ε
23
#
#
ACCEPT
(2)i*(i+i+i)
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#E
i*(i+i+i)#
POP,PUSH(E’T)
E→TE’
2
#E’T
i*(i+i+i)#
POP,PUSH(T’F)
T→FT’
3
#E’T’F
i*(i+i+i)#
POP,PUSH(i)
F→i
4
#E’T’i
i*(i+i+i)#
POP,NEXTSYM
5
#E’T’
*(i+i+i)#
POP,PUSH(T’F*)
T’→*FT’
6
#E’T’F*
*(i+i+i)#
POP,NEXTSYM
7
#E’T’F
(i+i+i)#
POP,PUSH()E()
F→(E)
8
#E’T’)E(
(i+i+i)#
POP,NEXTSYM
9
#E’T’)E
i+i+i)#
POP,PUSH(E’T)
E→TE’
10
#E’T’)E’T
i+i+i)#
POP,PUSH(T’F)
T→FT’
11
#E’T’)E’T’F
i+i+i)#
POP,PUSH(i)
F→i
12
#E’T’)E’T’i
i+i+i)#
POP,NEXTSYM
13
#E’T’)E’T’
+i+i)#
POP
T’→ε
14
#E’T’)E’
+i+i)#
POP,PUSH(E’T+)
E’→+TE’
15
#E’T’)E’T+
+i+i)#
POP,NEXTSYM
16
#E’T’)E’T
i+i)#
POP,PUSH(T’F)
T→FT’
17
#E’T’)E’T’F
i+i)#
POP,PUSH(i)
F→i
18
#E’T’)E’T’i
i+i)#
POP,NEXTSYM
19
#E’T’)E’T’
+i)#
POP
T’→ε
20
#E’T’)E’
+i)#
POP,PUSH(E’T+)
E’→+TE’
21
#E’T’)E’T+
+i)#
POP,NEXTSYM
22
#E’T’)E’T
i)#
POP,PUSH(T’F)
T→FT’
23
#E’T’)E’T’F
i)#
POP,PUSH(i)
F→i
24
#E’T’)E’T’i
i)#
POP,NEXTSYM
25
#E’T’)E’T’
)#
POP
T’→ε
26
#E’T’)E’
)#
POP
E’→ε
27
#E’T’)
)#
POP,NEXTSYM
28
#E’T’
#
POP
T’→ε
29
#E’
#
POP
E’→ε
30
#
#
ACCEPT
4.7考虑下面简化了的C声明文法:
<声明语句>→<类型><变量表>;
<类型>→int|float|char
<变量表>→ID,<变量表>|ID
(1)在该文法中提取左因子。
(2)为所得的文法的非终结符构造FIRST集合和FOLLOW集合。
(3)说明所得的文法是LL
(1)文法。
(4)为所得的文法构造LL
(1)分析表。
(5)假设有输入串为“charx,y,z;”,写出相对应的LL
(1)分析过程。
解:
(1)规则<变量表>→ID,<变量表>|ID提取公因子如下:
<变量表>→ID(,<变量表>|ε)
增加新的非终结符<变量表1>,规则变为:
<变量表>→ID<变量表1>
<变量表1>→,<变量表>|ε
C声明文法改变为:
<声明语句>→<类型><变量表>;
<类型>→int|float|char
<变量表>→ID<变量表1>
<变量表1>→,<变量表>|ε
(2)FIRST(<声明语句>)=FIRST(<类型>)={int,float,char}
FIRST(<变量表>)={ID}
FIRST(<变量表1>)={,,ε}
FOLLOW(<声明语句>)={#}
FOLLOW(<类型>)=FIRST(<变量表>)={ID}
FOLLOW(<变量表>)=FOLLOW(<变量表1>)={;}
(3)所得文法无左递归,且
FIRST(int)∩FIRST(float)∩FIRST(char)=Φ
FIRST(,<变量表>)∩FIRST(ε)=Φ
FIRST(,<变量表>)∩FOLLOW(<变量表1>)=Φ
因此,所得文法为LL
(1)文法。
(4)所得的文法构造LL
(1)分析表如下所示:
更常用且简单的LL
(1)分析表:
;
int
float
char
ID
,
#
<声明语句>
<声明语句>→<类型><变量表>;
<声明语句>→<类型><变量表>;
<声明语句>→<类型><变量表>;
<类型>
<类型>→int
<类型>→float
<类型>→char
<变量表>
<变量表>→ID<变量表1>
<变量表1>
<变量表1>→ε
<变量表1>→,<变量表>
(5)输入串“charx,y,z;”相对应的LL
(1)分析过程如下:
步骤
分析栈
余留输入串
分析表元素
所用产生式
1
#<声明语句>
charx,y,z;#
POP,
PUSH(;<变量表><类型>)
<声明语句>→<类型><变量表>;
2
#;<变量表><类型>
charx,y,z;#
POP,
PUSH(char)
<类型>→char
3
#;<变量表>char
charx,y,z;#
POP,
NEXTSYM
4
#;<变量表>
x,y,z;#
POP,
PUSH(<变量表1>ID)
<变量表>→ID<变量表1>
5
#;<变量表1>x
x,y,z;#
POP,
NEXTSYM
6
#;<变量表1>
,y,z;#
POP,
PUSH(<变量表>,)
<变量表1>→,<变量表>
7
#;<变量表>,
,y,z;#
POP,
NEXTSYM
8
#;<变量表>
y,z;#
POP,
PUSH(<变量表1>ID)
<变量表>→ID<变量表1>
9
#;<变量表1>y
y,z;#
POP,
NEXTSYM
10
#;<变量表1>
,z;#
POP,
PUSH(<变量表>,)
<变量表1>→,<变量表>
11
#;<变量表>,
,z;#
POP,
NEXTSYM
12
#;<变量表>
z;#
POP,
PUSH(<变量表1>ID)
<变量表>→ID<变量表1>
13
#;<变量表1>z
z;#
POP,
NEXTSYM
14
#;<变量表1>
;#
POP
<变量表1>→ε
15
#;
;#
POP,
NEXTSYM
16
#
#
ACCEPT
一、(20分)对于文法G(S):
S→(A)|a,A→A+S|S
(1)给出句型(a+(A))的最左推导。
(2)画出句型(a+(A))的语法树。
(3)写出上述句型的所有短语、简单短语和句柄。
二、(10分)给出语言{anbmcn|n,m≥0}的文法。
三、(10分)有正则文法如下。
画出该文法的状态图,并检查句子aaab是否合法。
G[Z]:
Z→Ab|b,A→Aa|a
四、(10分)构造正则表达式(a|b)*aa相应的NFA。
五、(10分)设M=({X,Y},{a,b},f,X,{Y})为一非确定的有限自动机,其中f定义如下:
f(X,a)={X,Y}f(X,b)={Y}f(Y,a)=Φf(Y,b)={X,Y}
请构造相应的确定有限自动机。
六、(10分)计算下列文法中每个非终结符号的FIRST集合和FOLLOW集合。
G[S]:
S→(A),A→a|Bb,B→bAa
七、(20分)有文法如下。
试问该文法是LL
(1)文法吗?
如果是,请构造预测分析表;如果不是,请先将该文法改造成LL
(1)文法,再构造LL
(1)分析表。
G[S]:
S→S+F|S-F|F,F→(S)|i
复习大纲
第1章编译概述
☐编译方式与解释方式
☐编译程序的组成
☐编译程序的结构(“遍”、“端”)
第2章文法和语言
☐文法形式定义
☐推导(规范推导)
☐句型、句子
☐语言
☐短语、简单短语和句柄
☐语法树
第3章词法分析
☐词法分析的任务
☐正则文法及状态图
☐正则表达式
☐有穷自动机(NFA、DFA)
NFA、DFA状态图
构造正则表达式的相应NFA
NFA确定化
DFA化简
第4章语法分析-自顶向下分析第5章语法分析-自底向上分析
第6章语法制导翻译技术
第7章符号表管理技术
☐符号表的内容和组织
☐符号表结构
☐错误处理
第9章语义分析和代码生成
☐语义分析的任务
☐中间代码:
(1)波兰后缀表示(逆波兰式)(掌握)
(2)N-元表示
(2-1)三元式(掌握)(2-2)四元式(掌握)(2-3)抽象机代码
(3)栈式抽象机及其汇编指令
第10章代码优化
☐局部优化
基本块的划分方法
基本块的DAG表示及优化实现
☐循环内优化
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 作业题