1、實驗一：簡易掃描器的DFA設計與實現實驗原理：詞法分析器的工作原理實驗內容：用程序模擬實現一個簡易掃描器的工作過程，從輸入字符串到分析完以后以（CLASS，VALUE）的標準格式輸出實驗要求：1 源程序設計語言G： |0|=|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z1|2|3|4|5|6|7|8|9|02 能識別下表所列的單詞符號：單詞符號類別編碼類別碼的助記符單詞之值begin1 BEGINend2ENDif3IFthen4TH

2、ENelse5ELSE標識符6ID整數7INT數字串8LT=9LE=10EQ11NE12GT=13GE+14ADD-15SUB*16MUL/17DIV；18SEM（19LB）20RB3 能跳過源程序中的空白格：兩個單詞之間的任何空格，制表符，回車，換行都是白空格，除了用來分隔單詞以外，沒有意義；4 能跳過注釋：1） 接連出現的/*到下一次接連出現的*/之間的任何文字都是注釋（多行）；2） 從某行接連出現的/到該行的結尾的任何文字都是注釋（單行）。實驗步驟：1 DFA及相關語義過程；2 流程圖（或程序的基本框架）；3 根據實驗要求編寫一個能夠完全遍歷整個詞法分析程序的輸入字符串；4 把課本P81

3、程序3-4的函數編寫完整。OUT(DIV,” ”)261. DFA及相關語義過程0非空格空格9OUT(EQ,” ”)C不=0時OUT(c,” ”)OUT(GT,” ”)OUT(GE,” ”)OUT(LT,” ”)OUT(NE,” ”)OUT(LE,” ”)OUT(INT,”TOKEN)C=0時OUT(ID,TOKEN)OUT(RB,” ”)OUT(LB” ”)OUTSEM” ”)OUT(MUL,” ”)OUT(SUB” ”)OUT(ADD,” ”)其他非d非字母和d+-*)(;*非=非=和=dd非/*非*字母,d字母換行非換行非/或非*/空格22212018131076532928272524

4、23171615191411124281START2.流程圖（或程序的基本框架）；退出識別ID或標識符除去空格換行符合無意義字符NY識別符號識別數字除去注釋是否文件尾開始3. 代碼#define _CRT_SECURE_NO_WARNINGS#include#include#include#define BEGIN 1#define END 2#define IF 3#define THEN 4#define ELSE 5#define ID 6#define INT 7#define LT 8#define LE 9#define EQ 10#define NE 11#define GT 1

5、2#define GE 13#define ADD 14#define SUB 15#define MUL 16#define DIV 17#define SEM 18#define LB 19#define RB 20char TOKEN20;int lookup(char*);/查找標識符void out(int, char*);/輸出掃描結果void report_error();/錯誤信息/extern int lookup(char*);int lookup(char* temp) if (strcmp(temp, begin) = 0)return BEGIN;else if (s

6、trcmp(temp, end) = 0)return END;else if (strcmp(temp, if) = 0)return IF;else if (strcmp(temp, then) = 0)return THEN;else if (strcmp(temp, else) = 0)return ELSE;else return 0;/extern void out(int,char*);void out(int a, char* s) switch (a)case BEGIN:printf(n, BEGIN, begin);break;case END:printf(n, END

7、, end);break;case IF:printf(n, IF, if);break;case THEN:printf(n, THEN, then);break;case ELSE:printf(n, ELSE, else);break;case ID:printf(n, ID, s);break;case INT:printf(n, INT, s);break;case LT:printf(n, LT, );break;case LE:printf(n, LE, =);break;case EQ:printf(n, EQ, =);break;case NE:printf(n, NE, )

8、;break;case GT:printf(n, GT, );break;case GE:printf(n, GE, =);break;case ADD:printf(n, ADD, +);break;case SUB:printf(n, SUB, -);break;case MUL:printf(n, MUL, *);break;case DIV:printf(n, DIV, /);break;case SEM:printf(n, SEM, ;);break;case LB:printf(n, LB, （);break;case RB:printf(n, RB, ）);break;defau

9、lt:break;/extern report_error(void);void report_error() printf(未識別字符n);void scanner_example(FILE* fp) char ch;int i=0, c;ch = fgetc(fp);if (ch = | ch = n | ch = -1) return;/略掉空格，換行符和無意義字符if (ch = /)/如果掃描到/char ch2 = fgetc(fp);/取下一個字符if (ch2 = /)/判斷這個字符是不是/printf(/);/條件成立構成/注釋while (ch2 = fgetc(fp)pr

10、intf(%c, ch2);/輸出信息調試用,要跳過，注釋這行即可if (ch2 = n) break; /到了行尾跳出else if (ch2 = *)/判斷是否多行注釋printf(/*);while (ch2 = fgetc(fp)if (ch2 = *) /如果遇到*ch2 = fgetc(fp);if (ch2 = /) break;/切下一個為/ 跳出elseprintf(%c, ch2);/輸出信息調試用,要跳過，注釋這行即可printf(*/n);return;fseek(fp, -1, 1);/沒成立的話、文件指針回退1if (isalpha(ch) /掃描字母TOKENi

11、= ch;i+;while (isalnum(ch) /字母后面帶數字的也是合法IDTOKENi = ch;i+;ch = fgetc(fp);TOKENi = 0;/給串打上結束符fseek(fp, -1, 1);strncpy(TOKEN, TOKEN+1,i);/剪切字串,不要頭個字符c = lookup(TOKEN);/查找是否關鍵字并得到返回值if (c = 0) out(ID, TOKEN);/不是關鍵字則輸出IDelse out(c, );/否則則輸出關鍵字elseif (isdigit(ch) /掃描數字TOKEN0 = ch;ch = fgetc(fp);i = 1;whil

12、e (isdigit(ch)TOKENi = ch;i+;ch = fgetc(fp);TOKENi = 0;fseek(fp, -1, 1);out(INT, TOKEN);else/前面都不成立的話、則查看是不是符號switch (ch) case )out(NE, );elsefseek(fp, -1, 1);out(LT, );break;case =:out(EQ, );break;case :ch = fgetc(fp);if (ch = =)out(GE, );else if (ch = )out(NE, );elsefseek(fp, -1, 1);out(GT, );brea

13、k;case +:out(ADD, );break;case -:out(SUB, );break;case *:out(MUL, );break;case /:out(DIV, );break;case (:out(LB, );break;case ):out(RB, );break;case ;:out(SEM, );break;break;default:report_error();/報錯break;return;int main() FILE* fp;fp = fopen(d:test.txt, r);int tt;while (!feof(fp)/如果文件沒到行尾則循環scanne

14、r_example(fp);return 0;測試文件：結果：心得:經過這次實驗，雖然在課堂上寫的程序有許多缺陷，但回去后，我認真的重寫了一遍，實現了要求的功能，并通過這次的實驗，加深了對掃描器的理解。實驗二：自頂向下分析：LL（1）分析方法實驗原理：語法分析器的工作原理實驗內容： 1、了解語法分析的其中一種自頂向下分析方式LL（1）；2、學會構造LL（1）分析表；3、上機實現課本P120預測分析器的工作流程。實驗要求：要求能對下列文法所產生的符號串進行語法分析：EE+T|E-T|TTT*F|T/F|FF(E)|num|id對輸入的符號在分析完之后，如果正確就報告，有誤就停止。實驗步驟：1、

15、消除文法的左遞歸（、產生式）；2、 對消除左遞規后的文法分別求出各FIRST集和FOLLOW集，再構造相應的LL（1）分析表；3、 根據參考程序（見程序設計指導），實現預測分析器的工作流程。程序設計指導：1、 本次實驗要完成的程序功能為：用程序實現預測分析器的工作流程，根據不斷地查找指定文法得出的LL（1）分析表，最終判斷輸入串是否符合該文法的語法要求；2、 首先，在本次實驗的預習報告中要先完成實驗步驟中的前面兩條；3、 參考程序：char stack50; /分析棧char a100;/輸入器gettop(stack); /自己定義is_nonterminal(x) ;/自己定義is_ter

16、minal(x)；/自己定義pop(1);/自己定義push();/自己定義int LL1driver(void) stack0=#; stack1=E; / 把初始符號移入空棧/* 輸入指示器指向輸入器的初始位置*/ while(！stack_empty() x=gettop(stack); /*取當前棧頂的符號x*/ /* 取當前指示器指向的位置*/ if(is_nonterminal(x) /*查LL(1)分析表,對應有產生式:xy1y2*/ if(查表成功) pop(1); / 棧頂x出棧 push(); /*把產生式右部的侯選式反序（y2y1）壓入分析棧*/ else printf(

17、語法分析過程有誤！);/查表不成功/end ifelse if(is_terminal(x)&x=ai) pop(1); /棧頂x出棧 /* 輸入指示器向前推進一個位置*/ elseif(x=ai=#) printf(success!); else printf(error!); /end while /end LL1driver1. 消除文法的左遞歸（、產生式）；EE+T|E-T|TETEE+TE|-TE|TT*F|T/F|FTFTT*FT|/FT|F(E)|num|id2. 對消除左遞規后的文法分別求出各FIRST集和FOLLOW集，再構造相應的LL（1）分析表；FIRSTFLOLLOWE

18、(,num,id),#E+,-,),#T(,num,id+,-,),#T*,/,+,-,),#F(,num,id*,/,+,-,),#numid+-*/()#EEETEETEETEEE+TEE-TEEETTFTTFTTFTTTTT*FTT/FTTTFFnumFidF(E)3.根據參考程序（見程序設計指導），實現預測分析器的工作流程。#define _CRT_SECURE_NO_WARNINGS#include#includestruct anlysischar vn;char vt;char rs20;productions19 = E,n,TX , E,i,TX , E,(,TX , X,+

19、,+TX , X,-,-TX , X,), , X,#, , T,n,FY , T,i,FY , T,(,FY , Y,*,*FY , Y,/,/FY , Y,+, , Y,-, , Y,), , Y,#, , F,n,n , F,i,i , F,(,(E) ,;char stack50, a50, token20;char gettop()char top;int j = strlen(stack) - 1;top = stackj;return top;int is_vn(char x)int i, c;for (i = 0;i19;i+)if (productionsi.vn = x)c

20、 = 1;return c;c = 0;return c;void pop()int j;j = strlen(stack) - 1;stackj = 0;void push()strcat(stack, token);void inv()char temp;int n = strlen(token);int i, j, m = (n - 2) / 2;for (i = 0;i = m;i+)j = n - 1 - i;temp = tokeni;tokeni = tokenj;tokenj = temp;void LL1driver(char a)stack0 = #;stack1 = E;

21、printf(n stack=%s,a=%s, stack, a);int k = 0;char x;dostart: x = gettop();if (is_vn(x)for (int i = 0;i = 19;i+)if (productionsi.vt = ak) & (productionsi.vn = x)for (int j = 0;jid+-*/()=#=3、 根據參考程序（見課本P137 程序4-5），實現算符優先分析器的工作流程。程序設計指導：1、 本次實驗要完成的程序功能為：用程序實現算符優先分析器的工作流程，根據不斷地查找指定文法得出的算符優先矩陣，最終判斷輸入串是否符合

22、該文法的語法要求；2、 首先，在本次實驗的預習報告中要先完成實驗原理部分以及實驗步驟中的前面兩條；3、 程序中用到的關鍵函數的說明：l IsHigherThan（）：用來返回兩個終結符之間是否有大于關系；l IsLowerThan（）：用來返回兩個終結符之間是否有小于關系；l IsEqualTo（）：用來返回兩個終結符之間是否有等于關系；l Reduce（）：把滿足當前應被規約的最左子串條件的字符串進行規約；l parser（）：根據算符優先分析算法設計的分析函數。#define _CRT_SECURE_NO_WARNINGS#include #include #include #includ

23、e # define SUCCESS 1# define ERROR 0# define MAXINPUT 300# define MAXSTACK 100char stackMAXSTACK, aMAXINPUT;struct relationschar row; /行char colum; /列char rel; /大小關系table70 = +,+, ,/1 +,-, ,/2 +,), ,/3 +,#, ,/4 -,+, ,/5 -,-, ,/6 -,), ,/7 -,#, ,/8 *,+, ,/9 *,-, ,/10 *,), ,/11 *,#, ,/12 *,*, ,/13 *,/,

24、 ,/14 /,+, ,/15 /,-, ,/16 /,), ,/17 /,#, ,/18 /,*, ,/19 /,/, ,/20 ),+, ,/21 ),-, ,/22 ),), ,/23 ),#, ,/24 ),*, ,/25 ),/, ,/26 n,+, ,/27 n,-, ,/28 n,), ,/29 n,#, ,/30 n,*, ,/31 n,/, ,/32 i,+, ,/33 i,-, ,/34 i,), ,/35 i,#, ,/36 i,*, ,/37 i,/, ,/38 +,*, ,/39 +,/, ,/40 +,(, ,/41 +,n, ,/42 +,i, ,/43 -,*,

25、 ,/44 -,/, ,/45 -,(, ,/46 -,n, ,/47 -,i, ,/48 *,(, ,/49 *,n, ,/50 *,i, ,/51 /,(, ,/52 /,n, ,/53 /,i, ,/54 (,+, ,/55 (,-, ,/56 (,*, ,/57 (,/, ,/58 (,(, ,/59 (,),= ,/60 (,n, ,/61 (,i, ,/62 #,+, ,/63 #,-, ,/64 #,*, ,/65 #,/, ,/66 #,(, ,/67 #,n, ,/68 #,i,返回1，否則返回0for (int i = 0;i )return 1;return 0;int

26、IsLowerThan(char stk, char cmp) / 返回1，否則返回0for (int i = 0;i = 69;i+)if (tablei.row = stk) & (tablei.colum = cmp) & (tablei.rel = )return 1;return 0;int IsEqualTo(char stk, char cmp) / =返回1，否則返回0for (int i = 0;i = 69;i+)if (tablei.row = stk) & (tablei.colum = cmp) & (tablei.rel = =)return 1;return 0;char Reduce(int begin, int end, int len) /歸約char token10;for (int i = 0;ilen;i+) /將要進行歸約的字符串存入tokentokeni = stackbegin + i;tokenlen = 0;/查找歸約表，返回歸約值for (int j = 0;j21;j+)if (strcmp(token, p