Class: LL::GrammarCompiler
- Inherits:
-
Object
- Object
- LL::GrammarCompiler
- Defined in:
- lib/ll/grammar_compiler.rb
Overview
The GrammarCompiler class processes an AST (as parsed from an LL(1) grammar) and returns an CompiledGrammar instance.
Instance Method Summary (collapse)
-
- (LL::CompiledGrammar) compile(ast)
-
- (Array) lookup_identifiers(node, compiled_grammar)
private
-
- (LL::Branch) on_branch(node, compiled_grammar)
Processes a single rule branch.
-
- (LL::Epsilon) on_epsilon(node, compiled_grammar)
Processes an epsilon.
-
- (Object) on_grammar(node, compiled_grammar)
Processes the root node of a grammar.
-
- (Object) on_header(node, compiled_grammar)
Processes a %header directive.
-
- (String) on_ident(node, compiled_grammar)
Extracts the name from an identifier.
-
- (Object) on_inner(node, compiled_grammar)
Processes an %inner directive.
-
- (Object) on_name(node, compiled_grammar)
Sets the name of the parser.
-
- (LL::Operator) on_plus(node, compiled_grammar)
Processes the “+” operator.
-
- (LL::Operator) on_question(node, compiled_grammar)
Processes the “?” operator.
-
- (String) on_ruby(node, compiled_grammar)
Processes a node containing Ruby source code.
-
- (Object) on_rule(node, compiled_grammar)
Processes the assignment of a rule.
-
- (Object) on_rule_prototype(node, compiled_grammar)
Creates a basic prototype for a rule.
-
- (LL::Operator) on_star(node, compiled_grammar)
Processes the “*” operator.
-
- (Array) on_steps(node, compiled_grammar)
Processes the steps of a branch.
-
- (Object) on_terminals(node, compiled_grammar)
Processes the assignment of terminals.
-
- (LL::CompiledGrammar) process(node, compiled_grammar)
-
- (Object) undefined_identifier!(name, node, compiled_grammar)
private
-
- (Object) verify_first_first(compiled_grammar)
Verifies all rules to see if they don’t have any first/first conflicts.
-
- (Object) verify_first_follow(compiled_grammar)
Adds errors for any rules containing first/follow conflicts.
-
- (Object) warn_for_unused_rules(compiled_grammar)
Adds warnings for any unused rules.
-
- (Object) warn_for_unused_terminals(compiled_grammar)
Adds warnings for any unused terminals.
Instance Method Details
- (LL::CompiledGrammar) compile(ast)
11 12 13 14 15 16 17 18 19 20 21 22 23 |
# File 'lib/ll/grammar_compiler.rb', line 11 def compile(ast) compiled = CompiledGrammar.new process(ast, compiled) warn_for_unused_terminals(compiled) warn_for_unused_rules(compiled) verify_first_first(compiled) verify_first_follow(compiled) return compiled end |
- (Array) lookup_identifiers(node, compiled_grammar) (private)
404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 |
# File 'lib/ll/grammar_compiler.rb', line 404 def lookup_identifiers(node, compiled_grammar) idents = [] node.children.each do |ident_node| retval = process(ident_node, compiled_grammar) # Literal rule/terminal names. if retval.is_a?(String) ident = compiled_grammar.lookup_identifier(retval) undefined_identifier!(retval, ident_node, compiled_grammar) if !ident # Epsilon else ident = retval end if ident ident.increment_references if ident.respond_to?(:increment_references) idents << ident end end return idents end |
- (LL::Branch) on_branch(node, compiled_grammar)
Processes a single rule branch.
301 302 303 304 305 306 307 308 309 310 311 |
# File 'lib/ll/grammar_compiler.rb', line 301 def on_branch(node, compiled_grammar) steps = process(node.children[0], compiled_grammar) if node.children[1] code = process(node.children[1], compiled_grammar) else code = nil end return Branch.new(steps, node.source_line, code) end |
- (LL::Epsilon) on_epsilon(node, compiled_grammar)
Processes an epsilon.
243 244 245 |
# File 'lib/ll/grammar_compiler.rb', line 243 def on_epsilon(node, compiled_grammar) return Epsilon.new(node.source_line) end |
- (Object) on_grammar(node, compiled_grammar)
Processes the root node of a grammar.
146 147 148 149 150 151 152 153 154 155 156 157 158 |
# File 'lib/ll/grammar_compiler.rb', line 146 def on_grammar(node, compiled_grammar) # Create the prototypes for all rules since rules can be referenced before # they are defined. node.children.each do |child| if child.type == :rule on_rule_prototype(child, compiled_grammar) end end node.children.each do |child| process(child, compiled_grammar) end end |
- (Object) on_header(node, compiled_grammar)
Processes a %header directive.
213 214 215 |
# File 'lib/ll/grammar_compiler.rb', line 213 def on_header(node, compiled_grammar) compiled_grammar.header = process(node.children[0], compiled_grammar) end |
- (String) on_ident(node, compiled_grammar)
Extracts the name from an identifier.
233 234 235 |
# File 'lib/ll/grammar_compiler.rb', line 233 def on_ident(node, compiled_grammar) return node.children[0] end |
- (Object) on_inner(node, compiled_grammar)
Processes an %inner directive.
204 205 206 |
# File 'lib/ll/grammar_compiler.rb', line 204 def on_inner(node, compiled_grammar) compiled_grammar.inner = process(node.children[0], compiled_grammar) end |
- (Object) on_name(node, compiled_grammar)
Sets the name of the parser.
166 167 168 169 170 171 172 173 174 175 176 177 |
# File 'lib/ll/grammar_compiler.rb', line 166 def on_name(node, compiled_grammar) if compiled_grammar.name compiled_grammar.add_warning( "Overwriting existing parser name #{compiled_grammar.name.inspect}", node.source_line ) end parts = node.children.map { |child| process(child, compiled_grammar) } compiled_grammar.name = parts.join('::') end |
- (LL::Operator) on_plus(node, compiled_grammar)
Processes the “+” operator.
351 352 353 354 355 356 357 358 359 360 361 362 363 |
# File 'lib/ll/grammar_compiler.rb', line 351 def on_plus(node, compiled_grammar) steps = lookup_identifiers(node, compiled_grammar) name = "_ll_plus#{node.source_line.line}#{node.source_line.column}" rule = Rule.new(name, node.source_line) rule.add_branch(steps, node.source_line) rule.increment_references compiled_grammar.add_rule(rule) return Operator.new(:plus, rule, node.source_line) end |
- (LL::Operator) on_question(node, compiled_grammar)
Processes the “?” operator.
372 373 374 375 376 377 378 379 380 381 382 383 384 |
# File 'lib/ll/grammar_compiler.rb', line 372 def on_question(node, compiled_grammar) steps = lookup_identifiers(node, compiled_grammar) name = "_ll_question#{node.source_line.line}#{node.source_line.column}" rule = Rule.new(name, node.source_line) rule.add_branch(steps, node.source_line) rule.increment_references compiled_grammar.add_rule(rule) return Operator.new(:question, rule, node.source_line) end |
- (String) on_ruby(node, compiled_grammar)
Processes a node containing Ruby source code.
223 224 225 |
# File 'lib/ll/grammar_compiler.rb', line 223 def on_ruby(node, compiled_grammar) return node.children[0] end |
- (Object) on_rule(node, compiled_grammar)
Processes the assignment of a rule.
252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 |
# File 'lib/ll/grammar_compiler.rb', line 252 def on_rule(node, compiled_grammar) name = process(node.children[0], compiled_grammar) if compiled_grammar.has_terminal?(name) compiled_grammar.add_error( "the rule name #{name.inspect} is already used as a terminal name", node.source_line ) end if compiled_grammar.has_rule_with_branches?(name) compiled_grammar.add_error( "the rule #{name.inspect} has already been defined", node.source_line ) return end branches = node.children[1..-1].map do |child| process(child, compiled_grammar) end rule = compiled_grammar.lookup_rule(name) rule.branches.concat(branches) end |
- (Object) on_rule_prototype(node, compiled_grammar)
Creates a basic prototype for a rule.
285 286 287 288 289 290 291 292 293 |
# File 'lib/ll/grammar_compiler.rb', line 285 def on_rule_prototype(node, compiled_grammar) name = process(node.children[0], compiled_grammar) return if compiled_grammar.has_rule?(name) rule = Rule.new(name, node.source_line) compiled_grammar.add_rule(rule) end |
- (LL::Operator) on_star(node, compiled_grammar)
Processes the “*” operator.
330 331 332 333 334 335 336 337 338 339 340 341 342 |
# File 'lib/ll/grammar_compiler.rb', line 330 def on_star(node, compiled_grammar) steps = lookup_identifiers(node, compiled_grammar) name = "_ll_star#{node.source_line.line}#{node.source_line.column}" rule = Rule.new(name, node.source_line) rule.add_branch(steps, node.source_line) rule.increment_references compiled_grammar.add_rule(rule) return Operator.new(:star, rule, node.source_line) end |
- (Array) on_steps(node, compiled_grammar)
Processes the steps of a branch.
319 320 321 |
# File 'lib/ll/grammar_compiler.rb', line 319 def on_steps(node, compiled_grammar) return lookup_identifiers(node, compiled_grammar) end |
- (Object) on_terminals(node, compiled_grammar)
Processes the assignment of terminals.
184 185 186 187 188 189 190 191 192 193 194 195 196 197 |
# File 'lib/ll/grammar_compiler.rb', line 184 def on_terminals(node, compiled_grammar) node.children.each do |child| name = process(child, compiled_grammar) if compiled_grammar.has_terminal?(name) compiled_grammar.add_error( "The terminal #{name.inspect} has already been defined", child.source_line ) else compiled_grammar.add_terminal(name, child.source_line) end end end |
- (LL::CompiledGrammar) process(node, compiled_grammar)
30 31 32 33 34 |
# File 'lib/ll/grammar_compiler.rb', line 30 def process(node, compiled_grammar) handler = "on_#{node.type}" return send(handler, node, compiled_grammar) end |
- (Object) undefined_identifier!(name, node, compiled_grammar) (private)
393 394 395 396 397 398 |
# File 'lib/ll/grammar_compiler.rb', line 393 def undefined_identifier!(name, node, compiled_grammar) compiled_grammar.add_error( "Undefined terminal or rule #{name.inspect}", node.source_line ) end |
- (Object) verify_first_first(compiled_grammar)
Verifies all rules to see if they don’t have any first/first conflicts. Errors are added for every rule where this is the case.
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 104 105 106 107 108 109 110 111 112 |
# File 'lib/ll/grammar_compiler.rb', line 75 def verify_first_first(compiled_grammar) compiled_grammar.rules.each do |rule| conflicting = Set.new rule.branches.each do |branch| next if conflicting.include?(branch) rule.branches.each do |other_branch| next if branch == other_branch || conflicting.include?(other_branch) overlapping = branch.first_set & other_branch.first_set unless overlapping.empty? conflicting << branch conflicting << other_branch end end end unless conflicting.empty? compiled_grammar.add_error( 'first/first conflict, multiple branches start with the same terminals', rule.source_line ) conflicting.each do |branch| labels = branch.first_set.map do |token| token.is_a?(Epsilon) ? 'epsilon' : token.name end compiled_grammar.add_error( "branch starts with: #{labels.join(', ')}", branch.source_line ) end end end end |
- (Object) verify_first_follow(compiled_grammar)
Adds errors for any rules containing first/follow conflicts.
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
# File 'lib/ll/grammar_compiler.rb', line 119 def verify_first_follow(compiled_grammar) compiled_grammar.rules.each do |rule| rule.branches.each do |branch| has_epsilon = branch.first_set.find { |step| step.is_a?(Epsilon) } if has_epsilon and !branch.follow_set.empty? compiled_grammar.add_error( 'first/follow conflict, branch can start with epsilon and is ' \ 'followed by (non) terminals', branch.source_line ) compiled_grammar.add_error( 'epsilon originates from here', has_epsilon.source_line ) end end end end |
- (Object) warn_for_unused_rules(compiled_grammar)
Adds warnings for any unused rules. The first defined rule is skipped since it’s the root rule.
42 43 44 45 46 47 48 49 50 51 |
# File 'lib/ll/grammar_compiler.rb', line 42 def warn_for_unused_rules(compiled_grammar) compiled_grammar.rules.each_with_index do |rule, index| next if index == 0 || rule.references > 0 compiled_grammar.add_warning( "Unused rule #{rule.name.inspect}", rule.source_line ) end end |
- (Object) warn_for_unused_terminals(compiled_grammar)
Adds warnings for any unused terminals.
58 59 60 61 62 63 64 65 66 67 |
# File 'lib/ll/grammar_compiler.rb', line 58 def warn_for_unused_terminals(compiled_grammar) compiled_grammar.terminals.each do |terminal| next if terminal.references > 0 compiled_grammar.add_warning( "Unused terminal #{terminal.name.inspect}", terminal.source_line ) end end |