华南师范大学 编译原理期末复习整理 pdf例题Word文档下载推荐.docx
- 文档编号:1132240
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:28
- 大小:704.93KB
华南师范大学 编译原理期末复习整理 pdf例题Word文档下载推荐.docx
《华南师范大学 编译原理期末复习整理 pdf例题Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《华南师范大学 编译原理期末复习整理 pdf例题Word文档下载推荐.docx(28页珍藏版)》请在冰点文库上搜索。
state:
=1;
{start}
whilestate=1or2do
casestateof
1:
caseinputcharacterof
letter:
advancetheinput;
state:
=2;
elsestate:
=...{errororother};
endcase;
2:
letter,digit:
state:
{actuallyunnecessary}
=3;
endcase;
endwhile;
ifstate=3thenacceptelseerror;
whilestate=1,2,3or4do
“/”:
state:
=...;
{errororother}
“*”:
3:
=4;
elseadvancetheinput;
{andstayinstate3}
4:
“/”:
=5;
{andstayinstate4}
ifstate=5thenacceptelseerror;
递归子程序分析法
问题1:
G[S]=
{
S→aA|bB
A→cdA|d
B→efB|f
}
试编写一个能分析该文法所对应任何串(如串acdd)的程序。
voidmatch(expectedToken){
if(token==expectedToken)
getToken();
else
Error();
voidS(){
if(token==‘a’){
match(‘a’);
A();
}elseif(token==‘b’){
match(‘b’);
B();
}elseError();
}//S
voidA(){
if(token==’c’){
match(‘c’);
match(‘d’);
}elseif(token==‘d’){
}//A
voidB(){
if(token==‘e’){
match(‘e’);
match(‘f’);
}elseif(token==‘f’){
}//B
intmain(){
getToken();
S();
return0;
}//main
问题2:
exp→expaddopterm|term
addop→+|-
term→termmulopfactor|factor
mulop→*|/
factor→(exp)|number
请写出递归子程序分析算法。
先消除左递归,得到
exp→term{addopterm}
term→factor{mulopfactor}
程序如下:
else
Error();
voidexp(){
term();
while(token==‘+’||token==‘-’){
match(token);
term();
}
voidterm(){
factor();
while(token==‘*’||token==‘/’){
factor();
voidfactor(){
if(token==‘(’){
match(‘(’);
exp();
match(‘)’);
}elseif(token==number){
match(number);
}elseError();
写出递归构建语法树的程序:
if(token==expectedToken)getToken();
elseError();
BtreeNode*exp(){
BtreeNode*Node,*tempNode;
Node=term();
tempNode=newBtreeNode;
tempNode->
data=token;
lchild=Node;
rchild=term();
Node=tempNode;
returnNode;
BtreeNode*term(){
Node=factor();
rchild=factor();
BtreeNode*factor(){
BtreeNode*Node;
Node=exp();
Node=newBtreeNode;
Node->
lchild=Node->
rchild=NULL;
returnNode;
BtreeNode*root;
root=exp();
例4.3消除下面文法的左递归
A→Ba|Aa|c
B→Bb|Ab|d
先消除A的直接左递归:
A→Ba{a}|c{a}
再将其代入到B的文法表达式中:
B→Bb|Ba{a}b|c{a}b|d
再消除B的直接左递归:
B→(d|c{a}b){(b|a{a}b)}
例4.9考虑简单整型算术表达式的文法:
试求:
First(exp)=?
First(term)=?
First(factor)=?
先消除左递归:
exp→term{addopterm}
由此得First(exp)={(,number}
First(term)={(,number}
First(factor)={(,number}
例4.10考虑if语句的文法:
statement→if-stmt|other
if-stmt→if(exp)statementelse-part
else-part→elsestatement|ε
exp→0|1
Follow(statement)=?
Follow(if-stmt)=?
Follow(else-part)=?
Follow(exp)=?
Follow(statement)={else,$}
Follow(if-stmt)={else,$}
Follow(else-part)={else,$}
Follow(exp)={)}
LL
(1)分析法:
问题1:
G[S]={
S→Ab|Bc
A→aA|dB
B→c|e
画出LL
(1)分析表和当匹配串adcb时的分析栈。
分析表为
c
d
e
S
S→Ab
S→Bc
A
A→aA
A→dB
B
B→c
B→e
分析栈为:
步骤
符号栈
输入串
动作
1
adcb
2
bA
3
bAa
匹配
4
dcb
5
bBd
6
bB
cb
7
bc
8
9
成功
问题2:
S→AbB|Bc
A→aA|ε
B→d|e
画出LL
(1)分析表和当匹配串abd时的分析栈。
分析表为:
S→AbB
A→ε
B→d
分析栈为:
abd
BbA
BbAa
bd
A→ε
Bb
LR(0)分析法:
G[A]:
A→(A)|a
画出DFA,并写出串((a))的分析过程。
先扩充文法,得到:
A'
→.A
A→.(A)
A→.a
DFA为:
状态
规则
输入
Goto
(
)
移进
规约
A'
→A
A→a
A→(A)
分析串((a))时的分析栈为:
分析栈
$0
((a))$
$0(3
(a))$
$0(3(3
a))$
$0(3(3a2
))$
用A→a规约
$0(3(3A4
$0(3(3A4)5
)$
用A→(A)规约
$0(3A4
移
$0(3A4)5
$
$0A1
接受
SLR
(1)分析:
文法:
E→E+n|n
画出该文法的SLR
(1)的DFA图、分析表和分析串n+n+n时的分析栈。
先扩充文法,得到
E'
→E
E→E+n
E→n
画出其DFA为:
其分析表如下:
n
+
E
s2
s3
r(E→n)
s4
r(E→E+n)
分析串n+n+n时的分析栈为:
n+n+n$
移进2
$0n2
+n+n$
用E→n规约
$0E1
移进3
$0E1+3
n+n$
移进4
$0E1+3n$
+n$
用E→E+n规约
n$
$0E1+3n4
LR
(1)分析:
画出该文法的LR
(1)的DFA图和分析表。
A→(A)
A→a
其DFA为:
s5
s6
r(A→a)
s7
r(A→(A))
s9
r(A→(a))
S→id|V:
=E
V→id
E→V|n
首先将文法扩展,得到:
S'
→S
S→id
S→V:
E→V
DFA图如下:
分析表如下:
id
:
=
V
r(V→id)
r(S→id)
s8
r(S→V:
=E)
r(E→V)
将上题的DFA图改写成符合LALR
(1)的DFA:
后缀表示:
写出if(m>
n)k=1;
elsem=0;
的后缀表示。
mn>
10BZk1=20BR
10:
m0=
20:
三元组表示:
写出表达式a*(b+c)对应的三元组。
(1)(+,b,c)
(2)(*,a,
(1))
四元组表示:
例子1
if(m>
n){k=0;
S=1;
}elsem=0;
将该语句转换为四元组表示。
(1)(J>
m,n,3)
(2)(J,,,6)
(3)(=,0,,k)
(4)(=,1,,S)
(5)(J,,,7)
(6)(=,0,,m)
(7)
例题2
if(A<
B&
&
C>
D)x=1;
elsex=0;
(1)(J<
A,B,3)
(2)(J,,,7)
(3)(J>
C,D,5)
(4)(J,,,7)
(5)(=,1,,x)
(6)(J,,,8)
(7)(=,0,,x)
(8)
例题3
while(m>
n){k=1;
S=0;
(3)(=,1,,k)
(4)(=,0,,S)
(5)(J,,,1)
(6)
例题4(08级的大三第二学期考这道)
if(A&
B&
C>
D)
if(X<
Y)F=1;
elseF=0;
elseG=1;
(1)(JNZ,A,,3)
(2)(J,,,13)
(3)(JNZ,B,5)
(4)(J,,,13)
(5)(J>
C,D,7)
(6)(J,,,13)
(7)(J<
X,Y,9)
(8)(J,,,11)
(9)(=,1,,F)
(10)(J,,,14)
(11)(=,0,,F)
(12)(J,,,14)
(13)(=,1,,G)
(14)
例题5
while(A&
(1)(JNZ,A,,3)
(2)(J,,,9)
(3)(JNZ,B,,5)
(4)(J,,,9)
(5)(J>
(6)(J,,,9)
(7)(=,1,,x)
(8)(J,,,1)
(9)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华南师范大学 编译原理期末复习整理 pdf例题 编译 原理 期末 复习 整理 pdf 例题