Module: Antelope::Generation::Constructor::Nullable

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

Overview

Contains the methods to determine if an object is nullable.

Instance Method Summary collapse

Instance Method Details

#initialize ⇒ Object

Initialize.



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

def initialize
  @nullifying = Set.new
end

#nullable?(token) ⇒ Boolean

Determine if a given token is nullable. This is how the method should behave:

nullable?(ϵ) == true  # if ϵ is the epsilon token
nullable?(x) == false # if x is a terminal
nullable?(αβ) == nullable?(α) && nullable?(β)
nullable?(A) == nullable?(a_1) || nullable?(a_2) || ... nullable?(a_n)
  # if A is a nonterminal and a_1, a_2, ..., a_n are all
  # of the right-hand sides of its productions

Parameters:

Returns:

  • (Boolean) —

    if the token can reduce to ϵ.



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/antelope/generation/constructor/nullable.rb', line 28

def nullable?(token)
  case token
  when Grammar::Token::Nonterminal
    nullifying(token) do
      productions = grammar.productions[token.name]
      !!productions.any? { |prod| nullable?(prod[:items]) }
    end
  when Array
    token.dup.delete_if { |tok|
      @nullifying.include?(tok) }.all? { |tok| nullable?(tok) }
  when Grammar::Token::Epsilon
    true
  when Grammar::Token::Terminal
    false
  else
    incorrect_argument! token, Grammar::Token, Array
  end
end

#nullifying(tok) { ... } ⇒ Boolean (private)

Helps keep track of the nonterminals we're checking for nullability. This helps prevent recursion.

Parameters:

Yields:

  • once.

Returns:

  • (Boolean) 


55
56
57
58
59
60
 
# File 'lib/antelope/generation/constructor/nullable.rb', line 55

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