实验1：源程序预处理
一、实验目的：
对源程序进行预处理（函数实现，该函数以后还要用到；输入是源程序，输出是预处理过的程序）
二、实验内容：
对源程序进行预处理，去掉空格，跳格，回车，换行，注释等；
三、实验要求：
从文本文件中读入源代码文本字符串，预处理结束后写入另外一个文本文件中；
实验2：构造词法分析器-自然分词
一、实验目的：
从源程序中分离出单词并归类（自然分词构造词法分析程序）
二、实验内容：
设计一个词法分析器，用C 语言或者其他的高级语言实现；
从预处理过的源代码文本文件（实验一的输出文件）中读取源代码字符串，词法分析输出的二元式写入另外一个文本文件中；
三、实验要求：
1
2
3
4、根据文法绘制状态转化图
（本图为示例图，实际的状态转化图要自己绘制完成）
自定义函数或者使用到变量的意义
char buffer[] 字符数组，存放源代码的文本；
char CHAR 字符变量，存放最新读进的源程序字符；
char TOKEN[] 字符数组，存放构成单词的字符串；
char GETCHAR(char buffer[]，int* searchIndex) 将下一输入字符读入CHAR，搜索指示器searchIndex前移一个字符；
void GETBC(char buffer[]) 检查CHAR中的字符是否为空白。若是则调用GETCHAR直至CHAR中进入一个非空白字符。
void CONCAT(char TOKEN[],char CHAR ) 把CHAR中的字符连接到TOKEN之后。
int LETTER(char CHAR) 判断CHAR中的字符是不是字母，从而给出真假值TRUE、FALSE。
int DIGIT(char CHAR) 判断CHAR中的字符是不是数字，从而给出真假值TRUE、FALSE。
void RESERVE(char RESERVE_TABLE[][],char TOKEN[]) 在保留字表RESERVE_TABLE[][]中查找TOKEN
void RETRACT(char buffer[],int* searchIndex) 把搜索指示器回调一个字节，把CHAR中的字符置为空白。
5、把状态转换图转化成程序，每个状态要建立一段程序，做的工作如下：
第一步：从输入缓冲区中取一个字符。使用函数GETCHAR，每次调用，推进先行指针，送回一个字符。
第二步：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找该单词的企图就失败了。
失败：先行指针必须重新回到开始指针处，并用另一状态图来搜索另一单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。
典型状态转换图处理流程如下
如上的状态转换图，处理代码如下所示：
switch（state）
{
case i：
CHAR = GETCHAR(buffer[] ,searchIndex)；
if（LETTER( CHAR ) == TRUE ）
{
CONCAT(TOKEN[],CHAR);
state = j ;
}
else if（ DIGIT(CHAR) == TRUE ）
{
CONCAT(TOKEN[],CHAR);
state = k ;
}
else if （CHAR==’/’）
{
CONCAT(TOKEN[],CHAR);
state = l;
}
else
{ FAIL(); }
break;
}
如上的状态转换图，处理代码如下所示：
switch(state)
{
case 0：
CHAR = GETCHAR(buffer[],searchIndex) ;
if ( LETTER(CHAR)==TRUE )
{
CONCAT(TOKEN[],CHAR);
state = 1 ;
}
else
{ FAIL(); }
break;
case 1：
CHAR = GETCHAR(buffer[],searchIndex);
if ( LETTER(CHAR)==TRUE || DIGIT(CHAR) ==TRUE )
{
CONCAT(TOKEN[],CHAR);
state = 1 ;
}
else
{ state = 2 ; }
break;
case 2：
//构造TOKEN[]对应的二元式
RETRACT( buffer[], searchIndex) ; //返回多读去的一个字符 return TOKEN[]对应的二元式 ;
}
如上的状态转换图，处理代码如下所示：
switch (state)
{
case 3 :
CHAR = GETCHAR(buffer[],searchIndex);
if ( DIGIT(CHAR)==TRUE )
{
CONCAT(TOKEN[],CHAR);
state = 3 ;
}
else
{
state = 4 ;
}
break;
case 4:
//构造TOKEN[]对应的二元式
RETRACT( buffer[], searchIndex) ; //返回多读去的一个字符
return TOKEN[]对应的二元式 ;
}
实验3：构造词法分析器-DFA
一、实验目的：
使用DFA实现词法分析（函数实现，该函数以后还要用到，输入预处理过的源程序，输出是分离出的单词符号和种别码的列表）
二、实验内容：
基于DFA设计一个词法分析器。
从预处理过的源代码文本文件（实验一的输出文件）中读取源代码字符串，词法分析输出的二元式写入另外一个文本文件中；
三、实验要求：
1
2
3
4
（下图为示例图，实际的状态转化图要自己绘制完成）
5、根据状态转化图生成转换表（DFA）
5、算法流程
初始化源程序文件；
标识符字串设置为空；
当前状态设置为初态；
从源程序文件中读取字符设置为当前字符；
do{
while( DFA[当前状态][当前字符] 存在后继状态)
{
将当前字符拼接进标识符字串中；
后继状态=DFA[当前状态][当前字符]；
当前字符指向源程序中后继字符；
当前状态设置为后继状态；
}
判断标识符字串的类别( 自定义标识符、关键字（保留字）、常数、运算符)；
构造标识符字串所对应的二元式；
将二元式写入二元式文件；
当前状态设置为初态；
标识符字串设置为空；
从源程序文件中读取下一个字符设置为当前字符；
}while(源程序未结束)；
实验4：人狼羊菜过河
一、实验目的：
输出人狼羊菜过河的方法
二、实验内容：
组合出所有可能状态
去除禁忌状态
构造图（邻接矩阵或者邻接表）
查找路径（深度优先、广度优先）
三、实验要求：
实验5：词法分析-LEX
一、实验目的：
使用LEX分析工具将LEX源程序编译为词法分析器
二、实验内容：
Lex工具是词法分析程序的生成器，它根据词法构成规则（正则表达式）生成单词识别程序，由该程序识别出输入源程序（程序设计者根据词法构成规则编写的源程序）中的各个单词。
1、lex程序的结构共有三部分：定义部分、规则部分、-用户子程序部分。其中规则部分是必须的，定义和用户子程序部分是任选的。
(1) 定义部分
定义部分起始于"%{"符号，终止于"%}"符号，其间可以是包括include语句、声明语句在内的C语句。
%{
#include "stdio.h"
#include "y.tab.h"
extern int lineno;
%}
(2) 规则部分
规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。
%%
[/t] {;}
[0-9]+/.?|[0-9]*/.[0-9]+
{ sscanf(yytext,"%1f", &yylval.val);
return NUMBER; }
/n { lineno++;return '/n'; }
. { return yytex+[0]; }
%%
(3) 用户子程序部分
用户子程序部分可以包含用C语言编写的子程序。这些子程序可以用在前面的动作中，可以达到简化编程的目的。下面是带有用户子程序的lex程序片段。
"/*" skipcmnts();
/* rest of rules */
%%
skipcmnts()
{
for ( ; ; )
{
while (input()!='*');
if(input()!='/') unput(yytext[yylen-1]);
else return;
}
2、lex工具的使用方法
首先编写一个lex程序
vi lex.l
%{
#include "stdio.h"
%}
%%
[/n] ;
[0-9]+ printf("Interger: %s /n",yytext);
[0-9]*/.[0-9]+ printf("Float: %s/n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Word:%s/n",yytext);
. printf("Other symbol:%c/n",yytext[0]);
%%
然后使用lex将lex.l转换成C语言程序
$lex lex.l
使用上述命令产生的C语言程序为lex.yy.c
然后使用C编译程序将lex.yy.c编译成可执行程序regn
$cc -c lex.yy.c
$cc lex.yy.o -ll -o regn
下面可以使用regn来识别单词
$vi testfile
x=355
y=113
p=x/y
# ./regn < testfile
Word:x
Other symbol:=
Interger: 355
Word:y
Other symbol:=
Interger: 113
Word:p
Other symbol:=
Word:x
Other symbol:/
Word:y
#
三、实验要求：
实验6：正则式转化为NFA
一、实验目的：
将输入的正则表达式转化为NFA
二、实验内容：
编程序实现正则表达式转化为NFA。
三、实验要求：
(1)程序接受文本文件中输入的正则表达式，生成该正则表达式对应的NFA，在屏幕上显示出这个NFA。
(2)统计并输出该NFA中的节点个数和边的个数；
(3)输入的正则表达式中包含的运算符包括：连接运算符”.”,闭包运算符“*”,逻辑或运算符“|”,左括号“(“,右括号“)”。运算符的运算优先级:
(4)输入的正则表达式中的字符限于大写英文字母，小写英文字母，数字0~9；
(5)NFA使用图的邻接链表或者邻接矩阵存储；
(6)程序的调试者和执行者保证输入的正则表达式正确，程序不检查正则表达式的正确性。
四、结构体和算法流程
NFA的栈结
算符优先算法
初始化状态栈；
初始化运算符栈；
# 压进入运算符栈；
在正则表达式末尾添加 # 运算符；
产生一个初始0号节点
读取正则表达式的第一个字符；
while (正则表达式没有结束)
{
if (当前字符是正则表达式的字符)
{
产生一对新开始和结束节点；
在开始节点和结束节点之间拉一条标注为当前字符的箭弧；
将开始节点和结束节点压入状态栈；
读取下一个字符；
}
else
{
if (当前操作符运算优先级别比栈顶运算符优先级别高)
{
当前操作符压入符号栈；
读取下一个字符；
}
else if（当前操作符运算优先级别比栈顶运算符优先级别低）
{
运算符栈的栈顶运算符出栈；
if（出栈运算符是连接符）
{
从状态栈中弹出一对开始结束节点A；
从状态栈中弹出一对开始结束节点B；
从B的结束节点拉一条ε指示的箭弧到A的开始节点；
B的开始节点和A的结束节点作为一对开始结束节点入状态栈；
}
else if(出栈运算符是逻辑或)
{
从状态栈中弹出一对开始结束节点A；
从状态栈中弹出一对开始结束节点B；
生成一对新的开始结束节点C；
从C的开始节点拉一条ε指示的箭弧到A的开始节点；
从C的开始节点拉一条ε指示的箭弧到B的开始节点；
从A的结束节点拉一条ε指示的箭弧到C的结束节点；
从B的结束节点拉一条ε指示的箭弧到C的结束节点；
C的开始节点和结束节点作为一对节点入状态栈；
}
else if（出栈运算符是闭包运算符）
{
从状态栈中弹出一对开始结束节点A；
生成一对新的开始结束节点C；
从C的开始节点拉一条ε指示的箭弧到A的开始节点；
从A的结束节点拉一条ε指示的箭弧到C的结束节点；
从A的结束节点拉一条ε指示的箭弧到A的开始节点
从C的开始节点拉一条ε指示的箭弧到C的结束节点
C的开始节点和结束节点作为一对开始结束节点入状态栈；
}
}
else if(当前操作符运算优先级别比栈顶运算符优先级别相等)
{
if（栈顶运算符是左括号且当前运算符是右括号）
{
左括号出运算符栈；
扫描下个字符；
}
else if（栈顶运算符是# 且当前运算符是#）
{
正则表达式处理完成，退出循环；
}
}
}
}
从状态栈中弹出一对开始结束节点A ；
从0号节点拉一条ε指示的箭弧到A 的开始节点；
操作说明：
产生一对新开始和结束节点： 将结构体 struct NFA 的成员stateCount 的值增加 2，表示结构体成员StateList 数组中的有效元素增加2个，数组的成员是结构体struct State ，该结构体有2个数据成员：nStateID （表示节点ID ）和 pFirstArrow （表示这个节点上出发的箭弧链表）；设置新增的2个数组成员的StateList[stateCount-1]和StateList[stateCount-2]的nStateID 的值为唯一的状态ID ，第一条箭弧的指针pFirstArrow 赋值为空；
在开始节点和结束节点之间拉一条标注为当前字符的箭弧：
在结构体NFA 的成员StateList 数组中查找到开始节点（找到开始节点对应的下标），该数组元素是个struct State 类型的结构体，结构体struct State 中有个指针成员pFirstArrow ，该指针成员指示的链表是所有从这个顶点出发的箭弧，在这个链表中增加一个链表元素（可以用头插法或者尾插法插入），表示新增加的边。该新增的链表元素是个结构体struct Arrow ，设置该结构体中的箭弧终点的节点状态nEndStateID 的值为结束节点的ID ，箭弧上标注的字符chLetter 的值为当前字符，箭弧的下一个指针pNextArrow 的值根据头使用插入还是尾插法进行不同的设置；
C 的开始节点和结束节点作为一对开始结束节点入状态栈：
C 实际是结构体NFA 中的成员StateList 数组中的2个数组成员，结构体的struct stateStack 的中代表栈空间的成员pStateList 是指针数组，数组的成员中存放struct State 类型的地址，只要把C 中2个节点在结构体NFA 中的成员StateList 数组中的地址赋值给stateStack 的中代表栈空间的成员
pStateList 的数组成员。
七、举例
实验7：NFA 转化为DFA
一、 实验目的： 将nfa 转化为dfa 二、 实验内容：
编程序实现NFA 转化为DFA 。 三、 实验要求：
六、结构体和算法流程
NFA的栈结
七、举例
实验8：DFA最小化
一、实验目的：
将DFA最小化
二、实验内容：
编程序实现DFA最小化。
三、实验要求：
四、结构体和算法流程
NFA的栈结
五、举例
实验9：正则式转化为DFA-完整程序
一、实验目的：
将输入的正则表达式转化为dfa（正则式转化为nfa，nfa转化为dfa，dfa最小化）
二、实验内容：
将输入的正则表达式转化为NFA的程序。
三、实验要求：
(1)程序接受文本文件中输入的正则表达式，生成该正则表达式对应的NFA，在屏幕上显示出这个NFA。
(2)统计并输出该NFA中的节点个数和边的个数；
(3)输入的正则表达式中包含的运算符包括：连接运算符”.”,闭包运算符“*”,逻辑或运算符“|”,左括号“(“,右括号“)”。运算符的运算优先级:
(4)输入的正则表达式中的字符限于大写英文字母，小写英文字母，数字0~9；
(5)NFA使用图的邻接链表或者邻接矩阵存储；
(6)程序的调试者和执行者保证输入的正则表达式正确，程序不检查正则表达式的正确性。
四、结构体和算法流程
NFA的栈结
算符优先算法
初始化状态栈；
初始化运算符栈；
# 压进入运算符栈；
在正则表达式末尾添加 # 运算符；
产生一个初始0号节点
读取正则表达式的第一个字符；
while (正则表达式没有结束)
{
if (当前字符是正则表达式的字符)
{
产生一对新开始和结束节点；
在开始节点和结束节点之间拉一条标注为当前字符的箭弧；
将开始节点和结束节点压入状态栈；
读取下一个字符；
}
else
{
if (当前操作符运算优先级别比栈顶运算符优先级别高)
{
当前操作符压入符号栈；
读取下一个字符；
}
else if（当前操作符运算优先级别比栈顶运算符优先级别低）
{
运算符栈的栈顶运算符出栈；
if（出栈运算符是连接符）
{
从状态栈中弹出一对开始结束节点A；
从状态栈中弹出一对开始结束节点B；
从B的结束节点拉一条ε指示的箭弧到A的开始节点；
B的开始节点和A的结束节点作为一对开始结束节点入状态栈；
}
else if(出栈运算符是逻辑或)
{
从状态栈中弹出一对开始结束节点A；
从状态栈中弹出一对开始结束节点B；
生成一对新的开始结束节点C；
从C的开始节点拉一条ε指示的箭弧到A的开始节点；
从C的开始节点拉一条ε指示的箭弧到B的开始节点；
从A的结束节点拉一条ε指示的箭弧到C的结束节点；
从B的结束节点拉一条ε指示的箭弧到C的结束节点；
C的开始节点和结束节点作为一对节点入状态栈；
}
else if（出栈运算符是闭包运算符）
{
从状态栈中弹出一对开始结束节点A；
生成一对新的开始结束节点C；
从C的开始节点拉一条ε指示的箭弧到A的开始节点；
从A的结束节点拉一条ε指示的箭弧到C的结束节点；
从A的结束节点拉一条ε指示的箭弧到A的开始节点
从C的开始节点拉一条ε指示的箭弧到C的结束节点
C的开始节点和结束节点作为一对开始结束节点入状态栈；
}
}
else if(当前操作符运算优先级别比栈顶运算符优先级别相等)
{
if（栈顶运算符是左括号，当前运算符是右括号）
{
左括号出运算符栈；
扫描下个字符；
}
else if（栈顶运算符是#，当前运算符是#）
{
正则表达式处理完成，退出循环；
}
}
}
}
从状态栈中弹出一对开始结束节点A；
从0号节点拉一条ε指示的箭弧到A的开始节点；
操作说明：
产生一对新开始和结束节点：
将结构体 struct NFA 的成员stateCount的值增加 2，表示结构体成员StateList数组中的有效元素增加2个，数组的成员是结构体struct State，该结构体有2个数据成员：nStateID（表示节点ID）和 pFirstArrow（表示这个节点上出发的箭弧链表）；设置新增的2个数组成员的StateList[stateCount-1]和StateList[stateCount-2]的nStateID的值为唯一的状态ID，第一条箭弧的指针pFirstArrow赋值为空；
在开始节点和结束节点之间拉一条标注为当前字符的箭弧：
在结构体NFA的成员StateList数组中查找到开始节点（找到开始节点对应的下标），该数组元素是个struct State类型的结构体，结构体struct State中有个指针成员pFirstArrow，该指针成员指示的链表是所有从这个顶点出发的箭弧，在这个链表中增加一个链表元素（可以用头插法或者尾插法插入），表示新增加的边。该新增的链表元素是个结构体struct Arrow，设置该结构体中的箭弧终点的节点状态nEndStateID的值为结束节点的ID，箭弧上标注的字符chLetter的值为当前字符，箭弧的下一个指针pNextArrow的值根据头使用插入还是尾插法进行不同的设置；
C的开始节点和结束节点作为一对开始结束节点入状态栈：
C实际是结构体NFA中的成员StateList数组中的2个数组成员，结构体的struct stateStack的中代表栈空间的成员pStateList是指针数组，数组的成员中存放struct State类型的地址，只要把C中2个节点在结构体NFA中的成员StateList数组中的地址赋值给stateStack的中代表栈空间的成员pStateList的数组成员。
五、举例
实验10：由上向下分析-递归下降分析器
一、实验目的：
（教材74页）
实现源程序的递归下降分析（输入是源程序和文法，输出源程序是否是由该文法产生的，用到前边的预处理程序，词法分析器程序）
二、实验内容：
三、实验要求：
实验11：由上向下分析-预测分析(一)-构造First和Follow
一、实验目的
根据文法求出First和Follow集合（First教材78页，Follow教材79页）
二、实验内容
构造First
构造Follow
三、实验过程
实验12：由上向下分析-预测分析(二)-构造预测分析表
一、实验目的：
根据文法计算预测分析表（教材79页）
二、实验内容：
三、实验要求：
实验13：由上向下分析-预测分析(三)-构造预测分析语法分析器一、实验目的：
实现预测分析程序（教材77页）
二、实验内容：
三、实验过程：
实验14：由上向下分析-SubC语法分析器
一、实验目的：
1．使用预测分析法编制一个语法分析子程序；
2．加强对语法分析原理、方法和基本实现技术的理解；
3．强化对系统软件综合工程实现能力的训练。
二、实验内容：
用 C 语言或者其他的高级语言开发完成SubC语言的语法分析器的设计和实现。
三、实验要求：
(1)语法分析器的程序输入文件是文本格式的C语言程序二元式，该文件是使用实验一的词法分析器程序输出。
(2)程序的输出文件是以文本格式存储的语法分析结果。分析结果中要求输出当前栈中的全部元素，当前出栈的栈顶状态，当前的输入符号，在使用某个产生式的右部替换栈顶元素时输出该产生式。
(3)指出分析结果正确或者错误。
四、SubC的文法
1).<程序>→int main(){<声明序列><语句序列>}
2).<声明序列>→<声明序列><声明语句>|<声明语句>|<空>
3).<声明语句>→int<标识符表>;|float<标识符表>;
4).<标识符表>→<标识符>,<标识符表>|<标识符>
5).<语句序列>→<语句序列><语句>|<语句>
6).<语句>→
7).<输入输出语句>→
8).
9).
10).
11).
12).
13).<复合语句>→{<语句序列>}
14).<赋值语句>→<表达式>;
15).<表达式>→<标识符>=<算数表达式>|<标识符>=<布尔表达式>
16).<布尔表达式>→<算数表达式>|<算数表达式><关系运算符><算数表达式>|<布尔表达式><逻辑运算符><布尔表达式>
17).<关系运算符>→>|<|>=|<=|==|!=
18).<逻辑运算符>→&& | ‘||’ | !
19).<算数表达式>→<算数表达式>+<项>|<算数表达式>-<项>|<项>
20).<项>→<项>*<因子>|<项>/<因子>|<因子>
21).<因子>→<标识符>|<无符号整数>|(<算数表达式>)
22).<标识符>→<字母>|<标识符><字母>|<标识符><数字>
23).<无符号整数>→<数字>|<无符号整数><数字>
24).<字母>→a|b|…|z|A|B|…|Z
25).<数字>→0|1|….|9
注：* 红色字体的产生式必做，紫色字体产生式，带灰影的产生式，蓝色字体产生式为选作；
* 绿色字体的产生式在词法分析器中已完成；
* 上述产生式要自己编码。含有左递归的要消除左递归，含有左公共因子的要左提公因子，转化为符合LL（1）的文法。
实验15：由下向上分析-算符优先(一)-构造FirstVT和LastVT
一、实验目的
根据文法求出FirstVT和LastVT（教材90页，91页）
二、实验内容
构造FirstVT和LastVT
三、实验过程
实验16：由下向上分析-算符优先(二)-构造算符优先表
一、实验目的
根据文法构造算法优先表（教材92页）
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分
南华大学 计算机科学与技术学院 实验报告 （ 2018~2019学年度第二学期） 课程名称编译原理 实验名称词法分析器的设计与 实现 姓名学号
专业班级 地点教师 1.实验目的及要求 实验目的 加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。 实验要求 1.对单词的构词规则有明确的定义； 2.编写的分析程序能够正确识别源程序中的单词符号； 3.识别出的单词以 <种别码，值 >的形式保存在符号表中，正确设计和维护 符号表； 4.对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误 提示，保证顺利完成整个源程序的词法分析； 2.实验步骤 1.词法分析规则 <标识符 >::=< 字母 >|< 标识符 ><字母 >|< 标识符 ><数字 >
<常数 >::=< 数字 >|< 数字序列 ><数字 > <数字序列 >:: ＝<数字序列 ><数字 >|< 数字 >|<.> <字母 >::=a|b|c|??|x|y|z <数字 >::=0|1|2|3|4|5|6|7|8|9 <运算符 >::=< 关系运算符 >|< 算运算符 >|< 运算符 >|< 位运算符 >|< 运算符 > <算数运算符 >:: ＝+|-|*|／|...|-- <关系运算符 >:: ＝<|>|!=|>=|<=|== <运算符 >::=&&| || |！ <位运算符 >::=&| | |！ <运算符 >::==|+=|-=|/=|*= <分界符 >:: ＝ ,|;|(|)|{|}|：| // |/**/ <保留字 >:: ＝ main|if|else|while|do|for|...|void 2.符号的 符号种符号种 main0>26 if1>=27 else2<28 while3<=29 do4!30 for5!=31
编译原理实验报告 题目构造识别字符串的自动机学院 专业 班级 学号 学生姓名 指导教师 西安思源学院教务处制 二〇一年
实验二构造识别符号串的自动机 一、实验目的 1 掌握形式语言与自动机的概念 2 了解正规集及有穷自动机的关系 3 能构造识别相应符号串的自动机 4 能构造词法分析程序所识别的各类单词的自动机 二、实验环境 Microsoft Visual C++ 6.0 三、实验内容 1 用高级语言编写程序：该程序能接受C++所有的标识符。 2 用高级语言编写程序：该程序能接受C++所有的常数(整数和定点小数)。 3 用高级语言编写程序：该程序能接受C++的所有保留字。 4 用高级语言编写程序：该程序能接受C++的所有界符、运算符。 四、设计说明 void main() { void find_word(); void show_all(); void Input(); Input(); cout<<"运行结果如下"<
院系：计算机科学学院 专业、年级： 07计科2大班 课程名称：编译原理 学号姓名： 指导教师： 2010 年11月17 日 组员学号姓名
实验 名称 实验一：词法分析实验室9205 实验目的或要求 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
实验二语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身 嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套， 其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。 其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。 要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理 具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉}
实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程
《编译原理》实验指导书 实验目的和内容 编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法、语法和语义分析程序，验证实际编译系统的实现方法，并加深对编译技术的认识。 实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求，有余力的同学可尝试实验的扩展要求部分。 实验报告 要求每人针对所完成的实验内容上交一份实验报告，其中主要包括三方面内容：1、实验设计：实验采用的实现方法和依据（如描述语言的文法及其机内表示，词分析 的单词分类码表、状态转换图或状态矩阵等，语法分析中用到的分析表或优先矩阵等，语法制导翻译中文法的拆分和语义动作的设计编写等）；具体的设计结果（应包括整体设计思想和实现算法，程序结构的描述，各部分主要功能的说明，法以及所用数据结构的介绍等）。 2、程序代码：实验实现的源程序清单，要求符合一般的程序书写风格，有详细的注释。 3、实验结果分析：自行编写若干源程序作为测试用例，对所生成的编译程序进行测试 （编译程序的输入与输出以文件的形式给出）；运行结果分析（至少包括一个正确和一个错误单词或语句的运行结果）；以及改进设想等。 注意事项 1、电子版实验报告和源程序在最后一次机时后的一周内上交。（每个同学上交一个压 缩文件，其命名格式为“学号_姓名.rar”，内含实验报告和一个命名为“源程序” 的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序，并应有相应的注释、运行环境和使用方法简介。） 2、不接受不完整的实验报告和没有说明注释的源程序，或者说明与程序、运行结果不 符合的作业。 特别鼓励：扩展题目 1、为亲身经历一个小型编译器的开发全过程，触摸一下与实际编译器开发相关的工作， 大家可以自由组成3人左右的小组，推举组长，模拟一个团队分工协作开发大型软件的实战环境，融入软件工程的思想规范和一般理论方法，初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务，完成相应的分析设计员、程序员和测试员等角色的工作，并以小组为单位提交一份实验报告和源程序，在报告封面上写明每个同学主要完成和负责的部分。 2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验，对于 选定的适当规模的文法（如C语言的一个大小适宜的子集），进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始，到中间代码生成的完整的编译器前端的开发，使所涉及到的编译系统的各个组成模块有机地衔接在一起，提交一份完整的实验报告和源程序，并将以下几个方面描述清楚：
《编译原理》课程实验指导书 课程编号： 课程名称：编译原理/Compiler Principles 实验总学时数： 8 适用专业：计算机科学与技术、软件工程 承担实验室：计算机学院计算机科学系中心实验室、计算机技术系中心实验室 一、实验教学的目的与要求 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实习题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验，每个实验的训练重点在于基本的编译技术和方法，而不强调面面俱到；实验的目的是旨在使学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容；培养学生编制算法的能力和编程解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法设计和程序代码的编写；上机时应随带有关的编译原理教材或参考书；要学会程序调试与纠错。 每次实验后要交实验报告，实验报告的内容应包括： （1）实验题目、班级、学号、姓名、完成日期； （2）简要的需求分析与概要设计； （3）详细的算法描述； （4）源程序清单； （5）给出软件的测试方法和测试结果； （6）实验的评价、收获与体会。 开发工具： （1）DOS环境下使用Turbo C； （2）Windows环境下使用Visual C++ 。 考核： 实验成绩占编译原理课程结业成绩的10%。 三、单项实验的内容和要求： 要求每个实验保证每个学生一台微机。 实验一（4学时）：单词的词法分析程序设计。 （一）目的与要求 1．目的 通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
编译原理程序设计实验报告 ——表达式语法分析器的设计班级：计算机1306班姓名：张涛学号：20133967 实验目标：用LL（1）分析法设计实现表达式语法分析器 实验内容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; //当前单词 char operate[4]={'+','-','*','/'}; //运算符 char bound[2]={'(',')'}; //界符 struct Token { int code; char ch[10]; }; //Token定义
struct Token tokenlist[50]; //Token数组 struct Token tokentemp; //临时Token变量struct Stack //分析栈定义 { char *base; char *top; int stacksize; }; ⑶分析表及流程图
Begin PUSH(#),PUSH(E) POP(x) x ∈VT x ∈VN x=w end W=#n y NEXT(w) y n err 查LL （1）分析表空？ n PUSH （i ）err n y 逆序压栈 ⑷关键函数： int IsLetter(char ch) //判断ch 是否为字母 int IsDigit(char ch) //判断ch 是否为数字 int Iskey(char *string) //判断是否为关键字 int Isbound(char ch) //判断是否为界符 int Isboundnum(char ch) //给出界符所在token 值 int init(STack *s) //栈初始化 int pop(STack *s,char *ch) //弹栈操作 int push(STack *s,char ch) //压栈操作 void LL1(); //分析函数 源程序代码：（加入注释）
《编译原理》实验报告软件131 陈万全132852
一、需求分析 通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。 通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。 1、词法分析程序设计与实现 假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。 输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 2、语法分析程序设计与实现 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的
一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 3、语义分析程序设计与实现 对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 输入：包含测试用例（由标识符、无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。 若源程序中有错误，应指出错误信息 二、设计思路 1、词法分析程序设计与实现 1)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。
集美大学计算机工程学院实验报告 课程名称：编译原理班级： 指导教师：： 实验项目编号：实验一学号： 实验项目名称：词法分析器的设计实验成绩： 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器，从输入的源程序（编写的语言为C语言的一个子集）中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 三、实验要求 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符 2 别单词的类型，将标识符和常量分别插入到相应的符号表中，增加错误处理等。 3、编程语言不限。
四、实验设计方案 1、数据字典 本实验用到的数据字典如下表所示：
3、实验程序 #include
编译原理实验指导书 主编：徐静李娜 信息与电气工程学院 2010年3月
概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节──词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。 二、实验方法 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容： 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会
实验一词法分析 一、实验目的： （1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。 （2）加深对有穷自动机模型的理解。 （3）掌握词法分析程序的实现方法和技术。 （4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法
大学学生实验报告 开课学院及实验室：年月日 实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 针对表达各类词语的一组正规表达式，设计一个确定化的最简的有限自动机，对输入的符号串进行单词划分及词类识别。 实验容 将词法分析器分解为以下几个部分： 1.正规表达式的解析：将正规表达式中的符号分解为常量字符、正规表达 式标识符和正规表达式运算符，然后基于正规表达式运算将正规表达式 分解为更小的正规表达式（通过正规表达式运算符进行串接）。 2.正规表达式到NFA的转换：根据转换规则，基于正规表达式运算，将正 规表达式转换为非确定有限自动机，并确定各类词的终止状态。
3.NFA的确定化：通过计算各状态的传递闭包，将NFA确定化，并确定 各类词的终止状态。 4.最小化：通过子集法，求得最简的确定有限自动机，并确定各类词的终 止状态。 例如：分析C语言子集的词法 1）关键字 main if else int return void while （都是小写）2）专用符号 = + —* / < <= < >= = = != ；：，{ } [ ] ( ) 3）其他模式（正规表达式） STRING::=" [^"]* ID::=letter(letter|digit)* INT::=digit digit* letter::= a|…|z|A|…|Z digit::= 0|…|9 4）空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。 部分单词符号对应的种别码
词法分析程序的功能 输入：所给文法的源程序字符串 输出：二元组（syn, token或sum）构成的序列。其中syn 为单词种别码；token 为存放的单词自身字符串；sum为整型常量（作为常量的值）。实现时，可将单词的二元组用结构进行处理 代码： #include
编译原理 实 验 指 导 书
前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。
实验时间：200 年月日实验小组：第组 组长：组员： 组员： 指导教师签名：实验情况评定： 实验二编写一个简单的FLEX脚本并编译运行 实验目的: 通过实验掌握下列知识: 1、进一步熟悉Visual C++的基本操作； 2、进一步熟悉Visual C++ 6.0里Win32 Console Application工程的建立和相应的编程知识； 3、了解如何建立和编译Flex脚本文件； 5、了解如何通过Visual C++ 6.0编译Flex程序； 内容及步骤: 一、输入一个Flex脚本，编译并运行: 1、按实验一介绍的方法，建立一个Win32 Console Application并选择“An empty project”； 2、从选课系统里下载“Flex源代码及编译系统”； 3、将下载的RAR文件解压到D盘的某个文件夹，然后将解压的所有文件复制到D盘的文件夹“D:\Flex”里； 4、打开“附件->记事本”，输入以下代码，并以文件名“DEMO1.L”保存到文件夹“D:\Flex”里： %{ #include
return 0; } 5、点击桌面左下角并运行“开始->程序->附件->命令提示符”； 6、在DOS窗口中输入命令(1)D: (2)cd \Flex(与你存储Flex文件的文件夹名有关) (3)flex DEMO1.L； 7、将D:Flex文件夹下的文件“emalloc.c”、“hash.c”、“LEXYY.C”、“libyywra.c”、“hash.h”、“types.h”和“DEMO1.L”全部复制到你的工程文件夹下； 8、运行VC并调入你建立的工程文件，然后点击左边的FileView，分别用鼠标右键点击Source Files和Header Files，并选择“Add Files to Folder”添加7步复制的c文件和h文件： 图1 9、在第8步添加的文件如下： 图2 10、点击“编译”菜单里的“重建全部”,或者点工具栏上的“!”运行； 注：Flex程序在DOS窗口里运行，词法分析程序是通过键盘输入文本信息，文本信息输入结束时，先按回车，再按Ctrl+Z即可结束文本输入； 实验报告要求: 1、记录错误信息、错误数量和警告数量，以及运行结果； 2、记录Flex脚本文件；
实验2 词法分析程序的设计 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 | (（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*) 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < = ( ) ； 关键字if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 五、实验步骤 1、根据正规式，画出状态转换图；
《编译原理》实验报告 班级：计C104 姓名：李云霄 学号：108490
实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。 输入：由无符号数和+，－，*，/, ( , ) 构成的算术表达式，如1.5E+2－100。 输出：对识别出的每一单词均单行输出其类别码（无符号数的值暂不要求计算）。 三、实现方法与环境 1、首先设计识别各类单词的状态转换图。 描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0，1，2，…，6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。 图1 文法G[<无符号数>]的状态转换图 其中编号0，1，2，…，6代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。 在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。 四则运算算术符号的识别很简单，直接在状态图的0状态分别引出相应标记的矢