编译原理实验一Word文档下载推荐.docx
《编译原理实验一Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《编译原理实验一Word文档下载推荐.docx（16页珍藏版）》请在冰点文库上搜索。
3、S—开始符号/识别符号，S∈VN；
4、P—产生式规则集（或叫规则或生成式或重写规则）；
产生式：
形如α→β或α:
:
=β的表达式，其中α为左部，β为右部。
α∈（VT∪VN）+且至少含一个VN；
β∈（VT∪VN）*。
5、VT∪VN=Ф。
仅由字母表A={ai=1，2，…，k}上的正规式α所组成的语言称为正规集，记为L（α）。
正规集的形式化描述式称为正规式。
字母表上的正规表达式和正规集递归定义如下：
1、中的a是正规表达式，其正规集为{a}；
2、空串是上的正规表达式，其正规集为{}；
3、空集是上的正规表达式，其正规集为；
4、如果e1和e2是上的正规表达式，它们所表示的正规集分别为L（e1）与L（e2），则：
e1|e2也是上的正规表达式，其正规集为L（e1|e2）=L（e1）∪L（e2）。
e1e2也是上的正规表达式，其正规集为L（e1e2）=L（e1）L（e2）。
（e1）*也是上的正规表达式，其正规集为L（（e1）*）=L（e1）*。
而确定有限自动机（DFA）理论定义DFAM=（Q，，t，q0，F）。
1、Q—有穷非空状态集；
2、—有穷输入字母表；
3、t—映射Q→Q（单值映射，下态确定）；
4、q0—q0∈Q,称为开始状态（唯一）；
5、F—非空终止状态集；
非确定有限自动机（NFAM）定义与DFAM的比较可知：
NFA可有多个初态，并可能含ε弧或字符串弧；
在NFA中，t是多值的，即t（s,a）无法唯一地确定下一状态。
对于FA，最重要的是给出其映射。
可以由状态转换表，状态转换图或者直接给出。
1、直接给出：
t（q,a）=q’；
2、状态转换表：
状态为表列，字母为表行；
3、状态转换图：
是由一组矢线连接的有限个结点所组成的有向图。
每一结点均代表在识别或分析过程中扫描器所处的状态。
它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。
下面是标识符的状态图：
标识符状态图
（正规式与有限自动机的等价性）定义：
对任何两个有限的自动机M1和M2，若有L（M1）=L（M2），则称M1与M2等价。
可通过子集法或造表法求解NFA的等价DFA（NFA的确定化方法）。
NFA的确定化方法算法（造表法）：
1、画一张具有n+1列的矩阵表P，n=NFA中出现的符号的个数。
各应列的名字分别为I，Ia，Ib，IC，…，其中，a，b，c…是NFA中出的所有字符。
2、令I=ε－CLOSURE（S0）。
S0：
NFA的初态集。
ε－CLOSURE（S0）=S0∪Sε
Sε={s|从S0的某一状态出发经过任意条ε弧可达s}
3、把I填入乘P的I列
4、计算Ia，Ib，IC，…，并填入相应的列。
Ia=ε－CLOSURE（Ja）
Ja={s|从I的某一状态出发经过一条a弧可到s}
5、若J∈{Ia，Ib，IC，…}未在I列出现，则令I=J。
并重复3~5直列所有的J均在I列中出现过。
6、把P中的各子集作为状态，并重新命名。
7、确定终态和初态：
初态：
I列的第一个元素。
终态：
含有原NFA任一终态的子集。
8、画出相应的DFA
正规文法到有穷自动机的转变步骤：
1、VT⇒Σ；
2、VN⇒Q,其中S⇒q0；
3、A中增加新状态Z作为终态；
4、U→aV⇒t（U，a）=V；
la∈VT或a=ε，V∈VN。
5、U→a（a∈VT）⇒t（U,a）=Z。
正规表达式到有穷自动机的转变，对于任意的一个正则表达式e，从开始，按照变换规则，逐步扩弧、扩结，直到转换图上所有的弧上都是∑中的单个符号为止。
对于引入的每一个新状态，应该赋予一个独有的名字。
其变换规则如下：
正规表达式到有穷自动机的变换规则图
对于一个语言来说，如何对其单词进行分类和编码并没有一个原则性的规定，而主要取决于处理上的方便。
通常按照语法分析的需要设置，用整数表示。
三、实验内容
编写PASCAL子集或C语言子集的词法分析程序，并完成词法分析程序的编程与调试。
C语言子集的词法分析程序程序输入/输出示例：
（2，”main”）
（5，”（“）
（5，”）“）
（5，”{“）
（1，”int”）
（2，”a”）
（5，”,”）
（2，”b”）
（5，”;
”）
（4，”=”）
（3，”10”）
（4，”+”）
（3，”20”）
（5，”}“）
如源程序为C语言。
输入如下一段：
main（）
{
inta,b;
a=10;
b=a+20;
}
要求输出如右图。
要求：
识别保留字：
if、int、for、while、do、return、break、continue；
单词种别码为1。
其他的都识别为标识符；
单词种别码为2。
常数为无符号整形数；
单词种别码为3。
运算符包括：
+、-、*、/、=、>
、<
、>
=、<
=、!
=；
单词种别码为4。
分隔符包括：
、;
、{、}、（、）；
单词种别码为5。
四、设计思路
这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。
在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。
经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：
常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。
0.定义部分：
定义常量、变量、数据结构。
1.初始化：
从文件将源程序全部输入到字符缓冲区中。
2.取单词前：
去掉多余空白。
3.取单词后：
4.取单词：
利用实验一的成果读出单词的每一个字符，组成单词，分析类型。
5.显示结果。
模块结构
词法分析程序流程图
五、注意事项
1.模块设计：
将程序分成合理的多个模块（函数），每个模块做具体的同一事情。
2.写出（画出）设计方案：
模块关系简图、流程图、全局变量、函数接口等。
3.编程时注意编程风格：
空行的使用、注释的使用、缩进的使用等。
六、相关代码
#include
<
iostream>
ctype.h>
fstream>
string.h>
malloc.h>
#define
NULL
"
abc"
using
namespace
std;
ifstream
fp（"
d:
\\cifa.cpp"
ios:
in）;
char
cbuffer;
*key[12]={"
if"
"
else"
for"
while"
do"
return"
break"
continue"
int"
void"
main"
const"
};
*border[6]={
;
{"
}"
（"
）"
*arithmetic[6]={"
+"
-"
*"
/"
++"
--"
*relation[7]={"
="
>
=="
!
*lableconst[80];
int
constnum=40;
lableconstnum=0;
search（char
searchchar[],int
wordtype）
{
i=0,t=0;
switch
（wordtype）
case
1:
for
（i=0;
i<
=11;
i++）
if
（strcmp（key[i],searchchar）==0）
return（i+1）;
}
return（0）;
2:
=5;
（strcmp（border[i],searchchar）==0）
3:
（strcmp（arithmetic[i],searchchar）==0）
4:
=6;
（strcmp（relation[i],searchchar）==0）
5:
（t=40;
t<
=constnum;
t++）
（strcmp（searchchar,lableconst[t]）==0）
return（t+1）;
lableconst[t-1]=（char
*）malloc（sizeof（searchchar））;
strcpy（lableconst[t-1],searchchar）;
constnum++;
return（t）;
6:
=lableconstnum;
（strcmp（searchchar,lableconst[i]）==0）
lableconst[i-1]=（char
strcpy（lableconst[i-1],searchchar）;
lableconstnum++;
return（i）;
default:
cout<
错误！
alphaprocess（char
buffer）
atype;
i=-1;
alphatp[20];
while
（（isalpha（buffer））||（isdigit（buffer）））
alphatp[++i]=buffer;
fp.get（buffer）;
alphatp[i+1]='
\0'
（atype=search（alphatp,1））
alphatp<
\t\t\t"
（atype-1）<
endl;
else
atype=search（alphatp,6）;
return（buffer）;
digitprocess（char
digittp[20];
dtype;
（（isdigit（buffer）））
digittp[++i]=buffer;
digittp[i+1]='
dtype=search（digittp,5）;
digittp<
（dtype-40）<
otherprocess（char
othertp[20];
otype,otypetp;
othertp[0]=buffer;
othertp[1]='
（otype=search（othertp,3））
othertp[1]=buffer;
othertp[2]='
（otypetp=search（othertp,3））
othertp<
（otypetp-1）<
goto
out;
（otype-1）<
（otype=search（othertp,4））
（otypetp=search（othertp,4））
（buffer=='
'
）
='
=
（2,2）\n"
（otype=search（othertp,2））
（（buffer!
\n'
）&
&
（buffer!
））
字符非法"
buffer<
out:
void
main（）
i;
=50;
lableconst[i]=NULL;
（!
fp）
文件打开错误！
！
fp.get
（cbuffer）;
fp.eof（））
（isalpha（cbuffer））
cbuffer=alphaprocess（cbuffer）;
（isdigit（cbuffer））
cbuffer=digitprocess（cbuffer）;
cbuffer=otherprocess（cbuffer）;
完成\n"
getchar（）;
cifa.cpp
a,b;
a=3;
b=2;
c;
return
0;
升级会员 