基于算符优先分析方法01.docx
- 文档编号:13250421
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:26
- 大小:181.13KB
基于算符优先分析方法01.docx
《基于算符优先分析方法01.docx》由会员分享,可在线阅读,更多相关《基于算符优先分析方法01.docx(26页珍藏版)》请在冰点文库上搜索。
基于算符优先分析方法01
基于算符优先分析方法
的表达式语法分析器
年级:
2007级
班级:
计算机科学与技术四班
姓名:
欧垚
学号:
20074042154
指导老师:
段明秀
年月日
摘要……………………………………………………………2
关键字…………………………………………………………2
构造算符优先表………………………………………………3
构造优先分析器………………………………………………6
分析归约流程图………………………………………………7
运行……………………………………………………………8
测试……………………………………………………………9
参考文献……………………………………………………12
附加代码……………………………………………………13
摘要:
算符优先分析法是Floyd在1963年首先提出来的,是一种古典而又实用的方法,用这种方法在分析程序语言中的各类表达式时尤为有效。
不少编译程序中都使用这种方法分析表达式。
算符优先分析法就是仿照算术表达式的运算过程而提出的一种自底向上的语法分析方法。
其基本思想是:
首先规定算符,这里是文法的终极符之间的优先关系,然后根据这种优先关系,通过比较相邻算符的优先次序来确定句型中的“句柄”,然后进行归约。
算符优先分析法的关键:
算符优先分析法的关键就是寻找当前句型中的最左素短语,并归约它。
关键字:
小于、大于、等于、句柄、归约、
一、对表达式文法G[E’
]构造算符优先关系表。
计算算符优先只针对于终结符,终结符之间的优先关系有三种,在计算优先关系之前我们先定义两个集合,对于任意两个终结符(a,b)FIRSTVT(B)={b|B=>b…或B=>Cb…},其中…表示V*中的符号串。
LASTVT(B)={a|B=>…a或B=>…aC}
三种优先关系:
(1)等于关系:
可直接查看产生式的右部,对如下形式的产生式A->…ab…A->…aBb…则有a=b成立。
(2)小于关系:
求出每个非终结符B的FIRSTVT(B),观察如下形式的产生式A->…aB…对每一
b∈FIRSTVT(B)有a≮b成立
(3)大于关系:
计算每个非终结符B的LASTVT(B),观察如下形式的产生式A->…Bb…对每一
a∈LASTVT(B)有a≯b成立
表达式文法G[E’
]:
E’→#E#
E→E+Q|Q
Q→Q-T|T
T→T*F|F
F→F/M|M
M→M^P|P
P→(E)|i
根据上面的规则手工构造上述文法的算符优先表如下:
+
-
*
/
^
(
)
i
#
+
≯
≮
≮
≮
≮
≮
≯
≮
≯
-
≯
≯
≮
≮
≮
≮
≯
≮
≯
*
≯
≯
≯
≮
≮
≮
≯
≮
≯
/
≯
≯
≯
≯
≮
≮
≯
≮
≯
^
≯
≯
≯
≯
≯
≮
≯
≮
≯
(
≮
≮
≮
≮
≮
≮
=
≮
)
≯
≯
≯
≯
≯
≯
≯
i
≯
≯
≯
≯
≯
≯
≯
#
≮
≮
≮
≮
≮
=
packagecom.op.core;
/*******************************************************************************
*简单表达式文法G[E’]构造算符优先关系表。
*E’→#E#
*E→E+Q|Q
*Q→Q-T|T
*T→T*F|F
*F→F/M|M
*M→M^P|P
*P→(E)|i
*@author
*/
publicclassPriorityTable{
privatestaticchartable[][]={
//+*/i()#^
{'>','<','<','<','<','>','>','<'},//+
{'>','>','>','<','<','>','>','<'},//*
{'>','>','>','<','<','>','>','<'},///
{'>','>','>','$','$','>','>','>'},//i
{'<','<','<','<','<','=','$','<'},//(
{'>','>','>','$','$','>','>','>'},//)
{'<','<','<','<','<','$','=','<'},//#
{'>','>','>','<','<','>','>','<'},//^
};//算符优先表
/***************************************************************************
*判断一个符号在算符优先表中位置
*
*@paramc
*@return
*/
privatestaticintjudgePriority(charc){
intpriority=0;
switch(c){
case'+':
priority=0;
break;
case'*':
priority=1;
break;
case'/':
priority=2;
break;
case'i':
priority=3;
break;
case'(':
priority=4;
break;
case')':
priority=5;
break;
case'#':
priority=6;
break;
case'^':
priority=7;
break;
}
returnpriority;
}
/**
*判断两个算术符的优先级
*
*@paramm
*为符号栈的栈顶元素
*@paramn
*为当前输入算术符
*@return
*/
publicstaticchargetPriority(charm,charn){
returnPriorityTable.table[judgePriority(m)][judgePriority(n)];
}
}
二、根据算符优先表用栈结构来实现算符优先分析
设置两个栈:
存放运算符的OPTR栈和存放操作数或运算结果的OPND栈。
具体算法描述如下:
(1)首先置操作数OPND栈为空栈,将#入运算符OPTR栈。
(2)依次读入表达式中每个单词,若是操作数则进OPND栈,若是运算符则转(3)。
(3)当前设读入的运算符为θ2,查找算符优先关系表,比较θ2与OPTR栈顶元素θ1:
若θ1<θ2,则θ2进OPTR栈,转
(2);
若θ1=θ2,如θ2为#,则分析成功,否则OPTR栈顶元素θ1出栈,并转
(2);
若θ1>θ2,则出栈OPND栈顶元素存放到b,又出栈其新栈顶元素存放到a,再出栈OPTR栈顶元素至t,进行运算r=atb(t为运算符),并将结果r存入栈OPND后转
(2);
(4)若θ1和θ2之间无优先关系,则报错。
publicclassOperatorPriority{
privateStack
privateStack
privateStringinput;//键盘输入字符串
/***
*构造函数
*@paraminput
*/
publicOperatorPriority(Stringinput){
super();
optrStack=newStack
opndStack=newStack
optrStack.push('#');
this.input=input;
}
/***
*操作两个数
*@parama操作数1
*@paramb操作数2
*@paramop操作符
*@return运算结果
*/
publicfloatoperateTwoNum(floata,floatb,charop){
BigDecimalda=newBigDecimal(Float.toString(a));
BigDecimaldb=newBigDecimal(Float.toString(b));
switch(op){
case'*':
returnda.multiply(db).floatValue();
case'+':
returnda.add(db).floatValue();
case'-':
returndb.subtract(da).floatValue();
case'/':
returndb.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue();//除不尽的情况取7位精确值。
case'^':
returndb.pow((int)a).floatValue();
}
return0;
}
/***
*判断是否为操作符
*@paramch被判断字符
*@return布尔值
*/
publicbooleanisOperator(charch){
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('
||ch==')'||ch=='#'||ch=='^')
returntrue;
else
returnfalse;
}
/***
*扫描字符串,判断是否对应文法,并计算出结果
*@return计算结果
*@throwsException如果不符合文法,或者除数等于0,都将抛出异常
*/
publicStringscanner()throwsException{
intpostion=0;//字符串上指示的指针
charoperator=0;//操作符
floata=0,b=0;//操作数
String[]exp=StringUtil.splitExp(input);
while(true){
//判断是否为运算符
if(exp[postion].length()==1&&isOperator(exp[postion].charAt(0))){
//需要进行运算符的比较
if(!
optrStack.isEmpty()){
if(PriorityTable.getPriority(optrStack.peek().charValue(),
exp[postion].charAt(0))=='<')
optrStack.push(exp[postion].charAt(0));
elseif(PriorityTable.getPriority(optrStack.peek()
.charValue(),exp[postion].charAt(0))=='>'){
a=opndStack.pop();
b=opndStack.pop();
operator=optrStack.pop().charValue();
opndStack.push(operateTwoNum(a,b,operator));
continue;
}elseif(PriorityTable.getPriority(optrStack.peek()
.charValue(),exp[postion].charAt(0))=='='){
optrStack.pop();
if(exp[postion].charAt(0)=='#'){
returnopndStack.pop().toString();
}
}
}else
optrStack.push(exp[postion].charAt(0));
}
//为运算数时
else{
opndStack.push(Float.valueOf((exp[postion])).floatValue());
}
postion++;
if(postion>=exp.length)
break;
}
thrownewException();
}
三、分析归约流程图:
四、运行
从键盘输入表达式串,利用算符优先法求出其值,如输入表达式有错,则给出报错提示。
表达式以“#”结尾。
从键盘输入句子:
packagecom.op.util;
importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;
publicclassIOUtil{
/***
*得到从键盘输入的字符串
*@return字符串
*/
publicstaticStringgetStringFromKeyBoard()
{
try
{
BufferedReaderreader=newBufferedReader(newInputStreamReader(System.in));
System.out.print("请输入一个表达式以#号结束:
");
Stringstr=reader.readLine();//获取字符串
//System.out.println("您输入的字符串是:
"+str);
returnstr;
}catch(IOExceptione)
{
e.printStackTrace();
}
returnnull;
}
}
五、测试
1、句子前有空格符
2、综合所有文法的句子
3不以#号结束的句子
4、加减按从左至右
5、先乘后减
6、有括号的先算括号里面的
7、乘方的优先级大于除法的
8、先乘方后乘除
9、乘除按从左至右法则
10、输入串含有不是指定文法的句子
测试人姓名
欧垚
测试时间
2010-06-27
错误个数
3
序号
路径
输入
输出
实际结果
1
在句子前面输入一个空格符号
(6-3+5^2*2/10)/2#
4.0
您输入的表达式(6-3+5^2*2/10)/2#有误
2
一个包含所有文法的句子
(6-3+5^2*2/10)/2#
4.0
4.0
3
不以#号结束的句子
3+4+5
12.0
您输入的表达式3+4+5有误
4
先减后加
6-3+2#
5.0
5.0
5
先加后减
3+4-2#
5.0
5.0
6
先乘后减
6-3*2#
0.0
0.0
7
有括号先算括号里面的
(6-3)*2#
6.0
6.0
8
乘方的优先级最大
25/5^2#
1.0
1.0
9
先乘方再从左至右
3*2/6^2#
0.1666667
0.1666667
10
先除后乘
25/5*2#
10.0
10.0
11
先乘后除
3*2/2#
3.0
3.0
12
输入串含有不是指定文法的句子
{3+2-[2*2-(3-2)]}#
2.0
您输入的表达式{3+2-[2*2-(3-2)]}#有误
六、参考文献:
1、黄贤英,刘贞,刘全利;“编译原理”课程的地位及教改思路[J];重庆科技学院学报(社会科学版);2005年03期
2、张素琴,吕映芝,蒋维杜,戴桂兰;《编译原理》(第二版);清华大学出版社;2009年5月第12次印刷
3、王雷,刘志成,周晶;编译原理课程设计;2005
4、期刊论文浅谈"编译原理"课程教学-广东工业大学学报(社会科学版)2005,5
附加代码:
packagecom.op.core;
importjava.math.BigDecimal;
importjava.util.Stack;
importcom.op.util.StringUtil;
importcom.op.util.IOUtil;
publicclassOperatorPriority{
privateStack
privateStack
privateStringinput;//键盘输入字符串
/***
*构造函数
*@paraminput
*/
publicOperatorPriority(Stringinput){
super();
optrStack=newStack
opndStack=newStack
optrStack.push('#');
this.input=input;
}
/***
*操作两个数
*@parama操作数1
*@paramb操作数2
*@paramop操作符
*@return运算结果
*/
publicfloatoperateTwoNum(floata,floatb,charop){
BigDecimalda=newBigDecimal(Float.toString(a));
BigDecimaldb=newBigDecimal(Float.toString(b));
switch(op){
case'*':
returnda.multiply(db).floatValue();
case'+':
returnda.add(db).floatValue();
case'-':
returndb.subtract(da).floatValue();
case'/':
returndb.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue();//除不尽的情况取7位精确值。
case'^':
returndb.pow((int)a).floatValue();
}
return0;
}
/***
*判断是否为操作符
*@paramch被判断字符
*@return布尔值
*/
publicbooleanisOperator(charch){
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('
||ch==')'||ch=='#'||ch=='^')
returntrue;
else
returnfalse;
}
/***
*扫描字符串,判断是否对应文法,并计算出结果
*@return计算结果
*@throwsException如果不符合文法,或者除数等于0,都将抛出异常
*/
publicStringscanner()throwsException{
intpostion=0;//字符串上指示的指针
charoperator=0;//操作符
floata=0,b=0;//操作数
String[]exp=StringUtil.splitExp(input);
while(true){
//判断是否为运算符
if(exp[postion].length()==1&&isOperator(exp[postion].charAt(0))){
//需要进行运算符的比较
if(!
optrStack.isEmpty()){
if(PriorityTable.getPriority(optrStack.peek().charValue(),
exp[postion].charAt(0))=='<')
optrStack.push(exp[postion].charAt(0));
elseif(PriorityTable.getPriority(optrStack.peek()
.charValue(),exp[postion].charAt(0))=='>'){
a=opndStack.pop();
b=opndStack.pop();
operator=optrStack.pop().charValue();
opndStack.push(operateTwoNum(a,b,operator));
continue;
}elseif(PriorityTable.getPriority(optrStack.peek()
.charValue(),exp[postion].charAt(0))=='='){
optrSta
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 优先 分析 方法 01