Class: Ibex::Normalizer

Inherits:
Object
  • Object
show all
Includes:
NormalizeDeclarations, NormalizeDiagnostics, NormalizeExpander, NormalizeGrammarBuilder, NormalizeInlineExpansion, NormalizeInlineValidation, NormalizeLexer, NormalizeNamedReferences, NormalizeNodes, NormalizeParameterEbnfLowering, NormalizeParameterLowering, NormalizeParameterSubstitution, NormalizeParameterValidation, NormalizeParameters, NormalizeParserConfiguration, 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 NormalizeGrammarBuilder

#build_grammar

Methods included from NormalizeParserConfiguration

#normalized_parser_contract, #parser_setting_location, #read_parser_configuration, #validate_isolated_entries, #validated_parser_setting_definition

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:



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
125
126
127
128
129
 
# File 'lib/ibex/normalize.rb', line 99

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[NormalizeParameters::parameter_frame]
  @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) 


304
305
306
 
# File 'lib/ibex/normalize.rb', line 304

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) 


309
310
311
312
 
# File 'lib/ibex/normalize.rb', line 309

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:



226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
# File 'lib/ibex/normalize.rb', line 226

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



164
165
166
167
 
# File 'lib/ibex/normalize.rb', line 164

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



158
159
160
161
 
# File 'lib/ibex/normalize.rb', line 158

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:



199
200
201
202
203
204
205
206
207
 
# File 'lib/ibex/normalize.rb', line 199

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



170
171
172
173
174
175
176
177
178
179
180
181
182
 
# File 'lib/ibex/normalize.rb', line 170

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) 


268
269
270
 
# File 'lib/ibex/normalize.rb', line 268

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

#normalize ⇒ IR::Grammar

RBS:

  • () -> IR::Grammar

Returns:



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/ibex/normalize.rb', line 132

def normalize
  read_declarations
  gather_parameter_templates
  gather_inline_rules
  intern_reserved_symbols
  intern_declared_terminals
  intern_user_nonterminals
  parser_contract = normalized_parser_contract
  normalize_user_productions
  expand_inline_rules
  validate_value_printers
  validate_recovery_declarations
  validate_grammar
  build_grammar(parser_contract)
end

#normalized_start_names ⇒ Array[String]

RBS:

  • () -> Array[String]

Returns:

  • (Array[String]) 


185
186
187
188
189
190
191
 
# File 'lib/ibex/normalize.rb', line 185

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]) 


285
286
287
288
289
 
# File 'lib/ibex/normalize.rb', line 285

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) 


292
293
294
295
296
297
298
299
300
301
 
# File 'lib/ibex/normalize.rb', line 292

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:



250
251
252
 
# File 'lib/ibex/normalize.rb', line 250

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) 


315
316
317
318
319
 
# File 'lib/ibex/normalize.rb', line 315

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) 


194
195
196
 
# File 'lib/ibex/normalize.rb', line 194

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

#symbol(name) ⇒ IR::GrammarSymbol?

RBS:

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

Parameters:

  • name (String)

Returns:



245
246
247
 
# File 'lib/ibex/normalize.rb', line 245

def symbol(name)
  @symbols_by_name[name]
end

#symbol_for_reference(reference) ⇒ IR::GrammarSymbol

RBS:

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

Parameters:

Returns:



255
256
257
258
259
260
261
262
263
264
265
 
# File 'lib/ibex/normalize.rb', line 255

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) 


273
274
275
 
# File 'lib/ibex/normalize.rb', line 273

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, Object value) -> void

Parameters:

  • name (Symbol)
  • value (Object) 


151
152
153
154
155
 
# File 'lib/ibex/normalize.rb', line 151

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]) 


210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/ibex/normalize.rb', line 210

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:



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

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