编译原理实验：使用C/C++语言编写C-语言的词法分析器

2023-11-17

文章目录

实验目的
实验任务
实验内容
实验步骤
源码

实验目的

学习和掌握词法分析程序手工构造状态图及其代码实现方法。

实验任务

（1）阅读已有编译器的经典词法分析源程序；
（2）用C或C++语言编写一门语言的词法分析器

实验内容

（1）阅读已有编译器的经典词法分析源程序。
选择一个编译器，如：TINY，其它编译器也可（需自备源代码）。阅读词法分析源程序，理解词法分析程序的手工构造方法——状态图代码化。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。TINY语言请参考《编译原理及实践》第2.5节（见压缩包里附带的文档）。
（2）确定今后其他实验中要设计编译器的语言，如TINY语言，又如更复杂的C－语言（其定义在《编译原理及实践》附录A中）。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。
（3）根据该语言的关键词和识别的词法单元以及注释等，确定关键字表，画出所有词法单元和注释对应的DFA图。
（4）仿照前面学习的词法分析器，编写选定语言的词法分析器。
（5）准备2~3个测试用例，要求包含正例和反例，测试编译结果。

实验步骤

分析c-的词法规则

在这里插入图片描述

算法基本思想

Step1 find token：

完整的词法分析器，应该先分清楚记号：在定义某一种语言的时候，会给出其需要使用的记号。Tiny语言的记号分为三类：8个保留字、10个特殊标号、其他记号：数和标识符。

Step2：DFA状态图构建

根据记号，可以构建DFA图，其注意事项如下：
①可以分别为不同种类的符号各自画出DFA图，最后合成一个DFA图；
②对于不同的DFA可能有多个接受状态，其返回值也不同。将多个状态图合并时，同时将接受状态合并为一个最终的接受状态；每个记号可以根据最后一个输入符号的不同，返回不同的词素，用来在最终状态中区分各种词素。
③需要注意语法惯例：如，{}为注释，之间不能有嵌套；最长子串原则；以及后续接识别记号。
④对空白符的处理：制表符、空格、回车被当做空白符处理。其处理过程在初始状态，如果输入的符号为空白符，那么当前状态仍为初始状态。即不将空白符当做一个词法单元处理。
⑤对保留字的处理：不单独为保留字设置DFA状态图，创建枚举类型来保留关键字；读取由字符构成的ID，该ID识别结束后，在枚举类型中查找是否是保留字，如果是保留字，则做特殊处理。
⑥两种获取下一个字符的方式：第一种是直接消耗掉输入符号，如果在识别一个记号的过程中，读到某一个符号就能确定该记号读取完毕，那么该符号是可以被直接消耗掉的；第二种是不消耗输入符号，如果在识别一个记号的过程中，读到某一个输入符号能确定该记号读取完毕，但是该符号并不属于该记号时，该符号不能被消耗。Tiny在区别这两种方式的方法是在DFA中添加[other]边，如果是通过[other]边到达接受符号，那么表示该[other]符号需要被回吐。
构造DFA图：
专用符号的状态转换图：
在这里插入图片描述
我们将由一个符号构成的专用符号：+ - * ; , ( ) [ ] { }合并为一条边，只要在初始状态中当前符号为以上符号，那么直接可以转向接收状态。
由两个符号构成的专用符号：”<=” 、“ >=” 、“ ==” 、“ !=”需要特殊处理。在输入前一个符号后进入一个中转状态（表示已接收到前一个符号），再检测接下来的输入符号。如果输入符号是特殊符号中的第二个符号，表示接受到了由两个符号组成的特殊符号，存储这个特殊符号，跳转到接受状态；如果输入符号为其他符号，那么说明我们接受到了由一个符号构成的特殊符号，需要将当前符号回吐，再跳转到接收状态。
在这里插入图片描述
特殊的符号’/’，该符号同时作为除的表示以及注释的开端，
INNUM、INID状态分别表示以及接受了一个以上的数字或者字母。如果接收到非数字或非字母的数字即跳转到接受状态，并且将最后一个输入的字符回吐。
注释是不会到达接受状态，因为注释不需要做词法分析，读到完整的注释之后返回初始状态即可
注释与除号第一个符号相同，在输入符号为/的情况下，下一个输入符号为时才表示注释开始。如果为其他符号，则表示/为除号。注释结束时，输入符号为，下一个输入符号为/时表示注释结束，下一个输入符号为其他符号时，则表示还在注释中。

Step3：使用while+switch双循环将DFA代码化

词法识别主要用到的函数是getToken，每执行一次，返回一个词法单元。
外层while循环为：当前状态不为接受状态时，每次循环获取一个字符；直到到达接受状态，说明一个词法单元识别完毕。将该词法单元存储，并打印出来。
内层switch循环为：判断当前状态，依据当前输入的符号进行状态的切换，同时选择该符号是否被存储、该字符是否被回吐以及在接受状态下设定当前词法单元的类型。

主程序流程

在这里插入图片描述

各程序模块之间层次关系

getNextChar
每次从文件中读入字符（长度为bufsize）存入缓冲区，每次返回缓冲区中的一个符号；
读取符号位置使用linepos标记，当linepos不小于bufsize的时候即缓冲区中符号读取完毕时，从文件中读取一行字符存入缓冲区，将linepos置为0。如果没有读取成功说明到达文件结尾EOF设置为true。

int getNextChar(void){
  if(!(linepos < bufsize)){/*行缓冲区用完了*/
  行标增加
  从source文件中读取长度为BUFLINE-1的字符串存到行缓冲区符串*/
         If(读取成功)
      将bufsize设置为缓冲区字符长度
  从buf最开始读取
  返回当前字符，并且列号+1
  }
  else{
  没有读取成功，说明文件结束
  }
  }
  else{
  返回当前字符
  }
}

unGetnextChar
如果文件没有结束，那么直接将linepos减去1就可以重新读取该字符以实现回吐的目的。
ReserveLookup
根据getToken返回的字符，在保留字数组中进行查找。如果找到，说明该词素为保留字，返回保留字的类型。否则返回ID表示该词素的类型为ID；
getToken：
使用while+switch方法，每调用一次getToken返回一个词素；每执行一趟while表示一次状态的跳转，其中还包括了对词素的存取等等。

设置开始状态state = START
设置是否存储标记save
While(当前状态不是接受状态)
C = 下一个字符；
save设置为保存
Switch(state){
      Case START:
          根据输入符号，判断跳转状态，C是否被储存、是否回吐
          break;
      Case INLCOM：
          根据输入符号，判断状态跳转，C是否被储存、是否回吐
          break;
       .................
       Case DONE：
       Default:
}
将C加入到词法单元字符串中
if(state == Done){
      获取到了一个词法
      If(currentToken==ID)
          检查词法类型是否为保留字
}
}

5.printToken
为了方便查看测试样例，打印输出每一次识别的词素，根据getToken中返回的词法单元，对每个词法单元进行打印。

主要变量说明

符号	词法类型	符号	词法类型	符号	词法类型
+	PLUS	/	OVER	=	EQ
-	MINUS	<	LT	;	SEMI
*	TIMES	>	GT	,	COMMA
(	LPAREN	)	RPAREN	[	LBRK
]	RBRK	{	LBRACE	}	RBRACE
<=	LTE	>=	GTE	==	EEQ
!=	NEQ	标识符	ID	数字	NUM

总状态图：
在这里插入图片描述

实验结果

在这里插入图片描述

结果分析：
1行为注释，没有被词法分析器分析
3-4行为C-语言的保留字，都被识别
6-10行为C-语言的特殊符号，都被识别
5行为被空格分割的标识符和数字，6行为被空格分割的标识符和标识符，分别被识别。

源码

#include<stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define MAXRESERVED 6 //关键字最大程度 
#define MAXTOKENLEN 40 //标识符最大长度 

/* allocate global variables */
int lineno = 0;
FILE * source; //读入文件 
FILE * listing; //output file 
//FILE * code;
/* allocate and set tracing flags */
int EchoSource = TRUE;
int TraceScan = TRUE;
int TraceParse = FALSE;
int TraceAnalyze = FALSE;
int TraceCode = FALSE;

int Error = FALSE;

typedef enum //枚举类型，保存词素类型
    /* book-keeping tokens */
   {ENDFILE,ERROR,
    /* reserved words */
    IF,ELSE,INT,RETURN,VOID,WHILE,
    /* multicharacter tokens */
    ID,NUM,
    /* special symbols */
    /*[]{} >= <= != == = < > + - * / () ; , */ 
    LBRK,RBRK,LBRACE,RBRACE,GTE,LTE,NEQ,EQ,ASSIGN,LT,GT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI,COMMA
   } TokenType;
   
typedef enum //枚举类型，保存状态
   { START,INRCOM,INLCOM,INCOMMENT,INNUM,INID,DONE,INLTE,INGTE,INEEQ,INNEQ}
   StateType;
char tokenString[MAXTOKENLEN+1]; //保存标识符
#define BUFLEN 256

static char lineBuf[BUFLEN]; /*读取一行字符保存 */
static int linepos = 0; /* 指示缓存中第几个字符 */
static int bufsize = 0; /* 当前缓存中字符串长度 */
static int EOF_flag = FALSE; /* 错误标识 */
static struct //关键字字结构，方便查询 
    { char* str;
      TokenType tok;
    } reservedWords[MAXRESERVED]
   = {{"if",IF},{"int",INT},{"else",ELSE},{"return",RETURN},
      {"void",VOID},{"while",WHILE}};
      
/* getNextChar fetches the next non-blank character
   from lineBuf, reading in a new line if lineBuf is
   exhausted */
static int getNextChar(void)//获取缓存中下一个字符
{ if (!(linepos < bufsize))
  { lineno++;
    if (fgets(lineBuf,BUFLEN-1,source))
    { if (EchoSource) fprintf(listing,"%4d: %s",lineno,lineBuf);
      bufsize = strlen(lineBuf);
      linepos = 0;
      return lineBuf[linepos++];
    }
    else
    { EOF_flag = TRUE;
      return EOF;
    }
  }
  else return lineBuf[linepos++];
}
/* ungetNextChar backtracks one character
   in lineBuf */
static void ungetNextChar(void)//将当前符号回吐
{ if (!EOF_flag) linepos-- ;}

/* lookup an identifier to see if it is a reserved word */
/* uses linear search */
static TokenType reservedLookup (char * s)// 查看标识符是否为关键字
{ int i;
  for (i=0;i<MAXRESERVED;i++)
    if (!strcmp(s,reservedWords[i].str))
      return reservedWords[i].tok;
  return ID;
}
void printToken( TokenType token, const char* tokenString )
{ switch (token)
  { case IF:
    case RETURN:
    case ELSE:
    case VOID:
    case WHILE:
    case INT: 
    	fprintf(listing,
         "reserved word: %s\n",tokenString);
      break;
    case EQ: fprintf(listing,"==\n"); break;
    case COMMA: fprintf(listing,",\n"); break;
    case LBRK: fprintf(listing,"[\n"); break;
    case RBRK: fprintf(listing,"]\n"); break;
    case LBRACE: fprintf(listing,"{\n"); break;
    case RBRACE: fprintf(listing,"}\n"); break;
    case LTE: fprintf(listing,"<=\n"); break;
    case GTE: fprintf(listing,">=\n"); break;
    case LT: fprintf(listing,"<\n"); break;
    case GT: fprintf(listing,">\n"); break;
    case NEQ: fprintf(listing,"!=\n"); break;
    case ASSIGN: fprintf(listing,"=\n"); break;
    case LPAREN: fprintf(listing,"(\n"); break;
    case RPAREN: fprintf(listing,")\n"); break;
    case SEMI: fprintf(listing,";\n"); break;
    case PLUS: fprintf(listing,"+\n"); break;
    case MINUS: fprintf(listing,"-\n"); break;
    case TIMES: fprintf(listing,"*\n"); break;
    case OVER: fprintf(listing,"/\n"); break;
    case ENDFILE: fprintf(listing,"EOF\n"); break;
    case NUM:
      fprintf(listing,
          "NUM, val= %s\n",tokenString);
      break;

    case ID:
      fprintf(listing,
          "ID, name= %s\n",tokenString);
      break;
    case ERROR:
      fprintf(listing,
          "ERROR: %s\n",tokenString);
      break;

    default: /* should never happen */
      fprintf(listing,"Unknown token: %d\n",token);
  }
}
TokenType getToken(void)
{
    int tokenStringIndex=0;
	TokenType currentToken;     // 声明一个当前状态 
	StateType state=START;     // 初始化当前状态为START 
	int save; //是否保存到tokenString 
	while(state!=DONE)
	{
		int c=getNextChar();
		save=TRUE;
		switch(state)
		{
	        case START:{
					if(isdigit(c))
					  state=INNUM;
					else if(isalpha(c))
					  state=INID;
					else if((c==' ') || (c=='\t') || (c=='\n'))
					  save=FALSE;
					else if(c=='=')
					  state=INEEQ;
					else if(c=='<')
						state=INLTE;
					else if(c=='>')
						state=INGTE;
					else if(c=='!')
						state=INNEQ;
					else if(c=='/')
						state=INLCOM;
					else
					{
						state=DONE;
						switch(c)
						{
							case EOF:
								save=FALSE;
								currentToken=ENDFILE;
								break;
							case '+':
								currentToken=PLUS;
								break;
							case '-':
								currentToken=MINUS;
								break;
							case '*':
								currentToken=TIMES;
								break;
							case '(':
								currentToken=LPAREN;
								break;
							case ')':
								currentToken=RPAREN;
								break;
							case '[':
								currentToken=LBRK;
								break;
							case ']':
								currentToken=RBRK;
								break;
							case '{':
								currentToken=LBRACE;
								break;
							case '}':
								currentToken=RBRACE;
								break;
							case ';':
								currentToken=SEMI;
								break;
							case ',':
								currentToken=COMMA;
								break;
							default:
								currentToken=ERROR;
								break;
						}
					}
					break;
			}
			case INLCOM:{
				if(c=='*')
				{
					tokenStringIndex=0;
					save=FALSE;
					state=INCOMMENT;
				}
	
				else if(c==EOF)
				{
					state=DONE;
					currentToken=ENDFILE;
				}
				else
				{
					currentToken=OVER;
					state=DONE;
				}
				break;
			}
			case INCOMMENT:{
				save=FALSE;
				if(c=='*')
					state=INRCOM;
				else if(c==EOF)
				{
					state=DONE;
					currentToken=ENDFILE;
					linepos--;
				}
				break;
			}
			case INRCOM:{
				save=FALSE;
				if(c=='/')
					state=START;
				else if(c==EOF)
				{
					state=DONE;
					currentToken=ENDFILE;
				}
				else 
					state=INCOMMENT;
				break;
	
			}
			case INNUM:{
				if(!isdigit(c))
				{
					ungetNextChar();
					save=FALSE;
					state=DONE;
					currentToken=NUM;
				}
				break;
			}
			case INID:{
				if(!isalpha(c))
				{
					ungetNextChar();
					save =FALSE;
					state=DONE;
					currentToken=ID;
				}
				break;
			}
			case INEEQ:{
				if(c=='=')
				{
					state=DONE;
					currentToken=EQ;
				}
				else
				{
					ungetNextChar();
					save =FALSE;
					state=DONE;
					currentToken=ASSIGN;
				}
				break;
			}
			case INLTE:{
				if(c=='=')
				{
					state=DONE;
					currentToken=LTE;
				}
				else
				{
					ungetNextChar();
					save =FALSE;
					state=DONE;
					currentToken=LT;
				}
				break;
			}
			case INGTE:{
				if(c=='=')
				{
					state=DONE;
					currentToken=GTE;
				}
				else
				{
					ungetNextChar();
					save =FALSE;
					state=DONE;
					currentToken=GT;
				}
				break;
			}
			case INNEQ:{
				if(c=='=')
				{
					state=DONE;
					currentToken=NEQ;
				}
				else
				{
					ungetNextChar();
					save =FALSE;
					state=DONE;
					currentToken=ERROR;
				}
				break;
			}
			case DONE:{
				break;
			}
			default:{
				fprintf(listing,"Scanner Bug:state=%d\n",state);
				state=DONE;
				currentToken=ERROR;
				break;
			}	
	    }

	    if((save) && (tokenStringIndex<=MAXTOKENLEN))
	       tokenString[tokenStringIndex++]=(char)c;

	     if(state==DONE)
	     {
	     	tokenString[tokenStringIndex]='\0';
	        if(currentToken==ID)
	        	currentToken=reservedLookup(tokenString);
		 }
    }
	if(TraceScan){
		fprintf(listing, "\t%d: ", lineno);
		printToken(currentToken, tokenString); 
	}
	
	return currentToken;
}
int main(int argc, char * argv[]){
	char pgm[120]; /* source code file name */
  /*if (argc != 2)
    { fprintf(stderr,"usage: %s <filename>\n",argv[0]);
      exit(1);
    }
  strcpy(pgm,argv[1]) ;
  if (strchr (pgm, '.') == NULL)
     strcat(pgm,".c-");*/
  //source = fopen(pgm,"r");
  source = fopen("test.c-","r");
  if (source==NULL)
  { fprintf(stderr,"File %s not found\n",pgm);
    exit(1);
  }
  listing = stdout; /* send listing to screen */
  fprintf(listing,"\nC- COMPILATION: %s\n",pgm);
  while(getToken()!=ENDFILE);
  fclose(source);
  return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)