Commits

Pierre-Marie de Rodat committed d9890e9

Enhance left recursive parsers detection with forward declarations

When looking for left recursive parsers, the algorithm memorize visited
forward declarations to check that they consume tokens before recursing over
itself. The previous implementation did the job but with too many recursive
calls for small grammars (see below).

This algorithm is enhanced in order to prove non left recursivity faster: it
keeps a list of forward declarations that are proved to be non left recursive
alongside with the already existing list of forward declaration found but not
checked yet. The optimisation goes when looking into “consuming” parts of
sequence parser combinations: we can then consider that already visited forward
declarations aren’t left recursive in recursive calls.

As very tiny benchmark, consider the grammar:

block = fwd()
expr = fwd()

expr.define(
(a('(') + expr + a(')')) |
(a('if') + expr + block))
stmt = (
(a('return') + expr) |
(a('while') + expr + stmt_block) |
expr)

block.define(many(stmt))

With the previous implementation, the left recursivity check used to call
itself 407 times for a recursive calling depth equal to 20.

With the new one, the calling count is 38 for a recursive calling depth equal
to 8.

  • Participants
  • Parent commits 9dd1920

Comments (0)

Files changed (1)

File src/funcparserlib/parser.py

             yield x
 
 
-def left_recursive(p, fwds=[], seqs=[]):
+def left_recursive(p, noprog_fwds=[], prog_fwds=[], seqs=[]):
     """Return a left-recursive part of parser `p` or `None`."""
     def any_(xs):
         for x in xs:
         return None
 
     if isinstance(p, (_Map, _Many, _Memoize)):
-        return left_recursive(p.p, fwds, seqs)
+        return left_recursive(p.p, noprog_fwds, prog_fwds, seqs)
     elif isinstance(p, _Fwd):
-        if p in fwds:
+        if p in noprog_fwds:
             return p
+        elif p in prog_fwds:
+            return None
         else:
-            return left_recursive(p.p, [p] + fwds, seqs)
+            return left_recursive(p.p, [p] + noprog_fwds, prog_fwds, seqs)
     elif isinstance(p, _Seq):
         if p in seqs:
             return None
             left = list(takewhile_included(lambda x: not makes_progress(x),
                                             p.ps))
             right = p.ps[len(left):]
-            return (any_(left_recursive(x, fwds, seqs) for x in left) or
-                    any_(left_recursive(x, [], [p] + seqs) for x in right))
+            return (any_(left_recursive(x, noprog_fwds, prog_fwds, seqs) for x in left) or
+                    any_(left_recursive(x, [], noprog_fwds + prog_fwds, [p] + seqs) for x in right))
     elif isinstance(p, _Alt):
-        return any_(left_recursive(x, fwds, seqs) for x in p.ps)
+        return any_(left_recursive(x, noprog_fwds, prog_fwds, seqs) for x in p.ps)
     else:
         return None