编译原理学习手记(1)– 代码生成(updating)

2012 年 12 月 26 日

代码生成原理在何炎祥教授的编译原理书（《编译原理》第三版，华中科技大学出版社）上是第12章，可以认为是理论说明的最后一章，后面两章分别是讲LEX和YACC这两个经典工具的使用，我们反过来阅读，是为了从目标出发，每一步都接近结果。

假想的计算机模型：

只有一个累加器（也就是寄存器一类的吧。。）m是存储单元或者变量。
每一个指令隐含第一操作数是累加器ACC，
LD m              loads to acc from m
ST m              saves acc to m
ADD m             adds acc by m
SUB m             substracts acc by m
MULT m            multiplies acc by m
DIV m             divides acc by m
ABS               acc = abs(acc), abs is absolute value 
CHS               chs = neg(acc), change the sign of acc

只有一个累加器（也就是寄存器一类的吧。。）m是存储单元或者变量。

每一个指令隐含第一操作数是累加器ACC，

LD m loads to acc from m

ST m saves acc to m

ADD m adds acc by m

SUB m substracts acc by m

MULT m multiplies acc by m

DIV m divides acc by m

ABS acc = abs(acc), abs is absolute value

CHS chs = neg(acc), change the sign of acc

给一个表达式：

  A*((A*B+C)-C*D))
也就是  A A B * C + C D * - *

1 2	A((AB+C)-CD)) 也就是 A A B C + C D * - *

基于上述假想指令集，我们应该输出怎样的代码呢？

出于简化，我们直接用12.5中提到的逆波兰式来生成，注意，我们直接把元数放在运算符后面，这样出现单双目同时出现的情况也能够很容易处理。

也就是:

A A B */2 C +/2 C D */2 -/2 */2

1	A A B /2 C +/2 C D /2 -/2 */2

我们要做三步操作：

1) 把上述代码按词组分开，由于输入已经是逆波兰式，只需要按空白分开即可。

2) 用gen(操作符,操作数)生成每一步运算的代码，必要的时候新增临时变量（操作数可以为空，对应一元的情况)

a) 对于输入的列表的每一个，将元素入栈

b) 如果这是一个可以调用的对象（运算符），按照其定义出栈参数，生成代码，因为第一个参数总是累加器ACC，而总是生成一个临时对象，临时对象入栈，所以写法上很简单(gen_insns)。我们总是固定一个流程：

i. gen(‘LD’, 参数1)

ii. gen(‘运算’, 参数2)或者gen(‘运算’)

iii.gen(‘ST’, 结果地址)

3) 适当优化和重定位变量的符号地址。

class Generator

  class GeneratorError < RuntimeError
      def initialize(what)
         STDOUT.puts what
         @what = what
      end
      def inspect
         "GeneratorError : #{what}"
      end
      alias to_s inspect
  end

  def initialize(opt = {})
    @opt = opt
  end

  #获得符号类型 
  def sym_type(a)
    case a
      when /^acc$/
         return [:acc, :acc]
         return [:imm, a.to_i]
      when /^(.+)/(d+)$/     #可调用对象
         return [:callable, $1, $2]
      else                   #标识符
         return [:ident, a]
    end
  end

  def gen(ins, oper = '')
    @sns.push [ins, oper]
  end

  def gen_insns(name, arity, args)
    a = args.shift
    gen('LD', a[1]) #累加器
    x = args.shift
    case name
       when '+'
         gen('ADD', x[1])
       when '-'
         gen('SUB', x[1])
       when '*'
         gen('MULT', x[1])
       when '/'
         gen('DIV', x[1])
       when 'abs'
         gen('ABS')  
       when 'neg'
         gen('CHS')  
    end
    tmpname = "tmp_#{@tmp+=1}"
    gen('ST', tmpname)
    @stack.push [:ident, tmpname]
  end

  def generate_code
    @stack = []
    @sns = []
    @tmp = 0
    @list.each_with_index{|x, i|
       @stack.push x
       while true
        x = @stack.pop
        case x[0]
          when :ident
             @stack.push x
             break
          when :callable #运算符，注意运算数不能全为ident
             _, name, arity = x
             arity = arity.to_i
             if @stack.size < arity
                raise GeneratorError.new("Stack underflow at #{i} : #{x}")
                #操作数不足
             end
             gen_insns(name, arity, @stack.pop(arity))
         end
       end
    }
  end

  #*假定我们生成的变量从baseaddr开始，每个占4个字节
  def relocate(baseaddr)
    @code    = ""
    @varptr  = baseaddr - 4
    @varaddr = {}
    @sns.each{|x|
       next if x[0] == :opt
       if x[1]!=''
          @varaddr[x[1]] ||= @varptr += 4
          @code << "#{x[0]}t#{sprintf("%08x", @varaddr[x[1]])} ; #{x[1]}n"
       else
          @code << "#{x[0]}n"
       end
    }
  end

  def generate_list(code)
    @list = code.split(/s+/).map{|x| sym_type(x)}
  end

  #做一个很简单的peephole
  def optimize
    (@sns.length-1).times{|x|
        if @sns[x,2].map(&:first) == ['ST', 'LD'] && @sns[x][1] == @sns[x+1][1]
           @sns[x][0] = @sns[x+1][0] = :opt #优化掉了
        end         

    }
  end

  def generate(text)
     generate_list(text)
     generate_code
     #做一个很简单的peephole
     optimize
     relocate(0x800000)
  end

  attr_accessor :code
end

#example :  A*((A*B+C)-C*D))
# i.e.   :  A A B * C + C D * - *
x = Generator.new
x.generate "A A B */2 C +/2 C D */2 -/2 */2"
#x.generate "A B +/2 A C -/2 */2"
print x.code

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

class Generator

class GeneratorError < RuntimeError

def initialize(what)

STDOUT.puts what

@what = what

end

def inspect

"GeneratorError : #{what}"

end

alias to_s inspect

end

def initialize(opt = {})

@opt = opt

end

#获得符号类型

def sym_type(a)

case a

when /^acc$/

return [:acc, :acc]

return [:imm, a.to_i]

when /^(.+)/(d+)$/ #可调用对象

return [:callable, $1, $2]

else #标识符

return [:ident, a]

end

def gen(ins, oper = '')

@sns.push [ins, oper]

end

def gen_insns(name, arity, args)

a = args.shift

gen('LD', a[1]) #累加器

x = args.shift

case name

when '+'

gen('ADD', x[1])

when '-'

gen('SUB', x[1])

when '*'

gen('MULT', x[1])

when '/'

gen('DIV', x[1])

when 'abs'

gen('ABS')

when 'neg'

gen('CHS')

end

tmpname = "tmp_#{@tmp+=1}"

gen('ST', tmpname)

@stack.push [:ident, tmpname]

end

def generate_code

@stack = []

@sns = []

@tmp = 0

@list.each_with_index{|x, i|

@stack.push x

while true

x = @stack.pop

case x[0]

when :ident

@stack.push x

break

when :callable #运算符，注意运算数不能全为ident

_, name, arity = x

arity = arity.to_i

if @stack.size < arity

raise GeneratorError.new("Stack underflow at #{i} : #{x}")

#操作数不足

end

gen_insns(name, arity, @stack.pop(arity))

end

}

end

#*假定我们生成的变量从baseaddr开始，每个占4个字节

def relocate(baseaddr)

@code = ""

@varptr = baseaddr - 4

@varaddr = {}

@sns.each{|x|

next if x[0] == :opt

if x[1]!=''

@varaddr[x[1]] ||= @varptr += 4

@code << "#{x[0]}t#{sprintf("%08x", @varaddr[x[1]])} ; #{x[1]}n"

else

@code << "#{x[0]}n"

end

}

end

def generate_list(code)

@list = code.split(/s+/).map{|x| sym_type(x)}

end

#做一个很简单的peephole

def optimize

(@sns.length-1).times{|x|

if @sns[x,2].map(&:first) == ['ST', 'LD'] && @sns[x][1] == @sns[x+1][1]

@sns[x][0] = @sns[x+1][0] = :opt #优化掉了

end

}

end

def generate(text)

generate_list(text)

generate_code

#做一个很简单的peephole

optimize

relocate(0x800000)

end

attr_accessor :code

end

#example : A*((A*B+C)-C*D))

# i.e. : A A B * C + C D * - *

x = Generator.new

x.generate "A A B */2 C +/2 C D */2 -/2 */2"

#x.generate "A B +/2 A C -/2 */2"

print x.code

结果:

LD      00800000 ; A
MULT    00800004 ; B
ADD     00800008 ; C
ST      0080000c ; tmp_2
LD      00800008 ; C
MULT    00800010 ; D
ST      00800014 ; tmp_3
LD      0080000c ; tmp_2
SUB     00800014 ; tmp_3
ST      00800018 ; tmp_4
LD      00800000 ; A
MULT    00800018 ; tmp_4
ST      0080001c ; tmp_5

LD 00800000 ; A

MULT 00800004 ; B

ADD 00800008 ; C

ST 0080000c ; tmp_2

LD 00800008 ; C

MULT 00800010 ; D

ST 00800014 ; tmp_3

LD 0080000c ; tmp_2

SUB 00800014 ; tmp_3

ST 00800018 ; tmp_4

LD 00800000 ; A

MULT 00800018 ; tmp_4

ST 0080001c ; tmp_5

编译原理学习手记(1)– 代码生成(updating)

发表评论 取消回复

发表评论取消回复