华南师范大学 编译原理期末复习整理 pdf例题.docx
- 文档编号:927227
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:28
- 大小:704.93KB
华南师范大学 编译原理期末复习整理 pdf例题.docx
《华南师范大学 编译原理期末复习整理 pdf例题.docx》由会员分享,可在线阅读,更多相关《华南师范大学 编译原理期末复习整理 pdf例题.docx(28页珍藏版)》请在冰点文库上搜索。
华南师范大学编译原理期末复习整理pdf例题
正则表达式:
例2.1在仅由字母表中的3个字符组成的简单字母表∑={a,b,c}中,考虑在这个字母表上的仅包括一个b的所有串的集合。
(a|c)*b(a|c)*
例2.2在与上面相同的字母表中,如果集合是包括了最多一个b的所有串。
(a|c)*b?
(a|c)*
DFA:
例2.6串中仅有一个b的集合的正则表达式对应的DFA为?
例2.8科学表示法的数字常量的正则表达式为:
nat=[0-9]+
signedNat=(+|-)?
nat
number=signedNat(“.”nat)?
(EsignedNat)?
如何画对应的DFA?
解:
先设digit=[0-9],sig=(+|-),得:
例2.9非嵌套注释的DFA描述。
Pascal注释{(~})*}对应的DFA为:
C注释/*...(*/不同时出现)...*/的DFA为:
NFA:
例2.12根据Thompson方法将正则表达式ab|a转换为NFA。
例2.13利用Thompson方法画出正则表达式letter(letter|digit)*对应的NFA。
例2.14与正则表达式a*相对应的NFA为:
NFA转DFA:
例2.15将下面的NFA转换为DFA:
解:
例2.16将下面的NFA转换为DFA:
解:
例2.17正则表达式letter(letter|digit)*对应的NFA转换成DFA:
解:
DFA最小化:
例2.18将与正则表达式letter(letter|digit)*相对应的DFA最小化:
(08级的大三第二学期考这道)
解:
状态转换表为
letter
digit
{1}
{2,3,4,5,7,10}
{2,3,4,5,7,10}
{4,5,6,7,9,10}
{4,5,7,8,9,10}
{4,5,6,7,9,10}
{4,5,6,7,9,10}
{4,5,7,8,9,10}
{4,5,7,8,9,10}
{4,5,6,7,9,10}
{4,5,7,8,9,10}
最小化DFA为:
例2.19将下面与正则表达式(a|ε)b*对应的DFA进行最小化。
解:
状态转换表为
a
b
{1}
{2}
{3}
{2}
{3}
{3}
{3}
最小化DFA为:
词法分析代码:
state:
=1;{start}
whilestate=1or2do
casestateof
1:
caseinputcharacterof
letter:
advancetheinput;
state:
=2;
elsestate:
=...{errororother};
endcase;
2:
caseinputcharacterof
letter,digit:
advancetheinput;
state:
=2;{actuallyunnecessary}
elsestate:
=3;
endcase;
endcase;
endwhile;
ifstate=3thenacceptelseerror;
state:
=1;{start}
whilestate=1,2,3or4do
casestateof
1:
caseinputcharacterof
“/”:
advancetheinput;
state:
=2;
elsestate:
=...;{errororother}
endcase;
2:
caseinputcharacterof
“*”:
advancetheinput;
state:
=3;
elsestate:
=...;{errororother}
endcase;
3:
caseinputcharacterof
“*”:
advancetheinput;
state:
=4;
elseadvancetheinput;{andstayinstate3}
endcase;
4:
caseinputcharacterof
“/”:
advancetheinput;
state:
=5;
“*”:
advancetheinput;{andstayinstate4}
elseadvancetheinput;
state:
=3;
endcase;
endcase;
endwhile;
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’);
A();
}elseif(token==‘d’){
match(‘d’);
}elseError();
}//A
voidB(){
if(token==‘e’){
match(‘e’);
match(‘f’);
B();
}elseif(token==‘f’){
match(‘f’);
}elseError();
}//B
intmain(){
getToken();
S();
return0;
}//main
问题2:
exp→expaddopterm|term
addop→+|-
term→termmulopfactor|factor
mulop→*|/
factor→(exp)|number
请写出递归子程序分析算法。
解:
先消除左递归,得到
exp→term{addopterm}
addop→+|-
term→factor{mulopfactor}
mulop→*|/
factor→(exp)|number
程序如下:
voidmatch(expectedToken){
if(token==expectedToken)
getToken();
else
Error();
}
voidexp(){
term();
while(token==‘+’||token==‘-’){
match(token);
term();
}
}
voidterm(){
factor();
while(token==‘*’||token==‘/’){
match(token);
factor();
}
}
voidfactor(){
if(token==‘(’){
match(‘(’);
exp();
match(‘)’);
}elseif(token==number){
match(number);
}elseError();
}
intmain(){
getToken();
exp();
return0;
}
写出递归构建语法树的程序:
voidmatch(expectedToken){
if(token==expectedToken)getToken();
elseError();
}
BtreeNode*exp(){
BtreeNode*Node,*tempNode;
Node=term();
while(token==‘+’||token==‘-’){
tempNode=newBtreeNode;
tempNode->data=token;
match(token);
tempNode->lchild=Node;
tempNode->rchild=term();
Node=tempNode;
}
returnNode;
}
BtreeNode*term(){
BtreeNode*Node,*tempNode;
Node=factor();
while(token==‘*’||token==‘/’){
tempNode=newBtreeNode;
tempNode->data=token;
match(token);
tempNode->lchild=Node;
tempNode->rchild=factor();
Node=tempNode;
}
returnNode;
}
BtreeNode*factor(){
BtreeNode*Node;
if(token==‘(’){
match(‘(’);
Node=exp();
match(‘)’);
}elseif(token==number){
Node=newBtreeNode;
Node->data=token;
match(number);
Node->lchild=Node->rchild=NULL;
}elseError();
returnNode;
}
intmain(){
BtreeNode*root;
getToken();
root=exp();
return0;
}
例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考虑简单整型算术表达式的文法:
exp→expaddopterm|term
addop→+|-
term→termmulopfactor|factor
mulop→*|/
factor→(exp)|number
试求:
First(exp)=?
First(term)=?
First(factor)=?
解:
先消除左递归:
exp→term{addopterm}
addop→+|-
term→factor{mulopfactor}
mulop→*|/
factor→(exp)|number
由此得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时的分析栈。
解:
分析表为
a
b
c
d
e
S
S→Ab
S→Bc
S→Ab
S→Bc
A
A→aA
A→dB
B
B→c
B→e
分析栈为:
步骤
符号栈
输入串
动作
1
S
adcb
S→Ab
2
bA
adcb
A→aA
3
bAa
adcb
匹配
4
bA
dcb
A→dB
5
bBd
dcb
匹配
6
bB
cb
B→c
7
bc
cb
匹配
8
b
b
匹配
9
成功
问题2:
G[S]={
S→AbB|Bc
A→aA|ε
B→d|e
}
画出LL
(1)分析表和当匹配串abd时的分析栈。
解:
分析表为:
a
b
c
d
e
S
S→AbB
S→AbB
S→Bc
S→Bc
A
A→aA
A→ε
B
B→d
B→e
分析栈为:
步骤
符号栈
输入串
动作
1
S
abd
S→AbB
2
BbA
abd
A→aA
3
BbAa
abd
匹配
4
BbA
bd
A→ε
5
Bb
bd
匹配
6
B
d
B→d
7
d
d
匹配
8
成功
LR(0)分析法:
问题1:
G[A]:
A→(A)|a
画出DFA,并写出串((a))的分析过程。
解:
先扩充文法,得到:
A'→.A
A→.(A)
A→.a
DFA为:
分析表为:
状态
动作
规则
输入
Goto
(
a
)
A
0
移进
3
2
1
1
规约
A'→A
2
规约
A→a
3
移进
3
2
4
4
移进
5
5
规约
A→(A)
分析串((a))时的分析栈为:
步骤
分析栈
输入
动作
1
$0
((a))$
移进
2
$0(3
(a))$
移进
3
$0(3(3
a))$
移进
4
$0(3(3a2
))$
用A→a规约
5
$0(3(3A4
))$
移进
6
$0(3(3A4)5
)$
用A→(A)规约
7
$0(3A4
)$
移
8
$0(3A4)5
$
用A→(A)规约
9
$0A1
$
接受
SLR
(1)分析:
问题1:
文法:
E→E+n|n
画出该文法的SLR
(1)的DFA图、分析表和分析串n+n+n时的分析栈。
解:
先扩充文法,得到
E'→E
E→E+n
E→n
画出其DFA为:
其分析表如下:
状态
输入
Goto
n
+
$
E
0
s2
1
1
s3
接受
2
r(E→n)
r(E→n)
3
s4
4
r(E→E+n)
r(E→E+n)
分析串n+n+n时的分析栈为:
步骤
分析栈
输入
动作
1
$0
n+n+n$
移进2
2
$0n2
+n+n$
用E→n规约
3
$0E1
+n+n$
移进3
4
$0E1+3
n+n$
移进4
5
$0E1+3n$
+n$
用E→E+n规约
6
$0E1
+n$
移进3
7
$0E1+3
n$
移进4
8
$0E1+3n4
$
用E→E+n规约
9
$0E1
$
接受
LR
(1)分析:
问题1:
文法:
A→(A)|a
画出该文法的LR
(1)的DFA图和分析表。
解:
先扩充文法,得到:
A'→A
A→(A)
A→a
其DFA为:
分析表为:
状态
输入
Goto
(
a
)
$
A
0
s2
s3
1
1
接受
2
s5
s6
4
3
r(A→a)
4
s7
5
s5
s6
8
6
r(A→a)
7
r(A→(A))
8
s9
9
r(A→(a))
问题2:
文法:
S→id|V:
=E
V→id
E→V|n
画出该文法的LR
(1)的DFA图和分析表。
解:
首先将文法扩展,得到:
S'→S
S→id
S→V:
=E
V→id
E→V
E→n
DFA图如下:
分析表如下:
状态
输入
Goto
id
:
=
n
$
V
E
S
0
s2
3
1
1
接受
2
r(V→id)
r(S→id)
3
s4
4
s8
s7
6
5
5
r(S→V:
=E)
6
r(E→V)
7
r(E→n)
8
r(V→id)
将上题的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(AD)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;}
将该语句转换为四元组表示。
解:
(1)(J>,m,n,3)
(2)(J,,,6)
(3)(=,1,,k)
(4)(=,0,,S)
(5)(J,,,1)
(6)
例题4(08级的大三第二学期考这道)
if(A&&B&&C>D)
if(X 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&&B&&C>D)x=1; 将该语句转换为四元组表示。 解: (1)(JNZ,A,,3) (2)(J,,,9) (3)(JNZ,B,,5) (4)(J,,,9) (5)(J>,C,D,7) (6)(J,,,9) (7)(=,1,,x) (8)(J,,,1) (9)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华南师范大学 编译原理期末复习整理 pdf例题 编译 原理 期末 复习 整理 pdf 例题