编译原理语法分析实验报告-班级:XXX学号:XXX姓名:XXX年月日1、摘要:用递归子程序法实现对pascal的子集程序设计语言的分析程序2、实验目的:通过完成语法分析程序，了解语法分析的过程和作用3、任务概述实验要求:对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用4、实验依据的原理递归子程序法是一种自顶向下的语法分析方法，它要求文法是LL(1)文法。

通过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，程序能够按LL(1)形式唯一地确定选择某个候选式进行推导，最终识别输入串是否与文法匹配。

递归子程序法的缺点是:对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如PASCAL，C等编译系统常常采用的语法分析方法。

为适合递归子程序法，对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下:<程序>?<程序首部><分程序>。

<程序首部>?PROGRAM标识符;<分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε<常量定义>?标识符=无符号整数<常量定义后缀>?，<常量定义><常量定义后缀> |ε<变量说明部分>?VAR<变量定义><变量定义后缀> |ε<变量定义>?标识符<标识符后缀>:<类型>;<标识符后缀>?，标识符<标识符后缀> |ε<变量定义后缀>?<变量定义><变量定义后缀> |ε<类型>?INTEGER | LONG<过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε<过程首部>?PROCEDURE标识符<参数部分>;<参数部分>?(标识符: <类型>)|ε<过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε<语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句>|<写语句>|<复合语句>|ε<赋值或调用语句>?标识符<后缀><后缀>?:=<表达式>|(<表达式>)|ε<条件语句>?IF<条件>THEN<语句><当型循环语句>?WHILE<条件>DO <语句><读语句>?READ(标识符<标识符后缀>)<写语句>?WRITE(<表达式><表达式后缀>)<表达式后缀>?，<表过式><表达式后缀>|ε<复合语句>?BEGIN<语句><语句后缀>END<语句后缀>?;<语句><语句后缀>|ε<条件>?<表达式><关系运算符><表达式>|ODD<表达式><表达式>?+<项><项后缀>|-<项><项后缀>|<项><项后缀><项后缀>?<加型运算符><项><项后缀>|ε<项>?<因子><因子后缀><因子后缀>?<乘型运算符><因子><因子后缀>|e<因子>?标识符|无符号整数|(<表达式>)<加型运算符>?+|-<乘型运算型>?*|/<关系运算符>? =|<>|<|<=|>|>=5、程序设计思想为每个非终结符设计一个识别的子程序，寻找该非终结符也就是调用相应的子程序。

由于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。

在这里将词法分析作为语法分析的一个子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词。

语法分析的作用是识别输入符号串是否是文法上定义的句子，即判断输入符号串是否是满足“程序”定义的要求。

也就是当语法识别程序从正常退出表示输入符号串是正确的“程序”;若从出错退出，则输入符号串不是正确的“程序”。

出错时，可以根据读字符的位置判断出错的位置。

表2-1为非终结符和函数名对照表。

表2-1 非终符和函数名对照表非终结符函数名非终结符函数名 <程序> <程序首部> program proghead <分程序> <常量说明部分> block consexpl <常量定义> <变量说明部分> consdefi varexl <常量定义后缀> <变量定义> conssuff vandefi <变量定义后缀> <>过程说明部分> varsuff procdefi <类型> <过程首部> typeil procedh <过程说明部分后缀> <赋值或调用语句> procsuff assipro <语句> <后缀> sentence suffix <条件语句> <读语句> ifsent read <当型循环语句> <标识符后缀> whilsent idsuff <写语句> <复合语句> write compsent <表达式后缀> <语句后缀> exprsuff sentsuff <条件> <项后缀> conditio termsuff <表达式> <项> express term <因子后缀> <参数部分> factsuff argument <因子> <加型运算符> factor addoper <乘型运算符> <关系运算符> muloper respoper 表2-2为词法分析中的内码单词对照表。

表2-2 内部码对照表内码单词内码单词内码单词内码单词 1 PROGRAM 2 CONST 3 VAR 4 INTEGER 5 LONG 6 PROCEDURE 7 IF 8 THEN 9 WHILE 10 DO 11 READ 12 WRITE 13 BEGIN 14 END 15 ODD 16 + 17 - 18 * 19 / 20 = 21 <> 22 < 23 <= 24 > 25 >= 26 . 27 , 28 ; 29 : 30 := 31 ( 32 )无符号整数标识符 33 34 35 #6、实验结果分析样例1:正确的pascal子集程序代码PROGRAM test;CONST b=3;VAR x:INTEGER;y:LONG; PROCEDURE c(d:INTEGER); BEGINd(5);x:=d+4;y:=b*2+2;END;BEGINWHILE x<10 DO x:=x+b;IF x>5 THEN x:=2*x-b;END.运行结果1:样例2:错误的pascal子集程序代码test;CONST b=3;VAR x:INTEGER;y:; PROCEDURE c(d:INTEGER); BEGINd(5);x:=d+4;y:=b*2+;END;BEGINWHILE x<10 DO x:=x+b; IF x>5 x:=2*x-b;END运行结果2:7、总结通过本次实验，我能够用递归子程序法设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，更加了解了语法分析的过程和作用。

附件:LEX代码:%{#include <stdio.h>#include <stdlib.h>#include <string.h>FILE *fp;int line = 1;%}delim [" "\t]whitespace {delim}+ backspace [\n]program [pP][rR][oO][gG][rR][aA][mM]const [cC][oO][nN][sS][tT] var [vV][aA][rR]integer [iI][nN][tT][eE][gG][eE][rR]long [lL][oO][nN][gG] procedure [pP][rR][oO][cC][eE][dD][uU][rR][eE] if [iI][fF]then [tT][hH][eE][nN] while [wW][hH][iI][lL][eE] do [dD][oO]read [rR][eE][aA][dD] write [wW][rR][iI][tT][eE] begin[bB][eE][gG][iI][nN] end [eE][nN][dD]odd [oO][dD][dD]add \+minus -multiply \*div \/equal =m21 <>m22 <m23 <=m24 >m25 >=m27 ,m26 \.m28 ;m29 :m30 :=m31 \(m32 \)constant ([0-9])+identfier [A-Za-z]([A-Za-z]|[0-9])*%%{program} {fprintf(fp,"%d %d\n",1,line);} {const} {fprintf(fp,"%d%d\n",2,line);} {var} {fprintf(fp,"%d %d\n",3,line);} {integer}{fprintf(fp,"%d %d\n",4,line);} {long} {fprintf(fp,"%d %d\n",5,line);} {procedure} {fprintf(fp,"%d %d\n",6,line);} {if} {fprintf(fp,"%d%d\n",7,line);} {then} {fprintf(fp,"%d %d\n",8,line);} {while}{fprintf(fp,"%d %d\n",9,line);} {do} {fprintf(fp,"%d %d\n",10,line);} {read} {fprintf(fp,"%d %d\n",11,line);} {write} {fprintf(fp,"%d%d\n",12,line);} {begin} {fprintf(fp,"%d %d\n",13,line);} {end}{fprintf(fp,"%d %d\n",14,line);} {odd} {fprintf(fp,"%d %d\n",15,line);} {add} {fprintf(fp,"%d %d\n",16,line);} {minus} {fprintf(fp,"%d%d\n",17,line);} {multiply} {fprintf(fp,"%d %d\n",18,line);} {div} {fprintf(fp,"%d %d\n",19,line);} {equal} {fprintf(fp,"%d %d\n",20,line);} {m21} {fprintf(fp,"%d %d\n",21,line);} {m22} {fprintf(fp,"%d%d\n",22,line);} {m23} {fprintf(fp,"%d %d\n",23,line);} {m24}{fprintf(fp,"%d %d\n",24,line);} {m25} {fprintf(fp,"%d %d\n",25,line);} {m26} {fprintf(fp,"%d %d\n",26,line);} {m27} {fprintf(fp,"%d%d\n",27,line);} {m28} {fprintf(fp,"%d %d\n",28,line);} {m29}{fprintf(fp,"%d %d\n",29,line);} {m30} {fprintf(fp,"%d %d\n",30,line);} {m31} {fprintf(fp,"%d %d\n",31,line);} {m32} {fprintf(fp,"%d%d\n",32,line);} {constant} {__int64 maxnum=0xffffffff;if(strlen(yytext)>10)printf("line %d constant error:'%s'\n",line,yytext);elsefprintf(fp,"%d %d\n",33,line);}{identfier} {if(strlen(yytext)>20){printf("line %d identfier error:'%s'\n",line,yytext);}elsefprintf(fp,"%d %d\n",34,line);}{whitespace} { }{backspace} { if(strcmp(yytext,"\n")==0){line++;}}%%void main(){yyin=fopen("example.txt","r");fp=fopen("data.txt","w");fclose(fp);fp=fopen("data.txt","a");yylex(); /* start the analysis*/fclose(yyin);fclose(fp);}int yywrap(){return 1;}主程序代码:#include<string>#include<iostream>#include<fstream>#include"lex.yy.c"using namespace std;int token[2000][2] = {NULL}; int h = 0;int i,j,p=0;void program();void block();void consdefi();void conssuff(); void varsuff(); void typeil(); void procsuff(); void sentence(); void ifsent(); void whilsent(); void write(); void exprsuff(); void conditio(); void express(); void factsuff(); void factor(); void muloper(); void proghead(); void consexpl(); voidvarexl(); void vandefi(); void procdefi(); void procedh(); void assipro(); void suffix(); void read();void idsuff(); void compsent(); void sentsuff(); void termsuff(); void term();void argument(); void addoper(); void respoper();void program() {proghead();block();if (token[h][0] ==26){h++;if (token[h][0] == 0){printf("语法分析完成\n");}}else{p=1;printf("第%d行缺少.\n",token[h-1][1]);}return;}void proghead(){if (token[h][0] == 1){h++;if (token[h][0] == 34){h++;if (token[h][0] == 28){h++;}else{p=1;printf("第%d行缺少;\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少PROGRAM\n", token[h][1]); if (token[h][0] == 34){h++;if (token[h][0] == 28){h++;}}}}void block() {consexpl();varexl();procdefi();compsent();return;}void consexpl() {if (token[h][0] != 6 && token[h][0] != 3 && token[h][0] != 13) {if (token[h][0] == 2){h++;consdefi();conssuff();if (token[h][0] == 28){h++;}else{p=1;printf("第%d行缺少;\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少CONST\n", token[h][1]); consdefi();conssuff();if (token[h][0] == 28){h++;}}}return;}void consdefi(){if (token[h][0] == 34){h++;if (token[h][0] == 20){h++;if (token[h][0] == 33){h++;}else{p=1;printf("第%d行缺少无符号整数\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少=\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]);if (token[h][0] == 20){h++;if (token[h][0] == 33){h++;}}}return;}void conssuff(){if (token[h][0] != 6 && token[h][0] != 3 && token[h][0] != 13) {if (token[h][0] == 28)return;if (token[h][0] == 27){h++;consdefi();conssuff();}else{p=1;printf("第%d行缺少,\n", token[h-1][1]);consdefi();conssuff();}}return;}void varexl(){if (token[h][0] != 6 && token[h][0] != 13) {if (token[h][0] == 3){h++;vandefi();varsuff();}else{p=1;printf("第%d行缺少VAR\n", token[h][1]); vandefi();varsuff();}}return;}void vandefi(){if (token[h][0] == 34){h++;idsuff();if (token[h][0] == 29){h++;typeil();if (token[h][0] == 28){h++;}else{p=1;printf("第%d行缺少;\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少:\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]); idsuff();if (token[h][0] == 29){h++;typeil();if (token[h][0] == 28){h++;}}}return;}void idsuff(){if (token[h][0] == 4 || token[h][0] == 5){return;}if (token[h][0] != 32 && token[h][0] != 29){if (token[h][0] == 27){h++;if (token[h][0] == 34){h++;idsuff();}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少,\n", token[h-1][1]);}}return;}void varsuff() {if (token[h][0] != 6 && token[h][0] != 13){vandefi();varsuff();}return;}void typeil() {if (token[h][0] == 4||token[h][0]==5){h++;}else{p=1;printf("第%d行缺少INTEGER或LONG\n", token[h-1][1]); }return;}void procdefi(){if (token[h][0] != 13){procedh();block();if (token[h][0] == 28){h++;procsuff();}else{p=1;printf("第%d行缺少;\n", token[h-1][1]); }}return;}void procedh(){if (token[h][0] == 6){h++;if (token[h][0] == 34){h++;argument();if (token[h][0] == 28){h++;}else{p=1;printf("第%d行缺少;\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少PROCEDURE\n", token[h][1]); if (token[h][0] == 34){h++;argument();if (token[h][0] == 28){h++;}}}return;}void read(){if (token[h][0] == 11){h++;if (token[h][0] == 31){h++;if (token[h][0] == 34){h++;idsuff();if (token[h][0] == 32){h++;}else{p=1;printf("第%d行缺少)\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少(\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少READ\n", token[h-1][1]); exit(0);}return;}void ifsent(){if (token[h][0] == 7){h++;conditio();if (token[h][0] == 8){h++;sentence();}else{p=1;printf("第%d行缺少THEN\n", token[h-1][1]); sentence();}}else{p=1;printf("第%d行缺少IF\n", token[h-1][1]); exit(0);}return;}void assipro(){if (token[h][0] == 34){h++;suffix();}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]);}return;}void procsuff(){if (token[h][0] != 13){procedh();block();if (token[h][0] == 28){h++;procsuff();}else{p=1;printf("第%d行缺少;\n", token[h-1][1]); }}return;}void sentence(){if (token[h][0] != 14 && token[h][0] != 28){if (token[h][0] == 34){assipro();}else if (token[h][0] == 7) {ifsent();}else if (token[h][0] == 9) {whilsent();}else if (token[h][0] == 11) {read();}else if (token[h][0] == 12) {write();}else if (token[h][0] == 13) {compsent();}}return;}void suffix(){if (token[h][0] != 14 && token[h][0] != 28) {if (token[h][0] == 30){h++;express();}else if (token[h][0] == 31){h++;express();if (token[h][0] == 32){h++;}else{p=1;printf("第%d行缺少)\n", token[h-1][1]);}}else{p = 1; printf("第%d行缺少(\n", token[h - 1][1]); }}return;}void whilsent(){if (token[h][0] == 9){h++;conditio();if (token[h][0] == 10){h++;sentence();}else{p=1;printf("第%d行缺少DO\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少WHILE\n", token[h-1][1]); exit(0);}return;}void write(){if (token[h][0] == 12){h++;if (token[h][0] == 31){h++;express();exprsuff();if (token[h][0] == 32){h++;}else{p=1;printf("第%d行缺少)\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少(\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少WRITE\n", token[h-1][1]); exit(0);}return;}void compsent(){if (token[h][0] == 13){h++;sentence();sentsuff();if (token[h][0] == 14){h++;}else{p=1;printf("第%d行缺少END\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少BEGIN\n", token[h-1][1]); sentence();sentsuff();if (token[h][0] == 14){h++;}}return;}void exprsuff() {if (token[h][0] != 32){if (token[h][0] == 27){h++;express();exprsuff();}else{p=1;printf("第%d行缺少,\n", token[h-1][1]); }}return;}void sentsuff() {if (token[h][0] == 28){h++;if (token[h][0] != 14){sentence();sentsuff();}}else{p=1;printf("第%d行缺少;\n", token[h-1][1]);}return;}void conditio() {if (token[h][0] == 15){h++;express();}else{express();respoper();express();}return;}void termsuff() {if (token[h][0] != 21 && token[h][0] != 22 && token[h][0] != 23 && token[h][0] != 24 && token[h][0] != 25 && token[h][0] != 32 && token[h][0] != 28&& token[h][0] != 14 && token[h][0] != 8 && token[h][0] != 10 && token[h][0] !=34){addoper();term();termsuff();}}void express() {if (token[h][0] == 16||token[h][0]==17) {h++;term();termsuff();}else{term();termsuff();}}void term(){factor();factsuff();}void factsuff(){if (token[h][0] != 21 && token[h][0] != 22 && token[h][0] != 23 && token[h][0] != 24 && token[h][0] != 25 && token[h][0] != 32 && token[h][0] != 28&& token[h][0] != 14 && token[h][0] != 16 && token[h][0] != 17 && token[h][0] !=8 && token[h][0] != 10 && token[h][0] != 34){muloper();factor();factsuff();}}void argument(){if (token[h][0] != 28){if (token[h][0] == 31){h++;if (token[h][0] == 34){h++;if (token[h][0] == 29){h++;typeil();if (token[h][0] == 32){h++;}else{p=1;printf("第%d行缺少)\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少:\n", token[h-1][1]);}}else{p=1;printf("第%d行缺少标识符\n", token[h-1][1]); }}else{p=1;printf("第%d行缺少(\n", token[h-1][1]); }}return;}void factor(){if (token[h][0] != 33 && token[h][0] != 34) {if (token[h][0] == 31){h++;express();if (token[h][0] == 32){h++;}else{p=1;printf("第%d行缺少)\n", token[h-1][1]); }}else{p = 1; printf("第%d行缺少标识符或无符号整数\n", token[h - 1][1]); }}else{h++;}return;}void addoper(){if (token[h][0] == 16 || token[h][0] == 17){h++;}else{p=1;printf("第%d行缺少+或-\n", token[h-1][1]);}return;}void muloper(){if (token[h][0] == 18 || token[h][0] == 19){h++;}else{p=1;printf("第%d行缺少*或/\n", token[h-1][1]);}return;}void respoper(){if (token[h][0] == 21 || token[h][0] == 22 || token[h][0] == 23 || token[h][0] == 25|| token[h][0] == 24){h++;}else{p=1;printf("第%d行缺少关系运算符\n", token[h-1][1]);}return;}void main(){mainf();FILE *p1 = fopen("data.txt", "r");if (!p1){printf("文件打开失败～\n");}else{printf("文件打开成功～\n语法分析开始\n"); }i = 0;while (!feof(p1)){for (j = 0; j < 2; j++){fscanf(p1, "%d", &token[i][j]);}i++;}fclose(p1);program();if (p == 0){printf("Success!\n"); }else{printf("Fail!\n");}}。