编译原理实验报告

课程名：编译原理实验

任课教师：葛林

姓名：甘言海

学号：020332010027

院系：信息科学与工程学院

专业年级：2010级计算机信息保密

实验一

Cygwin环境的熟悉和lex的使用1

一、 实验目的

熟悉cygwin环境的使用，学习使用lex写简单的词法分析程序，会在cygwin环境下使用flex调试lex写的程序。

二、 实验内容

读懂exam1.l和exam2.l两个例子，使用cygwin下的flex工具将exam1.l和exam2.l编译并调试通过。并且修改exam2.l，在其基础上增加如下记号：

? 左右大小括号：{ } ( )

? 将关系算符改写成C中的形式 ? 分号、赋值号：; = ? 关键字：if else

? 双斜线表示的注释：// ? 算术运算符号：+ - * /

? 将标识符改为可含有下划线，并且可以以下划线开头 ? 将注释内容忽略

三、 实验结果与心得

1. 了解和掌握了flex词法分析器生成工具的使用，lex的语法规则和组织方

式。熟悉了cygwin环境的使用，并能在cygwin下使用flex调试lex程序，利用gcc编译生成的lex.yy.c文件。 2. 在lex定义段使用递归方式的正规定义，简洁有效。

3. 状态的定义和使用，有时候通过状态可有效的解决一些复杂问题，比如

对注释的操作等。不同的状态之间可以使用“BEGIN”进行切换，在不同的状态中对同一正规式表示的句子可以执行不同的动作。 4. 有时候动作可以是一个空语句，这时候相当于过滤掉某些输入。 5. 动作中有返回语句时，返回值应当事先在定义段的第一部分用C语言的

语法进行定义，以便于后面的操作和使用。 6. 在词法规则段，lex总是尽可能匹配较长的句子。当发生冲突时，在词法

规则段中首先出现的正规式将被匹配。 7. 掌握了一些具体的lex元字符的使用方法，可以简化正规定义。 8. 当想要将元字符作为正文字符使用时，可以使用转义字符\\或””。 9. 熟悉了yyin、yyout、yyleng、yytext、yylex()、yywrap()等常用变量和函数

的具体意义和使用方法。

10. 理解了用C语言写的辅助函数对于词法分析的重要作用。这些辅助函数

一方面可以作为语义动作的一部分，另一方面可以为词法分析提供依据。而且可以将main函数作为辅助函数放在这里，当单独使用词法分析器的时候可以在main函数里实现对词法分析器的调度和使用。

实验二

Cygwin环境的熟悉和lex的使用2

一、 实验目的

熟悉cygwin环境的使用，学习使用lex写简单的词法分析程序，会在cygwin环境下使用flex调试lex写的程序。

二、 实验内容

在实验1所改写的程序的基础上增加string记号。string是字符串，如果”出现在字符串中，则必须转义，写成\\”形式；如果\\出现在字符串中，也必须转义，写成\\\\形式。

三、 实验结果与心得

1. 由于字符串以”开始，以”结束，且中间可以包含转义字符\\”，所以不能

简单的将两个引号之间的部分识别为字符串，因为最后一个引号可能是\\”的形式，这将构成一个词法错误。所以有必要设置一个状态用以标志一个字符串即将产生。 2. 由于字符串中不允许含有换行、\\和”，但是可以含有\\\\和\\”，所以可以用

一个正规式来标志\\\\和\\”，比如 example (\\\\\\\\)|(\\\\\\”)。然后再定义一个能匹配除换行、\\和”之外的所有可打印字符的正规式，定义字符串为这两种句子混合组成的所有句子。空格、制表符以及其他转义字符都可放入example的定义中，也可专门用一个正规式来匹配他们，并把该正规式纳入字符串的定义中。 3. 当输入遇到一个”时就进入字符串状态，再遇到一个单独的”就重新进入

初始状态。如果分析器一直处于字符串状态直至输入结束，调用yywrap()返回1，词法分析结束，这时候其实是输入出现了错误。为了检测出这个错误应当在字符串返回的时候检查输入的下一个字符是不是”，如果不是就说明输入出现了词法错误，进行相应的错误处理。对于串中出现了\\或换行的情况，这种方法同样能够检测到词法错误。 4. 如果要求在扫描输入的时候把字符串中的转义字符转变为实际意义，则

需要分开扫描，在分析器进入字符串状态后用不同的正规式来匹配普通字符构成的串和转义字符，并把转义字符转义成其实际代表的字符。这时候由于涉及到字符串操作，需要设置缓存区并用作全局变量。 5. 对于空字符串如果想要产生一个返回值，则需要特殊处理。因为进入字

符串状态后，接着识别一个”就重新返回初始状态。可以设置正规式\\”\\”用来专门识别空字符串，然后在动作中返回一个值用以标志这是一个空字符串。

实验三

词法分析的各类用途1

一、 实验目的

通过实验使学生明白词法分析的作用不仅仅在于写词法分析器，它还有很多其他用途。

二、 实验内容

写一个lex程序，它读入一个文件，将该文件中的所有的单独或连续的一段空白（包括一个或多个空格、制表、换行组成的空白）都替换成一个空格。

三、 实验结果与心得

1. 回顾和熟练了文件的简单操作。

2. 词法分析不仅仅能够用来写词法分析器，而且可以实现输入文件的格式

转换，字符串替换等其他操作。

3. 对空白的识别较为简单，设置一个正规式即可。

4. 每次识别一串空白后就将一个空格写入输出文件，识别到其他内容就原

样写入输出文件，因此应有能够区分空白和其他字符串的正规式，以下是其正规定义：

delim ws

[ \\t \\n]

normal[^ \\t \\n]+

{delim}+

5. 实验结果，输出文件将输入文件中所有的空白串都替换为了一个空格，

其他内容未作修改。

实验四

词法分析的各类用途2

一、 实验目的

通过实验使学生明白词法分析的作用不仅仅在于写词法分析器，它还有很多其他用途。

二、 实验内容

写一个lex程序，它读入一个c语言文件，将其中所有的float关键字都替换成double关键字。

三、 实验结果与心得

1. 可以利用词法分析对源程序文件进行修改，比如关键字的替换等。 2. 由于只有两侧均为空白的“float”串才能被替换为“double”串，其他

的字符串不应该被修改或替换，例如形如“ffloat”的字符串应该作为一个ID或其他内容处理，而不因该被修改为“fdouble”。所以为了区分“float”关键字和其他字符串，应设置三个不同的正规式，其中一个用来表示空白，另一个用来表示其他字符串。以下是其正规定义：

delim ws id

[ \\t \\n] {delim}+ [^ \\t\\n]+

3. 由于所有的关键字或ID都由空白隔开，所以上述正规定义完全可以用来

区分“float”关键字和其他字符串，因为lex总是尽可能匹配较长的字符串，所以形如“ffloat”的串不会被修改。

4. 在词法规则段，每当识别到一个“float”关键字就向输出文件中写入一

个“double”串，识别到空白或其他字符串就原样写入输出文件。

5. 实验结果，输出文件将输入文件中所有的“float”关键字都替换为了

“double”，其他内容未作修改。

实验五

验证Yacc的使用

一、 实验目的

熟悉语法分析器生成工具Yacc的使用，并学会在cygwin下使用bison工具编译Yacc文法说明文件。学习如何使用lex和yacc合作进行语法分析。

二、 实验内容

根据给出的calculator例子（calculator0,calculator1,calculator2,calculator3）完成下面题目：用lex和yacc写一个计算布尔表达式真值的计算器。

三、 实验结果与心得

1. 将lex与yacc结合使用，需要处理好两者之间的衔接问题，首先所有终

结符都在文法说明文件中定义，lex文件中在定义段的第一部分要使用“#include “cal.tab.h””将bison生成的包含各种数据定义的头文件包含进来，这里面含有各种终结符的符号定义和全局变量的定义。lex文件词法规则段中匹配正规式的动作的返回值符号要与文法说明文件中的定义一致，否则将发生无法识别的错误。

2. 通过在文法说明文件语法规则段中相应产生式的语义动作里计算综合属

性来一步步得出布尔表达式的真值。将所有终结符与非终结符的属性值类型都定义为char类型，在文法说明文件定义段的第一部分添加“#YYTYPE char”语句即可。

3. 词法分析器在返回一个记号之前先要为其指定属性值，使用全局变量

yylval给属性赋值。

4. 在二义文法中，通过指定运算符的优先级来避免冲突，定义如下：

%token TRUE FALSE LPAREN RPAREN ENTER %left OR %left AND %right NOT

在指定运算符的优先级之后，语法分析可以正常进行，有效解决了语法分析的移进-归约冲突，并可保证分析结果的正确性。二义文法的语法规则如下：

prog :progexpln

| expln ;

: expr ENTER {printf(\value of the expression is %s.\\n\($1?

;

expln

\

expr :expr OR expr {$$ = $1 || $3;}

| expr AND expr {$$ = $1 && $3;} |

NOT expr {$$ = !$2;}

|LPAREN expr RPAREN {$$ = $2;} | TRUE | FALSE ;

5. 可以将文法改造成无二义的，改造后的语法规则如下：

prog :progexpln

| expln ;

: expr ENTER {printf(\value of the expression is %s.\\n\($1?

;

expln

\

expr :expr OR term {$$ = $1 || $3;}

|term; ; |factor; ;

| LPAREN expr RPAREN {$$ = $2;} | TRUE | FALSE ;

{$$ = $1;} {$$ = $1;}

term : term AND factor {$$ = $1 && $3;}

factor : NOT factor {$$ = !$2;}

改造成的无二义的文法依然能够完成计算布尔表达式真值的工作，和前

面使用带优先级的二义文法的效果相同。两者比较来看，带优先级的二义文法的书写更加简便一些，只需为相应的运算符指定优先级就可以了。而改造后的无二义的文法结构更加清晰，容易理解。