Class: Ibex::Normalizer

Inherits:
Object
  • Object
show all
Includes:
NormalizeDeclarations, NormalizeDiagnostics, NormalizeExpander, NormalizeInlineExpansion, NormalizeInlineValidation, NormalizeLexer, NormalizeNamedReferences, NormalizeNodes, NormalizeParameterEbnfLowering, NormalizeParameterLowering, NormalizeParameterSubstitution, NormalizeParameterValidation, NormalizeParameters, NormalizeRecoveryDeclarations
Defined in:
lib/ibex/normalize.rb,
sig/ibex/normalize.rbs

Overview

Converts a frontend AST into immutable Grammar IR.

Constant Summary collapse

RESERVED_NAMES =

Signature:

  • Array[String]

Returns:

  • (Array[String]) 
%w[result val _values].freeze
RUBY_KEYWORDS =

Returns:

  • (Array[String]) 
%w[
  __ENCODING__ __FILE__ __LINE__ alias and begin break case class def defined do else elsif end ensure false for if
  in module next nil not or redo rescue retry return self super then true undef unless until when while yield
].freeze
DEFAULT_MAX_PARAMETER_SPECIALIZATIONS =

Signature:

  • Array[String]

Returns:

  • (::Integer) 
1_000
DEFAULT_MAX_INLINE_EXPANSIONS =

Returns:

  • (::Integer) 
10_000

Instance Method Summary collapse

Methods included from NormalizeDiagnostics

#productive_terminal?, #productive_terminal_ids, #reachable_symbol_ids, #validate_grammar, #validate_symbol_metadata, #warn_duplicate_productions, #warn_empty_language, #warn_unreachable_nonterminals, #warn_unreachable_terminals, #warn_unused_precedence, #warn_unused_terminals

Methods included from NormalizeInlineExpansion

#advance_inline_expansion_frame?, #append_inline_array, #append_inline_symbol, #charge_inline_expansion!, #clone_inline_expansion_frames, #combine_inline_variant, #combined_inline_precedence, #combined_inline_steps, #complete_inline_expansion_frame?, #composed_inline_action, #composed_inline_production, #composition_plan_step, #copy_inline_production, #drain_inline_expansion_frames, #empty_inline_variant, #enforce_inline_choice_limit!, #expand_inline_production, #expand_inline_rules, #finish_inline_choice, #finish_inline_precedence, #inline_action_step, #inline_expansion_frame, #inline_implicit_code, #inline_production_expansion, #inline_source_provenance, #rebuild_inline_symbols, #remap_inline_production, #remap_inline_reference, #remap_inline_steps, #remap_inline_symbol, #resolve_inline_reference, #schedule_inline_choice_branches

Methods included from NormalizeExpander

#add_group_production, #add_production, #build_optional, #build_plus, #build_separated_list, #build_star, #expand_group, #expand_inline_action, #expand_optional, #expand_plus, #expand_separated_list, #expand_star, #group_value_expression, #new_helper, #normalize_action, #normalize_alternative, #normalize_item, #normalize_user_productions, #normalized_alternative_items, #synthetic_action, #synthetic_origin

Methods included from NormalizeNodes

#normalize_node_annotation, #validate_node_fields

Methods included from NormalizeNamedReferences

#add_named_reference, #named_reference_in, #reject_group_named_references, #unwrap_reference

Methods included from NormalizeParameters

#clear_parameter_alternative, #drain_parameter_worklist, #enforce_parameter_limits!, #growing_parameter_arguments?, #new_parameter_helper, #parameter_argument_contains?, #parameter_frame, #prepare_parameter_alternative?, #prepare_parameter_alternative_entry, #schedule_parameter_specialization, #specialize_parameterized_reference

Methods included from NormalizeParameterLowering

#advance_parameter_alternative, #finish_parameter_alternative, #finish_parameter_item, #lower_parameter_call, #lower_parameter_item, #parameter_items_remaining?, #process_parameter_operation, #start_parameter_item, #with_parameter_frame_context

Methods included from NormalizeParameterEbnfLowering

#finish_parameter_group_alternative, #finish_parameter_separated_list, #finish_parameter_suffix, #lower_parameter_group, #lower_parameter_separated_list, #lower_parameter_suffix, #start_parameter_group_alternative

Methods included from NormalizeParameterSubstitution

#clone_parameter_call, #clone_parameter_group, #clone_parameter_item, #clone_parameter_separated_list, #clone_parameter_suffix, #clone_parameter_symbol, #substitute_formal_reference, #substitute_parameter_alternative, #substitute_parameter_item, #substitute_parameter_precedence

Methods included from NormalizeInlineValidation

#collect_inline_edges, #collect_live_formals, #gather_inline_rules, #parameter_formal_liveness, #validate_inline_cycles, #validate_inline_start, #validate_inline_terminal_collisions, #visit_inline_cycle

Methods included from NormalizeParameterValidation

#gather_parameter_templates, #gather_parameterized_rule, #parameter_template?, #parameterized_rule?, #reject_argument_named_reference, #reject_mixed_parameterized_rule, #validate_parameter_call, #validate_parameter_formals, #validate_parameter_item, #validate_parameter_references, #validate_parameter_terminal_collisions, #validate_parameterized_item

Methods included from NormalizeRecoveryDeclarations

#read_grammar_test, #read_on_error_reduce_declaration, #read_parser_control_declaration, #read_recovery_declaration, #validate_recovery_declarations

Methods included from NormalizeLexer

#decode_lexer_literal, #normalize_lexer, #normalize_lexer_pattern, #normalize_lexer_rule, #normalize_lexer_state, #risky_lexer_pattern?, #validate_lexer_action, #validate_lexer_regexp, #validate_lexer_token

Methods included from NormalizeDeclarations

#read_conversions, #read_declaration, #read_declarations, #read_extended_declaration, #read_option, #read_options, #read_parser_parameter, #read_precedence, #read_start_declaration, #read_symbol_metadata, #read_symbol_metadata_declaration, #read_tokens, #read_value_printer, #validate_value_printers

Constructor Details

#initialize(input, mode: :default, max_parameter_specializations: DEFAULT_MAX_PARAMETER_SPECIALIZATIONS, max_inline_expansions: DEFAULT_MAX_INLINE_EXPANSIONS) ⇒ Normalizer

Returns a new instance of Normalizer.

RBS:

  • (Frontend::AST::Root | Frontend::AST::Fragment | Frontend::Resolution input, ?mode: Symbol | String, ?max_parameter_specializations: Integer, ?max_inline_expansions: Integer) -> void

Parameters:



94
95
96
97
98
99
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
 
# File 'lib/ibex/normalize.rb', line 94

def initialize(input, mode: :default, max_parameter_specializations: DEFAULT_MAX_PARAMETER_SPECIALIZATIONS,
               max_inline_expansions: DEFAULT_MAX_INLINE_EXPANSIONS)
  validate_positive_limit!(:max_parameter_specializations, max_parameter_specializations)
  validate_positive_limit!(:max_inline_expansions, max_inline_expansions)
  normalized_mode = mode.to_sym
  raise ArgumentError, "mode must be :default or :extended" unless %i[default extended].include?(normalized_mode)

  @resolution = input if input.is_a?(Frontend::Resolution)
  ast = input.is_a?(Frontend::Resolution) ? input.root : input
  normalized_mode = :extended if ast.is_a?(Frontend::AST::Root) && ast.extended
  fail_at(ast.loc, "fragments must be resolved before normalization") if ast.is_a?(Frontend::AST::Fragment)
  unresolved = ast.declarations.find { |declaration| declaration.is_a?(Frontend::AST::Include) }
  fail_at(unresolved.loc, "includes must be resolved before normalization") if unresolved

  @ast = ast
  @mode = normalized_mode #: IR::grammar_mode
  @symbols = [] #: Array[IR::GrammarSymbol]
  @symbols_by_name = {} #: Hash[String, IR::GrammarSymbol]
  @productions = [] #: Array[IR::Production]
  @warnings = [] #: Array[IR::grammar_warning]
  @helper_sequence = 0
  @current_include_chain = [] #: Array[IR::source_provenance]
  @parameter_specializations = {} #: Hash[[String, Array[String]], String]
  @parameter_worklist = [] #: Array[Hash[Symbol, untyped]]
  @parameter_worklist_active = false
  @max_parameter_specializations = max_parameter_specializations
  @max_inline_expansions = max_inline_expansions
  @inline_expansion_count = 0
  @inline_symbol_ids = Set.new #: Set[Integer]
  @inline_rule_by_symbol = {} #: Hash[Integer, String]
end

Instance Method Details

#fail_at(location, message) ⇒ bot

RBS:

  • (Frontend::Location location, String message) -> bot

Parameters:

Returns:

  • (bot) 


314
315
316
 
# File 'lib/ibex/normalize.rb', line 314

def fail_at(location, message)
  raise Ibex::Error, "#{location}: #{message}"
end

#fail_hash(location, message) ⇒ bot

RBS:

  • (IR::location? location, String message) -> bot

Parameters:

  • location (IR::location, nil)
  • message (String)

Returns:

  • (bot) 


319
320
321
322
 
# File 'lib/ibex/normalize.rb', line 319

def fail_hash(location, message)
  rendered = location ? "#{location[:file]}:#{location[:line]}:#{location[:column]}" : "(grammar):1:1"
  raise Ibex::Error, "#{rendered}: #{message}"
end

#intern(name, kind, reserved: false, location: nil, documentation: nil, metadata_name: nil) ⇒ IR::GrammarSymbol

RBS:

  • (String name, Symbol kind, ?reserved: bool, ?location: IR::location?, ?documentation: String?, ?metadata_name: String?) -> IR::GrammarSymbol

Parameters:

  • name (String)
  • kind (Symbol)
  • reserved: (Boolean) (defaults to: false)
  • location: (IR::location, nil) (defaults to: nil)
  • documentation: (String, nil) (defaults to: nil)
  • metadata_name: (String, nil) (defaults to: nil)

Returns:



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/ibex/normalize.rb', line 236

def intern(name, kind, reserved: false, location: nil, documentation: nil, metadata_name: nil)
  existing = symbol(name)
  if existing
    fail_hash(location, "symbol #{name} is both terminal and nonterminal") if existing.kind != kind
    return existing
  end

  precedence = @precedence[name]
  metadata_key = metadata_name || name
  definition = IR::GrammarSymbol.new(id: @symbols.length, name: name, kind: kind, reserved: reserved,
                                     precedence: precedence, location: location,
                                     display_name: @display_names[metadata_key],
                                     semantic_type: @semantic_types[metadata_key], documentation: documentation)
  @symbols << definition
  @symbols_by_name[name] = definition
  definition
end

#intern_declared_terminals ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



174
175
176
177
 
# File 'lib/ibex/normalize.rb', line 174

def intern_declared_terminals
  @declared_tokens.each { |name, loc| intern(name, :terminal, location: loc) }
  @precedence.each_key { |name| intern(name, :terminal, location: @precedence_locations[name]) }
end

#intern_reserved_symbols ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



168
169
170
171
 
# File 'lib/ibex/normalize.rb', line 168

def intern_reserved_symbols
  intern("$eof", :terminal, reserved: true)
  intern("error", :terminal, reserved: true)
end

#intern_user_nonterminal(rule) ⇒ void

This method returns an undefined value.

RBS:

  • (Frontend::AST::Rule rule) -> void

Parameters:



209
210
211
212
213
214
215
216
217
 
# File 'lib/ibex/normalize.rb', line 209

def intern_user_nonterminal(rule)
  definition = intern(
    rule.lhs, :nonterminal, location: rule.loc.to_h, documentation: @rule_documentation[rule.lhs]
  )
  return unless rule.inline

  @inline_symbol_ids << definition.id
  @inline_rule_by_symbol[definition.id] = rule.lhs
end

#intern_user_nonterminals ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



180
181
182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/ibex/normalize.rb', line 180

def intern_user_nonterminals
  @ast.rules.reject { |rule| parameterized_rule?(rule) }.each do |rule|
    intern_user_nonterminal(rule)
  end
  @start_names = normalized_start_names
  fail_at(@ast.loc, "grammar has no start rule") if @start_names.empty?
  @start_name = @start_names.fetch(0)
  @start_names.each do |name|
    next if symbol(name)&.nonterminal?

    fail_at(@start_location || @ast.loc, "undefined start symbol #{name}")
  end
end

#nonterminal_name?(name) ⇒ Boolean

RBS:

  • (String name) -> bool

Parameters:

  • name (String)

Returns:

  • (Boolean) 


278
279
280
 
# File 'lib/ibex/normalize.rb', line 278

def nonterminal_name?(name)
  name.match?(/\A[a-z_]/) && name != "error"
end

#normalize ⇒ IR::Grammar

RBS:

  • () -> IR::Grammar

Returns:



127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
# File 'lib/ibex/normalize.rb', line 127

def normalize
  read_declarations
  gather_parameter_templates
  gather_inline_rules
  intern_reserved_symbols
  intern_declared_terminals
  intern_user_nonterminals
  normalize_user_productions
  expand_inline_rules
  validate_value_printers
  validate_recovery_declarations
  validate_grammar
  IR::Grammar.new(class_name: @ast.class_name, superclass: @ast.superclass, start: @start_name,
                  expect: @expected_conflicts, options: @options, symbols: @symbols,
                  mode: @mode, starts: @start_names,
                  expect_rr: @expected_rr_conflicts,
                  parser_parameters: @parser_parameters,
                  value_printers: @value_printers.values,
                  grammar_tests: @grammar_tests,
                  lexer: normalize_lexer,
                  recovery: {
                    sync_tokens: @recovery_sync_tokens,
                    on_error_reduce: @on_error_reduce_groups
                  },
                  productions: @productions, user_code: normalized_user_code,
                  conversions: @conversions, warnings: @warnings, user_code_chunks: normalized_user_code_chunks,
                  source_provenance: {
                    file: @ast.loc.file, root: @resolution&.root_directory, byte_span: nil
                  })
end

#normalized_start_names ⇒ Array[String]

RBS:

  • () -> Array[String]

Returns:

  • (Array[String]) 


195
196
197
198
199
200
201
 
# File 'lib/ibex/normalize.rb', line 195

def normalized_start_names
  explicit = @explicit_starts
  return explicit if explicit

  candidate = @ast.rules.find { |rule| start_rule_candidate?(rule) }&.lhs
  candidate ? [candidate] : []
end

#normalized_user_code ⇒ Hash[String, String]

RBS:

  • () -> Hash[String, String]

Returns:

  • (Hash[String, String]) 


295
296
297
298
299
 
# File 'lib/ibex/normalize.rb', line 295

def normalized_user_code
  %w[header inner footer].to_h do |name|
    [name, @ast.user_code.fetch(name, Array.new(0)).map(&:code).join]
  end
end

#normalized_user_code_chunks ⇒ IR::user_code_chunks

RBS:

  • () -> IR::user_code_chunks

Returns:

  • (IR::user_code_chunks) 


302
303
304
305
306
307
308
309
310
311
 
# File 'lib/ibex/normalize.rb', line 302

def normalized_user_code_chunks
  chunks_by_name = %w[header inner footer].to_h do |name|
    chunks = @ast.user_code.fetch(name, Array.new(0)).map do |block|
      location = block.loc.to_h.merge(line: block.loc.line + 1, column: 1)
      IR::UserCodeChunk.new(code: block.code, location: location)
    end
    [name, chunks]
  end
  chunks_by_name.reject { |_name, chunks| chunks.empty? }
end

#required_symbol(name) ⇒ IR::GrammarSymbol

RBS:

  • (String name) -> IR::GrammarSymbol

Parameters:

  • name (String)

Returns:



260
261
262
 
# File 'lib/ibex/normalize.rb', line 260

def required_symbol(name)
  symbol(name) || raise(Ibex::Error, "missing normalized symbol #{name}")
end

#resolved_expansion ⇒ IR::production_expansion?

RBS:

  • () -> IR::production_expansion?

Returns:

  • (IR::production_expansion, nil) 


325
326
327
328
329
 
# File 'lib/ibex/normalize.rb', line 325

def resolved_expansion
  return unless @resolution || @current_parameter_expansion

  { parameter: @current_parameter_expansion, inline: nil, include_chain: @current_include_chain }
end

#start_rule_candidate?(rule) ⇒ Boolean

RBS:

  • (Frontend::AST::Rule rule) -> bool

Parameters:

Returns:

  • (Boolean) 


204
205
206
 
# File 'lib/ibex/normalize.rb', line 204

def start_rule_candidate?(rule)
  !parameterized_rule?(rule) && !rule.inline
end

#symbol(name) ⇒ IR::GrammarSymbol?

RBS:

  • (String name) -> IR::GrammarSymbol?

Parameters:

  • name (String)

Returns:



255
256
257
 
# File 'lib/ibex/normalize.rb', line 255

def symbol(name)
  @symbols_by_name[name]
end

#symbol_for_reference(reference) ⇒ IR::GrammarSymbol

RBS:

  • (Frontend::AST::SymbolReference reference) -> IR::GrammarSymbol

Parameters:

Returns:



265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/ibex/normalize.rb', line 265

def symbol_for_reference(reference)
  existing = symbol(reference.name)
  return existing if existing

  fail_at(reference.loc, "parameterized rule #{reference.name} requires arguments") if
    parameter_template?(reference.name)
  return undefined_nonterminal(reference) if nonterminal_name?(reference.name)

  warn_undeclared_terminal(reference)
  intern(reference.name, :terminal, location: reference.loc.to_h)
end

#undefined_nonterminal(reference) ⇒ bot

RBS:

  • (Frontend::AST::SymbolReference reference) -> bot

Parameters:

Returns:

  • (bot) 


283
284
285
 
# File 'lib/ibex/normalize.rb', line 283

def undefined_nonterminal(reference)
  fail_at(reference.loc, "undefined nonterminal #{reference.name}")
end

#validate_positive_limit!(name, value) ⇒ void

This method returns an undefined value.

RBS:

  • (Symbol name, untyped value) -> void

Parameters:

  • name (Symbol)
  • value (Object) 


161
162
163
164
165
 
# File 'lib/ibex/normalize.rb', line 161

def validate_positive_limit!(name, value)
  return if value.is_a?(Integer) && value.positive?

  raise ArgumentError, "#{name} must be a positive Integer"
end

#validated_rule_documentation ⇒ Hash[String, String]

RBS:

  • () -> Hash[String, String]

Returns:

  • (Hash[String, String]) 


220
221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'lib/ibex/normalize.rb', line 220

def validated_rule_documentation
  documentation = {} #: Hash[String, String]
  @ast.rules.each do |rule|
    text = rule.documentation
    next unless text

    existing = documentation[rule.lhs]
    fail_at(rule.loc, "conflicting documentation for rule #{rule.lhs}") if existing && existing != text

    documentation[rule.lhs] ||= text
  end
  documentation
end

#warn_undeclared_terminal(reference) ⇒ void

This method returns an undefined value.

RBS:

  • (Frontend::AST::SymbolReference reference) -> void

Parameters:



288
289
290
291
292
 
# File 'lib/ibex/normalize.rb', line 288

def warn_undeclared_terminal(reference)
  return if @declared_tokens.empty? || reference.name.start_with?("'", '"')

  @warnings << { type: :undeclared_terminal, symbol: reference.name, loc: reference.loc.to_h }
end