Module: Antelope::Generation::Constructor::First

Included in:
Antelope::Generation::Constructor
Defined in:
lib/antelope/generation/constructor/first.rb

Overview

Contains the methods to construct first sets for tokens.

Instance Method Summary collapse

Instance Method Details

#first(token) ⇒ Set<Grammar::Token::Terminal>

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.

Parameters:

Returns:

See Also:



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# 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

#first_array(tokens) ⇒ Set<Grammar::Token> (private)

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.

Parameters:

Returns:



60
61
62
63
64
65
66
67
68
69
 
# 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) { ... } ⇒ Set<Grammar::Token> (private)

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

Parameters:

Yields:

  • once.

Returns:



77
78
79
80
81
82
 
# File 'lib/antelope/generation/constructor/first.rb', line 77

def firstifying(tok)
  @firstifying << tok
  out = yield
  @firstifying.delete tok
  out
end

#initialize ⇒ Object

Initialize.



9
10
11
12
 
# File 'lib/antelope/generation/constructor/first.rb', line 9

def initialize
  @firstifying = []
  super
end