编译原理实验一Word文档下载推荐.docx
- 文档编号:923950
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:16
- 大小:92.47KB
编译原理实验一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;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验