实验一词法分析Word格式.doc
《实验一词法分析Word格式.doc》由会员分享，可在线阅读，更多相关《实验一词法分析Word格式.doc（10页珍藏版）》请在冰点文库上搜索。
=a|b|c|d|e|f|A|B|C|D|E|F
γ
=g|
h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|G|H|I|G|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
S
→
X’|Y’|Z’
X’
υ|υM’
M’
→ω|ωM’
υ
→β|γ
ω
→α|β|γ
Y’
α|αY’
Z’
αH|αW’H
W’
→μ|μW’
μ
→α|β
可见，上式方法中，X’表示出了语言的标识符，而Y’表示出了语言的无符号的十进制，Z’表示出了语言中的十六进制。
∵
上式G（S）文法中，各式右边只有单个的终结符号
∴
显然，以上文法G（S）已是正规文法。
（2）正规文法转成正规式：
具体步骤如下：
ω|ωM’
可表示为M’
→ω*ω
μ|μW’
可表示为W’
→μ*μ
α|αZ’
可表示为Z’
α*α
∴转换成正规表达式为：
S=υ|υω*ω|αH|αμ*μH|α*α
代入可得：
S=（β|γ）|（β|γ）（α|β|γ）*（α|β|γ）|αH|α（α|β）*
（α|β）H|α*α
（3）正规式转成NFA（分裂法）
初始的NFA图下所示：
图1
初始NFA图
经过替换规则替换后得到的最终NFA图如下所示：
图2
最终的NFA图
（4）NFA转成DFA及DFA最小化（造表法）
对应以上的NFA图，我们可用造表法来表示如下：
显然，由图可看出，状态2与状态5等价，而状态1与状态3等价，这里省去状态3和状态5，并将所以指向状态3的状态都指向状态1，指向状态5的都指向状态2。
由此可画出最小化的DFA图如下：
图3
最小化的DFA图
可见，终结状态1表示出了无符号的十进制，终结状态2表示出了标识符，状态6表示出了十六进制的整数。
b、
单词的BNF表示
<
标识符>
->
<
字母>
<
字母数字串>
|<
数字>
|
下划线>
|ε
无符号整数>
数字串>
|ε
加法运算符>
+
减法运算符>
-
大于关系运算符>
>
大于等于关系运算符>
=
由此可知，需将单词分为五种：
关键字1
标识符2
常数3
运算符4
分隔符5
printf
a
+
main
b
1
_
;
int
c
2
*
（
if
student
3
/
）
then
sum
4
{
else
k
5
>
}
return
m
6
….
7
8
9
!
（2）编码实现
#include<
stdio.h>
main（intargc,char*argv[]）{
inti,j,state,ERROR=-1;
/*state控制状态的转移1表示0~9数字，2表示字母，4表示a~f，6表示H，0为未输入状态
*ERROR=-1表示未输入任何字符串=1表示输入出错*/
charc;
/*暂时存放所取得的一个字符*/
char*string[]={"
"
"
UnsignedInteger"
Identifier"
Hex"
};
/*输出结果时用*/
for（i=1;
i<
argc;
i++）{
state=0;
/*初始态为0*/
ERROR=0;
/*控制是否为可识别词or非法字符*/
for（j=0;
（c=argv[i][j]）!
='
\0'
j++）{
switch（state）{
case0:
if（c>
0'
&
c<
9'
）
state=1;
elseif
（（c>
a'
z'
）||（c>
A'
Z'
））
state=2;
elseERROR=1;
break;
/*ERROR=1,表示当前字符c为非法字符。
*即此时无状态可转向。
*/
case1:
elseif（（c>
f'
F'
））
state=4;
elseif（c=='
H'
state=6;
else
ERROR=1;
case2:
if（（c>
case4:
elseif（c=='
case6:
ERROR=1;
}/*endswitch*/
if（ERROR==1）
/*退出内for的循环，完成一个词的分析。
}/*endinside-for*/
if（ERROR==1）
printf（"
%-15sisaun-identifyword!
\n"
argv[i]）;
elseif（ERROR==0）
%-15sisa%s\n"
argv[i],string[state]）;
}/*endoutside-for*/
/*未输入任何字符串时（除文件名外）*/
if（ERROR==-1）printf（"
Youinputnothing!
）;
exit（0）;
/*正常退出程序*/
}/*endmain*/
#include<
string.h>
stdlib.h>
ctype.h>
//定义关键字
char*table[7]={"
continue"
main"
int"
if"
then"
else"
return"
},TOKEN[20],ch;
boolzimu（charch）//判断是否为字母
if（ch>
ch<
||ch>
returntrue;
else
returnfalse;
//判断是否为数字
boolshuzi（charch）
intlookup（char*TOKEN）//关键字匹配函数,查询所述程序中的关键字
{
intm,i;
for（i=0;
6;
i++）
{
if（（m=strcmp（TOKEN,table[i]））==0）
return1;
}
return0;
voidout（intc,char*TOKEN）//输出函数
{printf（"
（%d,%s）\n"
c,TOKEN）;
}
voidscanner（FILE*fp）//扫描函数
{
charTOKEN[20]={'
charch;
inti;
ch=fgetc（fp）;
//获取字符，指针fp并自动指向下一个字符
if（zimu（ch）//判断该字符是否是字母，若ch指的是字母，返回非0，否则返回0
{TOKEN[0]=ch;
ch=fgetc（fp）;
//fgetc（fp）从数据流中区下一个字符
i=1;
while（shuzi（ch）||zimu（ch））//判断该字符是否是字母或数字
{
TOKEN[i]=ch;
ch=fgetc（fp）;
i++;
}
fseek（fp,-1,1）;
if（lookup（TOKEN））//判断是关键字还是普通的标识符
out（1,TOKEN）;
else
out（2,TOKEN）;
elseif（shuzi（ch））
TOKEN[0]=ch;
while（shuzi（ch））//判断该字符是否是字母或数字
fseek（fp,-1,1）;
out（3,TOKEN）;
//判断运算符并输出
elseif（ch=='
+'
）{TOKEN[0]=ch;
out（4,TOKEN）;
}
-'
*'
/'
'
//判断分隔符并输出
'
out（5,TOKEN）;
{'
}'
（'
）'
main（）
FILE*fp;
//读取文件内容，并返回文件指针，该指针指向文件的第一个字符
if（（fp=fopen（"
E:
\\222.txt"
r"
））==NULL）
{
fprintf（stderr,"
erroropening.\n"
exit
（1）;
do
if（ch=='
#'
）//文件以#结尾，作为扫描结束条件
break;
'
）//如果是空格，自动跳到下个字符
scanner（fp）;
fseek（fp,-1,1）;
//如果不是空格，则回退一个字符并扫描
}while（ch!
（3）系统调试
5.实验总结
通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。
此外，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；
实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。
这次的实验使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常通过自己编写此类的代码来提高自己的能力。
附录1
Little语言的EBNF文法
program>
:
=<
sequence>
sentence>
{;
inputsentence>
outputsentence>
evaluatesentence>
conditionsentence>
determinacyloopsentence>
indeterminacyloopsentence>
=read<
variable>
=write<
expression>
=if<
compareexpression>
then<
[else<
]fi
=to<
do<
end
=while<
relation>
term>
{<
weakoperator>
element>
strongoperator>
constant>
|<
|（<
digital>
char>
==|=<
|>
=|<
=+|-
=*|/
=0|1|2|3|4|5|6|7|8|9
=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
附录2
1.计算x!
的little程序（测试程序，用于测试你编写的词法分析程序）
Readn；
tondo
readx;
ifx>
0then
y:
=1,z:
=1;
whilez<
xdo
z:
=z+1;
=y*z
end;
writey
fi
2.计算å
x的little程序（测试程序，用于测试你编写的词法分析程序）
n=1;
whilen<
0do
sum=0;
whilex>
sum=sum+x;
x=x-1;
writesum;
readn;
10
升级会员 