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<Ace::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:



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/antelope/generation/constructor/first.rb', line 33

def first(token)
  case token
  when Ace::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 Ace::Token::Epsilon
    Set.new
  when Ace::Token::Terminal
    Set.new([token])
  else
    incorrect_argument! token, Ace::Token, Array
  end
end

#first_array(tokens) ⇒ Set<Ace::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:



62
63
64
65
66
67
68
69
70
71
 
# File 'lib/antelope/generation/constructor/first.rb', line 62

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<Ace::Token> (private)

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

Parameters:

Yields:

  • once.

Returns:



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

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

#initialize ⇒ Object

Initialize.



11
12
13
14
 
# File 'lib/antelope/generation/constructor/first.rb', line 11

def initialize
  @firstifying = []
  super
end