module Antelope::Generation::Constructor::Nullable

Contains the methods to determine if an object is nullable.

Public Class Methods

new() click to toggle source

Initialize.

# File lib/antelope/generation/constructor/nullable.rb, line 11
def initialize
  @nullifying = Set.new
end

Public Instance Methods

nullable?(token) click to toggle source

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

@param token [Grammar::Token, Array<Grammar::Token>] the token to

check.

@return [Boolean] if the token can reduce to ϵ.

# 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

Private Instance Methods

nullifying(tok) { || ... } click to toggle source

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

@param tok [Grammar::Token::Nonterminal] @yield once. @return [Boolean]

# File lib/antelope/generation/constructor/nullable.rb, line 55
def nullifying(tok)
  @nullifying << tok
  out = yield
  @nullifying.delete tok
  out
end