编译原理实验说课讲解

1、实验一 词法分析一、实验目的 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词， 即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内 部编码及单词符号自身值。二、实验题目如源程序为 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，”）”三、 实验理论依据（一）识别各种单词符号程序语言的单词符号一般分为五种：关键字（保留字/基本字）if、while、begin标识符：常量名、变量名 常数：34、56.78、true、 a'运算符：+、-、*、/、and、or、.界限符：,;（）/*识别单词：掌握单词的构成规则很重要标

3、识符的识别：字母|下划线+（字母/数字/下划线）关键字的识别：与标识符相同，最后查表常数的识别界符和算符的识别1-1时简筆谨言进齐诃法分析笛枚态转換圈图1-1大多数程序设计语言的单词符号都可以用转换图来识别，如图词法分析器输出的单词符号常常表示为二元式： （单词种别，单词符号的属性值） 单词种别通常用整数编码，如 1 代表关键字， 2 代表标识符等 关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起 来较为方便。标识符一般统归为一种 常数按类型（整、实、布尔等）分种 运算符可采用一符一种的方法。界符一般一符一种的分法。（二）超前搜索方法 词法分析时，常常会用到超前搜索方法。如

4、当前待分析字符串为“a>+”，当前字符为“”，此时，分析器倒底是将其分 析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字 符'+'，这时可知应将'>'解释为大于运算符。但此时，超前读了一个字符 '+'，所 以要回退一个字符，词法分析器才能正常运行。又比如： +'分析为正号还是加法 符号（三）预处理 预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及 删除注解等。由一个预处理子程序来完成。四、词法分析器的设计1、设计方法：2、写出该语言的词法规则。3、

5、把词法规则转换为相应的状态转换图。4、把各转换图的初态连在一起，构成识别该语言的自动机5、设计扫描器6、把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就 调用扫描器。7、扫描器从初态出发，当识别一个单词后便进入终态，送出二元式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 且不重复的整数 */else p=0;/* 不是保留字则用于返回的 p=0*/return(p);char alphaprocess(char buffer) int atype; /* 保留字数组中的位置 */ in

8、t i=-1;char alphatp20;while (isalpha(buffer)|(isdigit(buffer)|buffer='_') alphatp+i=buffer;buffer=fgetc(fp); /* 读一个完整的单词放入 alphatp 数组中 */ alphatpi+1='0'atype=search(alphatp,1);/* 对此单词调用 search 函数判断类型 */ 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 判断小数 */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 区分注释符号和除号 */ 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( ) 函数：从磁盘文件读取一个字符 */ 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;六、实验结果程序添加了识别小数，识别注释符，识别自加自减符号，识别头文件，识别转 义符号，识别或与符号，识别单引号和双引号，识别中括号，识别格式符，结果如 图 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)分析法一、实验目的：根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。 本次实验的目的主要是加深对预测分析LL(1)分析法的理解。二、实验题目实验规定对下列文法，用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;/* 字符个数*/ 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）分析表为:状态ACTIONGOTOab#S"bS0S3S412S1accS2S6S75S3S3S48S4r3r3S5r1S6S6S79S7r3S8r2r2S9r2（1）若输入baba#,则输出为:步骤状态栈符号栈输入串ACTION10#bab

45、a#S42o04#baba#r32302#Baba#S64026#Baba#S750267#Baba#error（2）若输入bb#，则输出为：GOTO步骤状态栈符号栈输入串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