编译原理上机实习 dws@pku.edu.cn

实习题目 利用词法分析程序的自动构造工具LEX构造一个识别C语言的单词的词法分析程序； 利用语法分析程序的自动构造工具Yacc构造一个识别C语言的程序的语法分析程序

LEX简介 YACC简介 实习要求

LEX简介 Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。这些词汇模式（或者常规表达式）在一种特殊的句子结构中定义

一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。

Lex 的常规表达式 常规表达式是一种使用元语言的模式描述。表达式由符号组成。符号一般是字符和数字，但是 Lex 中还有一些具有特殊含义的其他标记。下面两个表格定义了 Lex 中使用的一些标记并给出了几个典型的例子。

A-Z, 0-9, a-z 构成了部分模式的字符和数字。 A-Z, 0-9, a-z  构成了部分模式的字符和数字。  .  匹配任意字符，除了 \n。  -  用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。  [ ]  一个字符集合。匹配括号内的任意 字符。如果第一个字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一个。 

匹配0个或者多个上述的模式。 + 匹配1个或者多个上述模式。 *  匹配0个或者多个上述的模式。  +  匹配1个或者多个上述模式。  ?  匹配0个或1个上述模式。  $  作为模式的最后一个字符匹配一行的结尾。  { }  指出一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。  \  用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。  ^  否定。 

|  表达式间的逻辑或。  "<一些符号>;"  字符的字面含义。元字符具有。  /  向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。  ( )  将一系列常规表达式分组。

常规表达式举例 joke[rs]  匹配 jokes 或 joker。  A{1,2}shis+  匹配 AAshis, Ashis, AAshi, Ashi。  (A[b-e])+  匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 0 个或 1个。 

Lex 中的标记声明类似 C 中的变量名。每个标记都有一个相关的表达式。（下表中给出了标记和表达式的例子。）使用这个表中的例子，我们就可以编一个字数统计的程序了。我们的第一个任务就是说明如何声明标记。

标记声明举例 标记 相关表达式 含义  数字(number) ([0-9])+ 1个或多个数字  字符(chars) [A-Za-z] 任意字符  空格(blank) " " 一个空格  字(word) (chars)+ 1个或多个 chars  变量(variable) (字符)+(数字)*(字符)*(数字)* 

Lex 编程 Lex 编程可以分为三步： 以 Lex 可以理解的格式指定模式相关的动作。  在这一文件上运行 Lex，生成扫描器的 C 代码。  编译和链接 C 代码，生成可执行的扫描器。 

一个 Lex 程序分为三个段：第一段是 C 和 Lex 的全局声明，第二段包括模式（C 代码），第三段是补充的 C 函数。 例如, 第三段中一般都有 main() 函数。这些段以%%来分界。

例：字数统计的 Lex 程序 C 和 Lex 的全局声明 这一段中我们可以增加 C 变量声明。这里我们将为字数统计程序声明一个整型变量，来保存程序统计出来的字数。我们还将进行 Lex 的标记声明。

字数统计程序的声明 %{         int wordCount = 0;         %}         chars [A-za-z\抃'\.\"]         numbers ([0-9])+         delim [" "\n\t]         whitespace {delim}+         words {chars}+         %% 两个百分号标记指出了 Lex 程序中这一段的结束和三段中第二段的开始。

Lex 的模式匹配规则 字数统计程序中的 Lex 规则 {words} { wordCount++; /*         increase the word count by one*/ }         {whitespace} { /* do         nothing*/ }         {numbers} { /* one may         want to add some processing here*/ }         %%

C 代码 Lex 编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。注意这一段必须包括 yywrap() 函数。 Lex 有一套可供使用的函数和变量。 其中之一就是 yywrap。一般来说，yywrap() 的定义如下例。

字数统计程序的 C 代码段 void main()         {         yylex(); /* start the         analysis*/         printf(" No of words:         %d\n", wordCount);         }         int yywrap()         {         return 1;         }

高级 Lex Lex 变量 yyin FILE* 类型。 它指向 lexer 正在解析的当前文件。  yyout FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下，yyin 和 yyout 都指向标准输入和输出。  yytext 匹配模式的文本存储在这一变量中（char*）。  yyleng 给出匹配模式的长度。  yylineno 提供当前的行数信息。（lexer不一定支持。） 

高级 Lex ---Lex 函数 yylex() 这一函数开始分析。 它由 Lex 自动生成。  yywrap() 这一函数在文件（或输入）的末尾调用。如果函数的返回值是1，就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段，这就能够解析多个文件。 方法是使用 yyin 文件指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回 1 来表示解析的结束。  yyless(int n) 这一函数可以用来送回除了前憂? 个字符外的所有读出标记。  yymore() 这一函数告诉 Lexer 将下一个标记附加到当前标记后。 

YACC语言简介 什么是语法 ： 我们看到 Lex 从输入序列中识别标记。如果你在查看标记序列，你可能想在这一序列出现时执行某一动作。这种情况下有效序列的规范称为语法。Yacc 语法文件包括这一语法规范。它还包含了序列匹配时你想要做的事。

以英语为例， 这一套标记可能是：名词, 动词, 形容词等等。为了使用这些标记造一个语法正确的句子，你的结构必须符合一定的规则。一个简单的句子可能是名词+动词或者名词+动词+名词。 所以在我们这里，标记本身来自语言（Lex），并且标记序列允许用 Yacc 来指定这些标记(标记序列也叫语法)。

终端和非终端符号 终端符号: 代表一类在语法结构上等效的标记。 终端符号: 代表一类在语法结构上等效的标记。 终端符号有三种类型： 命名标记: 这些由 %token 标识符来定义。按照惯例，它们都是大写。 字符标记: 字符常量的写法与 C 相同。例如, ?? 就是一个字符标记。 字符串标记 : 写法与 C 的字符串常量相同。例如，"<<" 就是一个字符串标记。 lexer 返回命名标记。

非终端符号: 是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。 在例子中，file 是一个非终端标记而 NAME 是一个终端标记。

用 Yacc 来创建一个编译器包括四个步骤： 编写一个 .y 的语法文件（同时说明 C 在这里要进行的动作）。  编写一个词法分析器来处理输入并将标记传递给解析器。 这可以使用 Lex 来完成。  编写一个函数，通过调用 yyparse() 来开始解析。  编写错误处理例程（如 yyerror()）。  编译 Yacc 生成的代码以及其他相关的源文件。

用 Yacc 编写语法 如同 Lex 一样, 一个 Yacc 程序也用双百分号分为三段。它们是：声明、语法规则和 C 代码。 我们将解析一个格式为 姓名 = 年龄的文件作为例子，来说明语法规则。我们假设文件有多个姓名和年龄，它们以空格分隔。 在看 Yacc 程序的每一段时，我们将为我们的例子编写一个语法文件。

C 与 Yacc 的声明 C 声明可能会定义动作中使用的类型和变量，以及宏。还可以包含头文件。每个 Yacc 声明段声明了终端符号和非终端符号（标记）的名称，还可能描述操作符优先级和针对不同符号的数据类型。 lexer (Lex) 一般返回这些标记。所有这些标记都必须在 Yacc 声明中进行说明。

在文件解析的例子中我们感兴趣的是这些标记：name, equal sign, 和 age。Name 是一个完全由字符组成的值。 Age 是数字。于是声明段就会像这样： 文件解析例子的声明        %         #typedef char* string; /*         to specify token types as char* */         #define YYSTYPE string /*         a Yacc variable which has the value of returned token */         %}         %token NAME EQ AGE         %%

类似 Lex, Yacc 也有一套变量和函数可供用户来进行功能扩展。 YYSTYPE 定义了用来将值从 lexer 拷贝到解析器或者 Yacc 的 yylval （另一个 Yacc 变量）的类型。默认的类型是 int。 由于字符串可以从 lexer 拷贝，类型被重定义为 char*。

Yacc 语法规则 Yacc 语法规则具有以下一般格式：        result: components { /*         action to be taken in C */ }         ; 在这个例子中，result 是规则描述的非终端符号。Components 是根据规则放在一起的不同的终端和非终端符号。 如果匹配特定序列的话 Components 后面可以跟随要执行的动作。

param : NAME EQ NAME {         printf("\tName:%s\tValue(name):%s\n", $1,$3);}             | NAME EQ VALUE{             printf("\tName:%s\tValue(value):%s\n",$1,$3);}         ;

如果上例中序列 NAME EQ NAME 被匹配，将执行相应的 { } 括号中的动作。 这里另一个有用的就是 $1 和 $3 的使用, 它们引用了标记 NAME 和 NAME（或者第二行的 VALUE）的值。

标记 NAME 的 Lex 代码是这样的 char [A-Za-z]         name {char}+         %%         {name} { yylval = strdup(yytext);         return NAME; }

文件解析例子的规则段是这样的： 文件解析的语法        file : record file         | record         ;         record: NAME EQ AGE {         printf("%s is now %s years old!!!", $1, $3);}         ;         %%

附加 C 代码 一个函数如 main() 调用 yyparse() 函数（Yacc 中 Lex 的 yylex() 等效函数）。 一般来说，Yacc 最好提供 yyerror(char msg) 函数的代码。 当解析器遇到错误时调用 yyerror(char msg)。错误消息作为参数来传递。

一个简单的 yyerror( char. ) 可能是这样的： int yyerror(char 一个简单的 yyerror( char* ) 可能是这样的：        int yyerror(char* msg)         {         printf("Error: %s         encountered at line number:%d\n", msg, yylineno);         }

这一段还包括文件解析例子的主函数： 附加 C 代码 void main() { yyparse(); } int yyerror(char 这一段还包括文件解析例子的主函数： 附加 C 代码        void main()         {             yyparse();         }         int yyerror(char* msg)         {         printf("Error: %s         encountered \n", msg);

实习要求 用LEX编写C语言词法分析器 输入：C语言程序 输出：词法分析结果 用YACC编写C语言语法分析器 提交：.c文件和.exe文件 提交时间：最晚考试前提交 ftp上有Pascal的例子

需要的软件 Parser Generator 在ftp上包括这个软件的使用方法和安装文件 VC6或7

C语言 auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while