module Antelope::Generation::Constructor::First

Contains the methods to construct first sets for tokens.

Public Class Methods

new() click to toggle source

Initialize.

Calls superclass method
# File lib/antelope/generation/constructor/first.rb, line 9
def initialize
  @firstifying = []
  super
end

Public Instance Methods

first(token) click to toggle source

Constructs the first set for a given token. This is how the method should behave:

FIRST(ε)  == []  # if ε is the epsilon token
FIRST(x)  == [x] # if x is a terminal
FIRST(αβ) == if nullable?(α)
  FIRST(α) U FIRST(β)
else
  FIRST(α)
end
FIRST(A)  == FIRST(a_1) U FIRST(a_2) U ... U FIRST(a_n)
  # if A is a nonterminal and a_1, a_2, ..., a_3 are all
  # of the right-hand sides of its productions.

@param token [Grammar::Token, Array<Grammar::Token>] @return [Set<Grammar::Token::Terminal>] @see first_array

# File lib/antelope/generation/constructor/first.rb, line 31
def first(token)
  case token
  when Grammar::Token::Nonterminal
    firstifying(token) do
      productions = grammar.productions[token.name]
      productions.map { |prod|
        first(prod[:items]) }.inject(Set.new, :+)
    end
  when Array
    first_array(token)
  when Grammar::Token::Epsilon
    Set.new
  when Grammar::Token::Terminal
    Set.new([token])
  else
    incorrect_argument! token, Grammar::Token, Array
  end
end

Private Instance Methods

first_array(tokens) click to toggle source

Determines the FIRST set of an array of tokens. First, it removes any terminals we are finding the FIRST set for; then, it determines which tokens we have to find the FIRST sets for (since some tokens may be nullable). We then add those sets to our set.

@param tokens [Array<Grammar::Token>] @return [Set<Grammar::Token>]

# File lib/antelope/generation/constructor/first.rb, line 60
def first_array(tokens)
  tokens.dup.delete_if { |_| @firstifying.include?(_) }.
  each_with_index.take_while do |token, i|
    if i.zero?
      true
    else
      nullable?(tokens[i - 1])
    end
  end.map(&:first).map { |_| first(_) }.inject(Set.new, :+)
end
firstifying(tok) { || ... } click to toggle source

Helps keep track of the nonterminals we’re finding FIRST sets for. This helps prevent recursion.

@param tok [Grammar::Token::Nonterminal] @yield once. @return [Set<Grammar::Token>]

# File lib/antelope/generation/constructor/first.rb, line 77
def firstifying(tok)
  @firstifying << tok
  out = yield
  @firstifying.delete tok
  out
end