Class: Ibex::LALR::ConflictResolver

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

Overview

Applies yacc-compatible precedence and ordering rules to action candidates.

Instance Method Summary collapse

Constructor Details

#initialize(grammar) ⇒ ConflictResolver

Returns a new instance of ConflictResolver.

RBS:

  • (IR::Grammar grammar) -> void

Parameters:



8
9
10
 
# File 'lib/ibex/lalr/conflict.rb', line 8

def initialize(grammar)
  @grammar = grammar
end

Instance Method Details

#associativity_choice(shift, reduction, associativity) ⇒ [ IR::parser_action, IR::conflict_resolution ]

RBS:

  • (IR::shift_action shift, IR::reduce_action reduction, Symbol associativity) -> [IR::parser_action, IR::conflict_resolution]

Parameters:

  • shift (IR::shift_action)
  • reduction (IR::reduce_action)
  • associativity (Symbol)

Returns:

  • ([ IR::parser_action, IR::conflict_resolution ]) 


88
89
90
91
92
93
94
95
96
 
# File 'lib/ibex/lalr/conflict.rb', line 88

def associativity_choice(shift, reduction, associativity)
  case associativity.to_sym
  when :left then [reduction, { by: :associativity, associativity: :left, chose: :reduce }]
  when :right then [shift, { by: :associativity, associativity: :right, chose: :shift }]
  when :nonassoc then [{ type: :error }, { by: :associativity, associativity: :nonassoc, chose: :error }]
  when :precedence then [shift, { by: :default_shift, chose: :shift }]
  else raise Ibex::Error, "unknown associativity #{associativity.inspect}"
  end
end

#precedence_choice(shift, reduction, token_precedence, production_precedence) ⇒ [ IR::parser_action, IR::conflict_resolution ]

RBS:

  • (IR::shift_action shift, IR::reduce_action reduction, IR::precedence? token_precedence, IR::precedence? production_precedence) -> [IR::parser_action, IR::conflict_resolution]

Parameters:

  • shift (IR::shift_action)
  • reduction (IR::reduce_action)
  • token_precedence (IR::precedence, nil)
  • production_precedence (IR::precedence, nil)

Returns:

  • ([ IR::parser_action, IR::conflict_resolution ]) 


76
77
78
79
80
81
82
83
84
 
# File 'lib/ibex/lalr/conflict.rb', line 76

def precedence_choice(shift, reduction, token_precedence, production_precedence)
  return [shift, { by: :default_shift, chose: :shift }] unless token_precedence && production_precedence

  comparison = token_precedence[:level] <=> production_precedence[:level]
  return [shift, { by: :precedence, chose: :shift }] if comparison.positive?
  return [reduction, { by: :precedence, chose: :reduce }] if comparison.negative?

  associativity_choice(shift, reduction, token_precedence[:associativity])
end

#precedence_for_production(production_id) ⇒ IR::precedence?

RBS:

  • (Integer production_id) -> IR::precedence?

Parameters:

  • production_id (Integer)

Returns:

  • (IR::precedence, nil) 


99
100
101
102
103
104
105
106
107
108
 
# File 'lib/ibex/lalr/conflict.rb', line 99

def precedence_for_production(production_id)
  production = @grammar.productions.fetch(production_id)
  return required_symbol_by_id(production.precedence_override).precedence if production.precedence_override

  production.rhs.reverse_each do |symbol_id|
    grammar_symbol = required_symbol_by_id(symbol_id)
    return grammar_symbol.precedence if grammar_symbol.terminal? && grammar_symbol.precedence
  end
  nil
end

#reduction_actions(actions) ⇒ Array[IR::reduce_action]

RBS:

  • (Array[IR::parser_action] actions) -> Array[IR::reduce_action]

Parameters:

  • actions (Array[IR::parser_action])

Returns:

  • (Array[IR::reduce_action]) 


34
35
36
37
38
39
40
41
42
43
 
# File 'lib/ibex/lalr/conflict.rb', line 34

def reduction_actions(actions)
  reductions = [] #: Array[IR::reduce_action]
  actions.each do |action|
    next unless action[:type] == :reduce

    reduction = action #: IR::reduce_action
    reductions << reduction
  end
  reductions.sort_by { |action| action[:production] }
end

#required_symbol_by_id(id) ⇒ IR::GrammarSymbol

RBS:

  • (Integer id) -> IR::GrammarSymbol

Parameters:

  • id (Integer)

Returns:



116
117
118
 
# File 'lib/ibex/lalr/conflict.rb', line 116

def required_symbol_by_id(id)
  @grammar.symbol_by_id(id) || raise(Ibex::Error, "missing grammar symbol id #{id}")
end

#resolve(token_id, candidates) ⇒ [ IR::parser_action?, Array[IR::conflict] ]

RBS:

  • (Integer token_id, Array[IR::parser_action] candidates) -> [IR::parser_action?, Array[IR::conflict]]

Parameters:

  • token_id (Integer)
  • candidates (Array[IR::parser_action])

Returns:

  • ([ IR::parser_action?, Array[IR::conflict] ]) 


13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/ibex/lalr/conflict.rb', line 13

def resolve(token_id, candidates)
  actions = candidates.uniq
  return [actions.first, Array.new(0)] if actions.length <= 1

  accept = actions.find { |action| action[:type] == :accept }
  return [accept, Array.new(0)] if accept

  shift = actions.find { |action| action[:type] == :shift } #: IR::shift_action?
  reductions = reduction_actions(actions)
  chosen_reduce, conflicts = resolve_reductions(token_id, reductions)
  all_conflicts = widen_conflicts(conflicts)
  return [chosen_reduce, all_conflicts] unless shift
  return [shift, all_conflicts] unless chosen_reduce

  chosen, conflict = resolve_shift_reduce(token_id, shift, chosen_reduce)
  [chosen, all_conflicts << conflict]
end

#resolve_reductions(token_id, reductions) ⇒ [ IR::reduce_action?, Array[IR::reduce_reduce_conflict] ]

RBS:

  • (Integer token_id, Array[IR::reduce_action] reductions) -> [IR::reduce_action?, Array[IR::reduce_reduce_conflict]]

Parameters:

  • token_id (Integer)
  • reductions (Array[IR::reduce_action])

Returns:

  • ([ IR::reduce_action?, Array[IR::reduce_reduce_conflict] ]) 


52
53
54
55
56
57
58
59
60
61
 
# File 'lib/ibex/lalr/conflict.rb', line 52

def resolve_reductions(token_id, reductions)
  return [nil, Array.new(0)] if reductions.empty?
  return [reductions.first, Array.new(0)] if reductions.length == 1

  chosen = reductions.first
  conflict = { type: :reduce_reduce, symbol: token_name(token_id),
               reductions: reductions.map { |action| action[:production] },
               resolution: { by: :definition_order, chose: chosen[:production] } } #: IR::reduce_reduce_conflict
  [chosen, [conflict]]
end

#resolve_shift_reduce(token_id, shift, reduction) ⇒ [ IR::parser_action, IR::shift_reduce_conflict ]

RBS:

  • (Integer token_id, IR::shift_action shift, IR::reduce_action reduction) -> [IR::parser_action, IR::shift_reduce_conflict]

Parameters:

  • token_id (Integer)
  • shift (IR::shift_action)
  • reduction (IR::reduce_action)

Returns:

  • ([ IR::parser_action, IR::shift_reduce_conflict ]) 


65
66
67
68
69
70
71
72
 
# File 'lib/ibex/lalr/conflict.rb', line 65

def resolve_shift_reduce(token_id, shift, reduction)
  token_precedence = required_symbol_by_id(token_id).precedence
  production_precedence = precedence_for_production(reduction[:production])
  chosen, resolution = precedence_choice(shift, reduction, token_precedence, production_precedence)
  conflict = { type: :shift_reduce, symbol: token_name(token_id), shift_to: shift[:state],
               reduce: reduction[:production], resolution: resolution } #: IR::shift_reduce_conflict
  [chosen, conflict]
end

#token_name(token_id) ⇒ String

RBS:

  • (Integer token_id) -> String

Parameters:

  • token_id (Integer)

Returns:

  • (String) 


111
112
113
 
# File 'lib/ibex/lalr/conflict.rb', line 111

def token_name(token_id)
  required_symbol_by_id(token_id).name
end

#widen_conflicts(conflicts) ⇒ Array[IR::conflict]

RBS:

  • (Array[IR::reduce_reduce_conflict] conflicts) -> Array[IR::conflict]

Parameters:

  • conflicts (Array[IR::reduce_reduce_conflict])

Returns:

  • (Array[IR::conflict]) 


46
47
48
 
# File 'lib/ibex/lalr/conflict.rb', line 46

def widen_conflicts(conflicts)
  conflicts.map(&:itself) #: Array[IR::conflict]
end