哈工大威海编译原理实验报告.doc

哈工大威海编译原理实验报告

《编译原理》
实验报告

班级：
学号：
姓名：

实验一 词法扫描器设计
一 实验目的
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。

二 实验内容
设计一个简单的类C语言的词法扫描器。

三 实验要求
（一） 程序设计要求
（1） 根据附录给定的文法，从输入的类C语言源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分隔符五大类；文法见最后附录。
（2） 提供源程序输入界面；
（3） 词法分析后可查看符号表和TOKEN串表；
（4） 保存符号表和TOKEN串表（如：文本文件）；
（5） 遇到错误时可显示提示信息，然后跳过错误部分继续进行分析。
（二）实验报告撰写要求
（1） 系统功能（包括各个子功能模块的功能说明）；
（2） 开发平台（操作系统、设计语言）；
（3） 设计方案；
1） 主数据流图；
2） 主要子程序的流程框图（若有必要）；
3） 模块结构图；
4） 主要数据结构：符号表、TOKEN串表等。
（4） 具体设计过程（包括主控程序、各个功能模块的具体实现）。

1. 系统功能：
根据附录给定的文法，从输入的类C语言源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、分隔符五大类。然后输出本源程序的符号表显示在dos界面和存放在文本文件中。本程序以如下源程序（语法分析的例子）示范：

源程序;
int a;
int b;
int c;
a=2;
b=1;
if （a>b）
　c=a+b;
else
　c=a-b;

子功能模块有：
关键字处理过程；字母的处理过程；数字的处理过程；整个词法分析处理过程;运算符处理过程以及主程序。

2. 开发平台（操作系统、设计语言）；
Windows 7，Microsoft Visual C++ 6.0

3. 设计方案：
（1） 主流程图：

开始

读入文件

CiFaFenXi（）函数进行词法分析

关闭文件流

结束

（2） 主要子程序的流程框图：
判断 是否注释子模块①：

开始

输入文件，读完文件

是否为注释？
N

Ｙ

不处理
继续判断

模块①

判断是否是字符子模块②：

开始

是否为字符？
N

Ｙ
继续别的判断
字符临时赋值给字符串变量

读取下一字符

是否为字符或者数字？

Ｙ

N

字符串变量是否是关键字？

Ｙ
将变量 类型2输出到DOS界面并写入文件
将变量 类型1输出到DOS界面并写入文件

结束

模块②

判断是否为数字或者运算符子模块③：

开始

是否为运算符？
是否为数字？
N

Ｙ Ｙ

将数字赋给变量

对每一个运算符做相应的处理

读取下一变量

输入小数|指数|小数点

Ｙ

N
将变量 类型3写入结果

模块③

实验结果：

Test.txt内容：

Token.txt文件内容：

四 实验总结：
通过词法分析实验，首先我认识到词法分析就是将字符序列转换为单词（Token）序列的过程。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析阶段是编译过程的第一个阶段，这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。并且对符号表有了一定的理解，符号表是：
1、编译过程中编译程序不断汇集和反复查证出现在源程序中各种名字的属性和特征信息等有关信息。
这些信息通常记录在一张或几张符号表中。
2、符号表的每一项有两部分：
一部分是名字（标识符）；一部分是名字属性（标识符的有关信息）。
3、编译过程中，每当扫描器（词法分析器）识别出一个名字后，编译程序就查阅符号表，看其是否在符号表中。
如果它是一个新名字就将它填进表里。
它的有关信息将在词法分析和语法－语义分析过程中陆续填入表中。
4、符号表是边填边用。

附录：类C语言的词法文法
id® Letter <temp>
int10® Num int10 | Num
OP® +| - |* |/ |>| < | = | ( | ) | ; | ‘ | == | >= |<= | !=
Keyword®if | then | else | while | do
Letter®a|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|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
Num®0|1|2|3|4|5|6|7|8|9 |ε
<temp>® Letter <temp> | Num <temp> |ε
实验二 LR语法分析器设计
一 实验目的
通过设计调试LR语法分析程序，实现根据词法分析的输入TOKEN字，进行文法的语法分析；加深对课堂教学的理解；提高语法分析方法的实践能力。

二 实验内容
使用附录中的文法，可以对类似下面的程序语句进行语法分析：
int a;
int b;
int c;
a=2;
b=1;
if （a>b）
c=a+b;
else
c=a-b;
三 实验要求
（一） 程序设计要求
（1）给出主要数据结构：分析栈、符号表；
（2）将扫描器作为一个子程序，每次调用返回一个TOKEN；
（3）程序界面：表达式输入、语法分析的表示结果（文件或者图形方式）；
（二）实验报告撰写要求
（1）系统功能分析及设计（包括各个子功能模块的功能说明）；
（2）开发平台（操作系统、设计语言）；
（3）设计方案:包括功能模块结构图、主要函数的流程图；
（4）主要数据结构：分析栈、分析表、符号表；
（5）具体设计实现过程（包括主控程序、各个功能模块的具体实现）。
四 实验总结

一：系统功能分析及设计：
可对一段包含加减乘除括号的赋值语句进行语法分析，其必须以$为终结符，语句间以；隔离，判断其是否符合语法规则，依次输出判断过程中所用到的产生式，并输出最终结论。
二：开发平台（操作系统，设计语言）
Windows 7，Microsoft Visual C++ 6.0（Dos），C++
三：设计方案：（包括第四步的数据结构）
首先构造数据结构，分析栈，分析表，符号表等如下：
分析栈
struct FenXiZhan
{
char name[50];
char *type;
int value;
}FenXiZhan[1000];
分析表（）

Table[31][20]
{108,0,0,0,0,0,0,0,0,0,0,0,0,1,2,0,4,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1000,0,0,0,0,0,0,0,0,0},
{0,0,109,0,0,0,0,0,0,0,0,113,0,0,0,3,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,201,0,0,0,0,0,0,0,0,0},
{0,0,105,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,106,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{108,0,203,0,0,0,0,0,0,0,0,203,0,0,7,0,4,0,0,0},
{0,0,202,0,0,0,0,0,0,0,0,202,0,0,0,0,0,0,0,0},
{0,0,204,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,110,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,126,0,0,0,0,0,0,127,0,0,0,0,0,0,0,0,11,25},
{0,112,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,205,0,205,0,0,0,0,0,0,0},
{0,0,0,0,114,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,126,0,0,0,0,0,0,127,0,0,0,0,0,0,0,15,28,25},
{0,0,0,0,0,116,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,109,0,0,0,0,0,0,0,113,0,0,0,0,17,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,118,0,0,0,0,0,0,0},
{0,0,109,0,0,0,0,0,0,0,113,0,0,0,0,19,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,206,0,206,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,121,123,0,0,0,0,0,0,0,0,0,0,0},
{0,0,126,0,0,0,0,0,0,127,0,0,0,0,0,0,0,0,0,22},
{0,208,0,0,0,0,208,208,208,0,0,0,0,0,0,0,0,0,0,0},
{0,0,126,0,0,0,0,0,0,127,0,0,0,0,0,0,0,0,0,24},
{0,209,0,0,0,0,209,209,209,0,0,0,0,0,0,0,0,0,0,0},
{0,210,0,0,0,0,210,210,210,0,0,0,0,0,0,0,0,0,0,0},
{0,211,0,0,0,0,211,211,211,0,0,0,0,0,0,0,0,0,0,0},
{0,212,0,0,0,0,212,212,212,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,129,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,126,0,0,0,0,0,0,127,0,0,0,0,0,0,0,0,30,25},
{0,0,0,0,0,207,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
符号表：
struct TokenTable
{
char *type;
int attr;
}TokenTable[1000];
具体思路：首先对源文件进行词法分析，然后产生符号表FenXiTable（），然后对词法分析产生的Token进行语法分析，用分析栈和分析表进行GOTO和ACTION函数进行语法分析。

五：具体实现过程：
Main函数：
开始

输入源文件

词法分析建立符号表

语法分析LR()进行语法分析

输出结果

结束

词法分析流程：

开始

读入文件

CiFaFenXi（）函数进行词法分析

关闭文件流

结束

实验结果：

总结：通过这次语法分析LR（0）实验，我加深了对语法分析的理解，并且能熟练利用分析表进行GOTO函数和ACTION函数的应用，以前在书本上学到的东西，没有实验之前都很抽象，但是自己通过实验，利用数组产生了分析表，对LR（0）自动机也有了很深的理解！

附录：简单类c语言文法
产生式 语义规则
注：P为文法的开始符号
说明语句部分文法：
P → D S
D →L id ; D |ε
L → int | float

程序语句部分文法：
S → id = E; S.code = E.code || gen(id.place’:=’E.place)
S → if （C） S1 C.true = newlabel; C.false = S.next;
S1.next = S.next;
S.code = C.code || gen(C.true’:’) || S1.code
S → if （C） S1 else S2
S → while （C） S1 do S2
C.true = newlabel; C.false = newlabel;
S1.next = S2.next =S.next;
S.code = C.code || gen(C.true’:’) || S1.code
|| gen(‘goto’S.next)|| gen(C.false’:’)|| S2.code;
S → S ;S
C → E1 > E2
C.code = E1.code || E2.code ||
gen(‘if’E1.place’>’E2.place’goto’C.true) ||
gen(‘goto’C.false)
C → E1 < E2 C.code = E1.code || E2.code ||
gen(‘if’E1.place’<’E2.place’goto’C.true) ||
gen(‘goto’C.false)
C → E1 == E2 C.code = E1.code || E2.code ||
gen(‘if’E1.place’=’E2.place’goto’C.true) ||
gen(‘goto’C.false)
E → E1 + T E.place = newtemp;
E.code = E1.code||T.code||
gen(E.place’:=’E1.place’+’T.place)
E → E1 – T E.place = newtemp; E.code = E1.code || T.code ||
gen(E.place’:=’E1.place’-’T.place)
E → T E.place = T.place; E.code = T.code
T → F T.place = F.place; T.code = F.code
T → T1 * F T.place = newtemp;
T.code = T1.code || F.code ||
gen(T.place’:=’T1.place’*’F.place)
T → T1 / F T.place = newtemp; T.code = T1.code || F.code ||
gen(T.place’:=’T1.place’/’F.place)
F → ( E ) F.place = E.place; F.code = E.code
F → id F.place = id.name; F.code = ‘ ‘
F → int10 F.place = int10.value; F.code = ‘ ‘

实验三 语义分析及中间代码生成
一 实验目的
通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。

二 实验内容
实现简单的高级语言源程序的语义处理过程。

三 实验要求
（一） 程序设计要求
（1） 目 标 机：8086及其兼容处理器
（2） 中间代码：三地址码
（3） 设计结果：语法分析树（节点具有属性）、三地址码表、符号表、TOKEN串表
（4） 语义分析内容要求：
1) 变量说明语句
2) 赋值语句
3) 控制语句(任选一种)
（5） 其它要求：
1) 将词法分析（扫描器）作为子程序，供语法语义程序调用；
2) 使用语法制导的语义翻译方法；
3) 编程语言自定；
4) 最好提供源程序输入界面；
5) 目标代码生成暂不做；
6) 编译后，可查看TOKEN串、符号表、三地址码表；
7) 主要数据结构：产生式表、符号表、三地址码表。
所用文法使用实验2中的文法。
附录：语义分析源程序范例
int a;
int b;
int c;
a=2;
b=1;
if （a>b）
c=a+b;
else
c=a-b;

（二）实验报告撰写要求
（1） 系统功能分析及设计（包括各个子功能模块的功能说明）；
（2） 开发平台（开发软硬件环境）；
（3） 语义翻译中使用的数据结构；
一：系统功能分析及设计：
在词法分析和语法分析的基础上进一步分析含义，主要的工作是静态语义检查和三地址代码的翻译。
二：开发平台;
Windows 7，Microsoft Visual C++ 6.0（Dos），C++
三:数据结构：
struct token//词法 token结构体
{
int code;//编码
int num;//递增编号
token *next;
};
token *token_head,*token_tail;//token队列
struct str//词法 string结构体
{
int num;//编号
string word;//字符串内容
str *next;
};
str *string_head,*string_tail;//string队列
struct ivan//语法 产生式结构体
{
char left;//产生式的左部
string right;//产生式的右部
int len;//产生式右部的长度
};
ivan css[20];//语法 20个产生式
struct pank//语法 action表结构体
{
char sr;//移进或归约
int state;//转到的状态编号
};
pank action[46][18];//action表
int go_to[46][11];//语法 go_to表
struct ike//语法 分析栈结构体，双链
{
ike *pre;
int num;//状态
int word;//符号编码
ike *next;
};
ike *stack_head,*stack_tail;//分析栈首尾指针
struct L//语义四元式的数据结构
{
int k;
string op;//操作符
string op1;//操作数
string op2;//操作数
string result;//结果
L *next;//语义四元式向后指针
L *Ltrue;//回填true链向前指针
L *Lfalse;//回填false链向前指针
};
L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;//四元式链，true链，false链
struct symb//语义输入时符号表
{
string word;//变量名称
int addr;//变量地址
symb *next;
};
symb *symb_head,*symb_tail;//语义符号链表

四：实验流程图：

实验结果：

语法分析：
中间代码的生成

实验总结：通过语义分析和中间代码生成，我加深了对语义分析的理解，即在推导或者规约时进行一些语义动作。至于生成中间代码特别有好处，就是具有了可移植性，并且可以对其进行优化，从而提升代码执行的速度。

29 / 29