昆明理工大学信息工程与自动化学院学生实验报告

（ 20## —  20## 学年   第 1 学期 ）

课程名称：编译原理      开课实验室：信自楼机房444      20##年11月20日

一、    实验目的及内容

实验目的：能够采用C编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。

实验内容：实现我们定义的语言的词法分析器。这种语言的程序结构很简单，语法相当于c的函数体，即由一对大括号括起来的语句序列，没有过程或函数。声明语句、表达式语句及控制语句的写法都与c类似，但规定：一条声明语句只能声明一个整型变量，没有数组；控制语句只是if、for和while三个语句，这三个语句本身也可以包含语句序列；表达式仅局限于布尔表达式和整型算术表达式，布尔表达式由对两个算术表达式的比较组成，该比较使用<,>,<=,>=,= =,!=比较运算符；算术表达式可以包括整型常数、变量以及+,－,*,/这四个运算符。另外，还可以有复合语句。用read和write语句实现输入输出。注释用/*和*/括起来，但注释不能嵌套。

二、    实验原理及基本技术路线图（方框原理图或程序流程图）

词法分析器流程图:

三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件。

四、实验方法、步骤（或：程序代码或操作过程）

源代码：

#include <iostream>

#include<string>

using namespace std;

#define  MAX 22         

char ch =' ';

string key[15]={"begin","end","if","then","else","while","write","read",

"do", "call","const","char","until","procedure","repeat"};

int Iskey(string c){         //关键字判断

   int i;

   for(i=0;i<MAX;i++) {

      if(key[i].compare(c)==0) return 1;

       }

    return 0;

}

int IsLetter(char c) {        //判断是否为字母

    if(((c<='z')&&(c>='a'))||((c<='Z')&&(c>='A'))) return 1;

    else return 0;

}

int IsDigit(char c){          //判断是否为数字

     if(c>='0'&&c<='9') return 1;

     else return 0;

}

void analyse(FILE *fpin){

    string arr="";         

    while((ch=fgetc(fpin))!=EOF) {

            arr="";       

         if(ch==' '||ch=='\t'||ch=='\n'){}    

         else if(IsLetter(ch)){

                 while(IsLetter(ch)||IsDigit(ch)) {

                                if((ch<='Z')&&(ch>='A')) ch=ch+32;  

                             arr=arr+ch;

                    ch=fgetc(fpin);

                               }

                 fseek(fpin,-1L,SEEK_CUR);   

                 if (Iskey(arr)){cout<<arr<<"\t$关键字"<<endl;}    

                 else  cout<<arr<<"\t$普通标识符"<<endl;          

               }

     

            else if(IsDigit(ch)){

                  while(IsDigit(ch)||ch=='.'&&IsDigit(fgetc(fpin))){

                        arr=arr+ch;

                        ch=fgetc(fpin);

                       }

                  fseek(fpin,-1L,SEEK_CUR);

                  cout<<arr<<"\t$无符号实数"<<endl; 

             }

       else switch(ch){         

               case'+':

               case'-' :

               case'*' :

               case'=' :

               case'/' :cout<<ch<<"\t$运算符"<<endl;break;

               case'(' :

               case')' :

               case'[' :

               case']' :              

               case';' :

               case'.' :

               case',' :

               case'{' :

               case'}' :cout<<ch<<"\t$界符"<<endl;break;

               case':' :{ch=fgetc(fpin);

                        if(ch=='=') cout<<":="<<"\t$运算符"<<endl;

                        else {cout<<"="<<"\t$运算符"<<endl;;

                               fseek(fpin,-1L,SEEK_CUR);}

                        }break;

case'>' :{ch=fgetc(fpin);

                         if(ch=='=') cout<<">="<<"\t$运算符"<<endl;

                         if(ch=='>')cout<<">>"<<"\t$输入控制符"<<endl;

                         else {cout<<">"<<"\t$运算符"<<endl;

                             fseek(fpin,-1L,SEEK_CUR);}

                         }break;

               case'<' :{ch=fgetc(fpin);

                         if(ch=='=')cout<<"<="<<"\t$运算符"<<endl;

                         else if(ch=='<')cout<<"<<"<<"\t$输出控制符"<<endl;

                         else if(ch=='>') cout<<"<>"<<"\t$运算符"<<endl;

                         else{cout<<"<"<<"\t$运算符"<<endl;

                            fseek(fpin,-1L,SEEK_CUR);}

                        }break;

              default : cout<<ch<<"\t$无法识别字符"<<endl;

        }

    }

}

void main(){

   char in_fn[30];

   FILE * fpin;

   cout<<"请输入源文件名（包括路径和后缀名）:";

   for(;;){

       cin>>in_fn;

       if((fpin=fopen(in_fn,"r"))!=NULL) break;

       else cout<<"文件路径错误！请输入源文件名（包括路径和后缀名）:";

     }

   cout<<"\n********************分析如下*********************"<<endl;

   analyse(fpin);

   fclose(fpin);

}

五、实验过程原始记录( 测试数据、图表、计算等)

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

通过本次实验，我明白了词法分析程序又称扫描器，是编译过程的第一步，是下一步进行语法分析的基础。对程序设计语言来说，单词结构（词法）基本上都可以用3型文法及与之相关的正规表达式来描述；对于单词的识别，所谓的状态转换图或有限自动机则是十分有效的工具。对于一个程序设计语言来说，关键字、 标志符、常数、运算符及分隔符都是单词。它们的单词结构也是用相应文法中的若干个产生式来描述的。通过上机实践不仅加深了我对课程知识的了解，也提高了我的动手能力。

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。

 

第二篇：实验一：词法分析器编制实验

实验一：词法分析器编制实验

一 教学重点与实现的关键技术

1.1词法分析概述

人们理解一篇文章(或解析一个程序)起码是在单词级别上来思考的。同样，编译程序也是在单词的级别上来分析和翻译源程序的。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号（token），把作为字符串的源程序改造成单词符号串的中间程序。因此，词法分析是编译的基础。

执行词法分析的程序称为词法分析器。构造词法分析器的方法分为手工编制和自动生成（如用著名的词法分析器的自动生成工具Lex自动为某种语言的编译构造词法分析器）两种，本实验要求学生利用所学习掌握的知识手工编制一个小型的词法分析器。

1.2词法分析器的设计要求

1.2.1词法分析器的功能和输出形式

词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种。

（1）关键字

是由程序语言定义的具有固定意义的标志符。有时称这些标志符为保留字或基本字。例如，Pascal中的begin，end，if，while都是保留字。这些字通常不用作一般标志符。

（2）标识符

    用来表示各种名字，如变量名、数组名、过程名等等。

（3）常数

    常数的类型一般有整型、实型、布尔型、文字型等等。例如，100，3.14159，TRUE，‘Sample’。

（4）运算符

    如+、-、*、/等等

（5）界符

    如逗号、分号、括号、/*，*/等等。

一个程序语言的关键字、运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用通常都不加什么限制。

词法分析器所输出的单词符号常常表示成如下的二元式：

（单词种别，单词符号的属性值）

    单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎么编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。

    如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。

单词符号的属性是指单词符号的特性或特征。属性值则是反映特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。

在这里，我们给出一种编码方法（以FORTRAN语言为例）：

单词符号编码举例

1.2.2词法分析器作为一个独立子程序

为何将词法分析作为一个独立阶段呢？是否还应该将它安排为独立的一遍呢？

把词法分析安排为一个独立阶段的好处是，它可使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析要简单得多，可用更有效的特殊方法和工具进行处理。

    但是，这并不意味着我们也必须把词法分析作为独立的一遍。当然，也可以把词法分析安排成独立的一遍。让它把整个源程序翻译成一连串的单词符号存放于文件中。待语法分析器进入工作是在对从文件输进的这些单词符号进行分析。这种做法意味着必须在文件中保存整个源程序的内码形式，这似乎是没有必要的。我们可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。这样，把词法分析器安排成一个子程序就比较自然。

1.3 词法分析器的实现技术

在以下的讨论中，我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。

 1.3.1 输入、预处理

    词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作可以直接在这个缓冲区中进行。但在很多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。

对于许多程序语言来说，空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义。对于它们，预处理时可以将其剔掉。

    我们可以设想构造一个预处理子程序来完成预处理功能。每当词法分析器调用它时，它就处理出一串确定长度的输入字符，并将其装进词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样，分析器就可以在此缓冲区中直接进行单词符号的识别，而不必照管其它繁琐事务。

    分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。

   不论扫描缓冲区设的多大都不能保证单词符号不会被他的边界所打断。因此，扫描缓冲区最好使用一个如下所示的一分为二的区域，即著名的双缓冲区设计。具体的操作步骤如下图所示：

 

1.3.2 单词符号的识别：状态转换图

   使用状态转换图是设计词法分析器的一种好途径。转换图是一张有限方向图（有向图）。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连接。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。

举例：对于正规式IDN→letter(letter|digit)*描述的标识符，其状态图如下所示：

1.3.3 利用状态转换图识别单词（Token）的步骤

1. 从初态出发

2. 读入一字符

3. 按当前字符转入下一状态

4. 重复 2,3 直到无法继续转移

注：在遇到读入的字符是Token的分割符时，若当前状态是终止状态，说明读入的字符组成一单词；否则，说明输入不符合词法规则。

1.3.4算法描述

★子程序 scan( )

n       输入：字符流

n       输出：

n            Symbol(Code) :单词种别

n            Attr(value):属性（全局变量）

★数据结构与子例程

n         数据结构

n              ch        当前输入字符

n              token     输入缓冲区(字符数组)

n              symbol    单词种别（子程序的返回值）

n              attr      属性（全局变量）

n        子例程

n              Lookup(token):将 token 存入符号表，返回入口指针

n              isKeyword(token):判别 token是关键字？返回关键字种别或 -1

n              getchar():从输入缓冲区中读入一个字符放入ch

n              isdigit()  isalpha()

★该例的实现算法

1.    getchar()

2.    WHILE ch 是空格                   //跳过空格

2.1       DO getchar();

3.    CASE ch OF

4.      isdigit(ch) :

4.1       ch→token; getchar();

4.2       WHILE isdigit(ch) DO

              ch→token; getchar();

4.3       输入指针回退一个字符；

4.4       将token中的字符串变成数值→attr

4.5       返回 NUM

5.      isalpha(ch) :

5.1       ch→token; getchar();

5.2       WHILE isalpha(ch) OR isdigit(ch)

            DO   ch→token; getchar();

5.3          输入指针回退一个字符;

5.4       key = isKeyword(token);

5.5       IF key≥0 THEN  返回 key

5.6       Lookup(token)→attr;

5.7       返回 IDN

6       ':' : getchar();

6.1       IF ch等于'='  THEN 返回 ASG

6.2       出错处理

7      '+' :  返回 ADD

8      '-' :  返回 SUB

9      '*' :  返回 MUL

10     '/' :  返回 DIV

11     '=' :  返回 EQ

12     '>' :  返回 GT

13     '<' :  返回 LT

14     '(' :  返回 LP

15     ')' :  返回 RP

16     ';' :  返回 SEMI

17    其它 :  出错处理

18    END OF CASE

1.4实现的关键技术提示

     除了前述的双缓冲区设计、识别单词的状态转换图等，符号表的组织与实现也是不容忽视的一项关键技术。但由于学生初次接触编译系统的设计，往往忽略符号表的设计，即使想到了也无从下手。有的学生甚至认为标识符表既是符号表的全部——编译的运行环境只需要（也只能有）一张标识符表。这种理解上的偏差正是由于对符号表的作用（特别是对标识符表的特定用途）理解不够，而多数教科书在这个问题上往往只是给出一些宏观上的引导所至。下面将分别对符号表的作用与具体实现进行阐述。

 1.4.1 符号表的作用

    为了检查语义的正确性和生成代码，编译程序需要知道用户源程序中所使用的各种标识符的属性，这些属性信息常常由编译程序集中起来并存放于一张标识符表或符号表中。

    符号表用于存放程序中出现的有关各种名字的属性信息，以反应名字的语义特征，编译的各阶段均涉及符号表的操作。

    符号表的作用主要有以下几个方面：

1)      收集符号的各种属性。如名字、类型、定义的层次等。

2)      作为语义的合法性检查的依据。如引用时类型是否一致、层次是否得当等。

3)      作为目标代码生成阶段地址分配的依据。如根据符号表中该变量的特性可为其在适当的存储区域分配大小合适的存储空间。

1.4.2 符号表的建立

    符号表一般在编译程序的开始阶段（词法分析或语法分析阶段）就建立了，其内容的填写一般在词法分析、语法分析、语义分析阶段陆续填入，而它的使用与管理则贯穿于整个编译程序工作的各个阶段。

1.4.3 符号表的内容

    符号表的每一项（也称入口）由若干域构成，存放一个符号的所有属性信息。

程序设计语言中的符号一般分为两大部分：固定部分和非固定部分。

（1）固定部分

  符号表固定部分包括符号的名字域和种属域。

（2）非固定部分

   符号表的非固定部分包括符号的各种信息域。

   不同种属的符号有不同的信息域，如简单变量有类型、地址、存储类别、作用域等信息域，数组名可有类型、内情向量地址等信息域，过程名、函数名可有参数个数、参数表地址、入口地址等信息域。

1.4.4 符号表的组织

    符号表的组织直接关系到语义功能的实现和语义处理的时空效率。

  ★符号表的总体组织

    所谓符号表的总体组织就是构造多少张符号表，以及哪些符号放在同一张表中，一般可选以下三种方式之一：

1）将属性完全相同的符号（即同一种属的符号）组织在一起构成一张符号表，从而编译程序将使用多张符号表。优点是每张符号表的属性个数和结构完全相同，每个表项等长、表项中每个栏目均有效，对其中的每个符号的管理方便一致。缺点是编译程序要同时管理多个符号表，管理工作量和复杂度较大。

   2）所有符号都组织在一张符号表中。优点是管理集中，缺点是符号表的结构及相应的表处理较为复杂。

   3）前两种方式的折中，即按符号所具有的属性的相似程度分类组织成若干张表，其优缺点自然也是前两种方式的折中。

以上是关于符号表的一般描述。由于符号表是指存放与管理源程序中出现的各种名字的相关信息的表的总称，对于多趟扫描的编译系统，在具体实现时应包含名字表和标识表（如N.Wirth在其为著名的Tiny Pascal构造的范例编译程序就是这样设计的），名字表，顾名思义，只是用来存放源程序中出现的不同的各种名字（即标识符）的拼法（字符串），而标识符表则是在语义分析阶段随着分析的进程为每个过程体中说明的标识符动态地建立起来，并为语义分析与中间代码生成服务的；显然，同名的出现在不同过程体中的标识符（由于其作用域不同）将分别出现在与该过程体相关的标识符表中，这一点与名字表中的情形是不同的。这也是由于名字表与标识符表中存入的信息是在编译的不同阶段获取的。事实上，在词法分析阶段，并不会涉及到标识符的作用域分析与类型检查等工作,而只需收集源程序中出现的名字信息以及这些名字是否为关键字即可。因此只需要查填名字表。所以，名字表的实现较为简单，可用一字符串型的一维数组来实现。不同的名字在表（数组）中有不同的下标，我们就以名字在表中的下标代表不同的标识符。

当词法分析器析出一个名字时，还不能肯定其就是一个用户定义的标识符，因为它还可能是语言本身的保留字又称关键字，而关键字是不能被用作标识符的。为了在析出一个名字时能高效地判断其是否为关键字，在词法分析阶段要建立一张保留字（关键字）表。可设置一个结构型数组ResWords，其第一个域sp按保留字的长度从短到长的顺序存放保留字的拼法(spelling)，第二个域sy存放相应的内部符号。数组frw是为了加速比较而引入的，它的第i个元素是在保留字表ResWords中长度为i的第一个保留字的下标。

下图以Pascal语言的一个子集的保留字集合来说明设计思想。

二  词法分析器的具体要求

2.1实验目的

基本掌握计算机语言的词法分析器的开发方法。

2.2实验内容

编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析器。

2.3实验要求

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) 返回单词种别（用整数表示），

3) 返回单词属性（不同的属性可以放在不同的全局变量中）。

3编写测试程序，反复调用函数scan( )，输出单词种别和属性。

2.4实验环境

★ PC微机

★ DOS操作系统或Windows操作系统

★ Turbo C程序集成环境或Visual C++ 程序集成环境

2.5 实验步骤

1根据状态图，设计词法分析算法

2采用C语言，设计函数scan( )，实现该算法

3编制测试程序（主函数main）。

4调试程序：输入一组单词，检查输出结果。

2.6 基本测试数据

输入数据例：       0  92+data>  0x3f  00  while

正确结果：这些单词的单词种别及其属性

                     INT10            0

                     INT10            92

       +                   _

                     IDN        data

>                   _

              INT16            63

              INT8              0

              WHILE          _

2.7 实验报告要求

实验报告应包括以下几个部分：

1词法的正规式描述

2变换后的正规文法

3状态图

4词法分析器的数据结构与算法

2.8 思考题

1词法分析能否采用空格来区分单词？

2程序设计中哪些环节影响词法分析的效率？如何提高效率？