重点:语法制导翻译的基本思想,属性文法,翻译模式,说明语句的翻译方案。
三地址码,各种语句的目标**结构、属性文法与翻译模式。
难点:属性的意义,对综合属性,继承属性,固有属性的理解,属性计算,怎么通过属性来表达翻译。布尔表达式的翻译,对各种语句的目标**结构、属性文法与翻译模式的理解。
掌握语法制导翻译的基本思想,属性文法,综合属性,继承属性,固有属性,属性计算,s_属性文法,l_属性文法,说明语句的翻译方案,翻译模式、属性文法的实现。
掌握中间语言与语义分析的基本概念;熟练掌握语法(结构)树、三地址**、赋值与控制语句的翻译、说明语句的翻译;掌握组合数据说明的翻译、过程调用翻译。
例1 给定文法 e --t
r r --addopt r
r --t --e )
t --id
t --num
1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性。
画出按本翻译模式处理表达式 a + 20 + b - 10 ) 时所生成的语法树。
解】1)e的综合属性 p,r的继承属性i,综合属性s;t的综合属性p
2) 处理表达式 a + 20 + b - 10 ) 时所生成的语法树如下。
id, anum, 20
id, b) (num, 10)
例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示,解】计算器的文法。
l → ee → e1 + t | t
t → t1 * f | f
f → e ) digit
引进属性val,计算器的属性文法:
l → eprint( )l的虚属性)
e → e1 + t :=
e → t → t1 * f :=
t → f →
f → digit :=
lexval 是单词 digit 的属性。
例3给出对输入串6-3 3*5+4 的分析树与属性计算。
解】3*5+4 的分析树与属性计算。
例4定义一个说明语句的属性文法。
解】说明语句的文法。
d → t l
t → int
t → real
l → l1,id
l → id
要解决的问题:记录标识符的类型和类型信息传递。
方法:引进属性type,和in,用记录类型信息,并传给。
说明语句的属性文法如下:
d → t l :=
t → int :=integer’
t → real :=real’
l → l1,id :=
addtype( )
l → id addtype( )
entry 单词 id 的属性。
addtype 在符号表中为变量填加类型信息。
例5 给出输入串real id1,id2,id3 的分析树和属性计算。
例6 设下列文法生成变量的类型说明。
d → id l
l → id l | t
t → integer | real
试构造一个翻译模式,把每个标识符的类型存入符号表。
解】解题思路。
这是一个对说明语句进行语义分析的题目,不需要产生**,但要求把每个标识符的类型填入符号表中。
解答。对d,l,t设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type填入到符号表中。
翻译模式如下:
d → id l {addtype(
l → id l1 {addtype(
l → t {
t → integer {
t → real {
例7文法g的产生式如下:
s → l) |a
l → l , s | s
(1)试写出一个语法制导定义,它输出配对括号个数;
(2)写一个翻译方案,打印每个a的嵌套深度。如((a),a),打印2,1。
解】解题思路。
本题包括两部分,第1部分要求写语法制导定义,第2部分要求写翻译方案。语法制导定义(或属性文法)可以看作是关于语言翻译的高级规范说明,其中隐去实现细节,使用户从明确说明翻译顺序的工作中解脱出来。翻译方案(也称翻译模式)给出了使用语义规则进行计算的次序,把某些实现细节表示出来。
读者从下面解答中可体会两者的区别。
解答。为s、l引入属性h,代表配对括号个数。语法制导定义如下:
2)为s、l引入d,代表a的嵌套深度。翻译方案如下:
s’→{s →‘
ls →a{print(
l → l1
sl →
s例8下列文法对整型常数和实型常数施用加法运算符“+”生成表达式;当两个整型数相加时,结果仍为整型数,否则,结果为实型数:
e → e+t | t
t → num
(1)试给出确定每个子表达式结果类型的属性文法。
(2)扩充(1)的属性文法,使之把表达式翻译成后缀形式,同时也能确定结果的类型。应该注意使用一元运算符inttoreal把整型数转换成实型数,以便使后缀形如加法运算符的两个操作数具有相同的类型。
解】解题思路。
确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法,使之把表达式翻译成后缀形式。我们将不在name或向t归约的时候输出该运算对象,而是把运算对象的输出放在t或e+t向e归约的时候。
这是因为考虑输出类型转换算符inttoreal的动作可能在e+t归约的时候进行,如果这时两个运算对象都在前面name或向t归约的时候已输出,需要为第1个运算对象输出类型转换算符时就已经为时太晚。
还要注意的是,在e+t向e归约时,该加法运算的第1个运算对象已经输出。所以e→e+t的语义规则不需要有输出e运算对象的动作。
解答。1)为文法符号e和t配以综合属性type,用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下:
2)下面属性文法将表达式的后缀表示打印输出,其中lexeme属性表示单词的拼写。
例9 将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示:
a:=(b+c)*e+(b+c)/f
解】解题思路。
把中缀式转换为后缀式的简单方法:按中缀式中各运算符的优先规则,从最先执行的部分开始写,一层层套。如a≤b+c∧a>d∨a+b≠e,先把b+c写为bc+;然后把a≤套上去,成为abc+≤;再把a>d表示为ad>;然后把∧套上去,成为abc+≤ad>∧,依此类推。
四元式由4个部分组成:算符op、第1和第2运算量arg1和arg2,以及运算结果result。运算量和运算结果有时指用户自定义的变量,有时指编译程序引进的临时变量。
如果op是一个算术或逻辑算符,则result总是一个新引进的临时变量,用于存放运算结果。
三元式只需3个域:op、arg1和arg2。与四元式相比,三元式避免了临时变量的填入,而是通过计算这个临时变量的语句的位置来引用这个临时变量。
我们很容易把一个算术表达式或一个赋值句表示为四元式序列或三元式序列。
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想,分析器总体结构,分析表的构造,递归下降分析法基本思想,简单算术表达式的递归下降分析器。难点 first和follow集的求法,对它们的理解以及在构造ll 1 分析表时的使用。递归子程序法中如何体现分析的结果。基本要求。掌握语法分析 ...
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式,并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合,并判断该文法是否是ll 1 的,请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...
编译原理试题
东南大学。一 文法g1 e et t t tf f f fp p p e i1 试证明符号串tet i 是g1的一个句型 要求画出语法树 2 写出该句型的所有短语,简单短句和句柄。三 1 试写出一个上下文无关文法g3,它能产生配对的圆括号串 例如等,甚至包含0对括号 2 使用文法g3给出输入串 的自...