class LL::GrammarCompiler

The GrammarCompiler class processes an AST (as parsed from an LL(1) grammar) and returns an {LL::CompiledGrammar} instance.

Public Instance Methods

compile(ast) click to toggle source

@param [LL::AST::Node] ast @return [LL::CompiledGrammar]

# 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
on_branch(node, compiled_grammar) click to toggle source

Processes a single rule branch.

@see [#process] @return [LL::Branch]

# 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
on_epsilon(node, compiled_grammar) click to toggle source

Processes an epsilon.

@see [#process] @return [LL::Epsilon]

# File lib/ll/grammar_compiler.rb, line 243
def on_epsilon(node, compiled_grammar)
  return Epsilon.new(node.source_line)
end
on_grammar(node, compiled_grammar) click to toggle source

Processes the root node of a grammar.

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar

# 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
on_header(node, compiled_grammar) click to toggle source

Processes a %header directive.

@see [#process]

# File lib/ll/grammar_compiler.rb, line 213
def on_header(node, compiled_grammar)
  compiled_grammar.header = process(node.children[0], compiled_grammar)
end
on_ident(node, compiled_grammar) click to toggle source

Extracts the name from an identifier.

@see [#process] @return [String]

# File lib/ll/grammar_compiler.rb, line 233
def on_ident(node, compiled_grammar)
  return node.children[0]
end
on_inner(node, compiled_grammar) click to toggle source

Processes an %inner directive.

@see [#process]

# File lib/ll/grammar_compiler.rb, line 204
def on_inner(node, compiled_grammar)
  compiled_grammar.inner = process(node.children[0], compiled_grammar)
end
on_name(node, compiled_grammar) click to toggle source

Sets the name of the parser.

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar

# 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
on_plus(node, compiled_grammar) click to toggle source

Processes the “+” operator.

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar @return [LL::Operator]

# 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
on_question(node, compiled_grammar) click to toggle source

Processes the “?” operator.

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar @return [LL::Operator]

# 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
on_ruby(node, compiled_grammar) click to toggle source

Processes a node containing Ruby source code.

@see [#process] @return [String]

# File lib/ll/grammar_compiler.rb, line 223
def on_ruby(node, compiled_grammar)
  return node.children[0]
end
on_rule(node, compiled_grammar) click to toggle source

Processes the assignment of a rule.

@see [#process]

# 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
on_rule_prototype(node, compiled_grammar) click to toggle source

Creates a basic prototype for a rule.

@see [#process]

# 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
on_star(node, compiled_grammar) click to toggle source

Processes the “*” operator.

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar @return [LL::Operator]

# 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
on_steps(node, compiled_grammar) click to toggle source

Processes the steps of a branch.

@see [#process] @return [Array]

# File lib/ll/grammar_compiler.rb, line 319
def on_steps(node, compiled_grammar)
  return lookup_identifiers(node, compiled_grammar)
end
on_terminals(node, compiled_grammar) click to toggle source

Processes the assignment of terminals.

@see [#process]

# 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
process(node, compiled_grammar) click to toggle source

@param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar @return [LL::CompiledGrammar]

# File lib/ll/grammar_compiler.rb, line 30
def process(node, compiled_grammar)
  handler = "on_#{node.type}"

  return send(handler, node, compiled_grammar)
end
verify_first_first(compiled_grammar) click to toggle source

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.

@param [LL::CompiledGrammar] compiled_grammar

# 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
verify_first_follow(compiled_grammar) click to toggle source

Adds errors for any rules containing first/follow conflicts.

@param [LL::CompiledGrammar] compiled_grammar

# 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
warn_for_unused_rules(compiled_grammar) click to toggle source

Adds warnings for any unused rules. The first defined rule is skipped since it's the root rule.

@param [LL::CompiledGrammar] compiled_grammar

# 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
warn_for_unused_terminals(compiled_grammar) click to toggle source

Adds warnings for any unused terminals.

@param [LL::CompiledGrammar] compiled_grammar

# 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

Private Instance Methods

lookup_identifiers(node, compiled_grammar) click to toggle source

@see [#process] @return [Array]

# 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
undefined_identifier!(name, node, compiled_grammar) click to toggle source

@param [String] name @param [LL::AST::Node] node @param [LL::CompiledGrammar] compiled_grammar

# 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