计算机编译原理---语法分析预测分析法 .doc

编译原理实验报告-语法分析2预测分析法目录1.摘要：32、实验目的：33、任务概述34、实验依据的原理35、程序设计思想56、实验结果分析97、总结188、程序代码181.摘要：用CC+实现并运用预测分析法对Pascal的子集程序设计语言进行语法识别程序，并对语言进行判断，找出错误。 2、实验目的：通过预测分析法进行设计、编程、调试出一个语法分析程序，加深对预测分析法的语法分析原理的理解，掌握其设计方法。3、任务概述1）将源程序转换成内码流，然后用预测分析法进行分析。2）构造预测分析表，并利用分析表和一个栈来实现对Pascal的子集程序设计语言的分析程序。4、实验依据的原理4.1Pascal的子集程序设计语言的文法Pascal的子集程序设计语言的文法如下：<程序><程序首部><分程序>。<程序首部>PROGRAM标识符；<分程序><常量说明部分><变量说明部分><过程说明部分> <复合语句><常量说明部>CONST<常量定义><常量定义后缀> |<常量定义>标识符=无符号整数<常量定义后缀>，<常量定义><常量定义后缀> |<变量说明部分>VAR<变量定义><变量定义后缀> |<变量定义>标识符<标识符后缀>：<类型>；<标识符后缀>，标识符<标识符后缀> |<变量定义后缀><变量定义><变量定义后缀> |<类型>INTEGER | LONG<过程说明部分><过程首部><分程序>；<过程说明部分后缀>|<过程首部>PROCEDURE标识符<参数部分>；<参数部分>(标识符： <类型>)|<过程说明部分后缀><过程首部><分程序>；<过程说明部分后缀>|<语句><赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句>|<写语句>|<复合语句>|<赋值或调用语句>标识符<后缀><后缀>：=<表达式>|(<表达式>)|<条件语句>IF<条件>THEN<语句><当型循环语句>WHILE<条件>DO <语句><读语句>READ（标识符<标识符后缀>）<写语句>WRITE（<表达式><表达式后缀>）<表达式后缀>，<表过式><表达式后缀>|<复合语句>BEGIN<语句><语句后缀>END<语句后缀>；<语句><语句后缀>|<条件><表达式><关系运算符><表达式>|ODD<表达式><表达式>+<项><项后缀>|-<项><项后缀>|<项><项后缀><项后缀><加型运算符><项><项后缀>|<项><因子><因子后缀><因子后缀><乘型运算符><因子><因子后缀>|e<因子>标识符|无符号整数|（<表达式>）<加型运算符>+|-<乘型运算型>*|/<关系运算符> =|<>|<|<=|>|>=4.2内码对照表1-1 终结符的内部码对照表内码单词内码单词内码单词内码单词1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20=21<>22<23<=24>25>=26.27,28;29:30:=31(32)33无符号整数34标识符35#表1-2 非终结符和内码对照表内码非 终 结 符内码非 终 结 符内码非 终 结 符128程序129程序首部130分程序131常量说明部分132常量定义133常量定义后缀134变量说明部分135变量定义136变量定义后缀137类型138过程说明部分139过程首部140<过程说明部分后缀>141语句142赋值或调用语句143后缀144条件语句145当型循环语句146读语句147标识符后缀148写语句149表达式后缀150复合语句151语句后缀152条件153表达式154项后缀155项156因子后缀157因子158参数部分159加型运算符160乘型运算符161关系运算符5、程序设计思想5.1文法转化将上述文法转换成内码：128 129 130 26 0 129 1 34 28 0 130131 134 138 150 0131 2 132 133 28 0 1310 13234 20 33 013327 132 133 0 1330 1343 135 136 01340 13534 147 29 137 28 0 136135 136 01360 1374 0 1375 0138139 130 28 140 0 1380 139 6 34 158 28 0140139 130 28 140 0 1400 141142 0141144 0 141145 0 141146 0141148 0 141150 0 141014234 143 0 14330 153 0 14331 153 32 01430 1447 152 8 141 0 1459 152 10 141 014611 31 34 147 32 0 14727 34 147 0 147014812 31 153 149 32 0 14927 153 149 0 149015013 141 151 14 0 15128 141 151 0 1510152153 161 153 0 15215 153 0 15316 155 154 015317 155 154 0 153155 154 0 154159 155 154 01540 155157 156 0 156160 157 156 01560 15734 0 157 33 015731 153 32 0 15831 34 29 137 32 0 158015916 0 15917 0 16018 016019 0 16120 0 16121 016122 0 16123 0 16124 016125 05.2求非终结符的First集的方法：1.直接收取：若U>a（其中a是终结符）,把a收入到First(U)中；2.反复传送：若U>P（其中P是非终结符）,应把First(P)中的全部内容传送到First(U)中。5.3求非终结符的Follow集的方法（Follow集是从开始符号S开始推导，初始定义Follow（S）=#）：1.直接收取：若M>Ua,把a直接收入到Follow(U)中；2.直接收取：若M>UP(P是非终结符),把First(P)除去后直接收入到Follow(U)中；3.反复传送：若P>U（U是非终结符）,把Follow(P)中的全部内容传送到Follow(U)中。5.4求产生式的First集的方法： 若M>U1U2U3Un1. 若非终结符U1的First集含，则First(U1)除去后直接收入到该产生式的First集，再依次判断U2（方法类似U1）；2. 若非终结符U1的First集不含，则First(U1) 直接收入到该产生式的First集；3. 若U1为终结符，则将U1直接收入到该产生式的First集。5.5预测分析表的构造：对于文法中的每一个产生式A ->,执行以下2步：1.for aFIRST()，将A ->填入MA,a;2.if（FIRST()） aFOLLOW(A)，将A ->填入MA,a。5.6预测分析法分析对于任何（X，a），总控程序每次都执行下述三种可能的动作之一： （1）若X = a =#，则宣布分析成功，停止分析过程。 （2）若X = a#，则把X从STACK栈顶弹出，让a指向下一个输入符号。 （3）若X是一个非终结符，则查看预测分析表M。若MX，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MX，a中存放着的数值表示出错，则表示该程序有错。5.7错误情况在预测分析表中引入同步符后，程序出错分一下三种情况： （1）若X为终结符，但Xa，表示X前缺少符号； （2）若X为非终结符，但MX，a=-1（-1表示不存在对应产生式），表示X多余； （3）若X为非终结符，但MX，a=-2（-2表示同步符），表示X前缺少符号。program helloworld;begin write(1); a:=2end.5.8程序流程图是否计算每个产生式右部的FIRST集计算所有非终结符号的FOLLOW集根据FIRST集和FOLLOW集生成预测分析表读取文件中的程序根据预测分析表对程序进行分析词法分析是否正确语法分析正确提醒程序错误、错误的位置在哪里程序结束计算所有非终结符号的FIRST集语法分析是否正确程序入口语法分析失败是否6、实验结果分析6.1文件内容：6.2程序运行结果如下：6.2.1所有非终结符的First集6.2.2所有非终结符的Follow集6.2.3所有产生式的First集 6.2.4预测分析表6.2.5源程序显示6.2.6词法分析结果（1）若词法分析无误，则显示如下图所示并进行语法分析：（2）若词法分析有误，则显示如下图所示，即指出错误之处，但不能进行语法分析。text内容：结果如下：6.2.7语法分析结果（1）若语法分析无误，则显示如下图所示：（2）若语法分析有误，则显示如下图所示，即指出错误之处：i）栈中终结符与输入串中终结符不相匹配时的情况：text内容：结果显示:ii）栈中非终结符与输入串中终结符所对应的预测分析表中的数值为同步符时的情况：text内容：结果显示：iii）栈中非终结符与输入串中终结符所对应的预测分析表中的数值为不存在时的情况：text内容：结果显示：7、总结（1）本次实验完成了语法分析器-预测分析法的算法分析到实现的全部过程，结果满足设计要求，验证无误。通过本次实验让我了解了如何设计、编制并调试预测分析法的语法分析程序，在设计、实现、调试自己的语法分析器的同时，加深了我对语法分析器原理的理解；熟悉了预测分析法构造语法分析器的方法和相关原理，并能基本使用C语言直接编写语法分析器。（2）通过这次实验使我懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能更好地理解、消化、掌握所学知识，同时也可以提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到很多问题，可以说是困难重重，毕竟很多问题是无法预料和避免的，所以难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对课程所学的知识理解得不够深刻，掌握得不够牢固等等。（3）在本实验中，我锻炼了自己的上机操作能力及编程能力，并对理论知识有了进一步的了解。程序的难点是分析表的构造，解决实验中遇到的问题也花费了一部分的时间，增长了处理程序错误的能力。虽然这个程序还有许许多多的不足和欠缺，但它包含了我的想法和努力。总的来说，和成员一次完成这个语法分析器的设计很有意义。8、程序代码#include<stdio.h>#include<iostream>#include<string>#include<stack>#include<stdlib.h>using namespace std;#define MAX_1 1000#define MAX_2 100000/产生式的左右部以及右部的长度typedef struct productionint left;int rightMAX_1;int length;PRO;/程序每个字符的对应内码以及所在行数typedef struct characterstring ch;int code;int row;CHAR;/词法分析时发现的错误typedef struct errorchar ch;int row;ERR;/集合结构typedef struct aggregateint strMAX_1;int len;AGG;PRO *p=new PROMAX_1;/产生式CHAR charaMAX_2;/程序字符流ERR errorMAX_2;/词法分析时发现的错误AGG FirstMAX_1;/用于存放每个非终结符的First集AGG FollowMAX_1;/用于存放每个非终结符的Follow集int NONEMAX_1=0;/求每个非终结符的Follow集时避免死循环的变量AGG Pro_FirstMAX_1;/用于存放每个产生式右部的First集int TableMAX_1MAX_1;/预测分析表,-1表示不匹配，-2表示同步符号synchint N;/产生式的个数char setMAX_2;/用于存储初始代码char strMAX_2;/用于存储初步处理后的代码int errorNum=0;/词法分析发现错误数int errorNum2=0;/语法分析发现错误数int k=0;/程序字符流数int Program_row=1;/程序初始行数stack<int> Stack;/符号栈/非终结符string key15="PROGRAM","CONST","VAR","INTEGER","LONG","PROCEDURE","IF","THEN","WHILE","DO","READ","WRITE","BEGIN","END","ODD"string punctuation17="+","-","*","/","=","<>","<","<=",">",">=",".",",","",":",":=","(",")"/判断字符串是否是关键字，若是，则返回该关键字对应的内码；若不是，则返回0int IsKeyWord(string c)int i;for(i=0;i<15;i+)if(keyi.compare(c)=0)return i+1;return 0;/判断字符串c是否是符号，若是，则返回该符号对应的内码；若不是，则返回0int IsPunctuation(string c)int i;for(i=0;i<17;i+)if(punctuationi.compare(c)=0)return i+16;return 0;/判断字符c是否是字母，若是，则返回true；若不是，则返回falsebool IsLetter(char c)if(c>='a'&&c<='z')|(c>='A'&&c<='Z')return true;elsereturn false;/判断字符c是否是数字，若是，则返回true；若不是，则返回falsebool IsFigure(char c)if(c>='0'&&c<='9')return true;elsereturn false;/判断该词法错误是否已被检测bool test(int errorNum,int row,char ch)int i;for(i=0;i<errorNum;i+)if(errori.row =row&&errori.ch =ch)return false;return true;/词法分析void lexical_analysis()FILE *f;string tem=""char ch;int n=0,m=0;/程序代码储存数int i;if(f=fopen("test.txt","r")=NULL) printf("can not open the file!n"); exit(0); elsewhile(!feof(f)ch=getc(f);/getc函数带回一个字符，赋给chsetn=ch;/将文件的每一个字符都放入set数组中n+;fclose(f);/关闭文件setn-1='0'i=0;while(seti!='0')if(seti=' ')while(seti=' ')/扫描到有连续的空格i+;strm=' '/用一个空格代替扫描到的连续空格放入strm+;else if(seti='n')while(seti='n')/扫描到有连续的换行符i+;strm='n'/用一个换行符代替扫描到的连续换行符放入strm+;else/若当前字符不为空格或换行符就直接放入strif(seti>='a'&&seti<='z')strm=seti-32;elsestrm=seti;m+;i+;strm='0'/显示源程序printf("n-源程序显示-nn");for(i=0;i<m;i+)printf("%c",stri);printf("n");i=0;/将源程序转换成字符流for(i=0;i<m;i+)tem=""if(IsLetter(stri)|stri='_')while(IsLetter(stri)|IsFigure(stri)|stri='_')tem=tem+stri;i+;if(IsKeyWord(tem)>0)charak.ch=tem;charak.code=IsKeyWord(tem);charak.row =Program_row;k+;elsecharak.ch =tem;charak.code =34;charak.row =Program_row;k+;else if(IsFigure(stri)while(IsFigure(stri)tem=tem+stri;i+;if(IsLetter(stri)errorerrorNum.row=Program_row;errorerrorNum.ch =stri;errorNum+;elsecharak.ch=tem;charak.code=33;charak.row =Program_row;k+;tem=""tem=tem+stri;switch(stri)case':':case'>':i+;if(stri='=')tem=tem+stri;elsei-;charak.ch =tem;charak.code =IsPunctuation(tem);charak.row =Program_row;k+;break;case'<':i+;if(stri='='|stri='>')tem=tem+stri;elsei-;charak.ch =tem;charak.code =IsPunctuation(tem);charak.row =Program_row;k+;break;case'':case',':case'.':case'(':case')':case'+':case'-':case'*':case'/':case'=':charak.ch =tem;charak.code =IsPunctuation(tem);charak.row =Program_row;k+;break;case'#':charak.ch =tem;charak.code =35;charak.row =Program_row;k+;break;case' ':break;case'n':Program_row+;break;default:if(test(errorNum,Program_row,stri)errorerrorNum.row =Program_row;errorerrorNum.ch =stri;errorNum+;/所有产生式void production()N=67;/产生式共有67个/128129 130 26 0p0.left=128;p0.right0=129;p0.right1=130;p0.right2=26;p0.length=3;/1291 34 28 0p1.left=129;p1.right0=1;p1.right1=34;p1.right2=28;p1.length=3;/130131 134 138 150 0 p2.left=130;p2.right0=131;p2.right1=134;p2.right2=138;p2.right3=150;p2.length=4;/1312 132 133 28 0p3.left=131;p3.right0=2;p3.right1=132;p3.right2=133;p3.right3=28;p3.length=4;/1310p4.left=131;p4.right0=0;p4.length=1;/13234 20 33 0p5.left=132;p5.right0=34;p5.right1=20;p5.right2=33;p5.length=3;/13327 132 133 0p6.left=133;p6.right0=27;p6.right1=132;p6.right2=133;p6.length=3;/1330p7.left=133;p7.right0=0;p7.length=1;/1343 135 136 0p8.left=134;p8.right0=3;p8.right1=135;p8.right2=136;p8.length=3;/1340p9.left=134;p9.right0=0;p9.length=1;/13534 147 29 137 28 0p10.left=135;p10.right0=34;p10.right1=147;p10.right2=29;p10.right3=137;p10.right4=28;p10.length=5;/136135 136 0p11.left=136;p11.right0=135;p11.right1=136;p11.length=2;/1360p12.left=136;p12.right0=0;p12.length=1;/1374 0p13.left=137;p13.right0=4;p13.length=1;/1375 0p14.left=137;p14.right0=5;p14.length=1;/138139 130 28 140 0p15.left=138;p15.right0=139;p15.right1=130;p15.right2=28;p15.right3=140;p15.length=4;/1380p16.left=138;p16.right0=0;p16.length=1;/139 6 34 158 28 0p17.left=139;p17.right0=6;p17.right1=34;p17.right2=158;p17.right3=28;p17.length=4;/140139 130 28 140 0p18.left=140;p18.right0=139;p18.right1=130;p18.right2=28;p18.right3=140;p18.length=4;/1400p19.left=140;p19.right0=0;p19.length=1;/141142 0p20.left=141;p20.right0=142;p20.length=1;/141144 0p21.left=141;p21.right0=144;p21.length=1;/141145 0p22.left=141;p22.right0=145;p22.length=1;/141146 0p23.left=141;p23.right0=146;p23.length=1;/141148 0p24.left=141;p24.right0=148;p24.length=1;/141150 0p25.left=141;p25.right0=150;p25.length=1;/1410p26.left=141;p26.right0=0;p26.length=1;/14234 143 0p27.left=142;p27.right0=34;p27.right1=143;p27.length=2;/14330 153 0p28.left=143;p28.right0=30;p28.right1=153;p28.length=2;/14331 153 32 0p29.left=143;p29.right0=31;p29.right1=153;p29.right2=32;p29.length=3;/1430p30.left=143;p30.right0=0;p30.length=1;/1447 152 8 141 0p31.left=144;p31.right0=7;p31.right1=152;p31.right2=8;p31.right3=141;p31.length=4;/1459 152 10 141 0p32.left=145;p32.right0=9;p32.right1=152;p32.right2=10;p32.right3=141;p32.length=4;/14611 31 34 147 32 0p33.left=146;p33.right0=11;p33.right1=31;p33.right2=34;p33.right3=147;p33.right4=32;p33.length=5;/14727 34 147 0p34.left=147;p34.right0=27;p34.right1=34;p34.right2=147;p34.length=3;/1470p35.left=147;p35.right0=0;p35.length=1;/14812 31 153 149 32 0p36.left=148;p36.right0=12;p36.right1=31;p36.right2=153;p36.right3=149;p36.right4=32;p36.length=5;/14927 153 149 0p37.left=149;p37.right0=27;p37.right1=153;p37.right2=149;p37.length=3;/1490p38.left=149;p38.right0=0;p38.length=1;/