class Rley::Parser::ParseWalkerFactory
A factory that creates an Enumerator object that itself walks through a GFGParsing
object. The walker (= Enumerator) yields visit events. This class implements an external iterator for a given GFGParsing
object. This is different from the internal iterators, usually implemented in Ruby with an :each method. Allows to perform a backwards traversal over the relevant parse entries. backwards traversal means that the traversal starts from the accepting (final) parse entries and goes to the initial parse entry. Relevant parse entries are parse entries that “count” in the parse (i.e. they belong to a path that leads to the accepting parse entry)
Public Instance Methods
Source
# File lib/rley/parser/parse_walker_factory.rb, line 53 def build_walker(acceptingEntry, maxIndex, lazyWalk = false) msg = 'Internal error: nil entry argument' raise StandardError, msg if acceptingEntry.nil? # Local context for the enumerator ctx = init_context(acceptingEntry, maxIndex, lazyWalk) Enumerator.new do |receiver| # 'receiver' is a Yielder # At this point: current entry == accepting entry loop do event = visit_entry(ctx.curr_entry, ctx) receiver << event unless event.nil? if ctx.curr_entry.orphan? # No antecedent?... msg_prefix = "No antecedent for #{ctx.curr_entry}" msg_suffix = "at rank #{ctx.entry_set_index}" err_msg = "#{msg_prefix} #{msg_suffix}" raise StandardError, err_msg unless ctx.curr_entry.start_entry? break if ctx.backtrack_points.empty? receiver << use_backtrack_point(ctx) receiver << visit_entry(ctx.curr_entry, ctx) end result = jump_to_antecedent(ctx) # Emit detection of scan edge if any... receiver << result[0] if result.size > 1 ctx.curr_entry = result.last end end end
Build an Enumerator that will yield the parse entries as it walks backwards on the parse graph. @param acceptingEntry [ParseEntry] the final ParseEntry
of a
successful parse.
@param maxIndex [Integer] the index of the last input token. @param lazyWalk [Boolean] if true then take some shortcut in re-visits. @return [Enumerator] yields visit events when walking over the
parse result
rubocop: disable Style/OptionalBooleanParameter
Private Instance Methods
Source
# File lib/rley/parser/parse_walker_factory.rb, line 232 def add_backtrack_point(aContext) bp = WalkerBacktrackpoint.new bp.entry_set_index = aContext.entry_set_index bp.return_stack = aContext.return_stack.dup bp.visitee = aContext.curr_entry bp.antecedent_index = 0 aContext.backtrack_points << bp # puts "Backtrack size after addition #{aContext.backtrack_points.size}" bp end
Source
# File lib/rley/parser/parse_walker_factory.rb, line 178 def antecedent_of(aContext) new_entry = aContext.curr_entry.antecedents.first events = [new_entry] traversed_edge = new_entry.vertex.edges.first if new_entry.vertex.is_a?(GFG::EndVertex) # Return edge encountered # Push current entry onto stack # puts "Push on return stack #{aContext.curr_entry}" aContext.return_stack << aContext.curr_entry elsif traversed_edge.is_a?(GFG::CallEdge) # Pop top of stack err_msg = 'Return stack empty!' raise ScriptError, err_msg if aContext.return_stack.empty? aContext.return_stack.pop # puts "Pop from return stack matching entry #{new_entry}" elsif traversed_edge.is_a?(GFG::ScanEdge) # Scan edge encountered, decrease sigma set index aContext.entry_set_index -= 1 elsif traversed_edge.is_a?(GFG::EpsilonEdge) # Do nothing else raise NotImplementedError, "edge is a #{traversed_edge.class}" end events end
Handle the case of an entry having one antecedent only
Source
# File lib/rley/parser/parse_walker_factory.rb, line 159 def detect_scan_edge(ctx) nil unless ctx.curr_entry.dotted_entry? end
rubocop: enable Lint/DuplicateBranch
Source
# File lib/rley/parser/parse_walker_factory.rb, line 90 def init_context(acceptingEntry, maxIndex, lazyWalk) context = ParseWalkerContext.new context.entry_set_index = maxIndex context.curr_entry = acceptingEntry context.visitees = Set.new context.nterm2start = init_nterm2start context.return_stack = [] context.backtrack_points = [] context.lazy_walk = lazyWalk context end
Context factory method
Source
# File lib/rley/parser/parse_walker_factory.rb, line 104 def init_nterm2start Hash.new do |hsh, defval| entry, index = defval nonterm = entry.vertex.non_terminal if hsh.include? nonterm pre = hsh[nonterm] pre[index] = entry else hsh[nonterm] = { index => entry } end end end
Initialize the non-terminal to start entry mapping
Source
# File lib/rley/parser/parse_walker_factory.rb, line 166 def jump_to_antecedent(aContext) entries = [] return entries if aContext.curr_entry.orphan? if aContext.curr_entry.antecedents.size == 1 antecedent_of(aContext) else select_antecedent(aContext) end end
Given the current entry from context object Go to the parse entry that is one of its antecedent The context object is updated
Source
# File lib/rley/parser/parse_walker_factory.rb, line 207 def select_antecedent(aContext) case aContext.curr_entry.vertex when GFG::EndVertex # puts "Add backtrack point stack #{aContext.curr_entry}" # aContext.curr_entry.antecedents.each { |antec| puts "\t#{antec}" } bp = add_backtrack_point(aContext) new_entry = bp.visitee.antecedents[bp.antecedent_index] when GFG::StartVertex new_entry = select_calling_entry(aContext) when GFG::ItemVertex # Push current entry onto stack # puts "Special push on return stack #{aContext.curr_entry}" aContext.return_stack << aContext.curr_entry # puts "Add special backtrack point stack #{aContext.curr_entry}" bp = add_backtrack_point(aContext) new_entry = bp.visitee.antecedents[bp.antecedent_index] else raise StandardError, 'Internal error' end [new_entry] end
Handle the case of an entry having multiple antecedents
Source
# File lib/rley/parser/parse_walker_factory.rb, line 269 def select_calling_entry(aContext) raise ScriptError, 'Empty return stack' if aContext.return_stack.empty? # Retrieve top of stack # @type var tos : Rley::Parser::ParseEntry tos = aContext.return_stack.pop tos_dotted_item = tos.vertex.dotted_item antecedents = aContext.curr_entry.antecedents new_entry = antecedents.find do |antecd| item = antecd.vertex.dotted_item (antecd.origin == tos.origin) && tos_dotted_item.successor_of?(item) end new_entry ||= aContext.curr_entry # puts "Pop from return stack matching entry #{new_entry}" new_entry end
From the antecedent of the current parse entry Retrieve the one that corresponds to the parse entry on top of return stack Observation: calling parse entry is an parse entry linked to a item vertex
Source
# File lib/rley/parser/parse_walker_factory.rb, line 244 def use_backtrack_point(aContext) bp = aContext.backtrack_points.last bp.antecedent_index += 1 # Restore state aContext.entry_set_index = bp.entry_set_index aContext.return_stack = bp.return_stack.dup aContext.curr_entry = bp.visitee.antecedents[bp.antecedent_index] # Drop backtrack point if useless in future if bp.antecedent_index == bp.visitee.antecedents.size - 1 aContext.backtrack_points.pop end # puts "Backtracking to #{bp.visitee}" # puts "Backtrack size after backtracking #{aContext.backtrack_points.size}" # Emit a backtrack event [:backtrack, bp.visitee, aContext.entry_set_index] end
Source
# File lib/rley/parser/parse_walker_factory.rb, line 119 def visit_entry(anEntry, aContext) index = aContext.entry_set_index aContext.nterm2start[[anEntry, index]] if anEntry.start_entry? # steep:ignore # @type var event : [Symbol, ParseEntry, Integer] if aContext.visitees.include?(anEntry) # Already visited?... case anEntry.vertex when GFG::EndVertex if aContext.lazy_walk # Jump to related start entry... pairs = aContext.nterm2start[anEntry.vertex.non_terminal] new_entry = pairs[anEntry.origin] aContext.curr_entry = new_entry aContext.entry_set_index = new_entry.origin end event = [:revisit, anEntry, index] when GFG::StartVertex # Even for non-ambiguous parse, can be caused by # left recursive rule e.g. (S => S A) event = [:revisit, anEntry, index] when GFG::ItemVertex # Even for non-ambiguous parse, can be caused by # left recursive rule e.g. (S => S A) # Skip item entries while revisiting event = [:revisit, anEntry, index] else raise NotImplementedError end else # first time visit aContext.visitees << anEntry event = [:visit, anEntry, index] end event end
- event, entry, index, vertex
-
rubocop: disable Lint/DuplicateBranch