hakeの日記

Windows環境でプログラミングの勉強をしています。

raccを試す その2

マニュアルページを参考にif文を追加してみる。

if expr [then] statement [else statement] end

追加したstatementには現状if文と式(expr)しか存在しない。
if文の文法は上記のようにトークンthenと、else節を省略可能にしてendで終了。条件式は0以外を真とする。else節がない場合はnilを返す、これに合わせてfooterの記述もnilが帰ったら文字列"nil"を表示するように変更。

? if 1 then 10 else 100 end     # 省略なしの文法
=> 10
? if 0 then 10 else 100 end
=> 100

? if 1 10 else 100 end          # thenを省略
=> 10
? if 0 10 else 100 end
=> 100

? if 1 10 end                   # else節を省略
=> 10
? if 0 10 end
=> nil

上手く行ってるみたいなのだけれども、生成の際に1件conflictが発生した

state 14 contains 1 shift/reduce conflicts

-------- Grammar --------

rule 1 target: statement
rule 2 target: 
rule 3 statement: if_stmt
rule 4 statement: expr
rule 5 if_stmt: IF expr then statement else END
rule 6 then: THEN
rule 7 then: 
rule 8 else: ELSE statement
rule 9 else: 
rule 10 expr: expr "+" expr
rule 11 expr: expr "-" expr
rule 12 expr: expr "*" expr
rule 13 expr: expr "/" expr
rule 14 expr: "(" expr ")"
rule 15 expr: "-" NUMBER
rule 16 expr: NUMBER
rule 17 expr: IDENT "=" expr
rule 18 expr: IDENT

中略

state 14

   5) if_stmt : IF expr _ then statement else END
  10) expr : expr _ "+" expr
  11) expr : expr _ "-" expr
  12) expr : expr _ "*" expr
  13) expr : expr _ "/" expr

  "*"           shift, and go to state 15
  "/"           shift, and go to state 16
  "+"           shift, and go to state 17
  "-"           shift, and go to state 18
  "-"           [reduce using rule 7 (then)]
  THEN          shift, and go to state 22
  $default      reduce using rule 7 (then)

  then          go to state 23

このconflictは、UMINUSの定義を消すとなくなるので、その部分に原因があるような気がします。でも、outputの出力はルール7でreduceできるよ、というもの。ルール7はthenの省略についての定義のはずなので、これが何で関係あるのかよく解からん。


# $Id: calc.y,v 1.4 2005/11/20 13:29:32 aamine Exp $
#
# Very simple calculater.

class Calcp
  prechigh
    nonassoc UMINUS
    left '*' '/'
    left '+' '-'
    right '='
  preclow
rule
  target: statement
        | /* none */ { result = nil }

  statement: if_stmt
           | expr

  if_stmt:IF expr then statement else END
             { result = (val[1]!=0?val[3]:val[4]) }

  then   : THEN
         | 

  else   : ELSE statement  { result = val[1] }
         | /* none */      { result = nil }


  expr: expr '+' expr { result += val[2] }
      | expr '-' expr { result -= val[2] }
      | expr '*' expr { result *= val[2] }
      | expr '/' expr { result /= val[2] }
      | '(' expr ')' { result = val[1] }
      | '-' NUMBER  =UMINUS { result = -val[1] }
      | NUMBER
      | IDENT '=' expr { result = set_var(val[0], val[2]) }
      | IDENT          { result = ref_var(val[0]) }
end

---- header
# $Id: calc.y,v 1.4 2005/11/20 13:29:32 aamine Exp $
---- inner


  def initialize
    @var = Hash.new
  end

  def parse(str)
    @q = []
    until str.empty?
      case str
      when /\A\s+/
      when /\Aif/
        @q.push [:IF, $&]
      when /\Athen/
        @q.push [:THEN, $&]
      when /\Aelse/
        @q.push [:ELSE, $&]
      when /\Aend/
        @q.push [:END, $&]
      when /\A[A-Za-z]\w*/
        @q.push [:IDENT, $&]
      when /\A\d+/
        @q.push [:NUMBER, $&.to_i]
      when /\A.|\n/o
        s = $&
        @q.push [s, s]
      end
      str = $'
    end
    @q.push [false, '$end']
#p @q
    do_parse
  end

  def next_token
    @q.shift
  end

  def set_var(key, val)
    @var[key] = val
  end

  def ref_var(key)
     if @var[key].nil?
        raise MyError, "Undefined Variable : #{key}"
     else
        @var[key]
     end
  end

---- footer

class MyError < StandardError
end


parser = Calcp.new
puts
puts 'type "Q" to quit.'
puts
while true
  puts
  print '? '
  str = gets.chop!
  break if /q/i =~ str
  begin
    ret = parser.parse(str)
    ret = "nil" if ret.nil?
    puts "=> #{ret}"
  rescue ParseError
    puts $!
  rescue => e
    puts e.message
  end
end