lib/walrat/parslet_sequence.rb

   1 # Copyright 2007-2010 Wincent Colaiuta. All rights reserved.
   2 # Redistribution and use in source and binary forms, with or without
   3 # modification, are permitted provided that the following conditions are met:
   4 #
   5 # 1. Redistributions of source code must retain the above copyright notice,
   6 #    this list of conditions and the following disclaimer.
   7 # 2. Redistributions in binary form must reproduce the above copyright notice,
   8 #    this list of conditions and the following disclaimer in the documentation
   9 #    and/or other materials provided with the distribution.
  10 #
  11 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  12 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  13 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  14 # ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
  15 # LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  16 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  17 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  18 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  19 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  20 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  21 # POSSIBILITY OF SUCH DAMAGE.
  22
  23 require 'walrat'
  24
  25 module Walrat
  26   class ParsletSequence < ParsletCombination
  27     attr_reader :hash
  28
  29     # first and second may not be nil.
  30     def initialize first, second, *others
  31       raise ArgumentError if first.nil?
  32       raise ArgumentError if second.nil?
  33       @components = [first, second] + others
  34       update_hash
  35     end
  36
  37     # Override so that sequences are appended to an existing sequence:
  38     # Consider the following example:
  39     #
  40     #     A & B
  41     #
  42     # This constitutes a single sequence:
  43     #
  44     #     (A & B)
  45     #
  46     # If we then make this a three-element sequence:
  47     #
  48     #     A & B & C
  49     #
  50     # We are effectively creating an nested sequence containing the original
  51     # sequence and an additional element:
  52     #
  53     #     ((A & B) & C)
  54     #
  55     # Although such a nested sequence is correctly parsed it produces unwanted
  56     # nesting in the results because instead of returning a one-dimensional
  57     # array of results:
  58     #
  59     #     [a, b, c]
  60     #
  61     # It returns a nested array:
  62     #
  63     #     [[a, b], c]
  64     #
  65     # The solution to this unwanted nesting is to allowing appending to an
  66     # existing sequence by using the private "append" method.
  67     #
  68     # This ensures that:
  69     #
  70     #     A & B & C
  71     #
  72     # Translates to a single sequence:
  73     #
  74     #     (A & B & C)
  75     #
  76     # And a single, uni-dimensional results array:
  77     #
  78     #     [a, b, c]
  79     def &(next_parslet)
  80       append next_parslet
  81     end
  82
  83     SKIP_FIRST  = true
  84     NO_SKIP     = false
  85
  86     def parse string, options = {}
  87       parse_common NO_SKIP, string, options
  88     end
  89
  90     def parse_remainder string, options = {}
  91       parse_common SKIP_FIRST, string, options
  92     end
  93
  94     def parse_common skip_first, string, options = {}
  95       raise ArgumentError if string.nil?
  96       state           = ParserState.new(string, options)
  97       last_caught     = nil   # keep track of the last kind of throw to be caught
  98       left_recursion  = false # keep track of whether left recursion was detected
  99
 100       @components.each_with_index do |parseable, index|
 101         if index == 0 # for first component only
 102           if skip_first
 103             next
 104           end
 105           begin
 106             check_left_recursion(parseable, options)
 107           rescue LeftRecursionException => e
 108             left_recursion  = true
 109             continuation    = nil
 110             value           = callcc { |c| continuation = c }
 111             if value == continuation        # first time that we're here
 112               e.continuation = continuation # pack continuation into exception
 113               raise e                       # and propagate
 114             else
 115               grammar   = state.options[:grammar]
 116               rule_name = state.options[:rule_name]
 117               state.parsed grammar.wrap(value, rule_name)
 118               next
 119             end
 120           end
 121         end
 122
 123         catch :ProcessNextComponent do
 124           catch :NotPredicateSuccess do
 125             catch :AndPredicateSuccess do
 126               catch :ZeroWidthParseSuccess do
 127                 begin
 128                   parsed = parseable.memoizing_parse state.remainder, state.options
 129                   state.parsed parsed
 130                 rescue SkippedSubstringException => e
 131                   state.skipped e
 132                 rescue ParseError => e
 133                   # failed, will try to skip; save original error in case
 134                   # skipping fails
 135                   if options.has_key?(:skipping_override)
 136                     skipping_parslet = options[:skipping_override]
 137                   elsif options.has_key?(:skipping)
 138                     skipping_parslet = options[:skipping]
 139                   else
 140                     skipping_parslet = nil
 141                   end
 142                   raise e if skipping_parslet.nil?  # no skipper defined, raise original error
 143                   begin
 144                     # guard against self references (possible infinite recursion) here?
 145                     parsed = skipping_parslet.memoizing_parse state.remainder, state.options
 146                     state.skipped(parsed)
 147                     redo              # skipping succeeded, try to redo
 148                   rescue ParseError
 149                     raise e           # skipping didn't help either, raise original error
 150                   end
 151                 end
 152                 last_caught = nil
 153
 154                 # can't use "next" here because it would only break out of
 155                 # innermost "do" rather than continuing the iteration
 156                 throw :ProcessNextComponent
 157               end
 158               last_caught = :ZeroWidthParseSuccess
 159               throw :ProcessNextComponent
 160             end
 161             last_caught = :AndPredicateSuccess
 162             throw :ProcessNextComponent
 163           end
 164           last_caught = :NotPredicateSuccess
 165         end
 166       end
 167
 168       if left_recursion
 169         results = recurse(state)
 170       else
 171         results = state.results
 172       end
 173
 174       return results if skip_first
 175
 176       if results.respond_to? :empty? and results.empty? and last_caught
 177         throw last_caught
 178       else
 179         results
 180       end
 181     end
 182
 183     # Left-recursion helper
 184     def recurse state
 185       return state.results if state.remainder == '' # further recursion is not possible
 186       new_state = ParserState.new state.remainder, state.options
 187       last_successful_result = nil
 188       while state.remainder != ''
 189         begin
 190           new_results = parse_remainder new_state.remainder, new_state.options
 191           new_state.parsed new_results
 192           last_successful_result = ArrayResult[last_successful_result || state.results, new_results]
 193         rescue ParseError
 194           break
 195         end
 196       end
 197       last_successful_result || state.results
 198     end
 199
 200     def eql?(other)
 201       return false if not other.instance_of? ParsletSequence
 202       other_components = other.components
 203       return false if @components.length != other_components.length
 204       for i in 0..(@components.length - 1)
 205         return false unless @components[i].eql? other_components[i]
 206       end
 207       true
 208     end
 209
 210   protected
 211
 212     # For determining equality.
 213     attr_reader :components
 214
 215   private
 216
 217     def hash_offset
 218       40
 219     end
 220
 221     def update_hash
 222       # fixed offset to avoid unwanted collisions with similar classes
 223       @hash = hash_offset
 224       @components.each { |parseable| @hash += parseable.hash }
 225     end
 226
 227     # Appends another Parslet, ParsletCombination or Predicate to the receiver
 228     # and returns the receiver.
 229     #
 230     # Raises if next_parslet is nil.
 231     # Cannot use << as a method name because Ruby cannot parse it without the
 232     # self, and self is not allowed as en explicit receiver for private
 233     # messages.
 234     def append next_parslet
 235       raise ArgumentError if next_parslet.nil?
 236       @components << next_parslet.to_parseable
 237       update_hash
 238       self
 239     end
 240   end # class ParsletSequence
 241 end # module Walrat