算符优先文法实验
一、设计目的
了解用算符优先法对表达进行语法分析的方法,掌握自顶向下的预测语法分析程序的手工
构造方法。
二、设计内容
对简单表达式文法构造算符优先分析器。
三、设计要求
1、对下列简单表达式文法 G[ E’]构造算符优先关系表。
E’ →# E #
E → E + T | T
T → T * F | F
F → P / F |P
P → ( E )|i
2、根据算符优先关系表,使用栈结构来实现算符优先分析:设置两个栈:存放运算符的
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=a t b (t 为运算符),并将结果 r 存入栈 OPND 后转(2);
(4)若 θ1 和 θ2 之间无优先关系,则报错。
从键盘输入表达式,利用算符优先法求出其值,如输入表达式有错,则给出报错提示。表
达式以“#”结尾。
四、运行结果
1、从键盘输入表达式串: 10+15*4#
输出: 70
2、从键盘输入表达式串:10+*15+
输出: The expression is error!
五、提示
构造算符优先关系表如下:
+ - * / ( ) i #
+ ﹥ ﹥ ﹤ ﹤ ﹤ ﹥ ﹤ ﹥
- ﹥ ﹥ ﹤ ﹤ ﹤ ﹥ ﹤ ﹥
* ﹥ ﹥ ﹥ ﹥ ﹤ ﹥ ﹤ ﹥
/ ﹥ ﹥ ﹥ ﹥ ﹤ ﹥ ﹤ ﹥
( = ﹤ ﹤ ﹤ ﹤ ﹤ ﹤
) ﹥ ﹥ ﹥ ﹥ ﹥ ﹥
i ﹥ ﹥ ﹥ ﹥ ﹥ ﹥
# ﹤ ﹤ ﹤ ﹤ ﹤ =﹤