编译原理实验报告一

时间：2020-07-20 11:45:05 来源：蒲公英阅读网 本文已影响人

相关热词搜索：编译 原理 实验

　实验一

　词法分析程序实现 一、实验目的与要求

　通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符流形式的源程序转化为一个由各类单词符号组成的流的词法分析方法

　二、实验内容

　基本实验：

　题目：若某一程序设计语言中的单词包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码参见表 I）。

　表 表 I

　 语言中的各类单词符号及其分类码表

　单词符号

　类别编码

　类别码的助记符

　单词值

　begin

　1

　BEGIN

　 end

　2

　END

　 if

　3

　IF

　 then

　4

　THEN

　 else

　5

　ELSE

　 标识符

　6

　ID

　字母打头的字母数字串

　无符号常数

　7

　UCON

　机内二进制表示

　<

　8

　LT

　<=

　9

　LE

　 =

　10

　EQ

　 <>

　11

　NE

　 >

　12

　GT

　 >=

　13

　GE

　 :=

　14

　IS

　 +

　15

　PL

　 -

　16

　MI

　 *

　17

　MU

　 /

　18

　DI

　 ：

　输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。

　输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE 字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的 CLASS 字段上放置相应单词的类别码的助记符，VALUE 字段则为“空”。

　三、实现方法与环境

　词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词

　法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用 C 语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国 BELL 实验室研制的 LEX 就是一个被广泛使用的词法分析程序的自动生成工具。

　：

　处理过程简述：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移时所需执行的语义动作，就可以据此构造词法分析程序了。

　为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标

　识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。

　采用上述策略后，针对表 I 中的部分单词可以参考教材 P80 的图 3-22（见图 1）

　 图 图 1 1

　识别表 I I 所列语言中的部分单词的 A DFA 及相关的语义过程

　 图 图 1 1 中所出现的语义变量及语义函数的含义和功能说明如下：

　函数 GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量 ch，然后把扫描指示器前推一个字符位置。

　字符数组 TOKEN：用来依次存放一个单词词文中的各个字符。

　函数 CAT：每调用一次，就把当前 ch 中的字符拼接于 TOKEN 中所存字符串的右边。

　函数 LOOKUP：每调用一次，就以 TOKEN 中的字符串查保留字表，若

　查到，就将相应关键字的类别码赋给整型变量 c；否则将 c 置为零。

　函数 RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。

　函数 OUT：一般仅在进入终态时调用此函数，调用的形式为 OUT(c，VAL)。其中，实参 c 为相应单词的类别码助记符；实参 VAL 为 TOKEN（即词文）或为空串。函数 OUT 的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

　 总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用 LEX 等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。

　四．源程序

　#include <stdio.h>

　#include <ctype.h>

　#include <string.h>

　#include <math.h>

　 #define ID 6

　#define INT 7

　#define LT 8

　#define LE 9

　#define EQ 10

　#define NE 11

　#define GT 12

　#define GE 13

　#define IS 14

　#define PL 15

　#define MI 16

　#define MU 17

　#define DI 18

　#define MAX_KEY_NUMBER 20//关键字的数量

　#define KEY_WORD_END "waiting for your expanding"

　//关键字结束标记

　char *KeyWordTable[MAX_KEY_NUMBER]={"begin","end", "if", "then", "else", KEY_WORD_END};

　char TOKEN[20]="";

　char ch=" ";//用于存储带判断的字符

　int row=1;//row 标识错误在第几行

　 #define DIGIT 1

　#define POINT 2

　#define OTHER 3

　#define POWER 4

　#define PLUS 5

　#define MINUS 6

　#define UCON 7

　//假设无符号常量的类数是 7

　#define ClassOther 200

　#define EndState -1

　int index=0;//保存已读的字符串的索引

　int w,n,p,e,d;

　int Class;

　//用于表示类的词

　int ICON;

　float FCON;

　static int CurrentState;

　//用于目前的当前状态,初始值:0

　int EXCUTE (int state, int symbol,FILE *fp,char JudgeStr[],int row,int index);

　int GetChar (char ch);

　int HandleError (char StrJudge[],int row);

　 ///////////////////查保留字表，判断是否为关键字

　int lookup (char *token)

　{

　 int n=0;

　 while (strcmp(KeyWordTable[n], KEY_WORD_END)) //strcmp 比

　较两串是否相同，若相同返回 0

　 {

　if (!strcmp(KeyWordTable[n], token)) //比较 token 所指向的关键字和保留字表中哪个关键字相符

　{

　 return n+1; //根据单词分类码表 I，设置正确的关键字类别码，并返回此类别码的值

　 break;

　}

　n++;

　 }

　 return 6; //单词不是关键字，而是标识符

　}

　///////////////////输出分析结果

　void out (int i, char* pStr)

　{

　 char Mnemonic[5];

　 if(1==i)

　 {

　strcpy(Mnemonic,"BEGIN");

　 }

　 else if(2==i)

　 {

　strcpy(Mnemonic,"END");

　 }

　 else if(3==i)

　 {

　strcpy(Mnemonic,"IF");

　 }

　 else if(4==i)

　 {

　strcpy(Mnemonic,"THEN");

　 }

　 else if(5==i)

　 {

　strcpy(Mnemonic,"ELSE");

　 }

　 else if(6==i)

　 {

　strcpy(Mnemonic,"ID");

　 }

　 else if(7==i)

　 {

　strcpy(Mnemonic,"INT");

　 }

　 else if(8==i)

　 {

　strcpy(Mnemonic,"LT");

　 }

　 else if(9==i)

　 {

　strcpy(Mnemonic,"LE");

　 }

　 else if(10==i)

　 {

　strcpy(Mnemonic,"EQ");

　 }

　 else if(11==i)

　 {

　strcpy(Mnemonic,"NE");

　 }

　 else if(12==i)

　 {

　strcpy(Mnemonic,"GT");

　 }

　 else if(13==i)

　 {

　strcpy(Mnemonic,"GE");

　 }

　 else if(14==i)

　 {

　strcpy(Mnemonic,"IS");

　 }

　 else if(15==i)

　 {

　strcpy(Mnemonic,"PL");

　 }

　 else if(16==i)

　 {

　strcpy(Mnemonic,"MI");

　 }

　 else if(17==i)

　 {

　strcpy(Mnemonic,"MU");

　 }

　 else if(18==i)

　 {

　strcpy(Mnemonic,"DI");

　 }

　 else

　 {

　strcpy(Mnemonic,"Unkown Type");

　 }

　 printf("(%s

　)对应 %s\n",Mnemonic,pStr);

　}

　///////////////////报错

　void report_error (int row)

　{

　 printf("%s

　Error! In the %d row\n",TOKEN,row);

　}

　///////////////////扫描程序

　void scanner(FILE *fp)//总的判断函数开始就应该判断已读取的字符是否为空字符，不为则不用再读，直接进行判断，否则再读

　{

　 int i, c;

　 fseek(fp,-1,1);//首先回溯一个字符，就是将文件所有的字符都在 scanner 内部判断，外部 while 循环不会浪费任何字符

　 ch=fgetc (fp);//scanner 中要想判断字符，必须开头先读一个字符

　 while(" "==ch||"\n"==ch||"\t"==ch)//将文件中的所有空字符浪费在这里

　 {

　if("\n"==ch)

　{

　 row++;

　}

　ch=fgetc (fp);

　 }

　if(EOF==ch)

　 {

　return;

　 }//必须在这里判断一下

　 if (isalpha (ch))

　/*it must be a identifer!*/

　 {

　TOKEN[0]=ch; ch=fgetc (fp); i=1;

　while (isalnum (ch))

　{

　 TOKEN[i]=ch; i++;

　 ch=fgetc (fp);

　}

　TOKEN[i]= "\0";

　fseek(fp,-1,1);

　/* retract*/

　c=lookup (TOKEN);

　if (c!=6) out (c,TOKEN); else out (c,TOKEN);

　 }

　 else if(isdigit(ch)|| "."==ch)

　 {

　fseek (fp,-1,1);//首先回溯一个字符，下面为了循环内部使用先读字符后判断的格式。

　int Type;

　 CurrentState=0;

　i=0;

　do

　{

　 ch=fgetc(fp);

　 TOKEN[i]=ch;

　 i++;

　 TOKEN[i]="\0";//为随时输出字符串做准备

　 Type=GetChar(ch);

　 EXCUTE (CurrentState,Type,fp,TOKEN,row,i);

　}while(CurrentState!=EndState);

　 }

　 else

　 switch(ch)

　 {

　case "<": ch=fgetc(fp);

　 if(ch=="=")out(LE,"<=");

　 else if(ch==">") out (NE,"<>");

　 else

　 {

　fseek (fp,-1,1);

　out (LT,"<");

　 }

　break;

　case "=":

　 {

　ch=fgetc(fp);

　if("="==ch)

　{

　 out(EQ, "==");

　}

　else

　{

　 fseek (fp,-1,1);

　 out(IS, "=");

　}

　 }

　break;

　case ">": ch=fgetc(fp);

　 if(ch=="=")out(GE,">=");

　 else

　 {

　fseek(fp,-1,1);

　out(GT,">");

　 }

　break;

　case "+":

　 {

　out(PL,"+");

　 }

　 break;

　case "-":

　 {

　out(MI,"-");

　 }

　 break;

　case "*":

　 {

　out(MU,"*");

　 }

　 break;

　case "/":

　 {

　out(DI,"/");

　 }

　 break;

　 default: report_error(row); break;

　 }

　 return;

　}

　///////////////////判断矩阵执行程序

　int EXCUTE (int state, int symbol,FILE *fp,char JudgeStr[],int row,int index)//row 用于指示出错的行数，index 用于为待输出的字符串赋结束符‘\0’时用

　 {

　 switch (state)

　 {

　 case 0:switch (symbol)

　 {

　case DIGIT:

　n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;

　case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;

　default:

　 {

　Class=ClassOther;

　CurrentState=EndState;

　printf("无符号数的第一个字符是非法的！\n");

　 }

　 }

　 break;

　case 1:switch (symbol)

　 {

　case DIGIT: w=w*10+d;break;

　//CurrentState=1

　case POINT: CurrentState=2;break;

　case POWER: CurrentState=4;break;

　default:

　 {

　if (ch!=EOF)//如果是因为读到文件结束字符而终止识别，就不应该回退，否则可能造成死循环

　{

　 fseek(fp,-1,1);//遇到其他的字符，可能是一条语句中的其他字符，需后退，因为主函数外层循环每次都要读一个字符进行判断，而这个判读不回溯，所以在内部把这个多读的字符回溯

　}

　ICON=w;CurrentState=EndState;

　 JudgeStr[index-1]="\0";

　printf("(UCON,%i)对应 %s\n",ICON,JudgeStr);

　 }break;

　 }

　 break;

　case 2:switch (symbol)

　 {

　case DIGIT: n++;w=w*10+d;break;

　case POWER: CurrentState=4;break;

　default:

　 {

　if (ch!=EOF)

　{

　 fseek(fp,-1,1);

　}

　 FCON=w*pow(10,e*p-n);CurrentState=EndState;

　JudgeStr[index-1]="\0";

　printf("(UCON,%f) 对 应 于 %s\n",FCON,JudgeStr);

　 }

　 }

　 break;

　case 3:switch (symbol)

　 {

　case DIGIT: n++;w=w*10+d;CurrentState=2;break;

　default:

　 {

　HandleError(JudgeStr,row);CurrentState=EndState;//识别无符号数产生错误时，不应该再回溯，应该把造成错误的那个字符算到错误的无符号数字符串中，再向下面识别单词时跳过这个字符，不回溯就能达到这个目的

　 }

　 }

　 break;

　case 4:switch (symbol)

　 {

　case DIGIT: p=p*10+d;CurrentState=6;break;

　case MINUS: e=-1;CurrentState=5;break;

　case PLUS: CurrentState=5;break;

　default:

　 {

　/* if (ch!=EOF)

　{

　 fseek(fp,-1,1);

　}*/

　HandleError(JudgeStr,row);CurrentState=EndState;

　 }

　 }

　 break;

　case 5:switch (symbol)

　 {

　case DIGIT: p=p*10+d;CurrentState=6;break;

　default:

　 {

　HandleError(JudgeStr,row);CurrentState=EndState;//判断一个无符号数的最后一个字符应该都是多余读取的，所以为了防止引起后面再次判断下一无符号数时产生呑字符的现象，都应该回溯一个字符

　 }

　 }

　 break;

　case 6:switch (symbol)

　 {

　case DIGIT:p=p*10+d;break;

　default:

　 {

　if (ch!=EOF)

　{

　 fseek(fp,-1,1);

　}

　FCON=w*pow(10,e*p-n);CurrentState=EndState;

　JudgeStr[index-1]="\0";

　printf("(UCON,%f)对应 %s\n",FCON,JudgeStr);

　 }break;

　 }

　 break;

　 }

　 return CurrentState;

　}

　 ///////////////////无符号数判断过程中的字符类型判断程序

　int GetChar (char ch)

　{

　 if(isdigit(ch)) {d=ch-"0";return DIGIT;}

　 if (ch==".") return POINT;

　 if (ch=="E"||ch=="e") return POWER;

　 if (ch=="+") return PLUS;

　 if (ch=="-") return MINUS;

　 return OTHER;

　}

　///////////////////判断出错报错程序

　int HandleError (char StrJudge[],int row)

　{

　 printf ("Row: %d*****%s Error!\n",row,StrJudge); return 0;

　}

　///////////////////主程序

　int main(int argc, char* argv[])

　{

　FILE *p=fopen("D:\\YWD.txt","r");

　 if(ch=fgetc(p)==EOF)//不管小括号内的判断是否成功，p 指针都会向后移一个位置，判断不成功，ch 中存的字符不变

　 {

　printf("The file is null.\n");

　return 0;

　 }

　 printf("第一个字母是：%c\n",ch);

　 do

　 {

　scanner(p);

　 }while(ch=fgetc(p)!=EOF);

　 fclose(p);

　 return 0;

　}

　 五．测试用例及运行结果分析

　测试用例：begin 8E-5+8*7/1.5

　运 行 结 果 ：