編譯原理實驗說課講解

1、實驗一 詞法分析一、實驗目的 編制一個讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞， 即基本保留字、標識符、常數(shù)、運算符、分隔符五大類。并依次輸出各個單詞的內 部編碼及單詞符號自身值。二、實驗題目如源程序為 C 語言。輸入如下一段：main（）int a=-5,b=4,j;if（a>=b）j=a-b;要求輸出如下：else j=b-a;/ c”（ 2， ” main”）（5，”（”）（ 5， ”） ”）（5，”）”（ 1， ”int ）”（ 2， ”a）”（4，”=”）（3，”-5”）（5，”,）”（2，”b”）（4，”=”）（3，”4”）（5，”,）”（2，”j）”（5，

2、”;）”（1，”if）”（5，”（”）（ 2， ”a”）（4，”>=”）（2，”b”）（5，”）”）（2，”j ）”（4，”=”）（2，”a”）（4，”-”）（2，”b”）（5，”;）”（1，”else）”（2，”j）”（4，”=”）（2，”b”）（4，”-”）（2，”a”）（5，”;）”（5，”）”三、 實驗理論依據(jù)（一）識別各種單詞符號程序語言的單詞符號一般分為五種：關鍵字（保留字/基本字）if、while、begin標識符：常量名、變量名 常數(shù)：34、56.78、true、 a'運算符：+、-、*、/、and、or、.界限符：,;（）/*識別單詞：掌握單詞的構成規(guī)則很重要標

3、識符的識別：字母|下劃線+（字母/數(shù)字/下劃線）關鍵字的識別：與標識符相同，最后查表常數(shù)的識別界符和算符的識別1-1時簡筆謹言進齊訶法分析笛枚態(tài)轉換圈圖1-1大多數(shù)程序設計語言的單詞符號都可以用轉換圖來識別，如圖詞法分析器輸出的單詞符號常常表示為二元式： （單詞種別，單詞符號的屬性值） 單詞種別通常用整數(shù)編碼，如 1 代表關鍵字， 2 代表標識符等 關鍵字可視其全體為一種，也可以一字一種。采用一字一種得分法實際處理起 來較為方便。標識符一般統(tǒng)歸為一種 常數(shù)按類型（整、實、布爾等）分種 運算符可采用一符一種的方法。界符一般一符一種的分法。（二）超前搜索方法 詞法分析時，常常會用到超前搜索方法。如

4、當前待分析字符串為“a>+”，當前字符為“”，此時，分析器倒底是將其分 析為大于關系運算符還是大于等于關系運算符呢？顯然，只有知道下一個字符是什么才能下結論。于是分析器讀入下一個字 符'+'，這時可知應將'>'解釋為大于運算符。但此時，超前讀了一個字符 '+'，所 以要回退一個字符，詞法分析器才能正常運行。又比如： +'分析為正號還是加法 符號（三）預處理 預處理工作包括對空白符、跳格符、回車符和換行符等編輯性字符的處理，及 刪除注解等。由一個預處理子程序來完成。四、詞法分析器的設計1、設計方法：2、寫出該語言的詞法規(guī)則。3、

5、把詞法規(guī)則轉換為相應的狀態(tài)轉換圖。4、把各轉換圖的初態(tài)連在一起，構成識別該語言的自動機5、設計掃描器6、把掃描器作為語法分析的一個過程，當語法分析需要一個單詞時，就 調用掃描器。7、掃描器從初態(tài)出發(fā)，當識別一個單詞后便進入終態(tài)，送出二元式N error圖1-2取單詞程序框圖五、程序代碼#include <stdio.h>#include <string.h>FILE *fp;char cbuffer;char *key8="if","else","for","while","do&

6、quot;,"return","break","continue"int atype,id=4;int isalpha( char c) if(c<='z')&&(c>='a')|(c<='Z')&&(c>='A')return 1;else return 0;int isdigit(char c)if(c>='0'&&c<='9')return 1;els

7、e return 0;int search(char searchchar ,int wordtype) /* 判斷單詞是保留字還是標識符 */int i=0;int p;switch (wordtype)case 1:for (i=0;i<=7;i+)if (strcmp(keyi,searchchar)=0) p=i+1; break; /* 是保留字則 p 為非 0 且不重復的整數(shù) */else p=0;/* 不是保留字則用于返回的 p=0*/return(p);char alphaprocess(char buffer) int atype; /* 保留字數(shù)組中的位置 */ in

8、t i=-1;char alphatp20;while (isalpha(buffer)|(isdigit(buffer)|buffer='_') alphatp+i=buffer;buffer=fgetc(fp); /* 讀一個完整的單詞放入 alphatp 數(shù)組中 */ alphatpi+1='0'atype=search(alphatp,1);/* 對此單詞調用 search 函數(shù)判斷類型 */ if(atype!=0) printf("(%d,"%s")n",atype-1,alphatp); id=1; else

9、 printf("(2,"%s")n",alphatp); id=2; return (buffer);char digitprocess(char buffer)int i=-1;/*1 判斷小數(shù) */char digittp20;while (isdigit(buffer)|buffer='.')digittp+i=buffer; buffer=fgetc(fp);digittpi+1='0' printf("(3,"%s")n",digittp);id=3;return(buf

10、fer);char otherprocess(char buffer)char ch20; ch0=buffer;ch1='0' if(ch0=','|ch0=''|ch0=''|ch0=''|ch0='('|ch0=')') printf("(5,"%s")n",ch);buffer=fgetc(fp);id=5;return(buffer); if(ch0='/') buffer=fgetc(fp); if(buffer=&

11、#39;*') /*2 區(qū)分注釋符號和除號 */ ch1=buffer; buffer=fgetc(fp); while(buffer!='*') buffer=fgetc(fp); ch2=buffer; buffer=fgetc(fp); if(buffer='/')ch3=buffer; ch4='0'printf("(5,"%s")n",ch);else printf("(4,"%s")n",ch);id=4;return(buffer); buffe

12、r=fgetc(fp);id=5; return(buffer);if(ch0='*') printf("(4,"%s")n",ch); buffer=fgetc(fp);id=4; return(buffer);if(ch0='='|ch0='!'|ch0='<'|ch0='>') buffer=fgetc(fp);if(buffer='=') ch1=buffer; ch2='0' printf("(4,"%

13、s")n",ch);else printf("(4,"%s")n",ch);id=4;return(buffer);buffer=fgetc(fp);id=4;return(buffer);if(ch0='+'|ch0='-') if(id=4) /* 在當前符號以前是運算符，則此時為正負號 */ buffer=fgetc(fp);ch1=buffer;ch2='0'printf("(3,"%s")n",ch);id=3;buffer=fgetc(

14、fp);return(buffer);ch1='0'printf("(4,"%s")n",ch);buffer=fgetc(fp);id=4;return(buffer);if(ch0='#')/*3 識別頭文件 */ char t20; int i=0; t0=ch0; buffer=fgetc(fp); while(isalpha(buffer)|buffer=' '|buffer='<'|buffer='>') t+i=buffer;buffer=fgetc

15、(fp);ti+1='0' printf("(6,"%s")n",t); id=6;return (buffer);if(ch0='') /*4 識別轉義符號 */ buffer=fgetc(fp);ch1=buffer;printf("(6,"%s")n",ch);buffer=fgetc(fp);return(buffer);判斷或與 */判斷雙引號和單引號 */if(ch0='|'|ch0='&') /*5 buffer=fgetc(fp

16、);if(ch0=buffer)ch1=buffer;ch2='0'printf("(4,"%s")n",ch);buffer=fgetc(fp); return(buffer);if(ch0='"'|ch0=''') /*6 printf("(5,"%s")n",ch);id=5;buffer=fgetc(fp);return(buffer);int main()if (fp=fopen("example.c","r&

17、quot;)=NULL)/* 只讀方式打開一個文件 */printf("error");else cbuffer = fgetc(fp); /*fgetc( ) 函數(shù)：從磁盤文件讀取一個字符 */ while (cbuffer!=EOF)if(cbuffer=' '|cbuffer='n')/* 掠過空格和回車符 */cbuffer=fgetc(fp);elseif(isalpha(cbuffer) cbuffer=alphaprocess(cbuffer); elseif (isdigit(cbuffer) cbuffer=digitpro

18、cess(cbuffer);else cbuffer=otherprocess(cbuffer);return 0;六、實驗結果程序添加了識別小數(shù)，識別注釋符，識別自加自減符號，識別頭文件，識別轉 義符號，識別或與符號，識別單引號和雙引號，識別中括號，識別格式符，結果如 圖 1-3 所示：-1url4> > > > / > >> > 曰 Riu>+-H4un +* 72 "2 *&: lr j 叮"二二二"丄二器二二二二二二 7 ± 亠二一丄建“二直 g racvia- -fezrJ-4-.i

19、c 日 > yJ-曰一；/初；14：/亠 D- 晶,»fj s J-II口EC5.K2理応9之吐 T5MT3t.M£24HF:N4r:1l>u 斗3匸3-1丘出1:之42灶 4n C:L c c;匚 Jf fl.c Jrt:c Jk- tCJC .-_L>C .»k4J_L-c-.JL.r- c-lr_ Jf實驗二 LL (1)分析法一、實驗目的：根據(jù)某一文法編制調試LL(1)分析程序，以便對任意輸入的符號串進行分析。 本次實驗的目的主要是加深對預測分析LL(1)分析法的理解。二、實驗題目實驗規(guī)定對下列文法，用LL( 1)分析法對任意輸入的符號串

20、進行分析:(1) E:=TG(2) G:=+TG(3) G:= £(4) T:=FS(5) S:=*FS(6) S:=£(7) F:=(E)(8) F:=i若輸入串為i+i*i# ，則輸出為：步分析棧剩余串產生式1#i+i*iETG2#Gi+i*iT FS3#GSi+i*iF i4#GSi+i*ii5#G+i*iS ?6#+i*iG+TG7#GT+i*i+LL(1)的分析表為:i+*()#說明E eeSelect(E TG)= (,iGggigiSeleet (Gf +TG)= +Seleet (G ?)= #,) ttSeleet (T FS)= (,iSsissisiS

21、eleet (S *FS)= *Seleet (4 ?)= #,) +F flfSeleet (F (E)= (Seleet (F i)= i三、程序代碼#in elude <iostream>#in elude <cstdio>#in elude <estri ng>using n amespaee std;char A20;/* 分析棧 */ehar B20;/* 剩余串 */ehar v120= 'i','+','*','(',')','#' /* 終結符

22、*/ehar v220= 'E','G',T,'S','F' /*非終結符*/int j=0,b=0,top=0,l;/*L 為輸入串長度*/typedef struet type/*產生式類型定義*/ehar origin;/* 大寫字符 */ehar array5;/*產生式右邊字符*/int length;/* 字符個數(shù)*/ type;type e,t,g,g1,s,s1,f,f1;/* 結構體變量*/type C1010,cha;/* 預測分析表*/void print()/* 輸出分析棧 */int a;/* 指針 */

23、for(a=0; a<=top+1; a+) printf("%c",Aa);printf("tt");void print1()/* 輸出剩余串 */int j;for(j=0; j<b; j+) /*輸出對齊符 */ printf(" ");for(j=b; j<=l; j+)printf("%c",Bj);printf("ttt");int main()/* 把文法產生式賦值結構體 */ e.origin='E'strcpy(e.array,"T

24、G");e.length = 2;t.origin='T' strcpy(t.array,"FS"); t.length = 2;g.origin='G' strcpy(g.array,"+TG"); g.length = 3;g1.origin='G'g1.array0=s：strcpy(g1.array,"A");g1.length = 1;s.origin='S'strcpy(s.array,"*FS");s.length = 3;s1

25、.origin='S's1.array0=s：strcpy(s1.array,"A");s1.length = 1;f.origin='F'strcpy(f.array,"(E)");f.length = 1;f1.origin='F'strcpy(f1.array,"i");f1.length = 1;for(int m=0; m<=4; m+) /* 初始化分析表 */ for(int n=0; n<=5; n+)Cmn.origin='N'/* 全部賦為

26、空 */ cha.origin = 'N'/* 填充分析表 */C00=e;C03=e;C11=g;C14=g1;C15=g1;C20=t;C23=t;C31=s1;C32=s;C34=C35=s1;C40=f1;C43=f;char ch;do/* 讀入分析串 */ scanf("%c",&ch);if (ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')

27、9;)&&(ch!='#') printf(" 輸入串中有非法字符 n");break;Bj=ch;j+;while(ch!='#');l=j;ch=B0;Atop='#'A+top='E'printf(" 步驟 tt 分析棧 tt int k = 1;int flag = false;int finish = false;int n,m;dochar x; x=Atop-; printf("%d",k+); printf("tt");/* 分析

28、串長度 */* 當前分析字符 */*'#','E' 進棧 */ 剩余字符 tt 所用產生式 n");/*x 為當前棧頂字符 */* 判斷是否為終結符 */for(j=0; j<=5; j+)if(x=v1j)flag=1;break;if(flag=1)/* 如果是終結符 */ if(x='#' && ch = '#') finish=1;/* 結束標記 */ print(); print1(); printf("acc!n"); getchar();/* 接受 */ getch

29、ar(); break; if(x=ch) print(); print1(); printf("%c 匹配 n",ch); ch=B+b;/* 下一個輸入字符 */ flag=0;/* 恢復標記 */else/*出錯處理*/ print(); print1();printf("%c出錯n”,ch);/*輸出出錯終結符*/ break;else/*非終結符處理*/for(j=0; j<=4; j+)if(x=v2j)m=j; /* 行號*/break;for(j=0; j<=5; j+)if(ch=v1j)n=j;/* 列號 */break;cha=C

30、mn;if(cha.origin!='N')/* 判斷是否為空 */print();print1();printf("%c->",cha.origin);/* 輸出產生式 */for(j=0; j<cha.length; j+)printf("%c",cha.arrayj);printf("n");for(j=(cha.length-1); j>=0; j-) /*產生式逆序入棧 */A+top=cha.arrayj;if(Atop='A')/* 為空則不進棧 */top-;elsep

31、rint();print1();printf("%c 出錯 C 表不存在 n",ch);/* 輸出出錯終結符 */ break; while(true);return 0;四、實驗結果輸入字符串i+i*i#進行分析，如圖2-1所示:QI D諦國侯螫二迄hiy“rii2e:xa012345673 4 Lf> -$JJ f DO t 1 l l i J -"-1ff1<R牝粘和右右黃鴕兀曙曙霑孔雹昭巧需卑十;Tl;ISFSilzl 51SFSis利余字汗i+i+i« i+i*ifll+i*i«+i*i«hHiXiifif心*i

32、1i#L«所曲產生式E-?TG 7->FSF->i 三匚!陽 s->_ G-+TG- El配-應F->1i匹配 s->m 咂配F->i 血甲 s-v g->a mJ圖2-1輸入字符串i)#進行分析，如圖2-2所示：Ml «x 杖 T s s s TE cC-GCIG yT. ±1 ±> ±> £1rocess rettorned 0 (OiO) m日 any key tc continue.剩余字符 i什 i片 i片 i”)fi%日畑二niizn time ;所月嚴生云E->

33、TG T >F5F-X 晉己G-»岀錯4.c'33 s圖2-2實驗三 逆波蘭式的產生及計算一、實驗目的將用中綴式表示的算術表達式轉換為用逆波蘭式表示的算術表達式，并計算用 逆波蘭式來表示的算術表達式的值二、實驗題目如輸入如下： 21+（42-2）*15+6 ） -18#輸出為：原來表達式： 21+（ 42-2）*15+6 ）- 18#后綴表達式： 21&42&2&-15&*6&+18&- 計算結果： 609三、算法流程圖圖3-1生成逆波蘭式的程序流程圖圖3-2計算逆波蘭式的程序流程圖四、程序代碼#i nclude <

34、iostream> #in elude <cstdio> #in elude <cstri ng> using n amespace std;char ch; int top,le ngth,t; char ex100; char str100;double calculate。double d;double stack100,xx = 0;top = -1;for(i nt t = 0; t < le ngth;)ch = ext;switch(ch)case '+':stacktop-1=stacktop-1+stacktop; top-

35、;t+; break;case '-': stacktop-1=stacktop-1-stacktop; top-; t+; break;case '*': stacktop-1=stacktop-1*stacktop; top-; t+; break;case '/': if(stacktop!=0) stacktop-1=stacktop-1/stacktop;else printf("nt 除零錯誤 !n"); break; /* 異常退出 */ top-;t+; break;case 'A': /sta

36、cktop=stacktop*stacktop; xx = stacktop-1;for(int i = 0; i < stacktop-1; i+)xx = xx*stacktop-1; stacktop-1 = xx; top-; t+; break;default :d=0;int flag = false;while(ch = '' | (ch>='0'&&ch<='9')if(ch = '')flag = true;t+;ch = ext; continue; d=10*d+ch-

37、9;0' t+; ch=ext;if(ch = '.')double temp = 0;t+;ch = ext;int k = 1;while( (ch>='0'&&ch<='9') | ch = '') if(ch = '')flag = true;t+;ch = ext; continue;double temp1 = 1;for(int s = 0; s < k; s+)temp1 *= 0.1;temp = temp + temp1*(ch-'0')

38、; t+;ch=ext;d += temp;if(ch = '&')t+;ch = ext;top+;if(flag = true)d = -d;stacktop=d;return stack0;int main()char stack100;memset(stack,0,sizeof(stack);length = 0;while(true)scanf("%c",&ch);if(ch = '#')break;strlength+ = ch;strlength = '0'printf(" 原式： %s

39、n",str); t = 0;top = -1;for(int i = 0; i < length; )ch = stri; switch(ch)case '+':case '-':while(top>=0 && stacktop!='(') ext=stacktop;top-;t+; top+; stacktop=ch; i+; break;case '/':while(stacktop='*'|stacktop='/' | stacktop = 'A

40、') ext=stacktop;top-;t+; top+; stacktop=ch; i+;break;case 'A': while(stacktop='A') ext=stacktop; top-; t+; top+; stacktop=ch;i+; break;case '(': top+; stacktop=ch; i+;break;case ')': while( stacktop!= '(' && top >= 0 ) ext=stacktop;top-;t+;top-;

41、i+;break;default:int flag = false;while(ch = '' | (ch>='0'&&ch<='9') | ch = '.') if(ch = '')flag = true;i+; ch = stri; continue;ext=ch;t+; /*ex 中存放逆波蘭式 */ i+; /*str 中存放中綴表達式 */ ch=stri;if(flag)ext = ''t+;ext='&'t+;break;while(

42、top>=0)ext=stacktop;t+;top-;ext = '0'printf(" 逆波蘭： %sn",ex);length = t;printf(" 得出： %fn",calculate();return 0;五、實驗結果輸入表達式 21+(42-2)*15+2)-18#進行計算，結果如圖 3-3 所示：.(DnuwqxIOQ 口 4 All>£ AUMntACDp»馭寸怕 H 八 suii：|. COHSffls (OMO 0 g 也 aoop§§§ “rpe 丈出

43、f禹境S血署g戊咄舞®SftIM g)+gu睡 誌./©蕊IA¥g-170 ®ssM44fcffitt£(cxl*govg)+g w 坦«<«*BrKIH4lICO 口-HAm/ Auie 茴如rnMd sLn奪r-M- euIHF !WEq.noaJia (0X0) 0 po)口 ml-rDhssnJoQAn.000000 .s “田惡 i雯It寓蓋已禹離其品 哺>異 S&十已Aee3)十& “肓畦 訪1金十曰¥(甲尋)十岳 氏！而 UAlllii 常<口 產實驗四 LR（1）分

44、析法一、實驗目的構造LR（1）分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法 識別的句子，了解LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分 析方法二、實驗題目：1、對下列文法，用LR（ 1）分析法對任意輸入的符號串進行分析:（0）E->S（1）S->BB（2）B->aB（3）B->b2、LR（1）分析表為:狀態(tài)ACTIONGOTOab#S"bS0S3S412S1accS2S6S75S3S3S48S4r3r3S5r1S6S6S79S7r3S8r2r2S9r2（1）若輸入baba#,則輸出為:步驟狀態(tài)棧符號棧輸入串ACTION10#bab

45、a#S42o04#baba#r32302#Baba#S64026#Baba#S750267#Baba#error（2）若輸入bb#，則輸出為：GOTO步驟狀態(tài)棧符號棧輸入串10#bb#204#bb#302#Bb#4027#Bb#5025#BB#601#S#ACTIONS4r3S7r3r1accGOTO251三、算法流程圖四、程序代碼#in clude<stdio.h>#in clude<stri ng.h>FACTION 表 */#in clude<stdlib.h>char *actio n103="S3#","S4#&quo

46、t;,NULL,NULL,NULL,"acc", "S6#","S7#",NULL, "S3#","S4#",NULL, "r3#","r3#",NULL, NULL,NULL,"r1#","S6#","S7#",NULL,NULL,NULL,"r3#","r2#","r2#",NULL,NULL,NULL,"r2#"

47、 int goto1102=1,2,0,0,0,5,0,8,0,0,0,0,0,9,0,0,0,0,0,0;char vt3='a','b','#'char vn2='S','B'/*QOTO 表 */* 存放非終結符 */* 存放終結符 */char *LR4="E->S#","S->BB#","B->aB#","B->b#"/* 存放產生式 */ int a10;char b10,c10,c1;int top1,top2,top3,top,m,n;int main()int g,h,i,j,k,l,p,y,z,count;char x,copy10,copy110;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0='#'count=0;z=0;printf(" 請輸入表達式 :n");do