编译原理课程研讨题.docx
- 文档编号:16993760
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:12
- 大小:25.35KB
编译原理课程研讨题.docx
《编译原理课程研讨题.docx》由会员分享,可在线阅读,更多相关《编译原理课程研讨题.docx(12页珍藏版)》请在冰点文库上搜索。
编译原理课程研讨题
第一次研讨、第一批(第3周)
1.讨论:
(1)编译方法与解释方法的主要区别
(2)编译程序组合中分端(前端/后端)和分遍(单遍/多遍)的作用
(3)编译程序生成方法中自编译与自展的含义
2.编写PL/O程序,功能:
输入正整数n,求sum=1!
+2!
+...+n!
3.扩充PL/O语言文法的定义,增加实数类型和数组类型例:
Vari:
integer;
r:
real;
A:
array[1..10]ofreal;
A[i]:
=r;
4.设有下列文法G1[S]和G2[S]:
1)指出文法的类型2)证明两者等价
G1[S]:
S—aAb|
bBa
A—aA|
a
B—Bb|
b
G2[S]:
S—aA|
bB
A—aA|
aC
B—bB|
bD
C—b
D—a
5.构造一个文法,使其语言是奇数集,且每个奇数不以0开头
6.文法G[S]的一个句子abbba的语法树如下图:
a
1)G[S]可能包含哪些产生式?
2)给出句子abbba的规范推导
3)求出句子abbba的句柄。
7.设有上下文无关文法G[S]:
S—aAbA—aBA—aB—bAB—b试构造与G[S]等价的正规文法。
8实验一识别标识符(A)
第一次研讨、第二批(第4周)
1编写PL/O程序,输入正整数n、XI、X2、…、xn,计算:
S=刀Xi!
i=1〜n2.构造下列语言的文法,并分析比较
(1)L1(G)={anbn|n>1}
(2)L2(G)={(ab)n|n>1}
(3)L3(G)={anbm|n,m>0}
(4)L4(G)={anbm|n,m>1}
3.定义一个文法,产生表达式E:
1)含有双目运算符+,*2)+的优先级高于*
3)+右结合,*左结合
4)运算对象为标识符i
5)可用括号改变算符的优先级
4.扩充PL/0语言文法的定义,增加for语句的功能for语句的示例如下:
fori:
=1to100dos:
=s+i;
5.定义一个文法,产生下列语言:
该语言由a、b符号串组成,串中a和b的个数相同
6.证明下列文法为二义文法(能否转换为等价的非二义文法?
)
⑴G1[S]:
S—AA—AAA—aAbA—ab
⑵G2[S]:
S—aSbS—SbS—b
7•试写出Vt={0,1},分别满足下述要求的正则表达式:
⑴所有以1开始和0结束的符号串。
⑵恰含有3个1的所有符号所组成的集合。
⑶集合{01,1}。
⑷所有以111结束的符号串。
8.实验一识别标识符(B)
1•构造一个DFA,接受刀={ab}上由正规式as*(a|bajb定义的字符串并给出相应的正规文法。
2.写出<简单查询语句>的文法.
例如:
有2个关系R(a,b,c),S(c,d,e)以下是简单查询语句的样例:
语句1:
SELECTa,bFROMRWHEREa=15ORb<18;
语句2:
SELECTR.a,S.cFROMR,SWHERER.c=S.cANDR.b<18;
3•下面文法G[S]产生ab字符数相等的非空ab字符串
S—aB|bA
B—bS|aBB|b
A—aS|bAA|a
1)证明该文法是二义的。
2)修改上述文法,使之非二义。
4.试用有限自动机的等价性证明以下2个正规式((a|b)*|aa)*b和(a|b)*b是等价的,并给出相应的正规文法。
5.写出工={a,b}上L={w|w中的a的个数为偶数}的正规式,构造接受L的DFA
6.构造一个最简的DFAM,接受工={ab}上同时满足下列条件的符号串:
1)以a开头,以b结尾;
2)符号串中包含“aba。
”
7.有一台自动售货机,接收1分和2分硬币,出售3分一块的硬糖。
顾客每次向机器中投放一个硬币,当投放硬币额>=3分时,机器会给顾客一块硬糖(只给糖不找钱)。
1)写出售后机售糖的正规表达式;
2)构造识别上述正规表达式的最简DFA。
8.实验二词法分析(A)
1.给出<嵌套查询语句>的文法
例如:
有2个关系R(a,b,c),S(c,d,e)。
以下是嵌套查询语句的样例:
语句:
SELECTa,b
FROMR
WHERER.cin(SELECTS.cFROMSWHEREd=15);
2.构造一个最简DFAM,接受
={d,.,e},上的正规式dd.dd(edd)表示的无符号数的集合。
其中d为0~9的数字。
3•正规文法(又称为右线性文法):
文法中每一条产生式a—的形式都为:
AfaB或A—a。
左线性文法:
每一条产生式a—的形式都为:
A—Ba或A—a。
设计一个算法,把给定的左线性文法转换为等价的右线性文法。
4.构造一个DFAM,接受工={a,b上满足下列条件的符号串:
1)以a开头,以b结尾;
2)不包含“aba。
”
5.对一个文法若消除了左递归,提取了左公共因子后是否一定为LL
(1))文法?
试
举例说明。
6•已知文法G[E]的定义如下:
E—E+T|T
T—T*F|F
F—(E)|i
试构造一组递归下降分析子程序,使之识别G[E]所产生的语言。
7.语言可接受的合法文件名为:
device:
name.extension其中device、name、
extension是长度至少为1的字符串,而且第一部分(device:
)和第三部分
(.extension)可缺省。
试画出识别这种文件名的最简DFA。
8.实验二词法分析(B)
1.设有文法G[S]:
S—SaF|FF—FbP|PP—c|d
(1)构造G[S]的算符优先关系表
(2)分别给出cadbdac#和dbcabc#的分析过程
2.已知文法G[P]的定义如下:
P—beginDSend
D—D;d|d
S—S;s|s
试构造一组递归下降分析程序,使之识别G[P]所产生的语言
3.设有文法G[S]:
S—aBc|bABA—aAb|bB—b|
⑴证明G[S]是一个LL
(1)文法。
⑵构造G[S]的预测分析表。
(3)给出baabbb的分析过程。
4.设有文法G[S']:
(0)S'—(1S)S—SaA
(2)S—a(3)A—AbS(4)A—b
(1)构造G[S]的LR(0)项目规范族C={IO,I1,…In}
⑵构造SLR
(1)分析表,判断G[S]的文法类型}
(3)写出句子aabba的分析过程}
5.设采用自底向上的移进-归约语法分析,属性文法G[A]如下:
A—aB
“O”}
A—c
“1”}
B—Ab
“2”}
(1)输入为
aacbb时,
打印的符号串是什么?
⑵写出aacbb的语法制导分析过程
6.设有文法G[E]:
E—E+T|EVT|T
T—T*F|TAF|FF—num|bool|(E)
设计G[E]的语义子程序,对表达式进行类型检查并翻译为逆波兰式
7.设有文法G[number]:
number—num•num
num—digitnum|digitdigit—O|1|2|3|4|5|6|7|8|9
设计G[number]的语义子程序,计算实数number的值。
8.实验三语法分析(A)
1.设有文法G[S]:
S—AA—AmDn|BB—a|mSnS|DbS
(1)构造G[S]的算符优先关系表。
(2)给出aman#和maban#的分析过程。
(3)由
(2)说明算符优先分析算法的局限性。
2.设有文法G[E]:
E—ETE|(E)|i
T—+|*
⑴证明G[E]是一个非LL⑴文法。
⑵把G[E]等价改写为LL⑴文法G1[E],并构造其预测分析表。
(3)给出句子(i+i)*(i+i)的分析过程。
3.设有文法G[S]:
S—Ab|Ba
A—aA|a
B—a
将其改造成LL
(1)文法,并编写递归下降分析程序,使之识别G[S]所产生的
4.设有文法G[S']:
(0)S'(—1)S—aS
(2)S—bA(3)A—dA(4)A—d
(1)构造G[S]的LR(O)项目规范族C={lo,li,…In},
(2)说明G[S]属于哪一种LR文法,构造相应的LR分析表
(3)写出句子aabbd的分析过程。
5.写出表达式(a+b*c)/(a+b)-d的四元式,逆波兰式及三元式序列
6.条件语句的语法简写为:
S—iSeS|iS|S;S|a
其中:
i代表if,e代表else,a代表赋值语句。
如果规定:
(1)else与其左边最近的if结合;
(2);服从左结合。
请给出文法中i、e和;的优先关系,然后构造出无二义的LR分析表,并对输
入串iiaea写出分析过程。
7.设采用自底向上的移进
-归约语法分析,属性文法G[E]如下:
E—E+T{print
“O”}
E—T{print
“1”}
T—T*F{print
“2”}
T—F{print
“3”}
F—(E){print
“4”}
F—i{print
“5”}
写出i*(i+i*i)的语法制导分析过程,打印的符号串是什么?
8.实验三语法分析(B)
1.以下是简单表达式(只含有加、减运算)计算的一个属性文法G(E)
E—TR
{R.in:
=
T.val;E.val:
=R.val}
R—+TRi
{R1.in:
=R.in+T.val;R.val:
=R1.val}
R—-TR1
{R1.in:
=R.in-T.val;R.val:
=R1.val}
R—
{R.val:
=R.in}
T—num
{T.val:
=lexval(num)}
其中:
lexval(num)表示从词法分析程序得到的常数的值。
试给出表达式8-3+6的语法树和相应的带标注语法分析树。
2.教材P224第4题。
3.写出下列语句的三地址中间代码(四元式序列):
while(A begin if(A>=1)thenC: =C+1elsewhile(A<=D)doA: =A+2; end 4.教材P252第2题 5.对下列基本块B应用DAG进行优化,设只有U,V在基本块后面还要继续引用。 B: T0: =100T1: =k+T0T2: =T0*2U: =T1+T2T3: =k+T0V: =T3*U6.1)把下列中间代码序列划分为基本块并作出其流图 1) read(C) 2) A=0 3) B=1 4) L4: A=A+B 5) ifB>CgotoL2 6) B=B+1 7) GotoL4 (8)L2: write(B) 2)找出题1)流图中的回边与循环 7•把下列中间代码序列划分为基本块并作出其流图 1) ⑴read(x) ⑵read(y) (3)A: =10 ⑷ifx (5)A: =20 ⑹x: =x+1 (7)y: =y-1 (8)ify<20goto(4) (9)B: =A (10)write(B) 2)找出题1)流图中的回边与循环 3)讨论题2)循环中的不变运算(A: =20)外提的可行性 8•实验四语义分析(A)或实验五中间代码生成(A) 第四次研讨、第二批(第10周) 1.教材P291第6题。 2.教材P224第5题。 123456 1 011000 2 001100 3 001000 4 000011 5 010001 6 000100 3.设有向图G(E,V)的邻接矩阵如右图所示: 找出G(E,V)中的回边与循环 4.给出下列源语句的四元式序列: i: =100; s: =0; while(i>0ors<1000)dobegin if(i>s)thens: =s+i;i: =i-1; end; 5.设有基本块 D: =A-C E: =A*C F: =D*E S: =2 T: =A-C Q: =A*C G: =2*S J: =T*Q K: =G*5 L: =K+J M: =L 假设基本块出口时只有M还被引用,写出DAG优化后的四元序列6.写出对下列四元式进行优化后的结果。 for(k=1;k<=100;k++){m=i+10*k;n=j+10*k;} (1)(=,1,-,k) (2)(j<,100,k,9) (3)(*,10,k,t1) (4)(+,i,t1,m) (5)(*,10,k,t2) (6)(+,j,t2,n) (7)(+,k,1,k) (8)(j,-,-,2) 7.设计一个算法,对逆波兰算术表达式解释执行. 例1: 输入345+*输出27 例2: 输入345*+输出23 8•实验四语义分析(B)或实验五中间代码生成(B)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 课程 研讨