實(shí)驗(yàn)一
詞法分析程序?qū)崿F(xiàn) 一、實(shí)驗(yàn)?zāi)康呐c要求
通過(guò)編寫和調(diào)試一個(gè)詞法分析程序，掌握在對(duì)程序設(shè)計(jì)語(yǔ)言的源程序進(jìn)行掃描的過(guò)程中，將字符流形式的源程序轉(zhuǎn)化為一個(gè)由各類單詞符號(hào)組成的流的詞法分析方法
二、實(shí)驗(yàn)內(nèi)容
基本實(shí)驗(yàn)：
題目：若某一程序設(shè)計(jì)語(yǔ)言中的單詞包括五個(gè)關(guān)鍵字begin、end、if、then、else；標(biāo)識(shí)符；無(wú)符號(hào)常數(shù)；六種關(guān)系運(yùn)算符；一個(gè)賦值符和四個(gè)算術(shù)運(yùn)算符，試構(gòu)造能識(shí)別這些單詞的詞法分析程序（各類單詞的分類碼參見(jiàn)表 I）。
表 表 I
語(yǔ)言中的各類單詞符號(hào)及其分類碼表
單詞符號(hào)
類別編碼
類別碼的助記符
單詞值
begin
1
BEGIN
end
2
END
if
3
IF
then
4
THEN
else
5
ELSE
標(biāo)識(shí)符
6
ID
字母打頭的字母數(shù)字串
無(wú)符號(hào)常數(shù)
7
UCON
機(jī)內(nèi)二進(jìn)制表示
<
8
LT
<=
9
LE
=
10
EQ
<>
11
NE
>
12
GT
>=
13
GE
:=
14
IS
+
15
PL
-
16
MI
*
17
MU
/
18
DI
：
輸入：由符合和不符合所規(guī)定的單詞類別結(jié)構(gòu)的各類單詞組成的源程序文件。
輸出：把所識(shí)別出的每一單詞均按形如（CLASS，VALUE）的二元式形式輸出，并將結(jié)果放到某個(gè)文件中。對(duì)于標(biāo)識(shí)符和無(wú)符號(hào)常數(shù)，CLASS字段為相應(yīng)的類別碼的助記符；VALUE 字段則是該標(biāo)識(shí)符、常數(shù)的具體值；對(duì)于關(guān)鍵字和運(yùn)算符，采用一詞一類的編碼形式，僅需在二元式的 CLASS 字段上放置相應(yīng)單詞的類別碼的助記符，VALUE 字段則為“空”。
三、實(shí)現(xiàn)方法與環(huán)境
詞法分析是編譯程序的第一個(gè)處理階段，可以通過(guò)兩種途徑來(lái)構(gòu)造詞
法分析程序。其一是根據(jù)對(duì)語(yǔ)言中各類單詞的某種描述或定義（如BNF），用手工的方式（例如可用 C 語(yǔ)言）構(gòu)造詞法分析程序。一般地，可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，該狀態(tài)矩陣連同控制程序一起便組成了編譯器的詞法分析程序；也可以根據(jù)文法或狀態(tài)轉(zhuǎn)換圖直接編寫詞法分析程序。構(gòu)造詞法分析程序的另外一種途徑是所謂的詞法分析程序的自動(dòng)生成，即首先用正規(guī)式對(duì)語(yǔ)言中的各類單詞符號(hào)進(jìn)行詞型描述，并分別指出在識(shí)別單詞時(shí)，詞法分析程序所應(yīng)進(jìn)行的語(yǔ)義處理工作，然后由一個(gè)所謂詞法分析程序的構(gòu)造程序?qū)ι鲜鲂畔⑦M(jìn)行加工。如美國(guó) BELL 實(shí)驗(yàn)室研制的 LEX 就是一個(gè)被廣泛使用的詞法分析程序的自動(dòng)生成工具。
?。?/p>
處理過(guò)程簡(jiǎn)述：在一個(gè)程序設(shè)計(jì)語(yǔ)言中，一般都含有若干類單詞符號(hào)，為此可首先為每類單詞建立一張狀態(tài)轉(zhuǎn)換圖，然后將這些狀態(tài)轉(zhuǎn)換圖合并成一張統(tǒng)一的狀態(tài)圖，即得到了一個(gè)有限自動(dòng)機(jī)，再進(jìn)行必要的確定化和狀態(tài)數(shù)最小化處理，最后添加當(dāng)進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)所需執(zhí)行的語(yǔ)義動(dòng)作，就可以據(jù)此構(gòu)造詞法分析程序了。
為了使詞法分析程序結(jié)構(gòu)比較清晰，且盡量避免某些枝節(jié)問(wèn)題的糾纏，我們假定要編譯的語(yǔ)言中，全部關(guān)鍵字都是保留字，程序員不得將它們作為源程序中的標(biāo)識(shí)符；在源程序的輸入文本中，關(guān)鍵字、標(biāo)識(shí)符、無(wú)符號(hào)常數(shù)之間，若未出現(xiàn)關(guān)系和算術(shù)運(yùn)算符以及賦值符，則至少須用一個(gè)空白字符加以分隔。作了這些限制以后，就可以把關(guān)鍵字和標(biāo)
識(shí)符的識(shí)別統(tǒng)一進(jìn)行處理。即每當(dāng)開(kāi)始識(shí)別一個(gè)單詞時(shí)，若掃視到的第一個(gè)字符為字母，則把后續(xù)輸入的字母或數(shù)字字符依次進(jìn)行拼接，直至掃視到非字母、數(shù)字字符為止，以期獲得一個(gè)盡可能長(zhǎng)的字母數(shù)字字符串，然后以此字符串查所謂保留字表（此保留字表要事先造好），若查到此字符串，則取出相應(yīng)的類別碼；反之，則表明該字符串應(yīng)為一標(biāo)識(shí)符。
采用上述策略后，針對(duì)表 I 中的部分單詞可以參考教材 P80 的圖 3-22（見(jiàn)圖 1）
圖 圖 1 1
識(shí)別表 I I 所列語(yǔ)言中的部分單詞的 A DFA 及相關(guān)的語(yǔ)義過(guò)程
圖 圖 1 1 中所出現(xiàn)的語(yǔ)義變量及語(yǔ)義函數(shù)的含義和功能說(shuō)明如下：
函數(shù) GETCHAR：每調(diào)用一次，就把掃描指示器當(dāng)前所指示的源程序字符送入字符變量 ch，然后把掃描指示器前推一個(gè)字符位置。
字符數(shù)組 TOKEN：用來(lái)依次存放一個(gè)單詞詞文中的各個(gè)字符。
函數(shù) CAT：每調(diào)用一次，就把當(dāng)前 ch 中的字符拼接于 TOKEN 中所存字符串的右邊。
函數(shù) LOOKUP：每調(diào)用一次，就以 TOKEN 中的字符串查保留字表，若
查到，就將相應(yīng)關(guān)鍵字的類別碼賦給整型變量 c；否則將 c 置為零。
函數(shù) RETRACT：每調(diào)用一次，就把掃描指示器回退一個(gè)字符位置（即退回多讀的那個(gè)字符）。
函數(shù) OUT：一般僅在進(jìn)入終態(tài)時(shí)調(diào)用此函數(shù)，調(diào)用的形式為 OUT(c，VAL)。其中，實(shí)參 c 為相應(yīng)單詞的類別碼助記符；實(shí)參 VAL 為 TOKEN（即詞文）或?yàn)榭沾?。函?shù) OUT 的功能是，在送出一個(gè)單詞的內(nèi)部表示之后，返回到調(diào)用該詞法分析程序的那個(gè)程序。
總的來(lái)說(shuō)，開(kāi)發(fā)一種新語(yǔ)言時(shí)，由于它的單詞符號(hào)在不停地修改，采用 LEX 等工具生成的詞法分析程序比較易于修改和維護(hù)。一旦一種語(yǔ)言確定了，則采用手工編寫詞法分析程序效率更高。
四．源程序
#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//關(guān)鍵字的數(shù)量
#define KEY_WORD_END "waiting for your expanding"
//關(guān)鍵字結(jié)束標(biāo)記
char *KeyWordTable[MAX_KEY_NUMBER]={"begin","end", "if", "then", "else", KEY_WORD_END};
char TOKEN[20]="";
char ch=" ";//用于存儲(chǔ)帶判斷的字符
int row=1;//row 標(biāo)識(shí)錯(cuò)誤在第幾行
#define DIGIT 1
#define POINT 2
#define OTHER 3
#define POWER 4
#define PLUS 5
#define MINUS 6
#define UCON 7
//假設(shè)無(wú)符號(hào)常量的類數(shù)是 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;
//用于目前的當(dāng)前狀態(tài),初始值: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);
///////////////////查保留字表，判斷是否為關(guān)鍵字
int lookup (char *token)
{
int n=0;
while (strcmp(KeyWordTable[n], KEY_WORD_END)) //strcmp 比
較兩串是否相同，若相同返回 0
{
if (!strcmp(KeyWordTable[n], token)) //比較 token 所指向的關(guān)鍵字和保留字表中哪個(gè)關(guān)鍵字相符
{
return n+1; //根據(jù)單詞分類碼表 I，設(shè)置正確的關(guān)鍵字類別碼，并返回此類別碼的值
break;
}
n++;
}
return 6; //單詞不是關(guān)鍵字，而是標(biāo)識(shí)符
}
///////////////////輸出分析結(jié)果
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
)對(duì)應(yīng) %s\n",Mnemonic,pStr);
}
///////////////////報(bào)錯(cuò)
void report_error (int row)
{
printf("%s
Error! In the %d row\n",TOKEN,row);
}
///////////////////掃描程序
void scanner(FILE *fp)//總的判斷函數(shù)開(kāi)始就應(yīng)該判斷已讀取的字符是否為空字符，不為則不用再讀，直接進(jìn)行判斷，否則再讀
{
int i, c;
fseek(fp,-1,1);//首先回溯一個(gè)字符，就是將文件所有的字符都在 scanner 內(nèi)部判斷，外部 while 循環(huán)不會(huì)浪費(fèi)任何字符
ch=fgetc (fp);//scanner 中要想判斷字符，必須開(kāi)頭先讀一個(gè)字符
while(" "==ch||"\n"==ch||"\t"==ch)//將文件中的所有空字符浪費(fèi)在這里
{
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);//首先回溯一個(gè)字符，下面為了循環(huán)內(nèi)部使用先讀字符后判斷的格式。
int Type;
CurrentState=0;
i=0;
do
{
ch=fgetc(fp);
TOKEN[i]=ch;
i++;
TOKEN[i]="\0";//為隨時(shí)輸出字符串做準(zhǔn)備
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;
}
///////////////////判斷矩陣執(zhí)行程序
int EXCUTE (int state, int symbol,FILE *fp,char JudgeStr[],int row,int index)//row 用于指示出錯(cuò)的行數(shù)，index 用于為待輸出的字符串賦結(jié)束符‘\0’時(shí)用
{
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("無(wú)符號(hào)數(shù)的第一個(gè)字符是非法的！\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)//如果是因?yàn)樽x到文件結(jié)束字符而終止識(shí)別，就不應(yīng)該回退，否則可能造成死循環(huán)
{
fseek(fp,-1,1);//遇到其他的字符，可能是一條語(yǔ)句中的其他字符，需后退，因?yàn)橹骱瘮?shù)外層循環(huán)每次都要讀一個(gè)字符進(jìn)行判斷，而這個(gè)判讀不回溯，所以在內(nèi)部把這個(gè)多讀的字符回溯
}
ICON=w;CurrentState=EndState;
JudgeStr[index-1]="\0";
printf("(UCON,%i)對(duì)應(yīng) %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) 對(duì) 應(yīng) 于 %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;//識(shí)別無(wú)符號(hào)數(shù)產(chǎn)生錯(cuò)誤時(shí)，不應(yīng)該再回溯，應(yīng)該把造成錯(cuò)誤的那個(gè)字符算到錯(cuò)誤的無(wú)符號(hào)數(shù)字符串中，再向下面識(shí)別單詞時(shí)跳過(guò)這個(gè)字符，不回溯就能達(dá)到這個(gè)目的
}
}
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;//判斷一個(gè)無(wú)符號(hào)數(shù)的最后一個(gè)字符應(yīng)該都是多余讀取的，所以為了防止引起后面再次判斷下一無(wú)符號(hào)數(shù)時(shí)產(chǎn)生呑字符的現(xiàn)象，都應(yīng)該回溯一個(gè)字符
}
}
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)對(duì)應(yīng) %s\n",FCON,JudgeStr);
}break;
}
break;
}
return CurrentState;
}
///////////////////無(wú)符號(hào)數(shù)判斷過(guò)程中的字符類型判斷程序
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;
}
///////////////////判斷出錯(cuò)報(bào)錯(cuò)程序
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)//不管小括號(hào)內(nèi)的判斷是否成功，p 指針都會(huì)向后移一個(gè)位置，判斷不成功，ch 中存的字符不變
{
printf("The file is null.\n");
return 0;
}
printf("第一個(gè)字母是：%c\n",ch);
do
{
scanner(p);
}while(ch=fgetc(p)!=EOF);
fclose(p);
return 0;
}
五．測(cè)試用例及運(yùn)行結(jié)果分析
測(cè)試用例：begin 8E-5+8*7/1.5
運(yùn) 行 結(jié) 果 ：
推薦訪問(wèn)： 編譯 原理 實(shí)驗(yàn)在偉大祖國(guó)73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動(dòng)，集中觀看了抗美援朝題材影片《長(zhǎng)津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國(guó)剛剛成立一年，
根據(jù)省局黨組《關(guān)于舉辦習(xí)近平談治國(guó)理政（第四卷）讀書班的通知》要求，我中心通過(guò)專題學(xué)習(xí)、專題研討以及交流分享等形式，系統(tǒng)的對(duì)《習(xí)近平談治國(guó)理政》（第四卷)進(jìn)行了深入的學(xué)習(xí)與交流，下面我就來(lái)談一談我個(gè)人
《習(xí)近平談治國(guó)理政》（第四卷）是在百年變局和世紀(jì)疫情相互疊加的大背景下，對(duì)以習(xí)近平同志為核心的黨中央治國(guó)理政重大戰(zhàn)略部署、重大理論創(chuàng)造、重大思想引領(lǐng)的系統(tǒng)呈現(xiàn)。它生動(dòng)記錄了新一代黨中央領(lǐng)導(dǎo)集體統(tǒng)籌兩個(gè)
《真抓實(shí)干做好新發(fā)展階段“三農(nóng)工作”》是《習(xí)近平談治國(guó)理政》第四卷中的文章，這是習(xí)近平總書記在2020年12月28日中央農(nóng)村工作會(huì)議上的集體學(xué)習(xí)時(shí)的講話。文章指出，我常講，領(lǐng)導(dǎo)干部要胸懷黨和國(guó)家工作大
在《習(xí)近平談治國(guó)理政》第四卷中，習(xí)近平總書記強(qiáng)調(diào)，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執(zhí)政黨，在中國(guó)共產(chǎn)黨的字典里，“人民”一詞從來(lái)都
黨的十八大以來(lái)，習(xí)近平總書記以馬克思主義戰(zhàn)略家的博大胸襟和深謀遠(yuǎn)慮，在治國(guó)理政和推動(dòng)全球治理中牢固樹(shù)立戰(zhàn)略意識(shí)，在不同場(chǎng)合多次圍繞戰(zhàn)略策略的重要性，戰(zhàn)略和策略的關(guān)系，提高戰(zhàn)略思維、堅(jiān)定戰(zhàn)略自信、強(qiáng)化戰(zhàn)
《習(xí)近平談治國(guó)理政》第四卷集中展示了以習(xí)近平同志為核心的黨中央在百年變局和世紀(jì)疫情相互疊加背景下，如何更好地堅(jiān)持和發(fā)展中國(guó)特色社會(huì)主義而進(jìn)行的生動(dòng)實(shí)踐與理論探索；對(duì)于新時(shí)代堅(jiān)持和發(fā)展什么樣的中國(guó)特色社
在黨組織的關(guān)懷下，我有幸參加了區(qū)委組織部組織的入黨積極分子培訓(xùn)班。為期一周的學(xué)習(xí)，學(xué)習(xí)形式多樣，課程內(nèi)容豐富，各位專家的講解細(xì)致精彩，對(duì)于我加深對(duì)黨的創(chuàng)新理論的認(rèn)識(shí)、對(duì)黨的歷史的深入了解、對(duì)中共黨員的
《習(xí)近平談治國(guó)理政》第四卷《共建網(wǎng)上美好精神家園》一文中指出：網(wǎng)絡(luò)玩命是新形勢(shì)下社會(huì)文明的重要內(nèi)容，是建設(shè)網(wǎng)絡(luò)強(qiáng)國(guó)的重要領(lǐng)域。截至2021年12月，我國(guó)網(wǎng)民規(guī)模達(dá)10 32億，較2020年12月增長(zhǎng)4
剛剛召開(kāi)的中國(guó)共產(chǎn)黨第十九屆中央委員會(huì)第七次全體會(huì)議上討論并通過(guò)了黨的十九屆中央委員會(huì)向中國(guó)共產(chǎn)黨第二十次全國(guó)代表大會(huì)的報(bào)告、黨的十九屆中央紀(jì)律檢查委員會(huì)向中國(guó)共產(chǎn)黨第二十次全國(guó)代表大會(huì)的工作報(bào)告和《