词法分析与算符优先

1、精选优质文档-倾情为你奉上计算机科学与技术学院课程设计报告 （ 2011 2012 学年度 第 1 学期 ）课程名称程序设计与编译设计题目词法分析与算符优先姓名学号专业班级地点教师课程设计一、词法分析器1. 概述1.1 设计内容对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词法分析器的基本方法。利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二元式的代码。1.2 设计要求1. 对单词的构词规则有明确的定义；2. 编写的分析程序能够正确识别源程序中的单词符号； 3. 识别出的单词以<单词符号，种别码>的形式保存在符号表中（链表）；2.

2、2 实验原理（1）算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号（2）其基本思想是根据扫描到的单词符号的第一个字符的种类，拼出相应的单词符号2. 程序设计#include<stdio.h>#include<stdlib.h>#include <ctype.h> #include<string.h>int main()FILE *fp,*fp1;int hanjsq=1;/行计数器，保存行号int guanjz(char ch1);/关键字和标识符判断char ch,infile15,outfile15;/定义输入和输出文件名p

3、rintf("*Enter the infile name*n");scanf("%s",infile);/输入需要扫描的文件名printf("*Enter the outfile name*n");scanf("%s",outfile);/输入需要另存为的文件名if(fp = fopen(infile,"r") = NULL)/打开需要扫描的文件printf("cannot open filen");exit(0);if(fp1 = fopen(outfile,"

4、w") = NULL)/打开需要存入的文件printf("cannot open filen");exit(0);printf("n*n");printf("* 开始进行词法分析 *n");printf("*n");printf("n*n");printf("行号字符串种别码n");printf("*n");fprintf(fp1,"*n");fprintf(fp1,"行号字符串种别码n");fprintf

5、(fp1,"*n");while(!feof(fp)ch=fgetc(fp);if(ch=10)hanjsq+;/*扫描头文件单词及保留字*/if(isalpha(ch) | ch='_')/如果第一个字符为字母或下划线则判断为标识符int i=0;char ch130;/假定每个标识符最长为ch1i+=ch;/将ch保存到ch10中并使i自加1while(!feof(fp)ch=fgetc(fp);if(ch=10)hanjsq+;/如果ch为换行符，则行计数器自加1if(isalpha(ch) | isdigit(ch) | ch='_'

6、)/如果ch为字母、数字或下划线就把ch放到ch1i中并使i自加1ch1i+=ch;if(ch='.')/如果ch为小数点则判断是否为头文件 if(ch=fgetc(fp)='h')/如果小数点后一位为h则判定其为头文件if(ch=10)hanjsq+;ch1i+='.'ch1i+='h'ch1i='0'/把结束标志放到ch1i中作为单词结束标志printf("line %d:%s83n",hanjsq,ch1);/以字符串形式输出ch1fprintf(fp1,"line %d:%s8

7、3n",hanjsq,ch1);break;else/如果小数点后一位不是h则判定其为标识符fseek(fp,-1,1);/fp回退1ch1i='0'/把结束标志放到ch1i中作为单词结束标志printf("line %d:%s%dn",hanjsq,ch1,guanjz(ch1);/以字符串形式输出ch1fprintf(fp1,"line %d:%s%dn",hanjsq,ch1,guanjz(ch1);break;if(!isalpha(ch) && !isdigit(ch) && ch!=&

8、#39;_' && ch!='.')/如果ch不为字母、数字、下划线和点时判断其为标识符ch1i='0'printf("line %d:%s%dn",hanjsq,ch1,guanjz(ch1);fprintf(fp1,"line %d:%s%dn",hanjsq,ch1,guanjz(ch1);break;/*扫描数字*/if(isdigit(ch) | ch='-')/如果ch为数字或'-'if(isdigit(ch)/如果ch为数字printf("li

9、ne %d:%c",hanjsq,ch);fprintf(fp1,"line %d:%c",hanjsq,ch);while(!feof(fp)ch=fgetc(fp);/预读一位如果ch为数字和点则循环输出if(isdigit(ch) | ch='.')printf("%c",ch);fprintf(fp1,"%c",ch);else/否则视为数字结束printf("46n");fprintf(fp1,"46n");fseek(fp,-1,1);/回退一位ch=

10、9;0'/置ch为0，以免影响下面误判并顺利退出扫描数字break;if(ch='-')/如果ch为'-'ch=fgetc(fp);/预读一位if(ch='-')/如果ch还是为'-'则判断为自减符'-'printf("line %d:-80n",hanjsq);fprintf(fp1,"line %d:-80n",hanjsq);if(ch='>')/如果ch为'>'，则判断为结构体运算符'->'pr

11、intf("line %d:->81n",hanjsq);fprintf(fp1,"line %d:->81n",hanjsq);if(isdigit(ch)/如果ch为数字则可能为减号或负号fseek(fp,-3,1);/回退3为判断ch=fgetc(fp);if(isdigit(ch)/如果ch为数字则判断'-'为减号 ch=fgetc(fp);printf("line %d:%c79n",hanjsq,ch);fprintf(fp1,"line %d:%c79n",hanjsq,c

12、h);else /否则判断'-'为负号ch=fgetc(fp);printf("line %d:%c",hanjsq,ch);fprintf(fp1,"line %d:%c",hanjsq,ch);while(!feof(fp)ch=fgetc(fp);/预读一位如果ch为数字和点则循环输出if(isdigit(ch) | ch='.')printf("%c",ch);fprintf(fp1,"%c",ch);else/否则视为数字结束printf("46n");

13、fprintf(fp1,"46n");fseek(fp,-1,1);/回退1break;/*扫描注释*/if(ch='/')/如果ch为'/'则可能为注释ch=fgetc(fp);/读下一个字符if(ch=10)hanjsq+;if(ch='/')/如果该字符也为'/'则判断为注释一行while(fgetc(fp)!=10);if(ch=10)hanjsq+;/直到遇到换行符出现才认为注释结束if(ch='*')/如果该字符为'*'则判断为注释多行/直到出现'*/'

14、;才认为注释结束while(!feof(fp)ch=fgetc(fp);if(ch=10)hanjsq+;if(ch='*')/出现'*'/且接着出现'/'if(ch=fgetc(fp)='/')break;else/否则原样输出'/'printf("line %d:/83n",hanjsq);fprintf(fp1,"line %d:/83n",hanjsq);fseek(fp,-1,1);/回退1break;/*扫描引号*/if(ch='"')/

15、出现引号int i=0;printf("line %d:%c82n",hanjsq,ch);fprintf(fp1,"line %d:%c82n",hanjsq,ch);printf("line %d:",hanjsq);fprintf(fp1,"line %d:",hanjsq);while(!feof(fp)/先整体输出引号内所有字符并定为第99类ch=fgetc(fp);i+;/用于积累回退长度if(ch=10)hanjsq+;if(ch!='"')if(ch!=32)printf(

16、"%c",ch);fprintf(fp1,"%c",ch);else break;printf("99n");fprintf(fp1,"99n");fseek(fp,-i,1);/回退到引号开始for(;i>0;i-)ch=fgetc(fp);if(ch=92)/如果ch为''则可能为转义字符char ch513="abfntv?'"0"/转义字符集ch=fgetc(fp);/预读一位for(int k=0;k<12;k+)/如果为转义字符则输出if

17、(ch=ch5k)printf("line %d:%c%dn",hanjsq,ch,k+33);fprintf(fp1,"line %d:%c%dn",hanjsq,ch,k+33);if(ch='d' && isdigit(fgetc(fp) && isdigit(fgetc(fp)/任意字符转换为三位八进制 fseek(fp,-2,1);printf("line %d:%c%c44n",hanjsq,fgetc(fp),fgetc(fp);fprintf(fp1,"line

18、 %d:%c%c44n",hanjsq,fgetc(fp),fgetc(fp);if(ch='x' && isdigit(fgetc(fp) && isdigit(fgetc(fp)/任意字符转换为二位十六进制 fseek(fp,-2,1);printf("line %d:%c%c45n",hanjsq,fgetc(fp),fgetc(fp);fprintf(fp1,"line %d:%c%c45n",hanjsq,fgetc(fp),fgetc(fp);if(ch='%')/如果

19、为'%'则可能为%s%c%dch=fgetc(fp);char bfh4="dcs"for(i=0;i<3;i+)if(bfhi=ch)printf("line %d:%c83n",hanjsq,ch);fprintf(fp1,"line %d:%c83n",hanjsq,ch);/*扫描其他符号*/if(!isdigit(ch) && !isalpha(ch) && ch!='_' && ch!='"' &&

20、; ch!='/')char ch214="#()'*:%"/定义部分单符号集char ch39="+?=|&!<>"/定义部分单符号或双符号（前半部分）集char ch49="+=|&="/定义部分双符号（后半部分）for(int i=0;i<13;i+)/判断单个符号if(ch=ch2i)printf("line %d:%c%dn",hanjsq,ch,i+48);fprintf(fp1,"line %d:%c%dn",hanjsq,

21、ch,i+48);for(int j=0;j<8;j+)/判断双符号if(ch=ch3j)/如果ch与ch3中第j个字符匹配ch=fgetc(fp);/预读一位/if(ch=10)hanjsq+;if(ch=ch4j)/且ch与ch4第j个匹配，则表示ch3j与ch4j连起来为一个双符号printf("line %d:%c%c%dn",hanjsq,ch3j,ch4j,j+69);fprintf(fp1,"line %d:%c%c%dn",hanjsq,ch3j,ch4j,j+69);if(ch='<' &&

22、ch3j='<')/判断'<<'符printf("line %d:<<77n",hanjsq);fprintf(fp1,"line %d:<<77n",hanjsq);if(ch='>' && ch3j='>')/判断'>>'符printf("line %d:>>78n",hanjsq);fprintf(fp1,"line %d:>>78n&

23、quot;,hanjsq);else/否则表示ch3j为单符号，不是双符号的一部分printf("line %d:%c%dn",hanjsq,ch3j,j+61);fprintf(fp1,"line %d:%c%dn",hanjsq,ch3j,j+61);fseek(fp,-1,1);/*/printf("*n");printf("* 词法分析结束 *n");printf("* 分析结果保存在文件%s中 *n",outfile);printf("* 欢迎下次使用，谢谢！ *n"

24、;);printf("*n");fprintf(fp1,"*n");fprintf(fp1,"* 词法分析结束 *n");fprintf(fp1,"* 欢迎下次使用，谢谢！ *n");fprintf(fp1,"*n");int guanjz(char ch1)/关键字和标识符判断char ch2329="auto","double","int","struct","break","els

25、e","long","switch","case","enum","register","typedef","char","extern","return","union","const","float","short","unsigned","continue","for&qu

26、ot;,"signed","void","default","goto","sizeof","volatile","do","while","static","if"/定义关键字集for(int i=0;i<32;i+)/逐个比对如果为关键字则返回类别i+1if(!strcmp(ch1,ch2i)return i+1;return 47;/否则返回一般标识符类3. 程序测试结果5. 总结词法

27、分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。课程设计二、算符优先1. 概述1.1 设计目的算符优先分析法是一种简单直观、特别方便于表达式分析，易于手式实现的方法。根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。1.2 设计要求（1）使用算符优先分析法（或简单优先法）完成以上程序设计（2）写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分

28、析程序后，设计若干用例，上机测试并通过所设计的分析程序。2. 设计的基本原理2.1 算法优先分析法的思想算符优先分析的基本思想是只规定算符(广义为终结符)之间的优先关系，也就是只考虑终结符之间的优先关系，不考虑非终结符之间的优先关系。在归约过程中只要找到可归约串就归约，并不考虑归约到那个非终结符名，算符优先分析的可归约串不一定是规范句型的句柄，所以算符优先归约不是规范归约。算符优先分析的可归约串是当前符号栈中的符号和剩余的输入符号构成句型的最左素短语。2.2 算符优先文法E->E+T|E-T|TT->T*F|T/F|F F->(E)|i3. 程序设计#include<i

29、ostream>using namespace std;/*构造一个保存操作数的栈及基本操作过程*/#define STACK_INT_SIZE 100#define STACK_INCREMENT 10typedef structint* base;/栈底int* top;/栈顶指针int stacksize;/栈的大小SqIntStack;/栈的顺序存储表示/构造一个空栈void initStack(SqIntStack& stack)stack.base=(int *)malloc(STACK_INT_SIZE*sizeof(int);stack.top=stack.bas

30、e;/初态，栈为空stack.stacksize=STACK_INT_SIZE;/initStack/用e返回stack的栈顶元素int getTop(SqIntStack stack)int e;e=*(stack.top-1);return e;/getTop/插入元素e为栈顶元素void push(SqIntStack& stack,int e)if(stack.top-stack.base>=stack.stacksize) /栈满，追加存储空间 stack.base=(int*)realloc(stack.base,(stack.stacksize+STACK_INCR

31、EMENT)*sizeof(int); stack.top=stack.base+stack.stacksize;/栈顶指针重新定向 stack.stacksize+=STACK_INCREMENT;/栈大小发生改变/if*stack.top+=e;/push/删除栈顶元素，用e返回int pop(SqIntStack&s)int e;e=*(-s.top);return e;/pop/*构造一个用来保存操作符的栈及基本操作过程*/#define STACK_INT_SIZE 100#define STACK_INCREMENT 10typedef structchar* base;c

32、har* top;/指向栈顶的前一个元素int stacksize;/栈的大小SqCharStack;/栈的顺序表示/构造一个空栈void initStack(SqCharStack& stack)stack.base=(char*)malloc(STACK_INT_SIZE*sizeof(char);stack.top=stack.base;stack.stacksize=STACK_INT_SIZE;/initStack/用e返回stack的栈顶元素char getTop(SqCharStack stack)char e;e=*(stack.top-1);return e;/get

33、Top/插入元素e为栈顶元素void push(SqCharStack& stack,char e)if(stack.top-stack.base>=stack.stacksize) /栈满，追加存储空间 stack.base=(char*)realloc(stack.base,(stack.stacksize+STACK_INCREMENT)*sizeof(char); stack.top=stack.base+stack.stacksize; stack.stacksize+=STACK_INCREMENT;/if*stack.top+=e;/push/删除栈顶元素，用e返回

34、char pop(SqCharStack& stack)char e;e=*(-stack.top);return e;/pop/*其他函数*/判断在栈内的运算符的优先级int isp(char e)switch(e)case'+': return 1;case'-': return 1;case'*': return 2;case'/': return 2;case'': return 3;case'(': return 0;case'#': return -1;defau

35、lt: exit(1);/switch/isp/判断在栈外，C的运算符的优先权int icp (char e)switch(e)case'+': return 1;case'-': return 1;case'*': return 2;case'/': return 2; case'': return 3; case'(': return 4; default: exit(1);/switch/icp/算术表达式分析，输出逆波兰式过程void postfix(char e1100,char e210

36、0)SqCharStack OPTR;/操作符栈initStack(OPTR);push(OPTR,'#');char C,X;int i=0;/控制e1int j=0;/控制e2C=e1i+;while(C!=0) if(C!='+'&& C!='-'&& C!='/'&& C!='*'&& C!='('&& C!=')'&& C!='')/如果是非操作符,直接加入到输出

37、序列e2中 /运算符用优先数法 e2j+=C; if(e1i='+'|e1i='-'|e1i='/'|e1i='*'|e1i='('|e1i=')'|e1i=''|e1i=0)/有可能下一个还是非操作字符 /中间不能用空格，这里先进行判断 e2j+=' ' /if else/是操作符 if(C=')') /连续出栈，直到遇到'(' while(getTop(OPTR)!='(') X=pop(OPTR); e2j+=X;

38、 cout<<"操作符"<<X<<"出栈,输出到逆波式序列"<<endl; e2j+=' ' /while X=pop(OPTR);/ /if else /比较优先数 while(isp(getTop(OPTR)>=icp(C) /如果栈中的操作符的优先级大于或等于新的操作符， /则将栈中操作符出栈，加入到输出序列e2中 X=pop(OPTR); cout<<"操作符"<<X<<"出栈,输出到逆波式序列"<

39、;<endl; e2j+=X; e2j+=' ' /while push(OPTR,C);/否则进栈 cout<<"操作符"<<C<<"进栈"<<endl; /else /else C=e1i+;/表达式的下一个字符/while while(getTop(OPTR)!='#') /弹出栈中剩余的运算符号 X=pop(OPTR); e2j+=X; cout<<"操作符"<<X<<"出栈,输出到逆波式序列&q

40、uot;<<endl; e2j+=' ' /while e2j+='#'/postfix /对T1，T2进行运算求值int T1toT2(int t1,int t2,char to)switch(to)case'+': return t1+t2;case'-': return t1-t2;case'*': return t1*t2;case'/': return t1/t2;default: return 0;/switch/T1toT2/对T1进行运算求值int T1toT2(int

41、t1,char to)switch(to)case'': return t1=t1*(-1);default: return 0;/switch/T1/对纯整型数字逆波兰式求出运算结果int evaluate(char e2100)SqIntStack OPND;initStack(OPND);char C;int j=0;int n;C=e2j+;while(C!='#') if(C>='0'&& C<='9') n=C-'0'/数字字符到整数的转化 while(e2j!='

42、')/处理多位数 n=n*10+(e2j-'0'); j+; /while push(OPND,n); /if else if(C='')int T1=pop(OPND); int T=T1toT2(T1,C);/对T1进行求值运算 push(OPND,T);/求值结果继续入栈，供下一次使用 /else if else int T2=pop(OPND); int T1=pop(OPND); int T=T1toT2(T1,T2,C);/对T1，T2进行求值运算 push(OPND,T);/求值结果继续入栈，供下一次使用 /else C=e2j+; if(

43、C=' ')/跳过空格 C=e2j+;/whilereturn pop(OPND);/evaluate/表达式合法性检测int check(char e3100) int k=0,m=0,n=0; while(e3k!=0) if(e3k='(') m=m+1; if(e3k=')') n=n+1; k+; if(m!=n) cout<<"表达式非法!左右括号数量不匹配!"return -1; k=0; while(e3k!=0) if(e30='+'|e30='-'|e30=

44、9;/'|e30='*'|e30=')') cout<<"表达式非法!不能以"<<e30<<"操作符为表达式开始!"return -1; else k+;continue; if(e3k='') if(e3k-1!='+'&&e3k-1!='-'&&e3k-1!='*'&&e3k-1!='/'&&e3k-1!=''&

45、;&e3k-1!='(') cout<<"表达式非法!操作数后不能接"<<e3k<<"操作符!"return -1; if(e3k+1='+'|e3k+1='-'|e3k+1='*'|e3k+1='/'|e3k+1=')'|e3k+1=0) cout<<"表达式非法!操作符"<<e3k<<"后无有效操作数!"return -1; if(e3k

46、='(') if(e3k-1!='+'&&e3k-1!='-'&&e3k-1!='*'&&e3k-1!='/'&&e3k-1!='(') cout<<"表达式非法!操作数后不能接"<<e3k<<"操作符!"return -1; if(e3k+1='+'|e3k+1='-'|e3k+1='*'|e3k+1='/'|e3k+1=')'|e3k+1=0) cout<<"表达式非法!操作符"<<e3k<<"后无有效操作数!"return -1; if(e3k='+'|e3k='-'|e3k='*'|e3k='/') if(e3k-1='+'|e3k-1='-'|e3k-1='*'|e3k-1='/'|e3k-1=&