class RLTK::Parser
The Parser
class may be sub-classed to produce new parsers. These parsers have a lot of features, and are described in the main documentation.
Attributes
@return [Environment] Environment
used by the instantiated parser.
Public Class Methods
If state (or its equivalent) is not in the state list it is added and it’s ID is returned. If there is already a state with the same items as state in the state list its ID is returned and state is discarded.
@param [State] state State to add to the parser.
@return [Integer] The ID of the state.
# File lib/rltk/parser.rb, line 193 def add_state(state) if (id = @states.index(state)) id else state.id = @states.length @states << state @states.length - 1 end end
Adds productions and actions for parsing empty lists.
@see CFG#empty_list_production
# File lib/rltk/parser.rb, line 401 def build_list_production(symbol, list_elements, separator = '') @grammar.build_list_production(symbol, list_elements, separator) end
Adds productions and actions for parsing nonempty lists.
@see CFG#nonempty_list_production
# File lib/rltk/parser.rb, line 790 def build_nonempty_list_production(symbol, list_elements, separator = '') @grammar.build_nonempty_list_production(symbol, list_elements, separator) end
This method checks to see if the parser would be in parse state dest after starting in state start and reading symbols.
@param [Symbol] start Symbol representing a CFG
production. @param [Symbol] dest Symbol representing a CFG
production. @param [Array<Symbol>] symbols Grammar symbols.
@return [Boolean] If the destination symbol is reachable from the start symbol after reading symbols.
# File lib/rltk/parser.rb, line 302 def check_reachability(start, dest, symbols) path_exists = true cur_state = start symbols.each do |sym| actions = @states[cur_state.id].on?(sym) actions = actions.select { |a| a.is_a?(Shift) } if CFG::is_terminal?(sym) if actions.empty? path_exists = false break end # There can only be one Shift action for terminals and # one GoTo action for non-terminals, so we know the # first action is the only one in the list. cur_state = @states[actions.first.id] end path_exists and cur_state.id == dest.id end
This method is used to (surprise) check the sanity of the constructed parser. It checks to make sure all non-terminals used in the grammar definition appear on the left-hand side of one or more productions, and that none of the parser’s states have invalid actions. If a problem is encountered a ParserConstructionException
is raised.
@return [void]
# File lib/rltk/parser.rb, line 250 def check_sanity # Check to make sure all non-terminals appear on the # left-hand side of some production. @grammar.nonterms.each do |sym| if not @lh_sides.values.include?(sym) raise ParserConstructionException, "Non-terminal #{sym} does not appear on the left-hand side of any production." end end # Check the actions in each state. each_state do |state| state.actions.each do |sym, actions| if CFG::is_terminal?(sym) # Here we check actions for terminals. actions.each do |action| if action.is_a?(Accept) if sym != :EOS raise ParserConstructionException, "Accept action found for terminal #{sym} in state #{state.id}." end elsif not (action.is_a?(GoTo) or action.is_a?(Reduce) or action.is_a?(Shift)) raise ParserConstructionException, "Object of type #{action.class} found in actions for terminal " + "#{sym} in state #{state.id}." end end if (conflict = state.conflict_on?(sym)) self.inform_conflict(state.id, conflict, sym) end else # Here we check actions for non-terminals. if actions.length > 1 raise ParserConstructionException, "State #{state.id} has multiple GoTo actions for non-terminal #{sym}." elsif actions.length == 1 and not actions.first.is_a?(GoTo) raise ParserConstructionException, "State #{state.id} has non-GoTo action for non-terminal #{sym}." end end end end end
Declares a new clause inside of a production. The right-hand side is specified by expression and the precedence of this production can be changed by setting the precedence argument to some terminal symbol.
@param [String, Symbol] expression Right-hand side of a production. @param [Symbol] precedence Symbol representing the precedence of this production. @param [:array, :splat] arg_type Method to use when passing arguments to the action. @param [Proc] action Action to be taken when the production is reduced.
@return [void]
# File lib/rltk/parser.rb, line 336 def clause(expression, precedence = nil, arg_type = @default_arg_type, &action) # Use the curr_prec only if it isn't overridden for this # clause. precedence ||= @curr_prec production, selections = @grammar.clause(expression) # Check to make sure the action's arity matches the number # of symbols on the right-hand side. expected_arity = (selections.empty? ? production.rhs.length : selections.length) if arg_type == :splat and action.arity != expected_arity raise ParserConstructionException, "Incorrect number of action parameters. Expected #{expected_arity} but got #{action.arity}." + ' Action arity must match the number of terminals and non-terminals in the clause.' end # Add the action to our proc list. @procs[production.id] = [ProdProc.new(arg_type, selections, &action), production.rhs.length] # If no precedence is specified use the precedence of the # last terminal in the production. @production_precs[production.id] = precedence || production.last_terminal end
Removes resources that were needed to generate the parser but aren’t needed when actually parsing input.
@return [void]
# File lib/rltk/parser.rb, line 365 def clean # We've told the developer about conflicts by now. @conflicts = nil # Drop the grammar and the grammar'. @grammar = nil @grammar_prime = nil # Drop precedence and bookkeeping information. @cur_lhs = nil @cur_prec = nil @prec_counts = nil @production_precs = nil @token_precs = nil # Drop the items from each of the states. each_state { |state| state.clean } end
Set the default argument type for the actions associated with clauses. All actions defined after this call will be passed arguments in the way specified here, unless overridden in the call to {Parser.clause}.
@param [:array, :splat] type The default argument type.
@return [void]
# File lib/rltk/parser.rb, line 393 def default_arg_type(type) @default_arg_type = type if type == :array or type == :splat end
Iterate over the parser’s states.
@yieldparam [State] state One of the parser automaton’s state objects
@return [void]
# File lib/rltk/parser.rb, line 695 def each_state current_state = 0 while current_state < @states.count yield @states.at(current_state) current_state += 1 end end
This function will print a description of the parser to the provided IO object.
@param [IO] io Input/Output object used for printing the parser’s explanation.
@return [void]
# File lib/rltk/parser.rb, line 412 def explain(io) if @grammar and not @states.empty? io.puts('###############') io.puts('# Productions #') io.puts('###############') io.puts max_id_length = @grammar.productions(:id).length.to_s.length # Print the productions. @grammar.productions.each do |sym, productions| max_rhs_length = productions.inject(0) { |m, p| if (len = p.to_s.length) > m then len else m end } productions.each do |production| p_string = production.to_s io.print("\tProduction #{sprintf("%#{max_id_length}d", production.id)}: #{p_string}") if (prec = @production_precs[production.id]) io.print(' ' * (max_rhs_length - p_string.length)) io.print(" : (#{sprintf("%-5s", prec.first)}, #{prec.last})") end io.puts end io.puts end io.puts('##########') io.puts('# Tokens #') io.puts('##########') io.puts max_token_len = @grammar.terms.inject(0) { |m, t| if t.length > m then t.length else m end } @grammar.terms.sort {|a,b| a.to_s <=> b.to_s }.each do |term| io.print("\t#{term}") if (prec = @token_precs[term]) io.print(' ' * (max_token_len - term.length)) io.print(" : (#{sprintf("%-5s", prec.first)}, #{prec.last})") end io.puts end io.puts io.puts('#####################') io.puts('# Table Information #') io.puts('#####################') io.puts io.puts("\tStart symbol: #{@grammar.start_symbol}'") io.puts io.puts("\tTotal number of states: #{@states.length}") io.puts io.puts("\tTotal conflicts: #{@conflicts.values.flatten(1).length}") io.puts @conflicts.each do |state_id, conflicts| io.puts("\tState #{state_id} has #{conflicts.length} conflict(s)") end io.puts if not @conflicts.empty? # Print the parse table. io.puts('###############') io.puts('# Parse Table #') io.puts('###############') io.puts each_state do |state| io.puts("State #{state.id}:") io.puts io.puts("\t# ITEMS #") max = state.items.inject(0) do |max, item| if item.lhs.to_s.length > max then item.lhs.to_s.length else max end end state.each do |item| io.puts("\t#{item.to_s(max)}") end io.puts io.puts("\t# ACTIONS #") state.actions.keys.sort {|a,b| a.to_s <=> b.to_s}.each do |sym| state.actions[sym].each do |action| io.puts("\tOn #{sym} #{action}") end end io.puts io.puts("\t# CONFLICTS #") if @conflicts[state.id].length == 0 io.puts("\tNone\n\n") else @conflicts[state.id].each do |conflict| type, sym = conflict io.print("\t#{if type == :SR then "Shift/Reduce" else "Reduce/Reduce" end} conflict") io.puts(" on #{sym}") end io.puts end end # Close any IO objects that aren't $stdout. io.close if io.is_a?(IO) and io != $stdout else raise ParserConstructionException, 'Parser.explain called outside of finalize.' end end
This method will finalize the parser causing the construction of states and their actions, and the resolution of conflicts using lookahead and precedence information.
No calls to {Parser.production} may appear after the call to Parser.finalize
.
@param [Hash] opts Options describing how to finalize the parser.
@option opts [Boolean,String,IO] :explain To explain the parser or not. @option opts [Boolean] :lookahead To use lookahead info for conflict resolution. @option opts [Boolean] :precedence To use precedence info for conflict resolution. @option opts [String,IO] :use A file name or object that is used to load/save the parser.
@return [void]
# File lib/rltk/parser.rb, line 550 def finalize(opts = {}) if @grammar.productions.empty? raise ParserConstructionException, "Parser has no productions. Cowardly refusing to construct an empty parser." end # Get the full options hash. opts = build_finalize_opts(opts) # Get the name of the file in which the parser is defined. # # FIXME: See why this is failing for the simple ListParser example. def_file = caller()[2].split(':')[0] if opts[:use] # Check to make sure we can load the necessary information # from the specified object. if opts[:use] and ( (opts[:use].is_a?(String) and File.exists?(opts[:use]) and File.mtime(opts[:use]) > File.mtime(def_file)) or (opts[:use].is_a?(File) and opts[:use].mtime > File.mtime(def_file)) ) file = self.get_io(opts[:use], 'r') # Un-marshal our saved data structures. file.flock(File::LOCK_SH) @lh_sides, @states, @symbols = Marshal.load(file) file.flock(File::LOCK_UN) # Close the file if we opened it. file.close if opts[:use].is_a?(String) # Remove any un-needed data and return. return self.clean end # Grab all of the symbols that comprise the grammar # (besides the start symbol). @symbols = @grammar.symbols << :ERROR # Add our starting state to the state list. @start_symbol = (@grammar.start_symbol.to_s + '\'').to_sym start_production, _ = @grammar.production(@start_symbol, @grammar.start_symbol).first start_state = State.new(@symbols, [start_production.to_item]) start_state.close(@grammar.productions) self.add_state(start_state) # Translate the precedence of productions from tokens to # (associativity, precedence) pairs. @production_precs.map! { |prec| @token_precs[prec] } # Build the rest of the transition table. each_state do |state| #Transition states. tstates = Hash.new { |h,k| h[k] = State.new(@symbols) } #Bin each item in this set into reachable transition #states. state.each do |item| if (next_symbol = item.next_symbol) tstates[next_symbol] << item.copy end end # For each transition state: # 1) Get transition symbol # 2) Advance dot # 3) Close it # 4) Get state id and add transition tstates.each do |symbol, tstate| tstate.each { |item| item.advance } tstate.close(@grammar.productions) id = self.add_state(tstate) # Add Goto and Shift actions. state.on(symbol, CFG::is_nonterminal?(symbol) ? GoTo.new(id) : Shift.new(id)) end # Find the Accept and Reduce actions for this state. state.each do |item| if item.at_end? if item.lhs == @start_symbol state.on(:EOS, Accept.new) else state.add_reduction(@grammar.productions(:id)[item.id]) end end end end # Build the production.id -> production.lhs map. @grammar.productions(:id).each { |id, production| @lh_sides[id] = production.lhs } # Prune the parsing table for unnecessary reduce actions. self.prune(opts[:lookahead], opts[:precedence]) # Check the parser for inconsistencies. self.check_sanity # Print the table if requested. self.explain(opts[:explain]) if opts[:explain] # Remove any data that is no longer needed. self.clean # Store the parser's final data structures if requested. if opts[:use] io = self.get_io(opts[:use]) io.flock(File::LOCK_EX) if io.is_a?(File) Marshal.dump([@lh_sides, @states, @symbols], io) io.flock(File::LOCK_UN) if io.is_a?(File) # Close the IO object if we opened it. io.close if opts[:use].is_a?(String) end end
Converts an object into an IO object as appropriate.
@param [Object] o Object
to be converted into an IO object. @param [String] mode String representing the mode to open the IO object in.
@return [IO, false] The IO object or false if a conversion wasn’t possible.
# File lib/rltk/parser.rb, line 678 def get_io(o, mode = 'w') if o.is_a?(TrueClass) $stdout elsif o.is_a?(String) File.open(o, mode) elsif o.is_a?(IO) o else false end end
@return [CFG] The grammar that can be parsed by this Parser
.
# File lib/rltk/parser.rb, line 704 def grammar @grammar.clone end
This method generates and memoizes the G’ grammar used to calculate the LALR(1) lookahead sets. Information about this grammar and its use can be found in the following paper:
Simple Computation of LALR(1) Lookahead Sets Manuel E. Bermudez and George Logothetis Information Processing Letters 31 - 1989
@return [CFG]
# File lib/rltk/parser.rb, line 717 def grammar_prime if not @grammar_prime @grammar_prime = CFG.new each_state do |state| state.each do |item| lhs = "#{state.id}_#{item.next_symbol}".to_sym next unless CFG::is_nonterminal?(item.next_symbol) and not @grammar_prime.productions.keys.include?(lhs) @grammar.productions[item.next_symbol].each do |production| rhs = '' cstate = state production.rhs.each do |symbol| rhs += "#{cstate.id}_#{symbol} " cstate = @states[cstate.on?(symbol).first.id] end @grammar_prime.production(lhs, rhs) end end end end @grammar_prime end
Inform the parser core that a conflict has been detected.
@param [Integer] state_id ID of the state where the conflict was encountered. @param [:RR, :SR] type Reduce/Reduce or Shift/Reduce conflict. @param [Symbol] sym Symbol that caused the conflict.
@return [void]
# File lib/rltk/parser.rb, line 754 def inform_conflict(state_id, type, sym) @conflicts[state_id] << [type, sym] end
Called when the Lexer
class is sub-classed, it installes necessary instance class variables.
@return [void]
# File lib/rltk/parser.rb, line 181 def inherited(klass) klass.install_icvars end
Installs instance class varialbes into a class.
@return [void]
# File lib/rltk/parser.rb, line 119 def install_icvars @curr_lhs = nil @curr_prec = nil @conflicts = Hash.new {|h, k| h[k] = Array.new} @grammar = CFG.new @lh_sides = Hash.new @procs = Array.new @states = Array.new # Variables for dealing with precedence. @prec_counts = {:left => 0, :right => 0, :non => 0} @production_precs = Array.new @token_precs = Hash.new @token_hooks = Hash.new {|h, k| h[k] = []} # Set the default argument handling policy. Valid values # are :array and :splat. @default_arg_type = :splat @grammar.callback do |type, which, p, sels = []| @procs[p.id] = [ case type when :optional case which when :empty then ProdProc.new { || nil } else ProdProc.new { |o| o } end when :elp case which when :empty then ProdProc.new { || [] } else ProdProc.new { |prime| prime } end when :nelp case which when :single ProdProc.new { |el| [el] } when :multiple ProdProc.new(:splat, sels) do |*syms| el = syms[1..-1] syms.first << (el.length == 1 ? el.first : el) end else ProdProc.new { |*el| el.length == 1 ? el.first : el } end end, p.rhs.length ] @production_precs[p.id] = p.last_terminal end end
This method is used to specify that the symbols in symbols are left-associative. Subsequent calls to this method will give their arguments higher precedence.
@param [Array<Symbol>] symbols Symbols that are left associative.
@return [void]
# File lib/rltk/parser.rb, line 765 def left(*symbols) prec_level = @prec_counts[:left] += 1 symbols.map { |s| s.to_sym }.each do |sym| @token_precs[sym] = [:left, prec_level] end end
The overridden new prevents un-finalized parsers from being instantiated.
# File lib/rltk/parser.rb, line 108 def new(*args) if @symbols.nil? raise UselessParserException else super(*args) end end
Instantiates a new parser and creates an environment to be used for subsequent calls.
# File lib/rltk/parser.rb, line 1255 def initialize @env = self.class::Environment.new end
This method is used to specify that the symbols in symbols are non-associative.
@param [Array<Symbol>] symbols Symbols that are non-associative.
@return [void]
# File lib/rltk/parser.rb, line 779 def nonassoc(*symbols) prec_level = @prec_counts[:non] += 1 symbols.map { |s| s.to_sym }.each do |sym| @token_precs[sym] = [:non, prec_level] end end
This function is where actual parsing takes place. The tokens argument must be an array of Token
objects, the last of which has type EOS. By default this method will return the value computed by the first successful parse tree found.
Additional information about the parsing options can be found in the main documentation.
@param [Array<Token>] tokens Tokens to be parsed. @param [Hash] opts Options to use when parsing input.
@option opts [:first, :all] :accept Either :first or :all. @option opts [Object] :env The environment in which to evaluate the production action. @option opts [Boolean,String,IO] :parse_tree To print parse trees in the DOT language or not. @option opts [Boolean,String,IO] :verbose To be verbose or not.
@return [Object, Array<Object>] Result or results of parsing the given tokens.
# File lib/rltk/parser.rb, line 812 def parse(tokens, opts = {}) # Get the full options hash. opts = build_parse_opts(opts) v = opts[:verbose] if opts[:verbose] v.puts("Input tokens:") v.puts(tokens.map { |t| t.type }.inspect) v.puts end # Stack IDs to keep track of them during parsing. stack_id = 0 # Error mode indicators. error_mode = false reduction_guard = false # Our various list of stacks. accepted = [] moving_on = [] processing = [ParseStack.new(stack_id += 1)] # Iterate over the tokens. We don't procede to the # next token until every stack is done with the # current one. tokens.each_with_index do |token, index| # Check to make sure this token was seen in the # grammar definition. raise BadToken if not @symbols.include?(token.type) v.puts("Current token: #{token.type}#{if token.value then "(#{token.value})" end}") if v # Iterate over the stacks until each one is done. while (stack = processing.shift) # Execute any token hooks in this stack's environment. @token_hooks[token.type].each { |hook| opts[:env].instance_exec &hook} # Get the available actions for this stack. actions = @states[stack.state].on?(token.type) if actions.empty? # If we are already in error mode and there # are no actions we skip this token. if error_mode v.puts("Discarding token: #{token.type}#{if token.value then "(#{token.value})" end}") if v # Add the current token to the array # that corresponds to the output value # for the ERROR token. stack.output_stack.last << token moving_on << stack next end # We would be dropping the last stack so we # are going to go into error mode. if accepted.empty? and moving_on.empty? and processing.empty? if v v.puts v.puts('Current stack:') v.puts("\tID: #{stack.id}") v.puts("\tState stack:\t#{stack.state_stack.inspect}") v.puts("\tOutput Stack:\t#{stack.output_stack.inspect}") v.puts end # Try and find a valid error state. while stack.state if (actions = @states[stack.state].on?(:ERROR)).empty? # This state doesn't have an # error production. Moving on. stack.pop else # Enter the found error state. stack.push(actions.first.id, [token], :ERROR, token.position) break end end if stack.state # We found a valid error state. error_mode = reduction_guard = true opts[:env].he = true moving_on << stack if v v.puts('Invalid input encountered. Entering error handling mode.') v.puts("Discarding token: #{token.type}#{if token.value then "(#{token.value})" end}") end else # No valid error states could be # found. Time to print a message # and leave. v.puts("No more actions for stack #{stack.id}. Dropping stack.") if v end else v.puts("No more actions for stack #{stack.id}. Dropping stack.") if v end next end # Make (stack, action) pairs, duplicating the # stack as necessary. pairs = [[stack, actions.pop]] + actions.map {|action| [stack.branch(stack_id += 1), action] } pairs.each do |stack, action| if v v.puts v.puts('Current stack:') v.puts("\tID: #{stack.id}") v.puts("\tState stack:\t#{stack.state_stack.inspect}") v.puts("\tOutput Stack:\t#{stack.output_stack.inspect}") v.puts v.puts("Action taken: #{action.to_s}") end if action.is_a?(Accept) if opts[:accept] == :all accepted << stack else v.puts('Accepting input.') if v opts[:parse_tree].puts(stack.tree) if opts[:parse_tree] if opts[:env].he raise HandledError.new(opts[:env].errors, stack.result) else return stack.result end end elsif action.is_a?(Reduce) # Get the production associated with this reduction. production_proc, pop_size = @procs[action.id] if not production_proc raise InternalParserException, "No production #{action.id} found." end args, positions = stack.pop(pop_size) opts[:env].set_positions(positions) if not production_proc.selections.empty? args = args.values_at(*production_proc.selections) end result = if production_proc.arg_type == :array opts[:env].instance_exec(args, &production_proc) else opts[:env].instance_exec(*args, &production_proc) end if (goto = @states[stack.state].on?(@lh_sides[action.id]).first) v.puts("Going to state #{goto.id}.\n") if v pos0 = nil if args.empty? # Empty productions need to be # handled specially. pos0 = stack.position pos0.stream_offset += pos0.length + 1 pos0.line_offset += pos0.length + 1 pos0.length = 0 else pos0 = opts[:env].pos( 0) pos1 = opts[:env].pos(-1) pos0.length = (pos1.stream_offset + pos1.length) - pos0.stream_offset end stack.push(goto.id, result, @lh_sides[action.id], pos0) else raise InternalParserException, "No GoTo action found in state #{stack.state} " + "after reducing by production #{action.id}" end # This stack is NOT ready for the next # token. processing << stack # Exit error mode if necessary. error_mode = false if error_mode and not reduction_guard elsif action.is_a?(Shift) stack.push(action.id, token.value, token.type, token.position) # This stack is ready for the next # token. moving_on << stack # Exit error mode. error_mode = false end end end v.puts("\n\n") if v processing = moving_on moving_on = [] # If we don't have any active stacks at this point the # string isn't in the language. if opts[:accept] == :first and processing.length == 0 v.close if v and v != $stdout raise NotInLanguage.new(tokens[0...index], tokens[index], tokens[index.next..-1]) end reduction_guard = false end # If we have reached this point we are accepting all parse # trees. if v v.puts("Accepting input with #{accepted.length} derivation(s).") v.close if v != $stdout end accepted.each do |stack| opts[:parse_tree].puts(stack.tree) end if opts[:parse_tree] results = accepted.map { |stack| stack.result } if opts[:env].he raise HandledError.new(opts[:env].errors, results) else return results end end
Adds a new production to the parser with a left-hand value of symbol. If expression is specified it is taken as the right-hand side of the production and action is associated with the production. If expression is nil then action is evaluated and expected to make one or more calls to Parser.clause
. A precedence can be associate with this production by setting precedence to a terminal symbol.
@param [Symbol] symbol Left-hand side of the production. @param [String, Symbol, nil] expression Right-hand side of the production. @param [Symbol, nil] precedence Symbol representing the precedence of this produciton. @param [:array, :splat] arg_type Method to use when passing arguments to the action. @param [Proc] action Action associated with this production.
@return [void]
# File lib/rltk/parser.rb, line 1069 def production(symbol, expression = nil, precedence = nil, arg_type = @default_arg_type, &action) # Check the symbol. if not (symbol.is_a?(Symbol) or symbol.is_a?(String)) or not CFG::is_nonterminal?(symbol) raise ParserConstructionException, 'Production symbols must be Strings or Symbols and be in all lowercase.' end @grammar.curr_lhs = symbol.to_sym @curr_prec = precedence orig_dat = nil if arg_type != @default_arg_type orig_dat = @default_arg_type @default_arg_type = arg_type end if expression self.clause(expression, precedence, &action) else self.instance_exec(&action) end @default_arg_type = orig_dat if not orig_dat.nil? @grammar.curr_lhs = nil @curr_prec = nil end
This method uses lookahead sets and precedence information to resolve conflicts and remove unnecessary reduce actions.
@param [Boolean] do_lookahead Prune based on lookahead sets or not. @param [Boolean] do_precedence Prune based on precedence or not.
@return [void]
# File lib/rltk/parser.rb, line 1105 def prune(do_lookahead, do_precedence) terms = @grammar.terms # If both options are false there is no pruning to do. return if not (do_lookahead or do_precedence) each_state do |state0| ##################### # Lookahead Pruning # ##################### if do_lookahead # Find all of the reductions in this state. reductions = state0.actions.values.flatten.uniq.select { |a| a.is_a?(Reduce) } reductions.each do |reduction| production = @grammar.productions(:id)[reduction.id] lookahead = Array.new # Build the lookahead set. each_state do |state1| if self.check_reachability(state1, state0, production.rhs) lookahead |= self.grammar_prime.follow_set("#{state1.id}_#{production.lhs}".to_sym) end end # Translate the G' follow symbols into G # lookahead symbols. lookahead = lookahead.map { |sym| sym.to_s.split('_', 2).last.to_sym }.uniq # Here we remove the unnecessary reductions. # If there are error productions we need to # scale back the amount of pruning done. pruning_candidates = terms - lookahead if terms.include?(:ERROR) pruning_candidates.each do |sym| state0.actions[sym].delete(reduction) if state0.conflict_on?(sym) end else pruning_candidates.each { |sym| state0.actions[sym].delete(reduction) } end end end ######################################## # Precedence and Associativity Pruning # ######################################## if do_precedence state0.actions.each do |symbol, actions| # We are only interested in pruning actions # for terminal symbols. next unless CFG::is_terminal?(symbol) # Skip to the next one if there is no # possibility of a Shift/Reduce or # Reduce/Reduce conflict. next unless actions and actions.length > 1 resolve_ok = actions.inject(true) do |m, a| if a.is_a?(Reduce) m and @production_precs[a.id] else m end end and actions.inject(false) { |m, a| m or a.is_a?(Shift) } if @token_precs[symbol] and resolve_ok max_prec = 0 selected_action = nil # Grab the associativity and precedence # for the input token. tassoc, tprec = @token_precs[symbol] actions.each do |a| assoc, prec = a.is_a?(Shift) ? [tassoc, tprec] : @production_precs[a.id] # If two actions have the same precedence we # will only replace the previous production if: # * The token is left associative and the current action is a Reduce # * The token is right associative and the current action is a Shift if prec > max_prec or (prec == max_prec and tassoc == (a.is_a?(Shift) ? :right : :left)) max_prec = prec selected_action = a elsif prec == max_prec and assoc == :nonassoc raise ParserConstructionException, 'Non-associative token found during conflict resolution.' end end state0.actions[symbol] = [selected_action] end end end end end
This method is used to specify that the symbols in symbols are right associative. Subsequent calls to this method will give their arguments higher precedence.
@param [Array<Symbol>] symbols Symbols that are right-associative.
@return [void]
# File lib/rltk/parser.rb, line 1215 def right(*symbols) prec_level = @prec_counts[:right] += 1 symbols.map { |s| s.to_sym }.each do |sym| @token_precs[sym] = [:right, prec_level] end end
Changes the starting symbol of the parser.
@param [Symbol] symbol The starting symbol of the grammar.
@return [void]
# File lib/rltk/parser.rb, line 1228 def start(symbol) @grammar.start symbol end
Add a hook that is executed whenever sym is seen.
The sym must be a terminal symbol.
@param [Symbol] sym Symbol to hook into @param [Proc] proc Code to execute when the block is seen
@return [void]
# File lib/rltk/parser.rb, line 1240 def token_hook(sym, &proc) if CFG::is_terminal?(sym) @token_hooks[sym] << proc else raise 'Method token_hook expects `sym` to be non-terminal.' end end
Private Class Methods
Build a hash with the default options for Parser.finalize
and then update it with the values from opts.
@param [Hash{Symbol => Object}] opts Hash containing options for finalize.
@return [Hash{Symbol => Object}]
# File lib/rltk/parser.rb, line 211 def build_finalize_opts(opts) opts[:explain] = self.get_io(opts[:explain]) { explain: false, lookahead: true, precedence: true, use: false }.update(opts) end
Build a hash with the default options for Parser.parse
and then update it with the values from opts.
@param [Hash{Symbol => Object}] opts Hash containing options for parse.
@return [Hash{Symbol => Object}]
# File lib/rltk/parser.rb, line 229 def build_parse_opts(opts) opts[:parse_tree] = self.get_io(opts[:parse_tree]) opts[:verbose] = self.get_io(opts[:verbose]) { accept: :first, env: self::Environment.new, parse_tree: false, verbose: false }.update(opts) end
Public Instance Methods
Parses the given token stream using the encapsulated environment.
@see .parse
# File lib/rltk/parser.rb, line 1262 def parse(tokens, opts = {}) self.class.parse(tokens, {:env => @env}.update(opts)) end