编译原理实验-(词法语法分析-附源代码.docx

编译原理实验报告
*******************************************************************************
*******************************************************************************
PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下：

<程序>::=<分程序>.
<分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句>
<常量说明> ::=CONST<常量定义>{，<常量定义>};
<常量定义> ::=<标识符>=<无符号整数>
<无符号整数> ::= <数字>{<数字>}
<变量说明> ::=VAR <标识符>{, <标识符>};
<标识符> ::=<字母>{<字母>|<数字>}
<过程说明> ::=<过程首部><分程序>{; <过程说明> };
<过程首部> ::=PROCEDURE <标识符>;
<语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句>
|<复合语句>|<读语句><写语句>|<空>
<赋值语句> ::=<标识符>:=<表达式>
<复合语句> ::=BEGIN <语句> {;<语句> }END
<条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式>
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= =|#|<|<=|>|>=
<条件语句> ::= IF <条件> THEN <语句>
<过程调用语句> ::= CALL 标识符
<当循环语句> ::= WHILE <条件> DO <语句>
<读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’
<写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’
<字母> ::= a|b|…|X|Y|Z
<数字> ::= 0|1|…|8|9

【预处理】
对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。

【实验一】词法分析
【实验目的】给出PL/0文法规范，要求编写PL/0语言的词法分析程序。
【实验内容】已给PL/0语言文法，输出单词（关键字、专用符号以及其它标记）。
【实验要求】
1. 确定编译中使用的表格、标识符与关键字的区分方法等。
2. 把词法分析器设计成一个独立一遍的过程。
3. 词法分析器的输出形式采用二元式序列，例如：
(ident, a)
(plus, + )
(number, 15)
(times, * )
(ident, b )
【输入输出】
输入：
PL/0源程序。例: a+15*b
输出：
(ident, a)
(plus, + )
(number, 15)
(times, * )
(ident, b )
【实验结果】
实验结果与实验要求相同，没有异议，对输入字符采取一个一个读入，到达句柄时，则采取LL(1)文法进行规约。
实验结果如下：

实验结果用文本来进行输入输出，所以在工程目录下还会有一个文本输入，输出文件。分别为in.txt out.txt

【实验体会】
在编写这段代码的过程中，比较麻烦得还是之前的语法预处理阶段，将不满足ll(1)文法的语法转化为标准的ll(1)文法。程序在处理词法分析的过程就是不断通过getsym()这个函数来条用getch()，不断形成一个一个的词汇，供下面语法分析时使用。记录词汇类型的sym是一个枚举类型。使用起来会方便许多，比较系统。其中还用到了文本输入输出的技巧，把读出的词汇保存起来。词法分析还是比较简单，在编写代码的时候没有太大的阻碍。
通过此次实验，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；熟悉了构造词法分析程序的手工方式的相关原理，使用某种高级语言（例如C++语言）直接编写此法分析程序。另外，也让我重新熟悉了C++语言的相关内容，加深了对C++语言的用途的理解。

【实验二】语法分析
【实验目的】给出PL/0文法规范，要求编写PL/0语言的语法分析程序。
【实验内容】已给PL/0语言文法，构造表达式部分的语法分析器。
【实验要求】
1. 将实验一“词法分析”的输出结果，作为表达式语法分析器的输入，进行语法解析，对于语法正确的表达式，报告“语法正确”；对于语法错误的表达式，报告“语法错误”， 指出错误原因。
2. 把语法分析器设计成一个独立一遍的过程。
3. 语法分析器的编写方法采用递归子程序法。
【输入输出】
输入：
PL/0表达式，用实验一的输出形式作为输入。例如: 对于PL/0表达式，a+15*b用下列形式作为输入：
(ident, a)
(plus, + )
(number, 15)
(times, * )
(ident, b )
输出：
对于语法正确的表达式，报告“语法正确”；
对于语法错误的表达式，报告“语法错误”， 指出错误原因。
【实验结果】
实验结果与实验要求相同，没有异议，对输入字符采取一个一个读入，对输入的一个语句进行判断，判断语法的正误，采用对算法的判断，若全为数字则进行最后的计算

【实验体会】
通过语法分析可以判断当前输入语句是否正确，实验通过对数学式的处理来进行对语句的判断是否正确，若正确则只要输入“语句正确”即可，若语句错误则需要根据错误的原因输出错误的理由，以方便编译员修改自己的代码。实现方法是通过对文本文件的输入，当前数据与即将输入的字符串进行匹配，若不符合LL（1）文法则判定为错误，若符合则继续向下完成语法分析。

【源代码】
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include <iostream>
#include <stack>
#include <string>
#include <fstream>
using namespace std;

ifstream fin("in.txt");
ofstream fout("out.txt");

enum symbol
{ //0 1 2 3 4 5 6 7
nul, ident, number, plus, minus, times, slash, oddsym,
eql, neq, lss, leq, gtr, geq, lparen, rparen,
comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym,
whilesym, writesym, readsym, dosym, callsym, constsym, varsym, procsym
};
#define symnum 32
char symwork[symnum][10];//单符号
#define norw 13 //key_word num
#define al 10 //maxstr
#define nmax 10//number long
char word[norw][al];//key word
char ch;//bufferchar getch()
enum symbol sym;
char id[al+1];// ident
char a[al+1];//temp
char ID[al+1];
int cc=0,ll=0,num;//当前在行的位置cc，行字符的长度ll，num数字的值
int nn=0;
char line[81];

int flg=0;// 正数；

//char line[81];
enum symbol ssym[256];
enum symbol wsym[norw];
//int cc,ll;//ch[cc]

int err;
void init()
{
int i;
for(i=0;i<=255;i++)
ssym[i]=nul;//0

ssym['+']=plus;
ssym['-']=minus;
ssym['*']=times;
ssym['/']=slash;
ssym['(']=lparen;
ssym[')']=rparen;
ssym['=']=eql;
ssym[',']=comma;
ssym['.']=period;
ssym['#']=neq;//not equal
ssym[';']=semicolon;

strcpy(&symwork[plus][0],"plus");
strcpy(&symwork[minus][0],"minus");
strcpy(&symwork[times][0],"times");
strcpy(&symwork[slash][0],"slash");
strcpy(&symwork[lparen][0],"lparen");
strcpy(&symwork[rparen][0],"rparen");
strcpy(&symwork[eql][0],"eql");
strcpy(&symwork[comma][0],"comma");
strcpy(&symwork[neq][0],"neq");
strcpy(&symwork[period][0],"period");
strcpy(&symwork[semicolon][0],"semicolon");

strcpy(&word[0][0],"begin");//关键字小写字母
strcpy(&word[1][0],"call");
strcpy(&word[2][0],"const");
strcpy(&word[3][0],"do");
strcpy(&word[4][0],"end");
strcpy(&word[5][0],"if");
strcpy(&word[6][0],"odd");
strcpy(&word[7][0],"procedure");
strcpy(&word[8][0],"read");
strcpy(&word[9][0],"then");
strcpy(&word[10][0],"var");
strcpy(&word[11][0],"while");
strcpy(&word[12][0],"write");

wsym[0]=beginsym;
wsym[1]=callsym;
wsym[2]=constsym;
wsym[3]=dosym;
wsym[4]=endsym;
wsym[5]=ifsym;
wsym[6]=oddsym;
wsym[7]=procsym;
wsym[8]=readsym;
wsym[9]=thensym;
wsym[10]=varsym;
wsym[11]=whilesym;
wsym[12]=writesym;

}

void WordAnalyse()
{
switch(sym)
{
case nul://fout <<"( "<<"nul"<<" , "<<ID<<" )"<<endl;
break;
case ident:fout <<"( "<<"ident"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"ident"<<" , "<<ID<<" )"<<endl;break;
case number:fout <<"( "<<"number"<<" , "<<num<<" )"<<endl;
cout<<"( "<<"number"<<" , "<<num<<" )"<<endl;break;
case plus:fout <<"( "<<"plus"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"plus"<<" , "<<ID<<" )"<<endl;break;
case minus:fout <<"( "<<"minus"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"minus"<<" , "<<ID<<" )"<<endl;break;
case times:fout <<"( "<<"times"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"times"<<" , "<<ID<<" )"<<endl;break;
case slash:fout <<"( "<<"slash"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"slash"<<" , "<<ID<<" )"<<endl;break;
case oddsym:fout <<"( "<<"oddsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"oddsym"<<" , "<<ID<<" )"<<endl;break;
case lss:fout <<"( "<<"lss"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"lsst"<<" , "<<ID<<" )"<<endl;break;
case eql:fout <<"( "<<"eql"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"eql"<<" , "<<ID<<" )"<<endl;break;
case neq:fout <<"( "<<"neq"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"neq"<<" , "<<ID<<" )"<<endl;break;
case leq:fout <<"( "<<"leq"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"leq"<<" , "<<ID<<" )"<<endl;break;
case gtr:fout <<"( "<<"gtr"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"gtr"<<" , "<<ID<<" )"<<endl;break;
case geq:fout <<"( "<<"geq"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"geqt"<<" , "<<ID<<" )"<<endl;break;
case lparen:fout <<"( "<<"lparent"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"lparent"<<" , "<<ID<<" )"<<endl;break;
case rparen:fout <<"( "<<"rparent"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"rparent"<<" , "<<ID<<" )"<<endl;break;
case comma:fout <<"( "<<"comma"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"comma"<<" , "<<ID<<" )"<<endl;break;
case semicolon:fout <<"( "<<"semicolon"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"semicolon"<<" , "<<ID<<" )"<<endl;break;
case period:fout <<"( "<<"period"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"period"<<" , "<<ID<<" )"<<endl;break;
case becomes:fout <<"( "<<"becomes"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"becomes"<<" , "<<ID<<" )"<<endl;break;
case beginsym:fout <<"( "<<"beginsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"beginsym"<<" , "<<ID<<" )"<<endl;break;
case endsym:fout <<"( "<<"endsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"endsym"<<" , "<<ID<<" )"<<endl;break;
case ifsym:fout <<"( "<<"ifsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"ifsym"<<" , "<<ID<<" )"<<endl;break;
case thensym:fout <<"( "<<"thensym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"thensym"<<" , "<<ID<<" )"<<endl;break;
case whilesym:fout <<"( "<<"whilesym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"whilesym"<<" , "<<ID<<" )"<<endl;break;
case writesym:fout <<"( "<<"writesym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"writesym"<<" , "<<ID<<" )"<<endl;break;
case readsym:fout <<"( "<<"readsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"readsym"<<" , "<<ID<<" )"<<endl;break;
case dosym:fout <<"( "<<"dosym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"dosym"<<" , "<<ID<<" )"<<endl;break;
case callsym:fout <<"( "<<"callsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"callsym"<<" , "<<ID<<" )"<<endl;break;
case constsym:fout <<"( "<<"constsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"constsym"<<" , "<<ID<<" )"<<endl;strcpy(ID,"");break;
case varsym:fout <<"( "<<"varsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"varsym"<<" , "<<ID<<" )"<<endl;break;
case procsym:fout <<"( "<<"procsym"<<" , "<<ID<<" )"<<endl;
cout<<"( "<<"procsym"<<" , "<<ID<<" )"<<endl;break;
default :break;
}
}

int getch()
{
if(cc==ll)
{
if(fin.eof())
{
cout<<"program incpmplete!!!"<<endl;
return -1;
}
ll=cc=0;
fin.getline(line,81);
ll=strlen(line);
ch=' ';
return 0;
}
if(cc==0) cout <<line<<endl;
ch=line[cc];
cout<<ch<<endl;
cc++;
nn=cc;
return 0;
}

#define getchdo if(-1==getch()) return -1

//词法分析部分 实验1
int getsym()//读符号 大写字母不要出现
{
int i,j,k; //用于循环等辅助计数
while(ch==' '||ch==9||ch==10) //////////////////////////////////////////
{
getchdo;
}
if(ch>='a'&&ch<='z')
{
k=0;
while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9') //名字或保留字以a.z 开头
{
if(k<al)
{
ID[k]=ch;
k++;
}
getchdo;
}
ID[k]=0;

i=0;
j=norw;

do /* 搜索当前符号是否为保留字 */
{
k=(i+j)/2;
if(strcmp(ID,word[k])<=0)j=k-1;
if(strcmp(ID,word[k])>=0)i=k+1;
}while(i<=j);

if(i-1>j)sym=wsym[k]; else sym=ident; /* 搜索失败，则是名字或数字 */
}
else
{
if(ch>='0'&&ch<='9')
{
k=0;
num=0;
sym=number;
do{
ID[k]=ch;
num=num*10+ch-'0';
k++;
getchdo;
}while(ch>='0'&&ch<='9');
if(flg==1) {
num=-num;
flg=0;
}
ID[k]=0;
k--;
if(k>nmax)
{
// error(30);
;
}
}
else
{
if(ch==':')
{
getchdo;
if(ch=='=')
{
sym=becomes;
strcpy(ID,":=");
getchdo;
}
else
{
sym=nul;
strcpy(ID,"NULL");
}
}
else
{
if(ch=='>')
{
getchdo;
if(ch=='=')
{
sym=geq;
strcpy(ID,">=");
getchdo;
}
else
{
sym=gtr;
strcpy(ID,">");
}
}
else
{
if(ch=='<')
{
getchdo;
if(ch=='=')
{
sym=leq;
strcpy(ID,"<=");
getchdo;
}
else
{
sym=lss;
strcpy(ID,"<");
}
}
else
{
sym=ssym[ch];
strcpy(ID,&ch);
//if(sym!=period)
{
getchdo;
}
}
}
}
}
}
return 1;
}

//语法分析部分 实验2
int lp=0;
int rp=0;
#define getsymdo if(-1==getsym()) return -1
#define expressiondo() if(-1==expression()) return -1
#define termdo() if(-1==term()) return -1
#define factordo() if(-1==factor()) return -1
int expression();

//语法分析
int factor()
{
if(sym!=ident &&sym!=number&&sym!=lparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("error----Factor Needs Ident or Number or Lparen\n");
}

if ((sym == ident) || (sym == number) || (sym == lparen))
{

if (sym == ident)
{
WordAnalyse();
if(getsym()==-1)
{
return -1;
}
if(sym!=times&&sym!=slash&&sym!=plus&&sym!=minus&&sym!=rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("变量后没有跟上+-*\\ \n");
}
if(lp==0 && sym==rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("没有左括号匹配\n");
}
}
else if (sym == number)
{
WordAnalyse();
if(getsym()==-1)
{

return -1;

}

if(sym!=times&&sym!=slash&&sym!=plus&&sym!=minus&&sym!=rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("数字后没有跟上+-*\\ \n");
}
if(lp==0 && sym==rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("没有左括号匹配\n");
}
}
else if (sym == lparen)
{
WordAnalyse();
lp++;
if(getsym()==-1)
{
lp--;
err++;
if(err==1) printf("语法错误: \n");
printf("error----Needs Rparen \n");
return -1;
}
expressiondo();
if (sym == rparen)
{
WordAnalyse();
lp--;
if(getsym()==-1)
{
return -1;
}

if(sym!=times&&sym!=slash&&sym!=plus&&sym!=minus)
{
err++;
if(err==1) printf("语法错误: \n");
printf("括号后没有跟上+-*\\ \n");
}
}
else
{
err++;
if(err==1) printf("语法错误: \n");
printf("error----Needs Rparen \n");
}
}
}
return 0;
}

int term()
{
factordo();
if(sym!=times&&sym!=slash&&sym!=plus&&sym!=minus&&sym!=ident&&sym!=number&&sym!=lparen&&sym!=rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("不能识别字符\n");
}

while ((sym == times) || (sym == slash))
{
WordAnalyse();
if(getsym()==-1)
{
err++;
if(err==1) printf("语法错误: \n");
printf("* \\ 后缺项\n");
return -1;
}
factordo();
}
return 0;
}

int expression()
{

if ((sym == plus) || (sym == minus))
{
//cout<<strlen(ID)<<endl;
if (sym==minus&&2==strlen(ID)+1)
flg=1;
else
{
flg=0;
WordAnalyse();
}
getsymdo;
termdo();
}
else
{
//WordAnalyse();
termdo();
}
if(sym!=times&&sym!=slash&&sym!=plus&&sym!=minus&&sym!=ident&&sym!=number&&sym!=lparen&&sym!=rparen)
{
err++;
if(err==1) printf("语法错误: \n");
printf("不能识别字符\n");
}
while ((sym == plus) || (sym == minus))
{
WordAnalyse();
if(getsym()==-1)
{
err++;
if(err==1) printf("语法错误: \n");

printf("+ - 后缺项\n");
return -1;
}
termdo();
}
return 0;
}

int main(int argc, char* argv[])
{

init();
err=0;
ifstream fin("in.txt");
ofstream fout("out.txt");
ch=' ';
lp=0;
getsymdo;
expression();
if(err==0) cout<<"语法正确"<<endl;
else
cout<<"语法错误，错误个数： "<<err<<endl;
}