当前位置：文档库 › 编译原理语法分析实验报告

编译原理语法分析实验报告

班级: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); BEGIN

d(5);

x:=d+4;

y:=b*2+2;

END;

BEGIN

WHILE 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); BEGIN

d(5);

x:=d+4;

y:=b*2+;

END;

BEGIN

WHILE x<10 DO x:=x+b; IF x>5 x:=2*x-b;

END

运行结果2:

7、总结

通过本次实验，我能够用递归子程序法设计、编制、调试一个典型的语法分析程序，

实现对词法分析程序所提供的单词序列进行语法检查和结构分析，更加了解了语法分

析的过程和作用。

附件:

LEX代码:

#include

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);

else

fprintf(fp,"%d %d\n",33,line);}

{identfier} {if(strlen(yytext)>20){

printf("line %d identfier error:'%s'\n",line,yytext);

}

else

fprintf(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

#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(); void

varexl(); 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)

{