写在前面：本博客为本人原创，严禁任何形式的转载！本博客只允许放在博客园（.cnblogs.com），如果您在其他网站看到这篇博文，请通过下面这个唯一的合法链接转到原文！
本博客全网唯一合法URL：http://www.cnblogs.com/acm-icpcer/p/9107838.html
基于C++语言实现的PL/0语言的算术表达式的自下而上的语法分析程序。该语言的其他语法实现思想与此一致，故不赘述。
运行此程序前，必须先将代码通过：【编译原理】c++实现词法分析器的词法分析，生成词法表（词法表是txt文件，为了语法分析成功，务必删除文件中最后空着的一行，即文件末尾不可以留空白行）。生成的该词法表为此程序的必要输入。
产生式：
S->X(AX)*|AX(AX)*
X->Y(MY)*
Y->I|N|(S)
A->+|-
M->*|/
C->=|#|<|<=|>|>=
进行自下而上的语法分析一定比自上而下要难。我们知道，做自下而上的语法的分析的核心在于“寻找可归约串”（即术语所说的“句柄”），而且要有一定的“向前展望性”，以防止在可以归约但却不应该归约的地方进行归约动作而不是继续移进下一个终结符或者非终结符。所以编译原理的语法分析做LR分析的核心目标就是能精确地控制计算机程序对待分析、编译的程序代码语句进行正确的、无二义的、符合编程者原目的的语法分析（在自下而上的语法分析中就是“归约”）。
那么知道了为什么要构造规范项目集族、构造确定的DFA、构造LR分析表后，对于上述产生式所代表的比较简单的算术表达式语句分析，我在本篇博客中就不使用传统的“构造规范项目集族、构造确定的DFA、构造LR分析表”这样一个套路来做自下而上语法分析了。
在本篇博客中，我使用比较简单易理解的模式匹配算法，结合面向对象程序设计思想中的“策略”设计模式来完成编程。
/*
this code was first initiated by TZ,COI,HZAU
contact email:xmb028@163.com
personal website:wnm1503303791.github.io
personal blogs:www.cnblogs.com/acm-icpcer/
this code has been posted on my personal blog,checking url:www.cnblogs.com/acm-icpcer/p/9107838.html
Copyright 2018/5/29 TZ.
All Rights Reserved.
*/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<fstream>
using namespace std; //预处理函数
bool preproccess(char *a,char *b)
{
int i1=,i2=;
memset(b,,'\0');
while(a[i2]!=',')
{
b[i1]=a[i2];
++i1,++i2;
}
b[i1]='\0';
//cout<<b<<endl;
return true;
} fstream f2("stack.txt", ios::out);//打开文件，供写
static int mcount=;//存储打印次数
//当移进或者归约时打印栈内情况，以供分析
bool outf(int head,char data[][],fstream &f)
{
f<<"times("<<mcount<<"),";
f<<"head is:"<<head<<endl;
for(int i=head;i>=;i--)
{
f<<data[i]<<endl;
}
mcount++;
f<<endl;
} //“策略”设计模式，面向对象方法
class presentation
{
private:
char data[][];//栈
fstream *infile;//词法分析表
int head;//栈顶指针
public:
//first initiated the object
presentation(fstream *in_f)
{
this->infile=in_f;
memset(data,sizeof(data),'\0');
head=-;
}
bool push()
{
head++; infile->getline(data[head],);
char t[];//存放字符标志
preproccess(data[head],t);
cout<<data[head]<<","<<t<<endl; memset(data[head],,'\0');
strcpy(data[head],t);
} /*
S->X(AX)*|AX(AX)*
X->Y(MY)*
Y->I|N|(S)
A->+|-
M->*|/
C->=|#|<|<=|>|>=
*/
//归约函数
bool reduce()
{
//S->X(AX)*|AX(AX)*
if( head>=&&
(!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
return true;
} if( head>=&&
(!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
return true;
} if( head>=&&
(!strcmp(data[head],"plus")||!strcmp(data[head],"minus"))&&
(!strcmp(data[head-],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
return true;
} if( head>=&&
(!strcmp(data[head],"plus")||!strcmp(data[head],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
return true;
} //X->Y(MY)*
if( head>=&&
(!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
return true;
} if( head>=&&
(!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
return true;
} if( head>=&&(!strcmp(data[head],"Y"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"X");
return true;
} //Y->I|N|(S)
if( head>=&&(!strcmp(data[head],"ident"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
return true;
} if( head>=&&(!strcmp(data[head],"number"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
return true;
} if( head>=&&
(!strcmp(data[head],"rparen"))&&
(!strcmp(data[head-],"S"))&&
(!strcmp(data[head-],"lparen"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"Y");
return true;
} return false;
}
//遍历栈
bool visit_data()
{
cout<<"current stack:"<<endl;
for(int i=head;i>=;i--) {
cout<<data[i]<<endl;
}
}
//主控函数
bool mainf()
{
while(!infile->eof())
{
push();
bool t=reduce();
outf(head,data,f2);
//每当移进结束时就检查一下是否有可规约串
while(t)//防止规约嵌套
{
t=reduce();
outf(head,data,f2);
}
//visit_data();
} visit_data(); bool flag=false;
for(int i=head;i>=;i--)
{
if(!strcmp(data[i],"S"))
{
flag=true;
}
if( strcmp(data[i],"S")&&
strcmp(data[i],"X")&&
strcmp(data[i],"A")&&
strcmp(data[i],"Y")&&
strcmp(data[i],"M")&&
strcmp(data[i],"C")
)
{
return false;
}
} return flag; /*
while(head>0)
{
bool t=reduce();
//每当移进结束时就检查一下是否有可规约串
while(t)//防止规约嵌套
{
t=reduce();
}
//visit_data();
outf(head,data,f2);
}
*/
}
}; int main()
{
fstream f1;
f1.open("lexical.txt", ios::in);//打开词法分析表，供读 presentation* s1=new presentation(&f1);
bool result=s1->mainf(); if(result)
cout<<"ACCEPTED!"<<endl;
else
cout<<"ERROR!"<<endl; f1.close();
f2.close();
return ;
}
当然了，对于不喜欢看面向对象设计模式的同学，我还写了另外一个面向过程的代码，这个更易理解。而且我在程序中已经将一张特定的词法分析表给出。
/*
this code was first initiated by TZ,COI,HZAU
contact email:xmb028@163.com
personal website:wnm1503303791.github.io
personal blogs:www.cnblogs.com/acm-icpcer/
this code has been posted on my personal blog,checking url:www.cnblogs.com/acm-icpcer/p/9107838.html
Copyright 2018/5/29 TZ.
All Rights Reserved.
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<fstream>
using namespace std; char mdata[][]={ "ident",
"times",
"rparen",
"number",
"plus",
"ident",
"lparen" /*
"lparen",
"ident",
"plus",
"number",
"rparen",
"times",
"ident"
*/
}; char data[][]; int head=; bool reduce()
{
//S->X(AX)*|AX(AX)*
if( (!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
head++;
return true;
} if( (!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
head++;
return true;
} if( (!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
head++;
return true;
} if( (!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
head++;
return true;
} //X->Y(MY)*
if( (!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
head++;
return true;
} if( (!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
head++;
return true;
} //Y->I|N|(S)
if( (!strcmp(data[head],"ident"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
head++;
return true;
} if( (!strcmp(data[head],"number"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
head++;
return true;
} if( (!strcmp(data[head],"rparen"))&&
(!strcmp(data[head-],"S"))&&
(!strcmp(data[head-],"lparen"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"Y");
head++;
return true;
} return false;
} bool visit_data()
{
cout<<"current stack:"<<endl;
for(int i=head;i>=;i--) {
cout<<data[i]<<endl;
}
} int main()
{ int i=;
while(i<=)
{
strcpy(data[head],mdata[i]);
head++;
bool t=reduce();
//每当移进结束时就检查一下是否有可规约串
while(t)//防止规约嵌套
{
t=reduce();
}
visit_data();
i++;
}
visit_data(); /*
int i=0;
while(i<=6)
{
strcpy(data[head],mdata[i]);
head++;
i++;
}
visit_data();
*/
}
运行示例：
(1)合法的语句：
(2)不合法的语句：
tz@dormitory HZAU
2018/5/30
last updated@COI HZAU
2018/6/12
【编译原理】c++实现自下而上语法分析器的更多相关文章
-
【编译原理】LL1文法语法分析器
上篇文章[编译原理]语法分析--自上向下分析 分析了LL1语法,文章最后说给出栗子,现在补上去. 说明: 这个语法分析器是利用LL1分析方法实现的. 预测分析表和终结符以及非终结符都是针对一个特定文法 ...
-
【编译原理】c++实现自下而上语法分析及中间代码(四元式)生成
写在前面:本博客为本人原创,严禁任何形式的转载!本博客只允许放在博客园(.cnblogs.com),如果您在其他网站看到这篇博文,请通过下面这个唯一的合法链接转到原文! 本博客全网唯一合法URL:ht ...
-
编译原理_P1004
龙书相关知识点总结 //*************************引论***********************************// 1. 编译器(compiler):从一中语言( ...
-
编译原理简单语法分析器（first,follow,分析表）源码下载
编译原理(简单语法分析器下载) http://files.cnblogs.com/files/hujunzheng/%E5%8A%A0%E5%85%A5%E5%90%8C%E6%AD%A5%E7%AC ...
-
<;编译原理 - 函数绘图语言解释器（2）语法分析器 - python>;
<编译原理 - 函数绘图语言解释器(2)语法分析器 - python> 背景 编译原理上机实现一个对函数绘图语言的解释器 - 用除C外的不同种语言实现 设计思路: 设计函数绘图语言的文法, ...
-
【编译原理】c++实现自上而下语法分析器
写在前面:本博客为本人原创,严禁任何形式的转载!本博客只允许放在博客园(.cnblogs.com),如果您在其他网站看到这篇博文,请通过下面这个唯一的合法链接转到原文! 本博客全网唯一合法URL:ht ...
-
Compiler Theory(编译原理)、词法/语法/AST/中间代码优化在Webshell检测上的应用
catalog . 引论 . 构建一个编译器的相关科学 . 程序设计语言基础 . 一个简单的语法制导翻译器 . 简单表达式的翻译器(源代码示例) . 词法分析 . 生成中间代码 . 词法分析器的实现 ...
-
必要的软件架构师——编译原理&;#183;语法
最近软测试.我观看进程的视频! 发现里面有很多内容已经在自我不错的接触过程.而占80%比例! 但其中的一部分.我很奇怪的一部分.研究,在这里,将我研究的内容整理分享给大家! 编译原理: 首先,我第一眼 ...
-
python实现算术表达式的词法语法语义分析（编译原理应用）
本学期编译原理的一个大作业,我的选题是算术表达式的词法语法语义分析,当时由于学得比较渣,只用了递归下降的方法进行了分析. 首先,用户输入算术表达式,其中算术表达式可以包含基本运算符,括号,数字,以及用 ...
随机推荐
-
19.dnw打不开
用dnw.exe烧写文件时,突然出现电脑死机,重启后,dnw就打不开了,dnw.ini的原因,该文件在c盘目录下,只需要删除它,就可以继续使用dnw了.
-
STM32F0xx_GPIO配置详细过程
前言 对于初学STM32的人来说,很多基础的知识没有掌握,这些基础知识就成为阻挡他们入门的门槛.因此,今天也把基础的知识分享出来,带领那些还没有迈过这个门槛的人入门. 今天总结“GPIO配置详细”,以 ...
-
cacti气象图调整（批量位置调整、更改生成图大小等）
cacti气象图能够非常直观的看到各个节点的流量.这里用的是CactiEZ中文版 V10 1.调整气象图大小 默认有一个1024像素的背景图可选, 这里我们须要新增一个1600像素的背景图. 背景图自 ...
-
java反射 顺序输出类中的方法
java反射可以获取一个类中的所有方法,但是这些方法的输出顺序,并非代码的编写顺序. 我们可以通过自定义一个注解来实现顺序输出类中的方法. 首先,先写一个类,定义增删改查4个方法 public cla ...
-
eval函数的坑
开发工作中遇到这样一种情形,需要执行用户输入的php代码串,于是决定使用eval函数.coding大概示例如下: function getStr($str) { return strlen($str) ...
-
在为知笔记中使用Markdown和思维导图
为知笔记Wiz是一款很好的网摘和笔记工具,作为为知的忠实用户,我在为知收费后第一时间就购买了两年的授权,毕竟这么多年积累的资料都在为知上,我也习惯了使用Wiz来做些工作相关的笔记.为知笔记自带Mark ...
-
【Linux】CentOS7下安装JDK详细过程
https://www.cnblogs.com/sxdcgaq8080/p/7492426.html
-
Python3 模块 -- Fabric自动化模版
安装 pip3 install fabric3 创建软连接 find / -type f -name "fab" /usr/local/python3/bin/fab ln -s ...
-
脚手架vue-cli系列一：安装与规范
我很喜欢Vue的一个重要原因就是因为它的vue-cli,这个工具可以让一个简单的命令行工具来帮助我快速地构建一个足以支撑实际项目开发的Vue环境,并不像Angular和React那样要在Yoman上找 ...
-
Linux实践二：模块
一.基本模块的实现: 1.进程遍历打印输出 2.简单地编写一个新的系统调用(替换空的系统调用号) 基本模块学到的知识点: 1.相关指令 make oldconfig 配置内核 make 编译内核 ma ...