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