编译原理课程设计-词法分析之基于Lex实现词法分析

课 程 设 计 说 明 书

设计题目： 编译原理课程设计

专 业：计算机科学与技术 班级：

设计人：

学 号：

山 东 科 技 大 学

2015年 7 月 12 日

课 程 设 计 任 务 书

学院 信息科学与工程学院 专业 计算机科学与技术 班级 2012-2 姓名 高世军 一、课程设计题目： 编译原理课程设计

二、课程设计主要参考资料

（1）韩太鲁等，编译原理. 石油大学出版社.2007.9 （2） （3） 三、课程设计应解决的主要问题：

（1）词法分析之基于Lex实现词法分析 （2）词法分析之基于文法的实现

（3）语法分析之 LL1分析法实现 （4） 四、课程设计相关附件（如：图纸、软件等）：

（1） vc++6.0 （2） Parser Generator 五、任务发出日期： 2015-7-5 课程设计完成日期： 2015-7-12

指导教师签字： 系主任签字：

指导教师对课程设计的评语

成绩：

指导教师签字：

年 月 日

目录

词法分析之基于Lex实现词法分析 ............................................................................... 3 一、设计目的 .............................................................................................................. 3 二、设计要求 .............................................................................................................. 3 三、设计说明 .............................................................................................................. 3 1. 需求分析 ............................................................................................................. 3 2. 概要设计 ............................................................................................................. 4 3. 详细设计 ............................................................................................................. 6 四、运行结果及分析 .................................................................................................. 8 1. 测试数据 ............................................................................................................. 8 2．测试输出的结果 ................................................................................................ 9 3. 设计与思考 ......................................................................................................... 9 五、总结 ...................................................................................................................... 9 词法分析之基于文法的实现 ........................................................................................ 10 一、设计目的 ............................................................................................................ 10 二、设计要求 ............................................................................................................ 10 三、设计说明 ............................................................................................................ 10 1. 需求分析： ....................................................................................................... 10 2. 概要设计 ........................................................................................................... 11 3. 详细设计 ........................................................................................................... 12 四、运行结果及分析 ................................................................................................ 16 1.测试数据 ............................................................................................................. 16 2.测试输出的结果 ................................................................................................. 17 3.设计和思考 ......................................................................................................... 17 五、总结 .................................................................................................................... 18

语法分析之 LL1分析法实现 ........................................................................................ 19 一、设计目的 ............................................................................................................ 19 二、设计要求 ............................................................................................................ 19 三、设计说明 ............................................................................................................ 20 1. 需求分析： ....................................................................................................... 20 2. 概要设计 ........................................................................................................... 21 3. 详细设计 ........................................................................................................... 22 四、运行结果及分析 ................................................................................................ 23 1.测试数据 ............................................................................................................. 23 2.测试输出的结果 ................................................................................................. 23 3.设计和思考 ......................................................................................................... 23 五、总结 .................................................................................................................... 24

词法分析之基于Lex实现词法分析

一、设计目的

通过编写并上机调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将其分解成各类单词的词法分析方法。

二、设计要求

编制一个读单词过程，从输入的源程序中，识别出各个具有意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。 并依次输出各个单词的内部编码及单词符号自身值。

（遇到错误时可显示“Error”，然后跳过错误部分继续显示）

三、设计说明 1. 需求分析

Lex输入文件由3个部分组成：定义集（definition），规则集（rule）和辅助程序集（auxiliary routine）或用户程序集（user routine）。这三个部分由位于新一行第一列的双百分号分开，因此，Lex输入文件的格式如下

{definitions} %%

{rules} %%

{auxiliary routines} 范围：

识别保留字：if、int、for、while、do、return等保留字类别码为1。

a) 输入及其范围

其他的都识别为标识符；单词类别码为2。 常数为无符号整形数；单词类别码为3。

运算符包括：+、-、*、/、=、>、<、>=、<=、!= ；类别码为4。 分隔符包括：,、;、{、}、(、)； 类别码为5。 错误字符 类别码为 6。

b) 输出形式

（[数字],“单词“）数字代表所识别的单词所属的类型。

c） 程序功能

读取文件中的源程序，然后对源程序分析，输出分析结果。 d） 测试数据

将测试数据写在文本文件中，测试为程序的输入数据。

2. 概要设计

a） 数据类型的定义

//定义集，包括头文件和变量定义 %{

#include #include #include #include

int lineno=1;//定义行号 %}

//定义正则表达式

letter [A-Za-z] //字母 digit [0-9] //数字

id ({letter}|[_])({letter}|{digit}|[_])* //开头为字母的标识符

error_id ({digit})+({letter})+ //开头为数字的错误标识符 num {digit}+ //数字集合 whitespace [ \]+ //空格 enter [\\n]+ //回车

//定义识别规则 %%

b） 主程序流程

c） 模块间的调用关系

3. 详细设计

主体代码部分： %%

//识别关键字 {key}

{printf(\"%d 行 \打印行号

printf(\"%s 关键字\\n\输出关键字 //识别数字 {num}

{printf(\"%d 行 \打印行号

printf(\"%s 数字\\n\输出数字 //识别关系运算符 {guanxi}

{printf(\"%d 行 \打印行号

printf(\"%s 关系运算符\\n\输出关系运算符 //识别关系运算符

{suanshu}

{printf(\"%d 行 \打印行号

printf(\"%s 算术运算符\\n\输出算术运算符 //识别分界符 {fenjie}

{printf(\"%d 行 \打印行号

printf(\"%s 关系运算符\\n\输出分界符 //识别注释符 {zhushi}

{printf(\"%d 行 \打印行号

printf(\"%s 注释符\\n\输出注释符号 //识别标识符

{id}

{printf(\"%d 行 \打印行号

printf(\"%s 标志符号\\n\打印标识符 //识别错误的标识符 {error}

{ printf(\"%d 行 \

printf(\"error: %s\\n\//识别空格

{whitespace} {}//忽略空格 //识别换行

{enter}

{linenum++;}//遇到回车行号自动加1

analyse文件是否为空退出读一个字符字母关键字非关键字，即为标识符继续判断，下一个单词

四、运行结果及分析 1. 测试数据

在test.txt文件中写入如下数据。 void main() { int x;int y;

x = input(); y = intput(); output((x,y));}

2．测试输出的结果

3. 设计与思考

基于lex的词法分析，一个模块定义好了之后，其他模块也就出来了。难点在于正则表达式的设计，每个模块都有定义集，规则集和辅助程序集。而且第一部分用“%{”和“%}”括起来。第一和第三个部分为C语言的代码和函数定义，第二个部分为一些规则。

五、总结

通过本次实验，学会了基于Lex的词法分析器构造方法。在实验过程中，万事开头难，刚开始不知道怎么做，以及不知道如何使用老师给的软件，在仔细分析了需求之后，查找了一些关于Parser Genarator 2软件的使用方法，很快的连接好了VC6.0和Parser Genarator2.然后输入简单的程序对其进行了测试，成功后，给自己 极大地信心继续完成接下来的实验，参考了资料的源程序之后，动手开始写自己的代码，最终一步步实现能够达到要求的程序。经过程序的书写，使我了解了Lex语言。了解了基于LEX语言的词法分析程序构造的重要性，对今后的学习和工作有很大的帮助。

词法分析之基于文法的实现

一、设计目的

通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。

二、设计要求

编制一个读单词过程，从输入的源程序中，识别出各个具有意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。 并依次输出各个单词的内部编码及单词符号自身值。

（遇到错误时可显示“Error”，然后跳过错误部分继续显示）

三、设计说明 1. 需求分析：

a） 输入及其范围

识别保留字：if、int、for、while、do、return、break、continue等；

保留字类别码为1。

其他的都识别为标识符；单词类别码为2。 常数为无符号整形数；单词类别码为3。

运算符包括：+、-、*、/、=、>、<、>=、<=、!= ；类别码为4。 分隔符包括：,、;、{、}、(、)； 类别码为5。 错误字符 类别码为 6。

b） 输出形式

词法分析器的单词符号常常表示成以下的二元式(单词类别码，单词符号的属性值)。本实验中，可采用的是一大类符号一类别码的方式。

c） 程序功能

词法分析器的功能是输入源程序，输出单词符号。

d） 测试数据

测试输入的程序为：

main() {

int a, b; a = 10; b = a + 20;

}

2. 概要设计

a）数据类型的定义

定义三个字符串，用于输入程序单词的匹配。

string Rword[RWD] = {\"if\string Opear[OPEAR] = {\"+\string Separ[SEPAR] = {\

b） 主程序流程

3. 详细设计

void main() {

vector input;

vector::iterator iter;

/*将源代码中的单词从文件中读出按成分存放在input中*/ ifstream myf; string str = \"\";

myf.open(\"test.txt\"); if(myf.fail()) {

cout<<\"error!\"<char ch;

ch = myf.get(); while(!myf.eof())

{

for(int i=0;i < SEPAR;i++)//判断是否为分隔符 {

string temp = \"\"; temp += ch;

if(temp == Separ[i]) {

if(str != \"\") {

input.push_back(str); str = \"\"; }

str = ch;

input.push_back(str); str = \"\"; ch=myf.get(); break; } }

if(ch=='\' || ch == ' ' || ch=='\\n')//判断是否为空格，回车

{

if(str != \"\") {

input.push_back(str); str = \"\"; }

ch=myf.get(); }

else if(ch=='!' || ch=='>' || ch=='<' || ch=='=')//判断是否为运算符 {

if(str != \"\") {

input.push_back(str); str = \"\"; }

str = ch; ch=myf.get(); if(ch == '=') {

str += ch;

input.push_back(str); ch=myf.get(); str = \"\"; } else {

input.push_back(str); } }

else if(ch=='+' || ch=='-' || ch=='*' || ch=='/') {

if(str != \"\") {

input.push_back(str); str = \"\"; }

str += ch;

input.push_back(str); ch=myf.get(); str = \"\"; } else {

str += ch; ch=myf.get(); } }

myf.close(); /*读文件结束*/

/*进行词法分析，并输出*/

for(iter = input.begin();iter != input.end();iter++) {

int sign = 0;

for(int i=0;iif(Rword[i] == *iter) {

cout<<\"(1,\\\"\"<<*iter<<\"\\\")\"<if(sign == 0)//判断是否为运算符 {

for(int i=0;iif(Opear[i] == *iter) {

cout<<\"(4,\\\"\"<<*iter<<\"\\\")\"<if(sign == 0)//判断是否为分隔符 {

for(int i=0;iif(Separ[i] == (*iter)) {

cout<<\"(5,\\\"\"<<*iter<<\"\\\")\"<}

if(sign == 0)//判断是否为无符号型常数或者变量 {

if((*iter)[0]>'0' && (*iter)[0]<='9') cout<<\"(3,\\\"\"<<*iter<<\"\\\")\"<cout<<\"(2,\\\"\"<<*iter<<\"\\\")\"</*判断结束，程序结束*/

四、运行结果及分析 1.测试数据

测试数据为test.txt文件内的数据：

2.测试输出的结果

3.设计和思考

本程序的设计是基于C++实现的词法分析程序，较为方便的使用了迭代器，对open的文件进行循环读取数据、分析、判断之后进行输出。难点在于对思路的整理和理解.

五、总结

经过努力，终于完成了本次实验，在实验中遇到了诸多问题，以及一些

小的细节的实现，实验开始之前，先温习了C++迭代器部分，觉得使用这部分内容来实现本次的作业很适合，然后开始写需求分析，整理思路以及代码的书写。经过不断地调试，代码部分总算完成，但是和理想中的结果还有很大的差距。分析之后，对代码整体上进行了调整，并参考资料，完成了本次的作业。通过本次作业，不仅学到了新的知识，而且对以往的知识进行了回顾，并在编码上提高了一个新的阶段。对今后的学习和工作都有很大的帮助。

语法分析之 LL1分析法实现

一、设计目的

根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

二、设计要求

程序输入/输出示例：

对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下：

(1)输入一以#结束的符号串(包括+—*/（）i#)： (2)输出过程如下：

步骤 分析栈 剩余输入串 所用产生式 1 E i+i*i# E->TG

（3）输入符号串为非法符号串(或者为合法符号串) 注意：

1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.测试用的表达式可以事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；

三、设计说明 1. 需求分析：

a） 输入及其范围

输入为文法，表达式中允许使用运算符（+-*/）、分割符（括号）、字

符i，结束符#。

b） 输出形式

步骤 分析栈 剩余输入串 所用产生式 1 E i+i*i# E->TG

c） 程序功能

根据输入的文法进行分析，利用LL（1）控制程序根据显示栈栈顶内容、

向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程

d） 测试数据

输入字符串i+i*i#作为测试。

2. 概要设计

a）数据类型的定义

char Stack[50];/*分析栈*/

char Left[20];/*剩余输入串*/

char arrZhongjie[20]={'i','+','-','*','/','(',')','#'};

char arrNozhongjie[20]={'E','G','T','S','F'}; b） 主程序流程

3. 详细设计

四、运行结果及分析 1.测试数据

输入字符串：i+i*i#

2.测试输出的结果

3.设计和思考

主要的难点在于对LL（1）的理解部分，消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，然后开始整理思路进行编码阶段。开始要对错误的文法进行分析，并提示详细的错误信息。思考之后实现了表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#。

五、总结

本次课程设计是本周实验来难点最大的一次作业，首先需要温习LL（1）的知识，如何消除左递归，区别二义性文法，以及对文法的分析。在实验的过程中，最重要的还是要理顺思路，想好解决办法，这也是我经过不断实验总结出的自我思考的方法。然后就进入了编码阶段，此次编码也有一定的难度，在代码量以及代码的整体设计上都有了提升，也是最值得思考的地方。最后，通过实验报告的书写，以及参考资料的查找，对今后的学习和工作都有很大的帮助。