Class: Ibex::Equiv::Machine

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/equiv/machine.rb,
sig/ibex/equiv/machine.rbs

Overview

Immutable, semantic-action-free LR state-stack machine.

Defined Under Namespace

Classes: BudgetExceeded, Configuration

Instance Method Summary collapse

Constructor Details

#initialize(automaton, max_actions:, max_stack:) ⇒ Machine

Returns a new instance of Machine.

RBS:

  • (IR::Automaton automaton, max_actions: Integer, max_stack: Integer) -> void

Parameters:

  • automaton (IR::Automaton)
  • max_actions: (Integer)
  • max_stack: (Integer) 


28
29
30
31
32
33
34
 
# File 'lib/ibex/equiv/machine.rb', line 28

def initialize(automaton, max_actions:, max_stack:)
  @automaton = automaton
  @max_actions = max_actions
  @max_stack = max_stack
  @terminals = automaton.grammar.terminals.to_h { |symbol| [symbol.name, symbol.id] }
  @eof_id = @terminals.fetch("$eof")
end

Instance Method Details

#apply_reduction!(stack, production_id) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[Integer] stack, Integer production_id) -> void

Parameters:

  • stack (Array[Integer])
  • production_id (Integer) 


106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/ibex/equiv/machine.rb', line 106

def apply_reduction!(stack, production_id)
  production = @automaton.grammar.productions.fetch(production_id)
  if production.rhs.length >= stack.length
    raise Ibex::Error, "(equiv):1:1: production #{production_id} underflows the state stack"
  end

  stack.pop(production.rhs.length)
  state = @automaton.states.fetch(stack.fetch(-1))
  target = state.gotos[production.lhs]
  raise Ibex::Error, "(equiv):1:1: missing goto after production #{production_id}" unless target

  stack << target
end

#consume(configuration, token_id, eof:) ⇒ Configuration

RBS:

  • (Configuration configuration, Integer token_id, eof: bool) -> Configuration

Parameters:

  • configuration (Configuration)
  • token_id (Integer)
  • eof: (Boolean)

Returns:



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/ibex/equiv/machine.rb', line 72

def consume(configuration, token_id, eof:)
  stack = configuration.stack.dup
  actions = configuration.actions
  reductions = configuration.reductions.dup
  loop do
    actions += 1
    enforce_action_budget!(actions)
    state = @automaton.states.fetch(stack.fetch(-1))
    action = state.actions.fetch(token_id, state.default_action || { type: :error })
    case action.fetch(:type)
    when :shift
      shift = action #: IR::shift_action
      stack << shift.fetch(:state)
      enforce_stack_budget!(stack)
      return Configuration.new(stack: stack, status: nil, actions: actions, reductions: reductions) unless eof
    when :reduce
      reduce = action #: IR::reduce_action
      production_id = reduce.fetch(:production)
      apply_reduction!(stack, production_id)
      reductions << production_id
      enforce_stack_budget!(stack)
    when :accept
      return Configuration.new(
        stack: stack, status: :accepted, actions: actions, reductions: reductions
      )
    when :error
      return Configuration.new(stack: stack, status: :error, actions: actions, reductions: reductions)
    else
      raise Ibex::Error, "(equiv):1:1: unknown parser action #{action.inspect}"
    end
  end
end

#enforce_action_budget!(actions) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer actions) -> void

Parameters:

  • actions (Integer) 


121
122
123
124
125
 
# File 'lib/ibex/equiv/machine.rb', line 121

def enforce_action_budget!(actions)
  return if actions <= @max_actions

  raise BudgetExceeded, "(equiv):1:1: simulation exceeded #{@max_actions} actions"
end

#enforce_stack_budget!(stack) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[Integer] stack) -> void

Parameters:

  • stack (Array[Integer]) 


128
129
130
131
132
 
# File 'lib/ibex/equiv/machine.rb', line 128

def enforce_stack_budget!(stack)
  return if stack.length <= @max_stack

  raise BudgetExceeded, "(equiv):1:1: simulation exceeded stack depth #{@max_stack}"
end

#finish(configuration) ⇒ Configuration

RBS:

  • (Configuration configuration) -> Configuration

Parameters:

Returns:



63
64
65
66
67
 
# File 'lib/ibex/equiv/machine.rb', line 63

def finish(configuration)
  return configuration if configuration.status

  consume(configuration, @eof_id, eof: true)
end

#push(configuration, token) ⇒ Configuration

RBS:

  • (Configuration configuration, String token) -> Configuration

Parameters:

Returns:



48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/ibex/equiv/machine.rb', line 48

def push(configuration, token)
  return configuration if configuration.status

  token_id = @terminals[token]
  unless token_id
    return Configuration.new(
      stack: configuration.stack, status: :error, actions: configuration.actions,
      reductions: configuration.reductions
    )
  end

  consume(configuration, token_id, eof: false)
end

#run(tokens) ⇒ Configuration

RBS:

  • (Array[String] tokens) -> Configuration

Parameters:

  • tokens (Array[String])

Returns:



43
44
45
 
# File 'lib/ibex/equiv/machine.rb', line 43

def run(tokens)
  tokens.reduce(start) { |configuration, token| push(configuration, token) }
end

#start ⇒ Configuration

RBS:

  • () -> Configuration

Returns:



37
38
39
40
 
# File 'lib/ibex/equiv/machine.rb', line 37

def start
  entry = @automaton.entry_states.fetch(@automaton.grammar.start)
  Configuration.new(stack: [entry], status: nil, actions: 0, reductions: [])
end