實驗一
詞法分析程序實現 一、實驗目的與要求
通過編寫和調試一個詞法分析程序，掌握在對程序設計語言的源程序進行掃描的過程中，將字符流形式的源程序轉化為一個由各類單詞符號組成的流的詞法分析方法
二、實驗內容
基本實驗：
題目：若某一程序設計語言中的單詞包括五個關鍵字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
運 行 結 果 ：
推薦訪問： 編譯 原理 實驗上一篇：氣象局黨務公開自檢自查報告
下一篇：時代楷模黃文秀個人事跡
在偉大祖國73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動，集中觀看了抗美援朝題材影片《長津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國剛剛成立一年，
根據省局黨組《關于舉辦習近平談治國理政（第四卷）讀書班的通知》要求，我中心通過專題學習、專題研討以及交流分享等形式，系統的對《習近平談治國理政》（第四卷)進行了深入的學習與交流，下面我就來談一談我個人
《習近平談治國理政》（第四卷）是在百年變局和世紀疫情相互疊加的大背景下，對以習近平同志為核心的黨中央治國理政重大戰略部署、重大理論創造、重大思想引領的系統呈現。它生動記錄了新一代黨中央領導集體統籌兩個
《真抓實干做好新發展階段“三農工作”》是《習近平談治國理政》第四卷中的文章，這是習近平總書記在2020年12月28日中央農村工作會議上的集體學習時的講話。文章指出，我常講，領導干部要胸懷黨和國家工作大
在《習近平談治國理政》第四卷中，習近平總書記強調，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執政黨，在中國共產黨的字典里，“人民”一詞從來都
黨的十八大以來，習近平總書記以馬克思主義戰略家的博大胸襟和深謀遠慮，在治國理政和推動全球治理中牢固樹立戰略意識，在不同場合多次圍繞戰略策略的重要性，戰略和策略的關系，提高戰略思維、堅定戰略自信、強化戰
《習近平談治國理政》第四卷集中展示了以習近平同志為核心的黨中央在百年變局和世紀疫情相互疊加背景下，如何更好地堅持和發展中國特色社會主義而進行的生動實踐與理論探索；對于新時代堅持和發展什么樣的中國特色社
在黨組織的關懷下，我有幸參加了區委組織部組織的入黨積極分子培訓班。為期一周的學習，學習形式多樣，課程內容豐富，各位專家的講解細致精彩，對于我加深對黨的創新理論的認識、對黨的歷史的深入了解、對中共黨員的
《習近平談治國理政》第四卷《共建網上美好精神家園》一文中指出：網絡玩命是新形勢下社會文明的重要內容，是建設網絡強國的重要領域。截至2021年12月，我國網民規模達10 32億，較2020年12月增長4
剛剛召開的中國共產黨第十九屆中央委員會第七次全體會議上討論并通過了黨的十九屆中央委員會向中國共產黨第二十次全國代表大會的報告、黨的十九屆中央紀律檢查委員會向中國共產黨第二十次全國代表大會的工作報告和《