編譯原理——詞法分析器實驗

實驗目的

掌握詞法分析器的功能。
掌握詞法分析器的實作。

實驗内容及要求

對于如下文法所定義的語言子集，試編寫并上機調試一個詞法分析程式：

<程式>→PROGRAM <辨別符>;<分程式>.

<分程式>→<變量說明>BEGIN<語句表>END

<變量說明>→VAR<變量表>：<類型>；| <空>

<變量表>→<變量表>，<變量> | <變量>

<類型>→INTEGER

<語句表>→<語句表>；<語句> | <語句>

<語句>→<指派語句> | <條件語句> | <WHILE語句> | <複合語句> | <過程定義>

<指派語句>→<變量>：=<算術表達式>

<條件語句>→IF<關系表達式>THEN<語句>ELSE<語句>

<WHILE語句>→WHILE<關系表達式>DO<語句>

<複合語句>→BEGIN<語句表>END

<過程定義>→PROCEDURE<辨別符><參數表>；

BEGIN<語句表>END

<參數表>→（<辨別符表>）| <空>

<辨別符表>→<辨別符表>，<辨別符> | <辨別符>

<算術表達式>→<算術表達式>+<項> | <項>

<項>→<項>*<初等量> | <初等量>

<初等量>→（<算術表達式>）| <變量> | <無符号數>

<關系表達式>→<算術表達式><關系符><算術表達式>

<變量>→<辨別符>

<辨別符>→<辨別符><字母> | <辨別符><數學> | <字母>

<無符号數>→<無符号數><數字> | <數字>

<關系符>→= | < | <= | > | >= | <>

<字母>→A | B | C | ··· | X | Y | Z

<數字>→0 | 1 | 2 | ··· | 8 | 9

<空>→

要求和提示：

（1）單詞的分類。

可将所有辨別符歸為一類；将常數歸為另一類；保留字和分隔符則采取一詞一類。

（2）符号表的建立。

可事先建立一保留字表，以備在識别保留字時進行查詢。變量名表及常數表則在詞法分析過程中建立。

（3）單詞串的輸出形式。

所輸出的每一單詞，均按形如（CLASS,VALUE）的二進制式編碼。對于變量标識符和常數，CLASS字段為相應的類别碼，VALUE字段則是該辨別符、常數在其符号表中登記項的序号（要求在變量名表登記項中存放該辨別符的字元串，其最大長度為四個字元；常數表登記項中則存放該整數的二進制形式）。對于保留字和分隔号，由于采用一詞一類的編碼方式，是以僅需在二進制式的 CLASS字段上放置相應的單詞的類别碼，VALUE字段則為“空”。不過，為便于檢視由詞法分析程式所輸出的單詞串，也可以在CLASS字段上直接放置單詞符号串本身。

單詞分類表

以下為單詞分類表（單詞符号，種别編碼）：

單詞符号	種别編碼	單詞符号	種别編碼
auto	1	void	30
break	2	volatile	31
case	3	while	32
char	4	辨別符	33
const	5	常型整量	34
continue	6	+	35
default	7	-	36
do	8	*	37
double	9	/	38
else	10	<	39
enum	11	<=	40
extern	12	>	41
float	13	>=	42
for	14	=	43
goto	15	==	44
if	16	<>	45
int	17	;	46
long	18	(	47
register	19	)	48
return	20	^	49
short	21	,	50
signed	22	#	51
sizeof	23	%	52
static	24	[	53
struct	25	]	54
switch	26	{	55
typedef	27	}	56
union	28	.	57
unsigned	29	//	58

單詞狀态圖

編譯原理——詞法分析器實驗

算法描述

1.首先，我将單詞類别總分為六大類：

1：辨別符

2：數字

3：算數運算符 + - * \

4：關系運算符 <、<=、>、>=、<>、=、==

5：保留字(32)

auto break case char const continue

default do double else enum extern

float for goto if int long

struct switch typedef union unsigned void

volatile while

6：界符 ;、(、)、^、,、#、%、[、]、{、}、.、\\

2.每種單詞類别的識别及判斷方法如下：

首先從檔案中讀一個字元，指派給ch，

如果ch為空格，則檔案掃描列序号加一；

如果ch為回車，則檔案掃描行序号加一；

其它情況如下：

（1）如果ch為字母或下劃線，繼續掃描，直到ch不是數字、字母或下劃線，則開始判斷單詞類型：

查找關鍵字表，若找到比對項，則為關鍵字；

否則為辨別符，查找辨別符表，若沒有找到比對項，則添加到辨別符表中。（動态生成辨別符表）

如果ch為數字，繼續掃描，直到ch不是數字，則開始判斷單詞類型：若數字在合法範圍内，則為數字，查找辨別符表，若沒有找到比對項，則添加到數字表中；（動态生成數字表）

否則為非法單詞。

（2）如果ch是加減乘，一定是算數運算符。

（3）如果ch為;、(、)、^、,、#、%、[、]、{、}、.，則一定是界符。

（4）如果ch為<，則繼續掃描下一個：

若下一個為=，則為<=；

若下一個為>，則為<>；

否則，為<。

（5）如果ch為>，則繼續掃描下一個：

若下一個為=，則為>=；

否則，為>。

（6）如果ch為/，則繼續掃描下一個：

若下一個為/，則為注釋，這一行剩下的全被注釋了；

否則，則為/。

3.出錯處理：

我使用了兩個全局變量：line，col，分别用于定位檔案中掃描的位置資訊，當發現目前字元為非法字元時，輸出報錯資訊，并輸出非法字元在檔案中的所在位置資訊。

4.輸出顯示：

将所輸出的每一單詞，均按形如（CLASS,VALUE）的二進制式編碼。對于變量辨別符和常數，CLASS字段為相應的類别碼，VALUE字段則是該辨別符、常數在其符号表中登記項的序号。對于保留字和分隔号，由于采用一詞一類的編碼方式，為便于檢視由詞法分析程式所輸出的單詞串，是以在CLASS字段上直接放置單詞符号串本身，VALUE字段則為“空”。使用分支結構，根據判斷結果，進而進行相應輸出顯示。

程式結構

1.變量常量定義：

對程式所需常量以及全局變量進行定義，其中包含：

（1）全局變量：

int seekresult：fseek的時候用來接着的；

string word=""：字元串,目前詞；

char ch：每次讀進來的一個字元；

int num=0：每個單詞中目前字元的位置；

int line=1：行數；

int col=1：列數；

bool flag：檔案是否結束掃描；

int type;：單詞的類型；

char IDentifierTable[1000][40]：辨別符表；

char DigitBTable[1000][40]常數表等。

（2）常量：

static char ReserveWord[32][20]：保留字表；

static char SuanshuOperator[4][4]：算術運算符表；

static char GuanxiOperator[7][4]：邏輯運算符表；

static char Jiefu[36][4]：界符表。

2.主要函數：

（1）bool Isletter(char x)函數：判斷字元x是否為字母；

（2）bool IsDigit(char x)函數：判斷字元x是否為數字；

（3）bool IsJiefu(char x)函數：判斷字元x是否為界符；

（4）bool IsSuanshuyunsuanfu(char x) 函數：判斷字元x是否為算數運算符；

（5）bool IsGuanxiyunsuanfu(char x)函數：判斷字元x是否為關系運算符；

（6）int Scanner(FILE *fp)函數：其主要功能為從檔案裡讀一個單詞，調用基礎函數進行單詞類别，。

（7）int main()函數：程式入口，進行檔案掃描，并調用Scanner(FILE *fp)函數對單詞進行判斷，輸出分析結果。

運作結果

1.待分析檔案code.txt：

編譯原理——詞法分析器實驗

2.運作結果：

編譯原理——詞法分析器實驗

3.檔案目錄：

編譯原理——詞法分析器實驗

4.常數表：

編譯原理——詞法分析器實驗

5.辨別符表：

編譯原理——詞法分析器實驗

調試情況

在此次實驗中，遇到的問題還是比較多的，主要分為以下幾種：

1.讀檔案和寫檔案操作：

由于待分析内容存儲在文本檔案中，是以檔案的讀取是必不可少的操作；而單詞分析時需要動态生成辨別符表和常數表，故需要追寫檔案。一開始由于語言功底不太紮實，實作的不太順利，但是在上網查找了解決方案以後，問題就迎刃而解了。

2.各種單詞類别的識别和判斷以及出錯處理：

這是詞法分析器的核心也是難點，這部分必須邏輯十厘清晰才可以實作，一開始雖然聽懂了課堂上的内容，但是了解的還是不夠深刻，感覺自己已經将單詞類别進行了合理的劃分，但是具體實作細節上還是遇到了不少的困難。比如，在一些相似單詞的識别上面困惑了一段時間，想到了老師上課所說的“超前搜尋”算法，是以我進行了實作，但是發現位置定位是一個需要特别關注的問題，我的解決方案就是：添加兩個全局位置變量以及一些局部位置變量，将檔案中現在正在掃描的位置以及這個單詞第一個字元的位置資訊記錄下來，然後捋清他們之間的關系以及使用目的，則問題也就解決了，并且也使得報錯資訊可以包含非法字元在檔案中的位置所在。

3.辨別符表和常數表的動态生成：

關于這個問題的解決，我将它放在了識别的過程當中，就可以做到動态生成，并且添加了檔案追寫，則可以在檔案中檢視生成的表資訊了。

4.輸出顯示：

這個問題一開始實作的有些困難，當我發現它的重心在于認清每個單詞的分類情況，并通過識别結果就可以很好的實作了。

測試檔案 code.txt

int main(void) {
  int min=2, mid=3, max=1, t;
  if (min > mid) {
    t = min;
    min = mid;
    mid = t;
  }
  if (min > max) {
    t = min;
    min = max;
    max = t;
  }
  if (mid > max) {
    t = mid;
    mid = max;
    max = t;
  }
}

源代碼

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>

using namespace std;

/*
1：辨別符
2：數字 
3：算數運算符 + - * 
4：關系運算符 <=、  >=、  <>、  == =、 <、>
5：保留字(32)
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
6：界符 
*/

int seekresult;		//fseek的時候用來接着的 
string word="";		//字元串,目前詞 
char ch;			//每次讀進來的一個字元
int num=0;			//每個單詞中目前字元的位置
int line=1;			//行數
int col=1;			//列數
bool flag;			//檔案是否結束掃描 
int type;			//單詞的類型

//保留字表
static char ReserveWord[32][20] = {
    "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"
};

//算術運算符表
static char SuanshuOperator[4][4] = {
    "+", "-", "*", "/"
};
//邏輯運算符表 
static char GuanxiOperator[7][4] = {
    "<", "<=", ">", ">=", "=", "==","<>"
};
//界符表(12)
static char Jiefu[36][4] = {
	";", "(", ")", "^", ",", "#","%", "[", "]", "{", "}","."
};

//辨別符表
//string IDentifierTable[1000] = { "" };
char IDentifierTable[1000][40] = {};

//常數表 
//int DigitBTable[1000][50] = {};
char DigitBTable[1000][40] = {};

int Inum=0;

int Dnum=0;


//判斷是否是：字母
bool Isletter(char x)
{
	if((x>='a'&&x<='z')||(x>='A'&&x<='Z'))
		return true;
	else return false;
}

//判斷是否是：數字 
bool IsDigit(char x)
{
	if(x>='0'&&x<='9')
		return true;
	else
		return false;
}

//判斷是否是：界符 
bool IsJiefu(char x) 
{
	int i=0;
	int temp=0;
	for(i=0;i<14;i++)
	{
		if( x == Jiefu[i][0] )
		{
			temp=1;
			break;
		 } 
	}
	if( temp == 1 )
		return true;
	else
		return false;
}

//判斷是否是 算數運算符：加減乘
bool IsSuanshuyunsuanfu(char x)
{
	if(x=='+'||x=='-'||x=='*')
		return true;
	else return false;
}

//判斷是否是 關系運算符：等于（指派），大于小于（大于等于，小于等于，大于小于） 
bool IsGuanxiyunsuanfu(char x)
{
	if(x=='='||x=='<'||x=='>')
		return true;
	else
		return false;
} 

//從檔案裡讀一個單詞 
int Scanner(FILE *fp)
{
	//先讀一個字元，指派給ch 
    ch=fgetc(fp);
    
    if(feof(fp)){
        flag=0;
		return 0;
    }
    else if(ch==' ')
    {
        col++;
        return 0;
    }
    else if(ch=='\n')
    {
        line++;
        col=1;
        return 0;
    }
    //如果是字母開頭或 '_' 看關鍵字還是辨別符 
    else if( Isletter(ch) || ch=='_' )
    {
        word+=ch;
		col++;
        while( (ch=fgetc(fp)) && ( Isletter(ch) || IsDigit(ch) || ch=='_'))
        {
            word+=ch;
			col++;
        }
		//檔案讀完，傳回true
        if(feof(fp)){
                flag=0;
				return 1;
        }
        //檢驗是否是保留字 
        for(int i=1;i<=32;i++){
            if( word == ReserveWord[i] ){
            	//SEEK_CUR目前位置，fseek函數作用：檔案位置指針從目前位置位移一個位置 
                seekresult=fseek(fp,-1,SEEK_CUR);
              	//5+i-1：保留字 
				return 5+i-1;
            }
        }
        for(int Ii=0;Ii<Inum;Ii++)
        {
        	if(Inum!=0 && strcmp(IDentifierTable[Ii],word.c_str())==0)
        	{
        		seekresult=fseek(fp,-1,SEEK_CUR);	
        		//1：辨別符 
        		//return 1;
        		return 1000+Ii+1;
			}
		}
        strcpy(IDentifierTable[Inum],word.c_str());
    	Inum=Inum+1;
		//寫追加 
		ofstream Arithmetic_operator;
		Arithmetic_operator.open("IDentifierTable.txt",ios::app);
		Arithmetic_operator<<word<<" "<<endl;
    	Arithmetic_operator.close();
    	
		seekresult=fseek(fp,-1,SEEK_CUR);	
        //1：辨別符 
        //return 1;
        return 1000+Inum;
    }
 
    //開始是加減乘，一定是算數運算符3 
    else if(IsSuanshuyunsuanfu(ch))
    {
        word+=ch;
		col++;
		//3：算數運算符 
        return 3;
    }
 
    //開始是數字就一定是數字2 
    else if(IsDigit(ch))
    {
        word+=ch;
		col++;
        while((ch=fgetc(fp)) && IsDigit(ch))
        {
            word+=ch;
			col++;
        }
        int Di=0;
        for(Di=0;Di<Inum;Di++)
        {
        	if(Dnum!=0 && strcmp(DigitBTable[Di],word.c_str())==0)
        	{
        		seekresult=fseek(fp,-1,SEEK_CUR);	
        		//2：數字 
        		//return 2;
        		return 2000+Di+1;
			}
		}
        strcpy(DigitBTable[Dnum],word.c_str());
    	Dnum=Dnum+1;
		//寫追加 
		ofstream Arithmetic_operator;
		Arithmetic_operator.open("DigitBTabl.txt",ios::app);
		Arithmetic_operator<<word<<" "<<endl;
    	Arithmetic_operator.close();
   	
//        if(feof(fp)){
//                flag=0;
//				return 2;
//        }

        seekresult=fseek(fp,-1,SEEK_CUR);
        //2：數字 
        return 2000+Dnum;
    }
 
    //檢驗界符6 
    else if(IsJiefu(ch))
    {
    	int Ji;
		for(Ji=0;Ji<12;Ji++)
		{
			if( ch == Jiefu[Ji][0] )
			{
				break;
			} 
		}
        word+=ch;col++;
        //6-1+32+i：界符 
        return (6-1+32+Ji);
    }
 
    //檢驗關系運算符4 ：<=、>=、<>、==、 < 、>
    else if( IsGuanxiyunsuanfu(ch) )
    {
        col++;
        word+=ch;
		//檢驗  <> <=
        if(ch=='<')   
        {
            ch=fgetc(fp);
            if(ch=='>' || ch=='=')
            {
                word+=ch;
                col++; 
                return 4;
            }
        }
        //檢驗  >= ==
        else{
            ch=fgetc(fp);
            if(ch=='=')
            {
                word+=ch;
                col++;
                return 4;
            }
        }
        if(feof(fp)){
                flag=0;
        }
        seekresult=fseek(fp,-1,SEEK_CUR);
        //3:算數運算符 
        return 3;
    }
 
    //首字元是 / 有可能是除号 也有可能是注釋
    else if(ch=='/')
    {
        col++;word+=ch;
        ch=fgetc(fp);
        //這種情況是除号
        if(ch!='*' && ch !='/')
        {
            seekresult=fseek(fp,-1,SEEK_CUR);
            //3:算數運算符 
            return 3;
        }
        //注釋符//：這一行剩下的全被注釋了
        if(ch=='/')
        {
            word.clear();
            while((ch=fgetc(fp)) && ch!='\n' && !feof(fp) )
            {}
            if(feof(fp)){
                flag=0;
				return 0;
            }
            else{
               seekresult=fseek(fp,-1,SEEK_CUR);
            }
            line++;col=1;
            return 0;
        }
        if(ch=='*')
        {
            bool flag5=1;
            while(flag5)
            {
                word.clear();
                ch=fgetc(fp);
                col++;
                if(ch=='\n')
				{
					line++;
					col=1;
				}
                if(ch!='*')
					continue;
                else 
				{
                    ch=fgetc(fp);
                    col++;if(ch=='\n'){line++;col=1;}
                    if(ch=='/'){
                        flag5=0;
                    }
                    else continue;
                }
                if(feof(fp))
				{
					flag=0;
					return 0;
				}
            }
        }
    }
    else {
        word+=ch;
        col++;
        return -1;
    }
}
 
int main()
{
	FILE *fp;
    
	cout<<"open "<<"code.txt"<<endl;
    system("pause");
 
    flag=1;
    
	//打開源代碼檔案 
	
	//未打開 
    if((fp=fopen("code.txt","r"))==NULL)
    {
        cout<<"Sorry,can't open this file."<<endl;
        flag=0;
    }
    //已打開 
    while(flag==1)
    {
		//反複調用掃描函數提取單詞
        type=Scanner(fp);	
 		
		//1：辨別符
        if(type>1000&&type<2000)
        {
            //cout<<"type:1 identifier      "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
            cout<<"("<<word<<","<<type-1000<<")"<<endl; 
			if(word.length()>20)
            	cout<<"ERROR Identifier length cannot exceed 20 characters"<<endl;
            word.clear();
        }
		//2：數字   
        else if(type>2000)
        {
            //cout<<"type:2 positive number "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
            cout<<"("<<word<<","<<(type-2000)<<")"<<endl;
			if(word[0]=='0')
            	cout<<"ERROR: The first digit cannot be 0!"<<endl;
            word.clear();
        }
		//3：算數運算符 + - * / 
        else if(type==3)
        {
            //cout<<"type:3 unary_operator  "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
            cout<<"("<<word<<","<<"3"<<")"<<endl;
            word.clear();
        }
        
        //4：關系運算符 <、<=、>、>=、= 、<> 
        else if(type==4)
        {
            //cout<<"type:4 double_operator "<<"line "<<line<<" col "<<col-2<<"  "<<word<<endl;
            cout<<"("<<word<<","<<"4"<<")"<<endl;
			word.clear();
        }
        //6-1+32 - 6-1+32+11：界符
        else if(type>=37)
        {
            //cout<<"type:5 Separator       "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
        	cout<<"("<<word<<","<<"_"<<")"<<endl;
			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
			word.clear();
        }
       //5 - 5-1+32：保留字 
        else if( type>=5 && type<=36)
        {
            //cout<<"type:6 reserved word   "<<"line "<<line<<" col "<<col-word.length()<<"  "<<word<<endl;
            cout<<"("<<word<<","<<"_"<<")"<<endl;
			//cout<<"("<<type<<","<<"_"<<")"<<endl;  
			word.clear();
        }
        //非法字元
        else if(type==-1)
        {
           cout<<"Illegal character   "<<"line "<<line<<" col "<<col-1<<"  "<<word<<endl;
           word.clear();
        }
    }
        int a=fclose(fp);
        cout<<"Do you want to close?(Y or N)"<<endl;
        char end;
        while(cin>>end && end!='Y'){
            cout<<"Do you want to close?(Y or N)"<<endl;
        }
    return 0;
}

編譯原理——詞法分析器實驗

實驗目的

實驗内容及要求

單詞分類表

單詞狀态圖

算法描述

程式結構

運作結果

調試情況

測試檔案 code.txt

源代碼

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述