编译原理词法分析程序实验报告.doc

编译原理实验报告

实验名称：编写词法分析程序

实验类型：设计性实验

指导教师：*****

专业班级：软件工程1401

姓名：****

学号：**********

实验地点：东六E座301

实验成绩：_________________

日期：2016年5月8日

实验一

编写词法分析程序

一、实验目的

通过设计、调试词法分析程序，掌握词法分析程序的设计工具〔有穷自动机〕，进一步理解自动机理论

掌握正那么文法和正那么表达式转换成有穷自动机的方法及有穷自动机实现的方法

确定词法分析程序的输出形式及标识符与关键字的区分方法

加深对理论知识的理解

二、实验设计

设计原理：

对源程序代码从头到尾扫描，将符合词法语言规那么的单词输出，包括：标识符、保存字、无符号整数、分界符、运算符、注释别离；判断程序的词法是否正确

TEST语言的词法规那么如下：

1〕、标识符：字母打头，后接任意字母或数字。

2〕、保存字：标识符的子集，包括：if,else,for,while,do,int,write,read。

3〕、无符号整数：由数字组成，但最高位不能为0，允许一位的0。

4〕、分界符：(、)、;、{、}

5〕、运算符：+、-、*、/、=、、、=、=、!=、==

6〕、注释符：/**/

设计方法：

用正那么表达式或正那么文法描述程序设计语言的词法规那么，通常采用正那么表达式；一个正那么表达式对应一条词法规那么

为每个正那么表达式构造一个NFA，用来识别正那么表达式描述的单词将每一个NFA合并、化简得到最简的DFA

将多个NFA合并为一个NFA

将NFA转换成等价的DFA。

最小化DFA

确定单词的输出形式。

化简后的DFA＋单词输出形式?构造词法分析程序

设计过程：

将TEST语言的六个语法规那么分别转换成正那么表达式

为每个正那么表达式构造一个NFA，用来识别正那么表达式描述的单词

将5个NFA转换成一个NFA，再将NFA化简确定化。

设计结果：

每一条TEST语言对应的正那么表达式如下：

标识符：(a|b|……|z|A|B……|Z)(0|1|……|9|a|b|……|z|A|B……|Z)*

保存字：标识符的子集

无符号整数：((1……|9)(0|1|……|9)*)|0

分界符：(|)|;|{|}

运算符：+|-|*|/|=|||=|=|!=|==

注释符：/*〔其他〕*/

NFA如图

化简、确定化的DFA

三、实验过程

将TEST语言的六个语法规那么转换成正那么表达式

将每个正那么表达式装换成NFA,再将NFA合并化简

最终得到设计结果如上所示：

根据确定化的DFA编写代码

测试实验数据

三、实验结果

测试数据：

{

/*Thisatestprogram.*/

intabc;

int123;

intA$@;

inti;

intn;

intb,c;

int2a;

inta2;

readn;

n=012345;

for(i=1;i=n;i=i+1)

{

abc=abc+i;

}

if(i!=n)n=n+i;

if(!n)b=b+c;

/*Theloopended

writeabc;

}

实验现象：

控制台显示的数据：

输出文本的数据：

{ {

int int

ID abc

; ;

int int

NUM 123

; ;

int int

ID A

Error $

Error @

; ;

int int

ID i

; ;

int int

ID n

; ;

int int

ID b

Error ,

ID c

; ;

int int

NUM 2

ID a

; ;

int int

ID a2

; ;

read read

ID n

; ;

ID n

= =

NUM 0

NUM 12345

; ;

for for

( (

ID i

= =

NUM 1

; ;

ID i

= =

ID n

; ;

ID i

= =

ID i

+ +

NUM 1

) )

{ {

ID abc

= =

ID abc

+ +

ID i

; ;

} }

if if

( (

ID i

!= !=

ID n

) )

ID n

= =

ID n

+ +

ID i

; ;

if if

( (

Error !

ID n

) )

ID b

= =

ID b

+ +

ID c

; ;

数据分析：

根据TEST语法规那么，我们可以知道

intA$@;这一句中的$和@是不合法的

i