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<Grammar::Token>
Returns the FOLLOW set of the given token.
-
#generate_follow_set(token) ⇒ Set<Grammar::Token>
private
Generates the FOLLOW set for the given token.
-
#initialize ⇒ Object
Initialize.
Instance Method Details
#follow(token) ⇒ Set<Grammar::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? Grammar::Token::Nonterminal incorrect_argument! token, Grammar::Token::Nonterminal end @follows.fetch(token) { generate_follow_set(token) } end |
#generate_follow_set(token) ⇒ Set<Grammar::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 100 101 |
# 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. @follows[token] = Set.new set = Set.new productions.each do |rule| items = rule.items i = 0 # Find all of the positions within the rule that our token # occurs, and then increment that position by one. while i < items.size next i += 1 unless items[i] == token position = i.succ # Find the FIRST set of every item after our token, and # put that in our set. set.merge first(items[position..-1]) # If we're at the end of the rule... if position == items.size || nullable?(items[position..-1]) # Then add the FOLLOW set of the left-hand side to our # set. set.merge follow(rule.label) end i += 1 end end # ReplGrammar 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 |