math.ace

%grammar.type "ruby"
%require "~> 0.1"

%token IDENT
%token NUM
%token PLUS "+"
%token MINUS "-"
%token DIVIDE "/"
%token MULTIPLY "*"
%token EQUALS "="

%%
statements: statement statements
          | nothing
statement: IDENT EQUALS expression
         | expression
expression: value op value
value: IDENT | NUM
op: PLUS | MINUS | DIVIDE | MULTIPLY
%%

class Parser
  %{write}
  
  def token(ident)
    ident.to_s.upcase.intern
  end
end

math.output

Productions:
   0 $start: statements $end
   1 statements: statement statements
   2 statements: $empty
   3 statement: IDENT "=" expression
   4 statement: expression
   5 expression: value op value
   6 value: IDENT
   7 value: NUM
   8 op: "+"
   9 op: "-"
  10 op: "/"
  11 op: "*"


Precedence:
  --- highest
  nonassoc 1:
    {_}
  nonassoc 0:
    {$end}
  --- lowest


  State 0:
    0/n0: $start →  • statements $end
      {}
    1/n1: statements →  • statement statements
      {}
    2/n1: statements →  • $empty
      {}
    3/n1: statement →  • IDENT "=" expression
      {}
    4/n1: statement →  • expression
      {}
    5/n1: expression →  • value op value
      {}
    6/n1: value →  • IDENT
      {}
    7/n1: value →  • NUM
      {}
    transitions:
      statements: State 1
      statement: State 2
      $empty: State 3
      IDENT: State 4
      expression: State 5
      value: State 6
      NUM: State 7
      $default: State 3

  State 1:
    8/n0: $start → statements • $end
      {}
    transitions:
      $end: State 8

  State 2:
    9/n1: statements → statement • statements
      {}
    10/n1: statements →  • statement statements
      {}
    11/n1: statements →  • $empty
      {}
    12/n1: statement →  • IDENT "=" expression
      {}
    13/n1: statement →  • expression
      {}
    14/n1: expression →  • value op value
      {}
    15/n1: value →  • IDENT
      {}
    16/n1: value →  • NUM
      {}
    transitions:
      statements: State 9
      statement: State 2
      $empty: State 3
      IDENT: State 4
      expression: State 5
      value: State 6
      NUM: State 7
      $default: State 3

  State 3:
    17/n1: statements → $empty •
      {$end}
    reductions:
      $end: Rule 2

  State 4:
    18/n1: statement → IDENT • "=" expression
      {}
    19/n1: value → IDENT •
      {"+", "-", "/", "*", IDENT, NUM, $end}
    transitions:
      "=": State 10
    reductions:
      "+": Rule 6
      "-": Rule 6
      "/": Rule 6
      "*": Rule 6
      IDENT: Rule 6
      NUM: Rule 6
      $end: Rule 6

  State 5:
    20/n1: statement → expression •
      {IDENT, NUM, $end}
    reductions:
      IDENT: Rule 4
      NUM: Rule 4
      $end: Rule 4

  State 6:
    21/n1: expression → value • op value
      {}
    22/n1: op →  • "+"
      {}
    23/n1: op →  • "-"
      {}
    24/n1: op →  • "/"
      {}
    25/n1: op →  • "*"
      {}
    transitions:
      op: State 11
      "+": State 12
      "-": State 13
      "/": State 14
      "*": State 15

  State 7:
    26/n1: value → NUM •
      {"+", "-", "/", "*", IDENT, NUM, $end}
    reductions:
      $default: Rule 7

  State 8:
    27/n0: $start → statements $end •
      {}
    accepting:
      $end: Rule 0

  State 9:
    28/n1: statements → statement statements •
      {$end}
    reductions:
      $end: Rule 1

  State 10:
    29/n1: statement → IDENT "=" • expression
      {}
    30/n1: expression →  • value op value
      {}
    31/n1: value →  • IDENT
      {}
    32/n1: value →  • NUM
      {}
    transitions:
      expression: State 16
      value: State 6
      IDENT: State 4
      NUM: State 7

  State 11:
    33/n1: expression → value op • value
      {}
    34/n1: value →  • IDENT
      {}
    35/n1: value →  • NUM
      {}
    transitions:
      value: State 17
      IDENT: State 4
      NUM: State 7

  State 12:
    36/n1: op → "+" •
      {IDENT, NUM}
    reductions:
      IDENT: Rule 8
      NUM: Rule 8

  State 13:
    37/n1: op → "-" •
      {IDENT, NUM}
    reductions:
      IDENT: Rule 9
      NUM: Rule 9

  State 14:
    38/n1: op → "/" •
      {IDENT, NUM}
    reductions:
      IDENT: Rule 10
      NUM: Rule 10

  State 15:
    39/n1: op → "*" •
      {IDENT, NUM}
    reductions:
      IDENT: Rule 11
      NUM: Rule 11

  State 16:
    40/n1: statement → IDENT "=" expression •
      {IDENT, NUM, $end}
    reductions:
      IDENT: Rule 3
      NUM: Rule 3
      $end: Rule 3

  State 17:
    41/n1: expression → value op value •
      {IDENT, NUM, $end}
    reductions:
      IDENT: Rule 5
      NUM: Rule 5
      $end: Rule 5

math.rb

class Parser
  
# This file assumes that the output of the generator will be placed
# within a module or a class.  However, the module/class requires a
# `type` method, which takes a terminal and gives its type, as a
# symbol.  These types should line up with the terminals that were
# defined in the original grammar.

# The actions to take during parsing.  In every state, there are a
# set of acceptable peek tokens; this table tells the parser what
# to do on each acceptable peek token.  The possible actions include
# `:accept`, `:reduce`, and `:state`; `:accept` means to accept the
# input and return the value of the pasing.  `:reduce` means to
# reduce the top of the stack into a given nonterminal.  `:state`
# means to transition to another state.
#
# @return [Array<Hash<(Symbol, Array<(Symbol, Numeric)>)>>]
ACTION_TABLE = [{:statements=>[:state, 1],
  :statement=>[:state, 2],
  :$empty=>[:state, 3],
  :IDENT=>[:state, 4],
  :expression=>[:state, 5],
  :value=>[:state, 6],
  :NUM=>[:state, 7],
  :$default=>[:state, 3]},
 {:$end=>[:state, 8]},
 {:statements=>[:state, 9],
  :statement=>[:state, 2],
  :$empty=>[:state, 3],
  :IDENT=>[:state, 4],
  :expression=>[:state, 5],
  :value=>[:state, 6],
  :NUM=>[:state, 7],
  :$default=>[:state, 3]},
 {:$end=>[:reduce, 2]},
 {:EQUALS=>[:state, 10],
  :PLUS=>[:reduce, 6],
  :MINUS=>[:reduce, 6],
  :DIVIDE=>[:reduce, 6],
  :MULTIPLY=>[:reduce, 6],
  :IDENT=>[:reduce, 6],
  :NUM=>[:reduce, 6],
  :$end=>[:reduce, 6]},
 {:IDENT=>[:reduce, 4], :NUM=>[:reduce, 4], :$end=>[:reduce, 4]},
 {:op=>[:state, 11],
  :PLUS=>[:state, 12],
  :MINUS=>[:state, 13],
  :DIVIDE=>[:state, 14],
  :MULTIPLY=>[:state, 15]},
 {:$default=>[:reduce, 7]},
 {:$end=>[:accept, 0]},
 {:$end=>[:reduce, 1]},
 {:expression=>[:state, 16],
  :value=>[:state, 6],
  :IDENT=>[:state, 4],
  :NUM=>[:state, 7]},
 {:value=>[:state, 17], :IDENT=>[:state, 4], :NUM=>[:state, 7]},
 {:IDENT=>[:reduce, 8], :NUM=>[:reduce, 8]},
 {:IDENT=>[:reduce, 9], :NUM=>[:reduce, 9]},
 {:IDENT=>[:reduce, 10], :NUM=>[:reduce, 10]},
 {:IDENT=>[:reduce, 11], :NUM=>[:reduce, 11]},
 {:IDENT=>[:reduce, 3], :NUM=>[:reduce, 3], :$end=>[:reduce, 3]},
 {:IDENT=>[:reduce, 5], :NUM=>[:reduce, 5], :$end=>[:reduce, 5]}]
.freeze

# A list of all of the productions.  Only includes the left-hand side,
# the number of tokens on the right-hand side, and the block to call
# on reduction.
#
# @return [Array<Array<(Symbol, Numeric, Proc)>>]
PRODUCTIONS  = [[:$start, 2, proc { |_| _ }],
[:statements, 2, proc { |_| _ }],
[:statements, 1, proc { |_| _ }],
[:statement, 3, proc { |_| _ }],
[:statement, 1, proc { |_| _ }],
[:expression, 3, proc { |_| _ }],
[:value, 1, proc { |_| _ }],
[:value, 1, proc { |_| _ }],
[:op, 1, proc { |_| _ }],
[:op, 1, proc { |_| _ }],
[:op, 1, proc { |_| _ }],
[:op, 1, proc { |_| _ }]].freeze

# Runs the parser.
#
# @param input [Array<Object>] the input to run the parser over.
# @return [Object] the result of the accept.
def parse(input)
  stack = []
  stack.push([nil, 0])
  input = input.dup
  last  = nil

  until stack.empty? do
    last = parse_action(stack, input)
  end

  last

end

# Actually performs the parsing action on the given stack on input.
# If you want to implement a push parser, than messing with this
# method is probably the way to go.
#
# @param stack [Array<Array<(Object, Numeric)>>] the stack of the
#   parser.  The actual order of the stack is important.
# @param input [Array<Object>] the input to run the parser over.
#   The elements of this may be passed to the `type` method.
# @return [Object] the result of the last accepting reduction.
def parse_action(stack, input)
  last = nil
  peek_token = if input.empty?
    :$end
  else
    type(input.first)
  end

  action = ACTION_TABLE[stack.last.last].fetch(peek_token) do
    ACTION_TABLE[stack.last.last].fetch(:$default)
  end
  case action.first
  when :accept
    production = PRODUCTIONS[action.last]
    last       = stack.pop(production[1]).first.first
    stack.pop
  when :reduce
    production = PRODUCTIONS[action.last]
    removing   = stack.pop(production[1])
    value = instance_exec(*removing.map(&:first), &production[2])
    goto  = ACTION_TABLE[stack.last.last][production[0]]
    stack.push([value, goto.last])
  when :state
    stack.push([input.shift, action.last])
  else
    raise NotImplementedError, "Unknown action #{action.first}"
  end

  last

rescue KeyError => e
  if handle_error(
    { :stack     => stack,
      :peek      => peek_token,
      :remaining => input,
      :error     => e,
      :expected  => ACTION_TABLE[stack.last.last].keys
    })
    retry
  end
end


  
  def token(ident)
    ident.to_s.upcase.intern
  end
end