程序编译原理实验情况报告.doc

《程序编译原理实验情况报告.doc》由会员分享，可在线阅读，更多相关《程序编译原理实验情况报告.doc（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实验一 词法分析程序实现一、实验目的与要求一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中， 将字符流形式的源程序转化为一个由各类单词符号组成的流的词法分析方法二、实验内容二、实验内容 基本实验题目：基本实验题目：若某一程序设计语言中的单词包括五个关键字 begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个 算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码参见表 I） 。表 I 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif

2、3IFthen4THENelse5ELSE标识符6ID字母打头的字母数字串无符号常数7UCON机内二进制表示11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI输入：输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将 结果放到某个文件中。对于标识符和无符号常数，CLASS 字段为相应的类别码的助记符； VALUE 字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码 形式，仅需在二元式的 CLASS 字段上放置相应单词的类别码的助记符，VALU

3、E 字段则为 “空” 。三、实现方法与环境三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其 一是根据对语言中各类单词的某种描述或定义（如 BNF） ，用手工的方式（例如可用 C 语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状 态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图 直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动 生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时， 词法分析程序所应进行的语义处理工作，然后由一个所谓词

4、法分析程序的构造程序对上述 信息进行加工。如美国 BELL 实验室研制的 LEX 就是一个被广泛使用的词法分析程序的自 动生成工具。 处理过程简述：处理过程简述：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为 每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到 了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移 时所需执行的语义动作，就可以据此构造词法分析程序了。 为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编 译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程 序的输

5、入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋 值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符 的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把 后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得 一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造 好） ，若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。 采用上述策略后，针对表 I 中的部分单词可以参考教材 P80 的图 3-22（见图 1）图 1 识别表 I 所列语言中的部分单

6、词的 DFA 及相关的语义过程图图 1 中所出现的语义变量及语义函数的含义和功能说明如下：函数函数 GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量 ch，然后把扫描指示器前推一个字符位置。字符数组字符数组 TOKEN：用来依次存放一个单词词文中的各个字符。函数函数 CAT：每调用一次，就把当前 ch 中的字符拼接于 TOKEN 中所存字符串的右边。函数函数 LOOKUP：每调用一次，就以 TOKEN 中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量 c；否则将 c 置为零。函数函数 RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回

7、多读的那个字符） 。函数函数 OUT：一般仅在进入终态时调用此函数，调用的形式为 OUT(c，VAL)。其中，实参 c 为相应单词的类别码助记符；实参 VAL 为 TOKEN（即词文）或为空串。函数 OUT 的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用 LEX 等工具生 成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。 四源程序四源程序 #include #include #include #include #define ID 6 #define INT

8、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 *KeyWordTableMAX_KEY_NUMBER=“begin“,“end“, “if“,

9、“then“, “else“, KEY_WORD_END; char TOKEN20=“; 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; i

10、nt Class; /用于表示类的词 int ICON; float FCON; static int CurrentState; /用于目前的当前状态,初始值:0int 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(KeyWordTablen,

11、 KEY_WORD_END) /strcmp 比较两串是否相同，若相 同返回 0 if (!strcmp(KeyWordTablen, token) /比较 token 所指向的关键字和保留字表中哪 个关键字相符 return n+1; /根据单词分类码表 I，设置正确的关键字类别码，并返回此类别 码的值 break; n+; return 6; /单词不是关键字，而是标识符 /输出分析结果 void out (int i, char* pStr) char Mnemonic5; if(1=i) strcpy(Mnemonic,“BEGIN“); else if(2=i) strcpy(Mne

12、monic,“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

13、,“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

14、“); else strcpy(Mnemonic,“Unkown Type“); printf(“(%s )对应%sn“,Mnemonic,pStr); /报错 void report_error (int row) printf(“%s Error! In the %d rown“,TOKEN,row); /扫描程序 void scanner(FILE *fp)/总的判断函数开始就应该判断已读取的字符是否为空字符，不为则 不用再读，直接进行判断，否则再读 int i, c; fseek(fp,-1,1);/首先回溯一个字符，就是将文件所有的字符都在 scanner 内部判断，外 部 whil

15、e 循环不会浪费任何字符 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!*/ TOKEN0=ch; ch=fgetc (fp); i=1; while (isalnum (ch) TOKENi=ch; i+; ch=fgetc (fp); TOKENi= 0; fseek(fp,-

16、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); TOKENi=ch; i+; TOKENi=0;/为随时输出字符串做准备 Type=GetChar(ch); EXCUTE (CurrentState,Type,fp,TOKEN,row,i);

17、 while(CurrentState!=EndState); else switch(ch) case ) out (NE,“=“); 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 s

18、ymbol,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(“无符

19、号数的第一个字符是非法的！n“);break;case 1:switch (symbol)case DIGIT: w=w*10+d;break; /CurrentState=1case POINT: CurrentState=2;break;case POWER: CurrentState=4;break;default: if (ch!=EOF)/如果是因为读到文件结束字符而终止识别，就不应该回 退，否则可能造成死循环fseek(fp,-1,1);/遇到其他的字符，可能是一条语句中的其他字符， 需后退，因为主函数外层循环每次都要读一个字符进行判断，而这个判读不回溯，所以在 内部把这个多读的字

20、符回溯ICON=w;CurrentState=EndState; JudgeStrindex-1=0;printf(“(UCON,%i)对应%sn“,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;JudgeStrindex-1=0;printf(“(UCON,%f)

21、对应于%sn“,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;ca

22、se 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;/判断一个无符号数的 最后一个字符

23、应该都是多余读取的，所以为了防止引起后面再次判断下一无符号数时产生呑字符的现象，都应该回溯一个字符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;JudgeStrindex-1=0;printf(“(UCON,%f)对应 %sn“,FCON,JudgeStr);break;break;return CurrentState;/无符号数判断过程中的字符类型判断程序 int GetC

24、har (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(“第一个字母是：%cn“,ch);do scanner(p); while(ch=fgetc(p)!=EOF); fclose(p); return 0; 五测试用例及运行结果分析五测试用例及运行结果分析 测试用例：begin 8E-5+8*7/1.5 运行结果：