I feel a need for some clarifications concerning Mouse. The theory
behind my approach is contained in
http://mousepeg.sourceforge.net/Documents/RecursiveAscent.pdf still
under review by Fundamenta Informaticae. The implementation of
"recursive ascent" boils down to construction of "dual grammar" that is
identical to the given grammar except for parts involved in left
recursion. The dual grammar is not left-recursive, and recursive-descent
parse according to that grammar constructs syntax tree according to the
given grammar. I believe to have demonstrated that: (1) The dual grammar
is not left-recursive if and only if the given grammar does not contain
"cycles", of which the simplest example is A -> A | "a". (2) The
language accepted by dual grammar is identical to that accepted by the
original grammar, for an arbitrarily complex structure of left
recursion. Mouse treats the dual grammar as PEG and transcribes it into
a recursive-descent parser with limited backtracking. There would be no
problem with using packrat technology, but according its name Mouse is
not a pack rat. Contrary to the theory explained above, the parser does
not construct syntax trees, but gives the designer a possibility to
specify semantic actions for individual expressions. If required, they
may be used to output a syntax tree.
Regards
Roman
On 2020-07-18 03:36, Luke Hutchison wrote:
I should also point out that I noticed the other thread on this list
about Mouse by Roman Redz ('[PEG] Left recursion in "Mouse" '). Mouse
solves left recursion the same way as the pika parser, by parsing
bottom-up. I believe this hybrid approach may actually be a
better solution in general than the pika parser, because of its higher
efficiency, and even before I posted to this PEG list I had already
started thinking about doing something very similar. However, at least
when I first looked at Mouse, I didn't understand all the implications
of the Mouse heuristics for bottom-up parsing of left-recursive rules
(in particular, how it would work with multiple nested loops around
cycles in the grammar), and I had previously arrived at some very
different heuristics for solving this problem, involving pushing onto
a stack of nested cycles. I need to implement my alternative to Mouse
to see if the heuristics do in fact work, then compare to Mouse.
All the best,
Luke
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
