Module: Antelope::Generation::Constructor::Follow
- Included in:
- Antelope::Generation::Constructor
- Defined in:
- lib/antelope/generation/constructor/follow.rb
Overview
Contains the methods to find the FOLLOW sets of nonterminals.
Instance Method Summary collapse
-
#follow(token) ⇒ Set<Ace::Token>
Returns the FOLLOW set of the given token.
-
#generate_follow_set(token) ⇒ Set<Ace::Token>
private
Generates the FOLLOW set for the given token.
-
#initialize ⇒ Object
Initialize.
Instance Method Details
#follow(token) ⇒ Set<Ace::Token>
Returns the FOLLOW set of the given token. If the given token isn't a nonterminal, it raises an error. It then generates the FOLLOW set for the given token, and then caches it.
24 25 26 27 28 29 30 |
# File 'lib/antelope/generation/constructor/follow.rb', line 24 def follow(token) unless token.is_a? Ace::Token::Nonterminal incorrect_argument! token, Ace::Token::Nonterminal end @follows.fetch(token) { generate_follow_set(token) } end |
#generate_follow_set(token) ⇒ Set<Ace::Token> (private)
Generates the FOLLOW set for the given token. It finds the positions at which the token appears in the grammar, and sees what could possibly follow it. For example, given the following production:
A -> aBz
With a
and z
being any combination of terminals and
nonterminals, and we're trying to find the FOLLOW set of
B
we add the FIRST set of z
to the FOLLOW set of B
:
FOLLOW(B) = FOLLOW(B) ∪ FIRST(z)
In the case that B
is at the end of a production, like so:
A -> aB
or
A -> aBw
(with w
being nullable) We also add the FOLLOW set of A
to B
:
FOLLOW(B) = FOLLOW(B) ∪ FOLLOW(A)
In case this operation is potentially recursive, we make
sure to set the FOLLOW set of B
to an empty set (since we
cache the result of a FOLLOW set, the empty set will be
returned).
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
# File 'lib/antelope/generation/constructor/follow.rb', line 69 def generate_follow_set(token) # Set it to the empty set so we don't end up recursing. set = @follows[token] = Set.new productions.each do |rule| items = rule.items # Find all of the positions within the rule that our token # occurs, and then increment that position by one. positions = items.each_with_index. find_all { |t, _| t == token }. map(&:last).map(&:succ) # Find the FIRST set of every item after our token, and # put that in our set. positions.map { |pos| first(items[pos..-1]) }. inject(set, :merge) positions.each do |pos| # If we're at the end of the rule... if pos == items.size || nullable?(items[pos..-1]) # Then add the FOLLOW set of the left-hand side to our # set. set.merge follow(rule.label) end end end # Replace the cached empty set with our filled set. @follows[token] = set end |
#initialize ⇒ Object
Initialize.
11 12 13 14 |
# File 'lib/antelope/generation/constructor/follow.rb', line 11 def initialize @follows = {} super end |