Sha256: 39b26072b1d71fa742634592a144f2938eaeea0456e678a9b6873a981bad6ead
Contents?: true
Size: 1.9 KB
Versions: 11
Compression:
Stored size: 1.9 KB
Contents
# encoding: utf-8
module Antelope
module Generation
class Constructor
# Contains the methods to determine if an object is nullable.
module Nullable
# Initialize.
def initialize
@nullifying = Set.new
end
# 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 [Ace::Token, Array<Ace::Token>] the token to
# check.
# @return [Boolean] if the token can reduce to ϵ.
def nullable?(token)
case token
when Ace::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 Ace::Token::Epsilon
true
when Ace::Token::Terminal
false
else
incorrect_argument! token, Ace::Token, Array
end
end
private
# Helps keep track of the nonterminals we're checking for
# nullability. This helps prevent recursion.
#
# @param tok [Ace::Token::Nonterminal]
# @yield once.
# @return [Boolean]
def nullifying(tok)
@nullifying << tok
out = yield
@nullifying.delete tok
out
end
end
end
end
end
Version data entries
11 entries across 11 versions & 1 rubygems