武汉理工大学《编译原理》课程设计说明书
赋值语句的递归下降翻译程序设计
1引言
递归下降法是语法分析中最易懂的一种方法。它的主要原理是,对每个非终极符按其产生式结构构造相应语法分析子程序,其中终极符产生匹配命令,而非终极符则产生过程调用命令。因为文法递归相应子程序也递归,所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。
本文将采用这种方法对赋值语句进行翻译,并得到逆波兰式的中间代码结果。另外我还完成了对逆波兰式的中间代码翻译执行的程序。
11逆波兰式简介
在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种
表示法也称为中缀表示。对中缀表达式的计值,并非按运算符出现的自然顺序来执行其中
的各个运算,而是根据算符间的优先关系来确定运算的次序,此外,还应顾及括号规则。
因此,要从中缀表达式直接产生目标代码一般比较麻烦。
波兰逻辑学家JLukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,
每一运算符都置于其运算对象之后,故称为后缀表示。这种表示法的一个特点是,表达式
中各个运算是按运算符出现的顺序进行的,故无须使用括号来指示运算顺序,因而又称为
无括号式。下面我们对照地给出一些表达式的两种表示:
中缀表示后缀表示
ABAB
(1)
ABCABC
(2)
ABCDABCD
(3)
xyzdexyzde
(4)
a0∧b3∨e∧xya0b3∧exy∧∨
(5)
从上面的例子可以看出:
1在两种表示中,运算对象出现的顺序相同;
1
f武汉理工大学《编译原理》课程设计说明书
2在后缀表示中,运算符按实际计算顺序从左到右排列,且每一运算符总是跟在其运算对象之后。
顺便提及,Lukasiewicz原来提出的是前缀表示,即把每一运算符置于其运算对象之前。例如,中缀式ab和abc相应的前缀表示分别为ab和abc。因此,为了区分前缀和后缀表示,通常将后缀表示称为逆波兰表示。因前缀表示并不常用,所以有时也将后缀表示就称为波兰表示。
2需求分析
本课程设计的目的是为了实现赋值语句的递归下降翻译程序设计,并给出对应的逆波兰式中间代码。
〈赋值语句〉〈标识符〉:〈算术表达式〉算术表达式的文法:〈算术表达式〉∷=〈项〉〈加法运算符〉〈项〉〈项〉∷=〈因子〉〈乘法运算符〉〈因子〉〈因子〉∷=〈标识符〉|〈无符号整数〉|‘(’〈表达式〉‘)’〈加法运算符〉∷=+|-〈乘法运算符〉∷=*|/设计赋值语句文法r