Skip to content
Browse files

. A complete hack job, but this runs lrecursive.rb

  • Loading branch information...
1 parent 6b5c33a commit bd64443cf512cc8d31fb928149c97ba3115b78c9 @kschiess committed
Showing with 105 additions and 4 deletions.
  1. +30 −0 experiments/lrecursive.rb
  2. +5 −2 lib/parslet/atoms/base.rb
  3. +66 −0 lib/parslet/atoms/context.rb
  4. +4 −2 lib/parslet/atoms/entity.rb
View
30 experiments/lrecursive.rb
@@ -0,0 +1,30 @@
+# An example that explores left recursion. This ruthlessly reopens parslets
+# internals and should not be used in production. I am however working on
+# something like this that will see a real release someday.
+
+$:.unshift File.dirname(__FILE__) + "/../lib"
+
+require 'pp'
+require 'parslet'
+require 'parslet/convenience'
+
+class SimpleLang < Parslet::Parser
+ # root(:b)
+ #
+ # # either any number of 'a's or a 'b'
+ # rule(:b) { c | e }
+ # rule(:c) { d }
+ # rule(:d) { b | str('a') }
+ # rule(:e) { str('b') }
+
+ root(:exp)
+ rule(:exp) { foo >> str('-') >> num | foo >> str('+') >> num | num }
+ rule(:foo) { exp }
+ rule(:num) { match['0-9'].repeat(1) }
+end
+
+# p SimpleLang.new.parse_with_debug('aaaa')
+# p SimpleLang.new.parse_with_debug('a')
+# p SimpleLang.new.parse_with_debug('b')
+
+p SimpleLang.new.parse_with_debug('1+2')
View
7 lib/parslet/atoms/base.rb
@@ -70,14 +70,17 @@ def apply(source, context) # :nodoc:
old_pos = source.pos
result = context.cache(self, source) {
+ p [:try, self, source.pos]
try(source, context)
}
# This has just succeeded, so last_cause must be empty
unless result.error?
+ p [:success, self, result.result]
@last_cause = nil
return result
end
+ p [:rollback, self]
# We only reach this point if the parse has failed. Rewind the input.
source.pos = old_pos
@@ -228,8 +231,6 @@ def cause? # :nodoc:
def error_tree
Parslet::ErrorTree.new(self)
end
-private
-
# Produces an instance of Success and returns it.
#
def success(result)
@@ -243,6 +244,8 @@ def error(source, str, pos=nil)
Fail.new(@last_cause)
end
+private
+
# Signals to the outside that the parse has failed. Use this in conjunction
# with #format_cause for nice error messages.
#
View
66 lib/parslet/atoms/context.rb
@@ -6,6 +6,8 @@ module Parslet::Atoms
class Context
def initialize
@cache = Hash.new { |h, k| h[k] = {} }
+ @growing = []
+ reset_call_stack
end
# Caches a parse answer for obj at source.pos. Applying the same parslet
@@ -36,6 +38,70 @@ def cache(obj, source, &block)
source.pos = beg + advance
return result
end
+
+ def stack(parslet, source, name)
+ p [:trying, source.pos, parslet, @stack, @growing]
+ pos = source.pos
+ if pos != @stack_pos
+ reset_call_stack(pos)
+ end
+
+ if @growing.include?(name)
+ p [:growing_include, @growing]
+ return parslet.success(nil)
+ end
+
+ if @stack.include?(name)
+ p [:detected, @stack]
+ @act_on_pop << name
+ return parslet.error(source, 'Direct or indirect recursion: #{@stack.inspect}.')
+ end
+
+ @stack.push name
+
+ res = yield
+
+ if @stack_pos==pos && @stack.last == name
+ @stack.pop
+ p [:pop, @stack, @act_on_pop]
+ if @act_on_pop.last == name
+ # This is probably the start of the recursion.
+ @act_on_pop.pop
+ return res if res.error?
+
+ # First result
+ p [:growing, res]
+ results = [:sequence, res.result]
+
+ @growing << name
+
+ # Now try to grow this:
+ loop do
+ p [:growing_inter, results]
+ reset_call_stack(source.pos)
+ @stack << name
+ res = yield
+ break if res.error?
+
+ results << res.result
+ end
+
+ if @growing.include?(name)
+ @growing = @growing.delete_if { |e| e==name }
+ end
+
+ return parslet.success(results)
+ end
+ end
+
+ res
+ end
+
+ def reset_call_stack(pos=0)
+ @act_on_pop = []
+ @stack = []
+ @stack_pos = pos
+ end
private
def lookup(obj, pos)
View
6 lib/parslet/atoms/entity.rb
@@ -18,7 +18,9 @@ def initialize(name, &block) # :nodoc:
end
def try(source, context) # :nodoc:
- parslet.apply(source, context)
+ context.stack(self, source, name) do
+ parslet.apply(source, context)
+ end
end
def parslet
@@ -32,7 +34,7 @@ def to_s_inner(prec) # :nodoc:
end
def error_tree # :nodoc:
- parslet.error_tree
+ @error_tree ||= parslet.error_tree
end
private

0 comments on commit bd64443

Please sign in to comment.
Something went wrong with that request. Please try again.