搜档网
当前位置:搜档网 › 4编译原理_算符优先算法分析程序

4编译原理_算符优先算法分析程序

4编译原理_算符优先算法分析程序
4编译原理_算符优先算法分析程序

#include

#include

#include

typedef struct

{ char R;

char r;

int flag;

}array;

typedef struct

{ char E;

char e;

}charLode;

typedef struct

{ charLode *base;

int top;

}charstack;

char str[80][80],arr[80][80],brr[80][80]; array F[20];

int m,kk,p,ppp,FF=1;

char r[10];

int crr[20][20],FLAG=0;

char ccrr1[1][20],ccrr2[20][1];

void Initstack(charstack &s)//定义栈

{ s.base=new charLode[20];

s.top=-1;

}

void push(charstack &s,charLode w) //入栈{ s.top++;

s.base[s.top].E=w.E;

s.base[s.top].e=w.e;

}

void pop(charstack &s,charLode &w) //出栈{ w.E=s.base[s.top].E;

w.e=s.base[s.top].e;

s.top--;

}

int IsEmpty(charstack s) //判断是否到栈顶

{ if(s.top==-1)

return 1;

else

return 0;

}

int IsLetter(char ch) //判断是不是大写字母(非终结符)

{ if(ch>='A'&&ch<='Z')

return 1;

else

return 0;

}

int judge1(int n)

{ int j=3,flag=0;

for(int i=0;i<=n;i++)

while(str[i][j]!='\0')

{ char a=str[i][j];

char b=str[i][j+1];

if(IsLetter(a)&&IsLetter(b)) //两个非终结符相连,不是算符文法 { flag=1;

break;

}

else

j++;

}

if(flag==1) //根据flag设定返回值

return 0;

else

return 1;

}

void judge2(int n)

{ for(int i=0;i<=n;i++)

if(str[i][3]=='~'||FLAG==1)//'~'代表空

{ cout<<"文法G不是算符优先文法!"<

FF=0;

break;

}

if(i>n)

cout<<"文法G是算符优先文法!"<

int search1(char r[],int kk,char a)

{ for(int i=0;i

if(r[i]==a)

break;

if(i==kk)

return 0;

else

return 1;

}

void createF(int n)

{ int k=0,i=1;char g;

char t[10];//t数组用来存放非终结符

t[0]=str[0][0];

while(i<=n)

{ if(t[k]!=str[i][0])

{ k++;

t[k]=str[i][0];

g=t[k];

i++; }

else i++; }

kk=0;

char c;

for(i=0;i<=n;i++)

{ int j=3;

while(str[i][j]!='\0')

{ c=str[i][j];

if(IsLetter(c)==0)

{ if(!search1(r,kk,c))

r[kk]=c;

kk++;//r数组用来存放终结符 } j++; } }

m=0;

for(i=0;i

for(int j=0;j

{ F[m].R=t[i];

F[m].r=r[j];

F[m].flag=0;

m++; }}

void search(charLode w)

{ for(int i=0;i

if(F[i].R==w.E&&F[i].r==w.e)

{ F[i].flag=1;break; }

}

void FirstVT(int n)//求FirstVT

{ charstack sta;

charLode w;

int i=0;

Initstack(sta);

while(i<=n)

{ int k=3;

w.E=str[i][0];

char a=str[i][k];

char b=str[i][k+1];

if(!IsLetter(a)) //产生式的后选式的第一个字符就是终

{ w.e=a;

push(sta,w);

search(w);

i++;

}

else if(IsLetter(a)&&b!='\0'&&!IsLetter(b)) //产生式的后选式的第一个字符是非终结符的情况

{ w.e=b;

push(sta,w);

search(w);

i++; }

else i++;

}

charLode ww;

while(!IsEmpty(sta))

{ pop(sta,ww);

for(i=0;i<=n;i++)

{ w.E=str[i][0];

if(str[i][3]==ww.E&&str[i][4]=='\0') { w.e=ww.e;

push(sta,w);

search(w);

break; } } }

p=0;int k=1;i=1;

while(i

{ if(F[i-1].flag==1)

{ arr[p][0]=F[i-1].R;

arr[p][k]=F[i-1].r;

}

while(F[i].flag==0&&i

i++;

if(F[i].flag==1)

{ if(F[i].R==arr[p][0])

k++;

else {arr[p][k+1]='\0';p++;k=1;} i++; } } }

void LastVT(int n)//求LastVT

{ charstack sta;

charLode w;

for(int i=0;i

F[i].flag=0;

i=0;

Initstack(sta);

while(i<=n)

{ int k=strlen(str[i]);

w.E=str[i][0];

char a=str[i][k-1];

char b=str[i][k-2];

if(!IsLetter(a))

{ w.e=a;

push(sta,w);

search(w);

i++; }

else if(IsLetter(a)&&!IsLetter(b))

{ w.e=b;

push(sta,w);

search(w);

i++; }

else i++; }

charLode ee;

while(!IsEmpty(sta))

{ pop(sta,ee);

for(i=0;i<=n;i++)

{ w.E=str[i][0];

if(str[i][3]==ee.E&&str[i][4]=='\0')

{ w.e=ee.e;

push(sta,w);

search(w); } } }

int k=1;i=1;

ppp=0;

while(i

{ if(F[i-1].flag==1)

{ brr[ppp][0]=F[i-1].R;

brr[ppp][k]=F[i-1].r;

}

while(F[i].flag==0&&i

i++;

if(F[i].flag==1)

{ if(F[i].R==arr[ppp][0])

k++;

else {brr[ppp][k+1]='\0';ppp++;k=1;} i++; } } }

void createYXB(int n)//构造优先表

{ int i,j;

for(j=1;j<=kk;j++)

ccrr1[0][j]=r[j-1];

for( i=1;i<=kk;i++)

ccrr2[i][0]=r[i-1];

for(i=1;i<=kk;i++)

for(j=1;j<=kk;j++)

crr[i][j]=0;

int I=0,J=3;

while(I<=n)

{ if(str[I][J+1]=='\0') //扫描右部

{ I++;

J=3;

}

else

{ while(str[I][J+1]!='\0')

{ char aa=str[I][J];

char bb=str[I][J+1];

if(!IsLetter(aa)&&!IsLetter(bb))//优先及等于的情况,用1值表示等于 { for(i=1;i<=kk;i++)

{ if(ccrr2[i][0]==aa)

break;

}

for(j=1;j<=kk;j++)

{ if(ccrr1[0][j]==bb)

break;

}

if(crr[i][j]==0)

crr[i][j]=1;

else { FLAG=1;

I=n+1;

}

J++;

}

if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str[I][ J+2]))//优先及等于的情况

{ for(i=1;i<=kk;i++

{ if(ccrr2[i][0]==aa) break;

}

for(int j=1;j<=kk;j++)

{

if(ccrr1[0][j]==str[I][J+2])

break;

}

if(crr[i][j]==0)

crr[i][j]=1;

else

{

FLAG=1;

I=n+1;

}

}

if(!IsLetter(aa)&&IsLetter(bb))//优先及小于的情况,用2值表示小于 {

for(i=1;i<=kk;i++)

{

if(aa==ccrr2[i][0])

break;

}

for(j=0;j<=p;j++)

{

if(bb==arr[j][0])

break;

}

for(int mm=1;arr[j][mm]!='\0';mm++)

{

for(int pp=1;pp<=kk;pp++)

{

if(ccrr1[0][pp]==arr[j][mm])

break;

}

if(crr[i][pp]==0)

crr[i][pp]=2;

else {

FLAG=1;I=n+1;

}

}

J++;

}

if(IsLetter(aa)&&!IsLetter(bb))//优先及大于的情况,用3值表示大于 {

for(i=1;i<=kk;i++)

{

if(ccrr1[0][i]==bb)

break;

}

for(j=0;j<=ppp;j++)

{ if(aa==brr[j][0]) break;

}

for(int mm=1;brr[j][mm]!='\0';mm++) {

for(int pp=1;pp<=kk;pp++)

{

if(ccrr2[pp][0]==brr[j][mm])

break;

}

if(crr[pp][i]==0)

crr[pp][i]=3;

else {FLAG=1;I=n+1;}

}

J++; } } } }}

int judge3(char s,char a)

{

int i=1,j=1;

while(ccrr2[i][0]!=s)

i++;

while(ccrr1[0][j]!=a)

j++;

if(crr[i][j]==3)

return 3;

else

if(crr[i][j]==2)

return 2;

else

if(crr[i][j]==1)

return 1;

else

return 0;

}

void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印归约的过程

{

cout<

for(int i=0;i<=k;i++)

cout<

cout<<" ";

for(i=q;i<=ii;i++)

cout<

cout<<" ";

}

void process(char STR[][20],int ii)//对输入的字符串进行归约的过程

{

cout<<"步骤"<<" "<<"符号栈"<<" "<<"输入串"<<" "<<"动作"<

char s[40],a;

s[k]='#';

print(s,STR,q,u,ii,k);

cout<<"预备"<

k++;

u++;

s[k]=STR[0][q];

q++;

print(s,STR,q,u,ii,k);

cout<<"移进"<

while(q<=ii)

{

a=STR[0][q];

if(!IsLetter(s[k])) j=k;

else j=k-1;

b=judge3(s[j],a);

if(b==3)//大于的情况进行归约

{

while(IsLetter(s[j-1]))

j--;

for(i=j;i<=k;i++)

s[i]='\0';

k=j;

s[k]='N';

u++;

print(s,STR,q,u,ii,k);

cout<<"归约"<

}

else if(b==2||b==1)//小于或等于的情况移进

{

k++;

s[k]=a;

u++;

q++;

print(s,STR,q,u,ii,k);

if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')

cout<<"接受"<

else cout<<"移进"<

}

else

{

cout<<"出错"<

break;

}

}

if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')

cout<<"归约成功"<

else cout<<"归约失败"<

}

void main()

{

int n,i,j;

cout<<"请输入你要定义的文法G的产生式的个数n:"; cin>>n;

cout<<"请输入文法产生式:"<

for(i=0;i

{

gets(str[i]);

j=strlen(str[i]);

str[i][j]='\0';

}

str[i][0]='Q'; //最末行添加扩展

str[i][1]='-';

str[i][2]='>';

str[i][3]='#';

str[i][4]=str[0][0];

str[i][5]='#';

cout<<"你定义的产生式如下:"<

str[i][6]='\0';

for(i=0;i<=n;i++)

cout<

if(judge1(n)==0) //判断文法G是否为算符文法

cout<<"文法G不是算符文法!"<

if(judge1(n)==1)

{ cout<<"文法G是算符文法!"<

createF(n);

FirstVT(n);

LastVT(n);

createYXB(n);

for(i=0;i<=p;i++)//打印FirstVT

{ cout<<"FirstVT("<

cout<

cout<

}

cout<<"FirstVT(Q)={#}"<

for(i=0;i<=ppp;i++)//打印LastVT

{

cout<<"LastVT("<

for(int l=1;brr[i][l+1]!='\0';l++)

cout<

cout<

}

cout<<"LastVT(Q)={#}"<

cout<<"优先表如下:"<

for(i=1;i

{ cout<<" ";

cout<

cout<

for(i=1;i

{ cout<

for(j=1;j

{ if(crr[i][j]==0)

cout<<" ";

else if(crr[i][j]==1)

cout<<"=";

else if(crr[i][j]==2)

cout<<"<";

else if(crr[i][j]==3)

cout<<">";

cout<<" ";

}

cout<

judge2(n);//判断文法G是否为算符优先文法 if(FF==1)

{ char STR[1][20];

cout<<"请输入要规约的字符串:"<

int ii=strlen(STR[0]);

STR[0][ii]='#';

cout<<"下面是规约的过程:"<

process(STR,ii); }}

编译原理课程设计报告_算符优先分析法

编译原理课程设计报告_算符优先分析法 编译原理课程设计报告 选题名称: 算符优先分析法 系(院): 计算机工程学院 专业: 计算机科学与技术 班级: 姓名: 学号: 指导教师: 学年学期: 7>2012 ~ 2013 学年第 1 学期 2012年 12 月 04 日 设计任务书 课题名称算符优先分析法 设计 目的 通过一周的课程设计,对算符优先分析法有深刻的理解,达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验环境Windows2000以上操作系统,Visual C++6.0编译环境 任务要求 1.判断文法是否为算符优先文法,对相应文法字符串进行算符优先分析; 2.编写代码,实现算符优先文法判断和相应文法字符串的算符优先分析; 3.撰写课程设计报告; 4提交报告。工作进度计划序号起止日期工作内容 1 理论辅导,搜集资料 2 ~编写代码,上机调试

3 撰写课程设计报告 4 提交报告 指导教师(签章): 年月日 摘要: 编译原理是计算机专业重要的一门专业基础课程,内容庞大,涉及面广,知识点多。本次课程设计的目的正是基于此,力求为学生提供一个理论联系实际的机会,通过布置一定难度的课题,要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的算符优先文法的相应的字符串进行算符优先分析,并输出算符优先分析的过程。算符优先分析法特别有利于表达式的处理,宜于手工实现。算符优先分析过程是自下而上的归约过程,但这种归约未必是严格的规范归约。而在整个归约过程中,起决定作用的是相继连个终结符之间的优先关系。因此,所谓算符优先分析法就是定义算符之间的某种优先关系,并借助这种关系寻找句型的最左素短语进行归约。通过实践,建立系统设计的整体思想,锻炼编写程序、调试程序的能力,学习文档编写规范,培养独立学习、吸取他人经验、探索前言知识的习惯,树立团队协作精神。同时,课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷。 关键字:编译原理;归约;算符优先分析;最左素短语; 目录 1 课题综述 1 1.1 课题来源 1 1.2课题意义 1 1.3 预期目标 1 1.4 面对的问题 1 2 系统分析 2

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

编译原理语法分析实验报告 - 班级: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(标识符<标识符后缀>)

编译原理-编写递归下降语法分析器

学号107 成绩 编译原理上机报告 名称:编写递归下降语法分析器 学院:信息与控制工程学院 专业:计算机科学与技术 班级:计算机1401班 姓名:叶达成 2016年10月31日

一、上机目的 通过设计、编制、调试一个递归下降语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,掌握常用的语法分析方法。通过本实验,应达到以下目标: 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理,添加语义加工工作比较方便。 递归下降分析程序的实现思想是:识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是:选择正确的右部,扫描完相应的字。在右部中有非终结符号时,调用该非终结符号对应的子程序来完成。 自上向下分析过程中,如果带回溯,则分析过程是穷举所有可能的推导,看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术,当选择某非终结符的产生时,可根据输入串的当前符号以及各产生式右部首符号而进行,效率高,且不易出错。 无回溯的自上向下分析技术可用的先决条件是:无左递归和无回溯。 无左递归:既没有直接左递归,也没有间接左递归。 无回溯:对于任一非终结符号U的产生式右部x1|x2|…|x n,其对应的字的首终结符号两两不相交。 如果一个文法不含回路(形如P?+ P的推导),也不含以ε为右部的产生式,那么可以通过执行消除文法左递归的算法消除文法的一切左递归(改写后的文法可能含有以ε为右部的产生式)。 三、上机结果 测试数据: (1)输入一以#结束的符号串(包括+—*/()i#):在此位置输入符号串例如:i+i*i# (2)输出结果:i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单: #include #include char str[50]; int index=0; void E(); //E->TX; void X(); //X->+TX | e void T(); //T->FY void Y(); //Y->*FY | e void F(); //F->(E) | i int main() /*递归分析*/ { int len; int m;

编译原理 实验3 算符优先分析

编译原理实验3 算符优先分析 一、实验目的 通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表、对给定符号串进行分析的程序,了解构造算符优先分析表的步骤,对文法的要求,生成算符优先关系表的算法,对给定的符号串进行分析的方法。 二、实验内容 1. 给定一文法G,输出G的每个非终结符的FIRSTVT集和LASTVT集。 2. 构造算符优先表。 3. 对给定的符号串进行分析,包含符号栈,符号栈栈顶符号和输入串当前符号的优先级,最左素短语和使用的产生式和采取的动作。 三、程序思路 在文法框内输入待判断文法产生式,格式E->a|S,注意左部和右部之间是“->”,每个产生式一行,ENTER键换行。文法结束再输入一行G->#E# 1. 先做文法判断,即可判断文法情况。 2. 若是算符优先文法,则在优先表栏显示优先表。 3. 写入要分析的句子,按回车即可。 4. 在分析过程栏,可以看到整个归约过程情况 四、实验结果 FunctorFirst.h #include #include #include #include usingnamespace std;

#define rightlength 20 #define product_num 20 // 产生式最多个数 #define num_noterminal 26 // 非终结符最多个数 #define num_terminal 26 // 终结符最多个数 struct Production { char Left; char Right[rightlength]; int num; }; struct VT { bool vt[num_noterminal][num_terminal]; }; struct Stack { char P; char a; }; class CMyDlg { public:CMyDlg(); void InputRule(); CString showLastVT(); CString showFirstVT(); CString shownoTerminal(char G[]); CString showTerminal(char g[]); CString showLeftS(char S[], int j, int k); void InitAll(); CString showSentence(CString sen, int start); CString showStack(char S[], int n); void Initarry(char arry[], int n); CString ProdtoCStr(Production prod); int selectProd(int i, int j, char S[]); void preFunctor(CString sen); void insertFirstVT(Stack S[], int&sp, char P, char a); void insertLastVT(Stack S[], int&sp, char P, char a); void ShowPreTable(); void createPreTable();

编译原理词法分析和语法分析报告+代码(C语言版)

词法分析 一、实验目的 设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都是小写。 (2)运算符和界符 : = + - * / < <= <> > >= = ; ( ) # (3)其他单词是标识符(ID)和整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。

3.1 主程序示意图: 主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 (2)程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想: 首先设置3个变量:①token用来存放构成单词符号的字符串;②sum用来整型单词;③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。

编译原理实验4算符优先算法

一、实验目的与任务 算术表达式和赋值语句的文法可以是(你可以根据需要适当改变): S→i=E E→E+E|E-E|E*E|E/E|(E)|i 根据算符优先分析法,将赋值语句进行语法分析,翻译成等价的一组基本操作,每一基本操作用四元式表示。 二、实验涉及的相关知识点 算符的优先顺序。 三、实验内容与过程 如参考C语言的运算符。输入如下表达式(以分号为结束):(1)a = 10; (2)b = a + 20; 注:此例可以进行优化后输出(不作要求):(+,b,a,20) (3)c=(1+2)/3+4-(5+6/7); 四、实验结果及分析 (1)输出:(=, a,10,-) (2)输出:(=,r1,20,-)

(+,r2,a,r1) (=,b,r2,-) (3)输出:(+,r1,1,2) (/,r2,r1,3) (/,r3,6,7) (+,r4,5,r3,) (+,r5,r2,4) (-,r6,r5,r4) (=,c,r6,-) 五、实验有关附件(如程序、附图、参考资料,等) ... ... h == '#') o][Peek(n0).No]; if(r == '<') h == 'E'&& Peek(1).ch == '#' && Token[ipToken].ch == '#') return TRUE; else return FALSE; } h) { k = TRUE; h == 'E') { n ++; } return n; } 词结束(遇到“#”号),无法移进,需要规约,返回:1 词没有结束,需判断是否可以移进 栈单词<=单词:移进后返回:2 栈单词>单词:不能移进,需要规约,返回:1 单词没有优先关系:出错,返回:-1 int MoveIn() { SToken s,t; h = '#';

编译原理词法分析和语法分析报告 代码(C语言版)

词法分析 三、词法分析程序的算法思想: 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3.1 主程序示意图: 扫描子程序主要部分流程图 其他

词法分析程序的C语言程序源代码: // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针; // 全局变量buffer与line对应保存源文件字符及其行号,char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意,第"<

编译原理第六章答案

第6 章自底向上优先分析 第1 题 已知文法G[S]为: S→a|∧|(T) T→T,S|S (1) 计算G[S]的FIRSTVT 和LASTVT。 (2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。 (3) 计算G[S]的优先函数。 (4) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。 答案: 文法展开为: S→a S→∧ S→(T) T→T,S T→S (1) FIRSTVT - LASTVT 表: 表中无多重人口所以是算符优先(OPG)文法。 友情提示:记得增加拓广文法 S`→#S#,所以# FIRSTVT(S),LASTVT(S) #。 (3)对应的算符优先函数为:

Success! 对输入串(a,(a,a))# 的算符优先分析过程为: Success! 第2 题 已知文法G[S]为: S→a|∧|(T) T→T,S|S

(1) 给出(a,(a,a))和(a,a)的最右推导,和规范归约过程。 (2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。答案:

(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串,而与 非终结符无关,只需知道把当前可归约串归约为某一个非终结符,不必知道该非终结符的名字是什么,因此去掉了单非终结符的归约。 规范归约的可归约串是句柄,并且必须准确写出可归约串归约为哪个非终结符。 第3题:

有文法G[S]: S V V T|ViT T F|T+F F )V*|( (1) 给出(+(i(的规范推导。 (2) 指出句型F+Fi(的短语,句柄,素短语。 (3) G[S]是否为OPG?若是,给出(1)中句子的分析过程。 因为该文法是OP,同时任意两个终结符的优先关系唯一,所以该文法为OPG。(+(i(的分析过程

编译原理作业集-第五章-修订(精选.)

第五章语法分析—自下而上分析 本章要点 1. 自下而上语法分析法的基本概念: 2. 算符优先分析法; 3. LR分析法分析过程; 4. 语法分析器自动产生工具Y ACC; 5. LR分析过程中的出错处理。 本章目标 掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。 本章重点 1.自下而上语法分析的基本概念:归约、句柄、最左素短语; 2.算符优先分析方法:FirstVT, LastVT集的计算,算符优先表的构造,工作原理;3.LR分析器: (1)LR(0)项目集族,LR(1)项目集簇; (2)LR(0)、SLR、LR(1)和LALR(1)分析表的构造; (3)LR分析的基本原理,分析过程; 4.LR方法如何用于二义文法; 本章难点 1. 句柄的概念; 2. 算符优先分析法; 3. LR分析器基本; 作业题 一、单项选择题: 1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀; b. 可归前缀; c. 项目; d. 句柄; 2. 算符优先分析法每次都是对________进行归约: (a)句柄(b)最左素短语(c)素短语(d)简单短语

3. 有文法G=({S},{a},{S→SaS,S→ε},S),该文法是________。 a. LL(1)文法; b.二义性文法; c.算符优先文法; d.SLR(1)文法; 4. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,和LL(1)分析法属于自顶向下分析; a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 5. 自底向上语法分析采用分析法,常用的是自底向上语法分析有算符优先分析法和LR分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进-归约 6. 一个LR(k)文法,无论k取多大,。 a. 都是无二义性的; b. 都是二义性的; c. 一部分是二义性的; d. 无法判定二义性; 7. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,和LR分析法属于自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 8. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,自顶向下分析试图为输入符号串构造一个; a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 9. 在编译程序中,语法分析分为自顶向下分析和自底向上分析两类,自底向上分析试图为输入符号串构造一个。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 10. 采用自顶向下分析方法时,要求文法中不含有。 a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归 11. LR分析是寻找右句型的;而算符优先分析是寻找右句型的。 a. 短语; b. 素短语; c. 最左素短语; d. 句柄 12. LR分析法中分析能力最强的是;分析能力最弱的是。 a. SLR(1); b. LR(0); c. LR(1); d. LALR(1) 13. 设有文法G: T->T*F | F F->F↑P | P P->(T) | a 该文法句型T*P↑(T*F)的最左直接短语是下列符号串________。 a. (T*F), b. T*F, c. P, d. P↑(T*F) 14. 在通常的语法分析方法中,()特别适用于表达式的分析。 a.算符优先分析法b.LR分析法c.递归下降分析法d.LL(1)分析法 15. .运算符的优先数之间有几种关系。 a.3种 b. 2种 c. 4种 d. 1种 16. 算符优先法属于() a.自上而下分析法 b.LR分析法 c.SLR分析法 d.自下而上分析法 17. 在LR分析法中,分析栈中存放的状态是识别规范句型的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目 一.答案: 1. b; 2. b; 3. b; 4. d; 5. d; 6. a; 7. c; 8. c; 9. d;10. b;11. d,c;12. c,b;13. a;14. a 15. a;16. d;17. c;

编译原理-语法分析-算符优先文法分析器

编译原理实验报告 实验名称:编写语法分析分析器实验类型: 指导教师: 专业班级: 学号: 电子邮件: 实验地点: 实验成绩:

一、实验目的 通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法,如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序,至少选一题。 2、选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式)作为分析对象,并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求: (a)根据算符优先分析算法,编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入: Ⅰ:通过构造算符优先关系表,设计编制并调试一个算法优先分析程序Ⅱ:输入FIRSTVT,LASTVT集合,由程序自动生成该文法的算符优先关系矩阵。 Ⅲ:输入已知文法,由程序自动生成该文法的算符优先关系矩阵。(b)程序具有通用性,即所编制的语法分析程序能够使用于不同文法以及各种输入单词串,并能判断该文法是否为算符文法和算符优先文法。 (c)有运行实例。对于输入的一个文法和一个单词串,所编制的语法分析程序应能正确地判断,此单词串是否为该文法的句子,并要求输出分析过程。 三、实验结果 算符优先分析器: 测试数据:E->E+T|T T->T*F|F F->(E)|i 实验结果:(输入串为i+i*i+i)

四、讨论与分析 自下而上分析技术-算符优先分析法: 算符文法:一个上下无关文法G,如果没有且没有P→..QR...(P ,Q ,R属于非终结符),则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...,则a∈FIRSTVT(P)。 2、若有产生式P→...,则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出:若存在某个产生式:…P…,则对所有:b∈firstVT(P)都有:a≦b。 构造优先关系表: 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式,则对于每个b∈FIRSTVT(P)都有

编译原理简答

1、给出算符优先文法的定义,算符优先表是否都存在对应的优先函数给出优先函数的定义。 设有一不含ε产生式的算符文法G,如果对任意两个终结符对a,b之间至多只有、和h三种关系的一种成立,则称G一个算符优先文法。 算符优先关系表不一定存在对应的优先函数 优先函数为文法字汇表中 2、考虑文法G[T]: T→T*F|F F→F↑P|P P→(T)|i 证明T*P↑(T*F)是该文法的一个句型,并指出直接短语和句柄。 首先构造T*P↑(T*F)的语法树如图所示。 句型T*P↑(T*F)的语法树 由图可知,T*P↑(T*F)是文法G[T]的一个句型。 直接短语有两个,即P和T*F;句柄为P。

3、文法G[S]为: S→SdT | T T→T

4、目标代码有哪几种形式生成目标代码时通常应考虑哪几个问题 三种形式:可立刻执行的机器语言代码;汇编语言程序;待装配的机器语言代码模块 考虑的问题包括: 每一个语法成分的语义; 目标代码中需要哪些信息,怎样截取这些信息。 5、符号表的作用是什么符号表的查找的整理技术有哪几种 作用:登记源程序中出现的各种名字及其信息,以及编译各阶段的进展状况。主要技术:线性表,对折查找与二叉树,杂凑技术。 1、实现高级语言程序的途径有哪几种它们之间的区别 计算机执行用于高级语言编写的程序主要有两种途径:解释和编译。 在解释方式下,翻译程序并不对高级语言进行彻底的翻译,而是读入一条语句,就解释其含义并执行,然后再读入下一条语句,再执行。 在编译方式下,翻译程序先对高级语言进行彻底的翻译并生成目标代码,然后再对目标代码进行优化,即对源程序的处理是先翻译后执行。 从速度上看,编译方式下,源程序的执行比解释方式下快,但在解释方式下,有

编译原理 六章 算符优先分析法

第六章算符优先分析法 课前索引 【课前思考】 ◇什么是自下而上语法分析的策略? ◇什么是移进-归约分析? ◇移进-归约过程和自顶向下最右推导有何关系? ◇自下而上语法分析成功的标志是什么? ◇什么是可归约串? ◇移进-归约过程的关键问题是什么? ◇如何确定可归约串? ◇如何决定什么时候移进,什么时候归约? ◇什么是算符文法?什么是算符优先文法? ◇算符优先分析是如何识别可归约串的? ◇算符优先分析法的优缺点和局限性有哪些? 【学习目标】 算符优先分析法是自下而上(自底向上)语法分析的一种,尤其适应于表达式的语法分析,由于它的算法简单直观易于理解,因此,也是学习其它自下而上语法分析的基础。通过本章学习学员应掌握: ◇对给定的文法能够判断该文法是否是算符文法 ◇对给定的算符文法能够判断该文法是否是算符优先文法 ◇对给定的算符文法能构造算符优先关系表,并能利用算符优先关系表判断该文法是否是算符优先文法。 ◇能应用算符优先分析算法对给定的输入串进行移进-归约分析,在分析的每一步能确定当前应移进还是归约,并能判断所给的输入串是否是该文法的句子。 ◇了解算符优先分析法的优缺点和实际应用中的局限性。 【学习指南】 算符优先分析法是自下而上语法分析的一种,它的算法简单、直观、易于理解,所以通常作为学习其它自下而上语法分析的基础。为学好本章内容,学员应复习有关语法分析的知识,如:什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。 【难重点】 ◇通过本章学习后,学员应该能知道算符文法的形式。 ◇对一个给定的算符文法能构造算符优先关系分析表,并能判别所给文法是否为算符优先文法。 ◇分清规范句型的句柄和最左素短语的区别,进而分清算符优先归约和规范归约的区别。 ◇算符优先分析的可归约串是句型的最左素短语,在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析(归约)步骤,并最终判断所给输入串是否为该文法的句子。 ◇深入理解算符优先分析法的优缺点和实际应用中的局限性。 【知识点】

编译原理词法分析器

一、实验目的 了解词法分析程序的两种设计方法:1.根据状态转换图直接编程的方式;2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1.根据状态转换图直接编程 编写一个词法分析程序,它从左到右逐个字符的对源程序进行扫描,产生一个个的单词的二元式,形成二元式(记号)流文件输出。在此,词法分析程序作为单独的一遍,如下图所示。 具体任务有: (1)组织源程序的输入 (2)拼出单词并查找其类别编号,形成二元式输出,得到单词流文件 (3)删除注释、空格和无用符号 (4)发现并定位词法错误,需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 (5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,类型(整型、实型、字符型),分配的数据区地址 注:词法分析阶段只填写变量名,其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构:常量名,常量值 2.编写DFA模拟程序 算法如下: DFA(S=S0,MOVE[][],F[],ALPHABET[]) /*S为状态,初值为DFA的初态,MOVE[][]为状态转换矩阵,F[] 为终态集,ALPHABET[] 为字母表,其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar();//读 i=0; while(nextchar!=NULL)//NULL代表此类单词 { if (nextcha r!∈ALPHABET[]){ERROR(“非法字符”),return(“非法字符”);} S=MOVE[S][nextchar] //下一状态 if(S=NULL)return(“不接受”);//下一状态为空,不能识别,单词错误 wordbuffer[i]=nextchar ;//保存单词符号 i++; nextchar=getchar(); } Wordbuffer[i]=‘\0’;

编译原理 语法分析器 (java完美运行版)

实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质,为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL (1 )分析程序,以便对任意输入的符号串 进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号 以及LL(1)分析表,对输入符号串自上而下的分析过程。 三、LL(1)分析法实验设计思想及算法 ◆模块结构: (1)定义部分:定义常量、变量、数据结构。 (2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等); (3)控制部分:从键盘输入一个表达式符号串; (4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。

四、实验要求 1、编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式,应输出错误提示信息。 3、对下列文法,用LL(1)分析法对任意输入的符号串进行分析:(1)E->TG (2)G->+TG|—TG (3)G->ε (4)T->FS (5)S->*FS|/FS (6)S->ε (7)F->(E) (8)F->i 输出的格式如下:

五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3;

编译原理算符优先算法语法分析实验报告

数学与计算机学院编译原理实验报告 年级专业学号姓名成绩 实验题目算符优先分析法分析器的设计实验日期 一、实验目的: 设计一个算符优先分析器,理解优先分析方法的原理。 二、实验要求: 设计一个算符优先分析器 三、实验内容: 使用算符优先分析算法分析下面的文法: E’→#E# E →E+T | T T →T*F | F F →P^F | P P →(E) | i 其中i可以看作是一个终结符,无需作词法分析。具体要求如下: 1、如果输入符号串为正确句子,显示分析步骤,包括分析栈中的内容、优先关系、输入符号串的变化情况; 2、如果输入符号串不是正确句子,则指示出错位置。 四、实验结果及主要代码: 1.主要代码 void operatorp()

{ char s[100]; char a,Q; int k,j,i,l; string input,temp; cin>>input; cout<<"步骤"<<'\t'<<"栈"<<'\t'<<"优先关系"<<'\t'<<"当前符号"<<'\t'<<"剩余输入串"<<'\t'<<"移进或归约"<') { cout<<'('<

for(l=1;l'<<'\t'<

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

词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2、1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都就是小写。 (2)运算符与界符 : = + - * / < <= <> > >= = ; ( ) # (3)其她单词就是标识符(ID)与整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符与换行符组成。空格一般用来分隔ID、SUM、运算符、界符与关键字,词法分析阶段通常被忽略。 2、2 各种单词符号对应的种别码: 表2、1 各种单词符号对应的种别码 2、3 词法分析程序的功能: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务就是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想就是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3、1 主程序示意图:

主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴ 关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin ”, “if ”, “then ”, “while ”, “do ”, “end ”,}; (2)3、2 扫描子程序的算法思想: 首先设置3个变量:①token 用来存放构成单词符号的字符串;②sum 用来整型单词;③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。

昆明理工大学 编译原理 实验二 语法分析器

昆明理工大学信息工程与自动化学院学生实验报告 (2011 —2012 学年第 1 学期) 课程名称:编译原理开课实验室: 445 2011年 12 月 19日年级、专业、 班 计科093 学号200910405310 姓名孙浩川成绩 实验项目名称语法分析器指导教师严馨 教 师评语 该同学是否了解实验原理: A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力: A.强□ B.中等□ C.差□ 该同学的实验是否达到要求: A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范: A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录: A.详细□ B.一般□ C.没有□ 教师签名: 年月日 一、实验目的及内容 实验目的:编制一个语法分析程序,实现对词法分析程序所提供的单词序列进行语法检 查和结构分析。 实验内容:在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。 已知待分析的C语言子集的语法,用EBNF表示如下: <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式>

<条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图(方框原理图或程序流程图)

编译原理词法分析及语法分析

编译原理 实验报告 实验名称:词法分析及语法分析专业班级: 姓名: 学号: 完成日期:

实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范,要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义,选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法,输出单词(关键字、专用符号以及其它标记)。 1、格式 输入:源程序文件。输出:关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符,对与不同的单词符号给出不同编码形式的编码,用以区分之。 3、实验方法 读懂Sample源代码,自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1. <字符集> → <字母>│<数字>│<单界符> 2. <字母> → A│B│…│Z│a│b│…│z 3. <数字> → 0│1│2│…│9 4. <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5.<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6.<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7.<双界符> → <>│<=│>=│:= │/*│*/│.. 8.<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9.<常数> → <整数>│<布尔常数>│<字符常数> 10.<整数> → <数字>│<整数> <数字> 11.<布尔常数> → true│false 12.<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计

相关主题