Class: Ibex::BisonImport::Importer
- Inherits:
-
Object
- Object
- Ibex::BisonImport::Importer
- Defined in:
- lib/ibex/bison_import/importer.rb,
sig/ibex/bison_import/importer.rbs
Overview
Converts Bison declarations and productions into analysis-only Ibex source without parsing or executing C. rubocop:disable Metrics/ClassLength -- declaration and rule recovery share one positioned directive report.
Constant Summary collapse
- DEFAULT_MAX_BYTES =
20 * 1024 * 1024
- DEFAULT_MAX_TOKENS =
1_000_000- DEFAULT_MAX_RULES =
50_000- DEFAULT_MAX_ACTIONS =
100_000
Instance Method Summary collapse
- #bounds ⇒ Hash[Symbol, Integer]
- #check_action_budget(count, token) ⇒ void
- #check_rule_budget(count) ⇒ void
- #consume_rule_directive(tokens, cursor, alternative) ⇒ Integer
- #declaration_atoms(detail) ⇒ Array[String]
- #declaration_chunks(source) ⇒ Array[{ name: String, detail: String, line: Integer, column: Integer }]
- #first_integer(value) ⇒ Integer?
- #identifier_atom?(value) ⇒ Boolean
-
#initialize(source, file:, class_name: nil, max_bytes: DEFAULT_MAX_BYTES, max_tokens: DEFAULT_MAX_TOKENS, max_rules: DEFAULT_MAX_RULES, max_actions: DEFAULT_MAX_ACTIONS) ⇒ Importer
constructor
A new instance of Importer.
-
#lhs_definition_at(tokens, cursor) ⇒ [ Integer, Integer ]?
Bison permits a named reference between an LHS and its colon:
expression[result]: .... - #literal_atom?(value) ⇒ Boolean
- #next_lhs(tokens, cursor) ⇒ [ Integer, Integer ]?
-
#nonterminal_name(value) ⇒ String
All imported nonterminals receive a lowercase namespace.
- #parse_alternatives(tokens, cursor) ⇒ [ Array[alternative], Integer ]
- #parse_declarations(source) ⇒ void
- #parse_precedence(association, detail) ⇒ void
- #parse_rules(tokens) ⇒ Array[rule]
- #parse_start(detail) ⇒ void
- #parse_token_declaration(detail) ⇒ void
- #positive_limit(value, name) ⇒ Integer
- #record_directive(name, line, column, detail) ⇒ void
- #register_nonterminals(tokens) ⇒ void
- #render_action(token) ⇒ String
- #render_precedence(lines) ⇒ void
- #render_rule(lines, rule) ⇒ void
- #render_source(rules) ⇒ String
- #render_symbol(token) ⇒ String
- #resolved_class_name ⇒ String
- #run ⇒ Result
- #sanitize_class_name(value) ⇒ String
- #sanitize_symbol(value) ⇒ String
- #split_sections ⇒ [ String, String, Integer ]
- #strip_declaration_comments(source) ⇒ String
- #structural_status ⇒ String
- #terminal_name(value) ⇒ String
- #transform_action(code) ⇒ String
- #validate_source ⇒ void
Constructor Details
#initialize(source, file:, class_name: nil, max_bytes: DEFAULT_MAX_BYTES, max_tokens: DEFAULT_MAX_TOKENS, max_rules: DEFAULT_MAX_RULES, max_actions: DEFAULT_MAX_ACTIONS) ⇒ Importer
Returns a new instance of Importer.
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# File 'lib/ibex/bison_import/importer.rb', line 21 def initialize(source, file:, class_name: nil, max_bytes: DEFAULT_MAX_BYTES, max_tokens: DEFAULT_MAX_TOKENS, max_rules: DEFAULT_MAX_RULES, max_actions: DEFAULT_MAX_ACTIONS) @source = source @file = file @class_name = class_name @max_bytes = positive_limit(max_bytes, :max_bytes) @max_tokens = positive_limit(max_tokens, :max_tokens) @max_rules = positive_limit(max_rules, :max_rules) @max_actions = positive_limit(max_actions, :max_actions) @directives = [] #: Array[Directive] @actions = [] #: Array[Action] @token_entries = [] #: Array[[String, String?]] @terminal_names = {} #: Hash[String, String] @nonterminal_names = {} #: Hash[String, String] @precedence_levels = [] #: Array[[String, Array[String]]] @starts = [] #: Array[String] @expected_sr = nil #: Integer? @expected_rr = nil #: Integer? end |
Instance Method Details
#bounds ⇒ Hash[Symbol, Integer]
507 508 509 510 511 512 |
# File 'lib/ibex/bison_import/importer.rb', line 507 def bounds { max_bytes: @max_bytes, max_tokens: @max_tokens, max_rules: @max_rules, max_actions: @max_actions } end |
#check_action_budget(count, token) ⇒ void
This method returns an undefined value.
490 491 492 493 494 495 496 497 |
# File 'lib/ibex/bison_import/importer.rb', line 490 def check_action_budget(count, token) return if count <= @max_actions raise BudgetExceeded.new( result: "budget_exhausted", phase: "actions", line: token.line, observed_actions: count, max_actions: @max_actions ) end |
#check_rule_budget(count) ⇒ void
This method returns an undefined value.
480 481 482 483 484 485 486 487 |
# File 'lib/ibex/bison_import/importer.rb', line 480 def check_rule_budget(count) return if count <= @max_rules raise BudgetExceeded.new( result: "budget_exhausted", phase: "rules", observed_rules: count, max_rules: @max_rules ) end |
#consume_rule_directive(tokens, cursor, alternative) ⇒ Integer
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 |
# File 'lib/ibex/bison_import/importer.rb', line 256 def consume_rule_directive(tokens, cursor, alternative) token = tokens.fetch(cursor) name = token.value.delete_prefix("%") record_directive(name, token.line, token.column, token.value) return cursor if name == "empty" if name == "prec" following = tokens[cursor + 1] if following && %i[symbol literal].include?(following.type) alternative[:precedence] = following.type == :literal ? following.value : terminal_name(following.value) return cursor + 1 end raise Ibex::Error, "#{@file}:#{token.line}:#{token.column}: %prec requires a symbol" end return cursor + 1 if %w[dprec merge].include?(name) && tokens[cursor + 1] cursor end |
#declaration_atoms(detail) ⇒ Array[String]
382 383 384 385 386 387 388 |
# File 'lib/ibex/bison_import/importer.rb', line 382 def declaration_atoms(detail) source = strip_declaration_comments(detail) source = source.gsub(/\b[A-Z][A-Z0-9_]*\([^()\n]*\)/, " ") source.scan( /<[^>]*>|"(?:\\.|[^"])*"|'(?:\\.|[^'])*'|[A-Za-z_$][A-Za-z0-9_$.-]*|\d+/ ).map(&:to_s) end |
#declaration_chunks(source) ⇒ Array[{ name: String, detail: String, line: Integer, column: Integer }]
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
# File 'lib/ibex/bison_import/importer.rb', line 111 def declaration_chunks(source) chunks = [] #: Array[{ name: String, detail: String, line: Integer, column: Integer }] current = nil #: { name: String, detail: String, line: Integer, column: Integer }? in_percent_code = false source.lines.each_with_index do |line, index| if line.match?(/^\s*%\{/) in_percent_code = true next end if in_percent_code in_percent_code = false if line.match?(/%\}\s*$/) next end match = line.match(/^(\s*)%([A-Za-z][A-Za-z0-9_-]*)(.*)$/) if match chunks << current if current current = { name: match[2].to_s, detail: match[3].to_s, line: index + 1, column: match[1].to_s.bytesize + 1 } elsif current current[:detail] = "#{current.fetch(:detail)}\n#{line}" end end chunks << current if current chunks end |
#first_integer(value) ⇒ Integer?
474 475 476 477 |
# File 'lib/ibex/bison_import/importer.rb', line 474 def first_integer(value) match = value.match(/\d+/) match ? Integer(match[0], 10) : nil end |
#identifier_atom?(value) ⇒ Boolean
399 400 401 |
# File 'lib/ibex/bison_import/importer.rb', line 399 def identifier_atom?(value) value.match?(/\A[A-Za-z_$][A-Za-z0-9_$.-]*\z/) end |
#lhs_definition_at(tokens, cursor) ⇒ [ Integer, Integer ]?
Bison permits a named reference between an LHS and its colon:
expression[result]: ....
216 217 218 219 220 221 222 |
# File 'lib/ibex/bison_import/importer.rb', line 216 def lhs_definition_at(tokens, cursor) return unless tokens[cursor]&.type == :symbol colon = cursor + 1 colon += 1 while tokens[colon]&.type == :tag [cursor, colon] if tokens[colon]&.type == :colon end |
#literal_atom?(value) ⇒ Boolean
404 405 406 |
# File 'lib/ibex/bison_import/importer.rb', line 404 def literal_atom?(value) value.start_with?('"', "'") end |
#next_lhs(tokens, cursor) ⇒ [ Integer, Integer ]?
204 205 206 207 208 209 210 211 |
# File 'lib/ibex/bison_import/importer.rb', line 204 def next_lhs(tokens, cursor) while cursor < tokens.length definition = lhs_definition_at(tokens, cursor) return definition if definition cursor += 1 end end |
#nonterminal_name(value) ⇒ String
All imported nonterminals receive a lowercase namespace. This avoids Ibex's terminal-by-case convention and declaration keyword collisions.
441 442 443 444 445 446 447 448 449 450 451 452 453 454 |
# File 'lib/ibex/bison_import/importer.rb', line 441 def nonterminal_name(value) nonterminal_names = @nonterminal_names #: Hash[String, String] nonterminal_names[value] ||= begin base = "bison_nt_#{sanitize_symbol(value).downcase}" used = nonterminal_names.values candidate = base suffix = 2 while used.include?(candidate) candidate = "#{base}_#{suffix}" suffix += 1 end candidate end end |
#parse_alternatives(tokens, cursor) ⇒ [ Array[alternative], Integer ]
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 |
# File 'lib/ibex/bison_import/importer.rb', line 225 def parse_alternatives(tokens, cursor) alternatives = [] #: Array[alternative] current = { items: [], precedence: nil } #: alternative while cursor < tokens.length token = tokens.fetch(cursor) if lhs_definition_at(tokens, cursor) alternatives << current return [alternatives, cursor] end case token.type when :pipe alternatives << current current = { items: [], precedence: nil } when :semicolon alternatives << current return [alternatives, cursor + 1] when :symbol, :literal current.fetch(:items) << render_symbol(token) when :action current.fetch(:items) << render_action(token) when :directive cursor = consume_rule_directive(tokens, cursor, current) end cursor += 1 end alternatives << current [alternatives, cursor] end |
#parse_declarations(source) ⇒ void
This method returns an undefined value.
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
# File 'lib/ibex/bison_import/importer.rb', line 94 def parse_declarations(source) chunks = declaration_chunks(source) chunks.each do |chunk| name = chunk.fetch(:name) detail = chunk.fetch(:detail) record_directive(name, chunk.fetch(:line), chunk.fetch(:column), detail) case name when "token" then parse_token_declaration(detail) when "left", "right", "nonassoc", "precedence" then parse_precedence(name, detail) when "start" then parse_start(detail) when "expect" then @expected_sr = first_integer(detail) when "expect-rr" then @expected_rr = first_integer(detail) end end end |
#parse_precedence(association, detail) ⇒ void
This method returns an undefined value.
160 161 162 163 164 |
# File 'lib/ibex/bison_import/importer.rb', line 160 def parse_precedence(association, detail) symbols = declaration_atoms(detail).select { |atom| identifier_atom?(atom) || literal_atom?(atom) } precedence_levels = @precedence_levels #: Array[[String, Array[String]]] precedence_levels << [association == "precedence" ? "%precedence" : association, symbols] unless symbols.empty? end |
#parse_rules(tokens) ⇒ Array[rule]
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 |
# File 'lib/ibex/bison_import/importer.rb', line 174 def parse_rules(tokens) rules = [] #: Array[rule] cursor = 0 while cursor < tokens.length definition = next_lhs(tokens, cursor) break unless definition lhs_index, colon_index = definition lhs = nonterminal_name(tokens.fetch(lhs_index).value) cursor = colon_index + 1 alternatives, cursor = parse_alternatives(tokens, cursor) rules << { lhs: lhs, alternatives: alternatives } check_rule_budget(rules.length) end raise Ibex::Error, "#{@file}:1:1: Bison grammar section contains no productions" if rules.empty? rules end |
#parse_start(detail) ⇒ void
This method returns an undefined value.
167 168 169 170 171 |
# File 'lib/ibex/bison_import/importer.rb', line 167 def parse_start(detail) symbol = declaration_atoms(detail).find { |atom| identifier_atom?(atom) } starts = @starts #: Array[String] starts << symbol if symbol end |
#parse_token_declaration(detail) ⇒ void
This method returns an undefined value.
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
# File 'lib/ibex/bison_import/importer.rb', line 143 def parse_token_declaration(detail) token_entries = @token_entries #: Array[[String, String?]] current = nil #: String? declaration_atoms(detail).each do |atom| if identifier_atom?(atom) token_entries << [current, nil] if current current = atom terminal_name(atom) elsif current && atom.start_with?('"') token_entries << [current, atom] current = nil end end token_entries << [current, nil] if current end |
#positive_limit(value, name) ⇒ Integer
500 501 502 503 504 |
# File 'lib/ibex/bison_import/importer.rb', line 500 def positive_limit(value, name) return value if value.positive? raise ArgumentError, "#{name} must be positive" end |
#record_directive(name, line, column, detail) ⇒ void
This method returns an undefined value.
373 374 375 376 377 378 379 |
# File 'lib/ibex/bison_import/importer.rb', line 373 def record_directive(name, line, column, detail) status = DIRECTIVES.fetch(name, :unsupported) directives = @directives #: Array[Directive] directives << Directive.new( name: name, status: status, line: line, column: column, detail: detail.strip ) end |
#register_nonterminals(tokens) ⇒ void
This method returns an undefined value.
194 195 196 197 198 199 200 201 |
# File 'lib/ibex/bison_import/importer.rb', line 194 def register_nonterminals(tokens) cursor = 0 while (definition = next_lhs(tokens, cursor)) lhs_index, colon_index = definition nonterminal_name(tokens.fetch(lhs_index).value) cursor = colon_index + 1 end end |
#render_action(token) ⇒ String
286 287 288 289 290 291 292 293 294 295 296 297 |
# File 'lib/ibex/bison_import/importer.rb', line 286 def render_action(token) actions = @actions #: Array[Action] check_action_budget(actions.length + 1, token) transformed = transform_action(token.value) encoded = transformed.unpack1("H*").to_s action = Action.new( id: actions.length + 1, line: token.line, column: token.column, original: token.value, transformed: transformed, encoded: encoded ) actions << action "{ #{FOREIGN_ACTION_SENTINEL}(#{encoded.inspect}) }" end |
#render_precedence(lines) ⇒ void
This method returns an undefined value.
349 350 351 352 353 354 355 356 357 358 359 |
# File 'lib/ibex/bison_import/importer.rb', line 349 def render_precedence(lines) precedence_levels = @precedence_levels #: Array[[String, Array[String]]] return if precedence_levels.empty? lines << "preclow" precedence_levels.each do |association, symbols| rendered = symbols.map { |symbol| literal_atom?(symbol) ? symbol : terminal_name(symbol) } lines << " #{association} #{rendered.join(' ')}" end lines << "prechigh" end |
#render_rule(lines, rule) ⇒ void
This method returns an undefined value.
362 363 364 365 366 367 368 369 370 |
# File 'lib/ibex/bison_import/importer.rb', line 362 def render_rule(lines, rule) alternatives = rule.fetch(:alternatives) alternatives.each_with_index do |alternative, index| prefix = index.zero? ? "#{rule.fetch(:lhs)}:" : " |" items = alternative.fetch(:items) suffix = alternative[:precedence] ? " = #{alternative.fetch(:precedence)}" : "" lines << "#{prefix} #{items.join(' ')}#{suffix}".rstrip end end |
#render_source(rules) ⇒ String
310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 |
# File 'lib/ibex/bison_import/importer.rb', line 310 def render_source(rules) directives = @directives #: Array[Directive] token_entries = @token_entries #: Array[[String, String?]] starts = @starts #: Array[String] lines = [ "# Imported from #{@file} for analysis only.", "# C actions are opaque; Ruby parser generation is intentionally refused.", "# #{STRUCTURAL_STATUS_MARKER}: #{structural_status}" ] directives.select { |directive| directive.status == :unsupported }.each do |directive| lines << "# unsupported %#{directive.name} at #{directive.line}:#{directive.column}" end lines.push("class #{resolved_class_name}", "pragma extended") token_entries.uniq.sort.each do |name, alias_name| rendered = "token #{terminal_name(name)}" rendered = "#{rendered} #{alias_name}" if alias_name lines << rendered end render_precedence(lines) lines << "expect #{@expected_sr}" if @expected_sr lines << "%expect-rr #{@expected_rr}" if @expected_rr lines << "start #{starts.uniq.map { |name| nonterminal_name(name) }.join(' ')}" unless starts.empty? lines << "rule" rules.each { |rule| render_rule(lines, rule) } lines << "end" "#{lines.join("\n")}\n" end |
#render_symbol(token) ⇒ String
278 279 280 281 282 283 |
# File 'lib/ibex/bison_import/importer.rb', line 278 def render_symbol(token) return token.value if token.type == :literal nonterminal_names = @nonterminal_names #: Hash[String, String] nonterminal_names.fetch(token.value) { terminal_name(token.value) } end |
#resolved_class_name ⇒ String
457 458 459 460 461 462 |
# File 'lib/ibex/bison_import/importer.rb', line 457 def resolved_class_name return sanitize_class_name(@class_name) if @class_name stem = File.basename(@file).sub(/\.[^.]+\z/, "") "Imported#{sanitize_class_name(stem)}Parser" end |
#run ⇒ Result
43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# File 'lib/ibex/bison_import/importer.rb', line 43 def run validate_source declarations, grammar, grammar_line = split_sections parse_declarations(declarations) tokens = Tokenizer.new(grammar, start_line: grammar_line, max_tokens: @max_tokens).tokenize register_nonterminals(tokens) rules = parse_rules(tokens) source = render_source(rules) Result.new( source: source, file: @file, class_name: resolved_class_name, directives: @directives, actions: @actions, rule_count: rules.length, bounds: bounds ) end |
#sanitize_class_name(value) ⇒ String
465 466 467 468 469 470 471 |
# File 'lib/ibex/bison_import/importer.rb', line 465 def sanitize_class_name(value) parts = value.scan(/[A-Za-z0-9]+/).map(&:to_s) rendered = parts.map { |part| part.sub(/\A./, &:upcase) }.join rendered = "Grammar" if rendered.empty? rendered = "Grammar#{rendered}" if rendered.match?(/\A\d/) rendered end |
#sanitize_symbol(value) ⇒ String
409 410 411 412 413 |
# File 'lib/ibex/bison_import/importer.rb', line 409 def sanitize_symbol(value) sanitized = value.gsub(/[^A-Za-z0-9_]/, "_") sanitized = "_#{sanitized}" if sanitized.match?(/\A\d/) sanitized.empty? ? "_bison_symbol" : sanitized end |
#split_sections ⇒ [ String, String, Integer ]
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
# File 'lib/ibex/bison_import/importer.rb', line 73 def split_sections source = @source #: String lines = source.lines markers = [] #: Array[Integer] percent_code = false lines.each_with_index do |line, index| percent_code = true if line.match?(/^\s*%\{/) markers << index if !percent_code && line.match?(%r{^\s*%%(?:\s|/|$)}) percent_code = false if percent_code && line.match?(/%\}\s*$/) break if markers.length == 2 end raise Ibex::Error, "#{@file}:1:1: expected two Bison %% section markers" if markers.length < 2 first = markers.fetch(0) second = markers.fetch(1) header_lines = lines[0...first] #: Array[String] grammar_lines = lines[(first + 1)...second] #: Array[String] [header_lines.join, grammar_lines.join, first + 2] end |
#strip_declaration_comments(source) ⇒ String
391 392 393 394 395 396 |
# File 'lib/ibex/bison_import/importer.rb', line 391 def strip_declaration_comments(source) pattern = %r{("(?:\\.|[^"])*"|'(?:\\.|[^'])*')|/\*.*?\*/|//[^\n]*|^[ \t]*\#[^\n]*}m source.gsub(pattern) do |match| match.start_with?('"', "'") ? match : " " end end |
#structural_status ⇒ String
339 340 341 342 343 344 345 346 |
# File 'lib/ibex/bison_import/importer.rb', line 339 def structural_status directives = @directives #: Array[Directive] unsupported = directives.select do |directive| directive.status == :unsupported && !STRUCTURE_NEUTRAL_UNSUPPORTED.include?(directive.name) end unsupported.empty? ? "complete" : "incomplete" end |
#terminal_name(value) ⇒ String
416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 |
# File 'lib/ibex/bison_import/importer.rb', line 416 def terminal_name(value) return "error" if value == "error" terminal_names = @terminal_names #: Hash[String, String] terminal_names[value] ||= begin sanitized = sanitize_symbol(value) base = if sanitized.match?(/\A[A-Z][A-Z0-9_]*\z/) sanitized else "BISON_T_#{sanitized.upcase}" end used = terminal_names.values candidate = base suffix = 2 while used.include?(candidate) candidate = "#{base}_#{suffix}" suffix += 1 end candidate end end |
#transform_action(code) ⇒ String
300 301 302 303 304 305 306 307 |
# File 'lib/ibex/bison_import/importer.rb', line 300 def transform_action(code) transformed = code.gsub(/\$<[^>]+>\$/, "result") transformed = transformed.gsub(/\$<[^>]+>(\d+)/) { "val[#{::Regexp.last_match(1).to_i - 1}]" } transformed = transformed.gsub("$$", "result") transformed = transformed.gsub(/\$(\d+)/) { "val[#{::Regexp.last_match(1).to_i - 1}]" } transformed = transformed.gsub(/@<[^>]+>(\d+)/, '@\1') transformed.gsub(/@\$/, "result_loc") end |
#validate_source ⇒ void
This method returns an undefined value.
61 62 63 64 65 66 67 68 69 70 |
# File 'lib/ibex/bison_import/importer.rb', line 61 def validate_source source = @source #: String if source.bytesize > @max_bytes raise BudgetExceeded.new( result: "budget_exhausted", phase: "input_bytes", observed_bytes: source.bytesize, max_bytes: @max_bytes ) end raise Ibex::Error, "#{@file}:1:1: Bison grammar must be valid UTF-8" unless source.valid_encoding? end |