Re: Re parse-result

[John Cowan]

On Thu, Jan 17, 2019 at 2:56 AM Zelphir Kaltstahl <
address@hidden> wrote:

For example, what is the difference
> between PEG parsing and parser combinators?
>

Both of them do top-down parsing (try to match the top-level grammar rule,
which is
done by trying to match the lower-level rules which make it up, and so on
until we
get down to single tokens.  They differ in the amount of lookahead that's
provided.

Parser combinators are a facade over recursive-descent parsing, where you
write
a procedure corresponding to each rule in the parser, and you can only look
ahead
one token to guide parsing.  This is known as LL(1) parsing. It's very easy
to write
these procedures, so you don't really need an engine like yacc to do the
job.
One character of lookahead isn't usually enough, so there is a lower-level
lexer
that uses (typically) regular expressions to aggregate things like numbers
and
identifiers into single parsing tokens.

PEG parsing allows *infinite* lookahead, all the way to the end of the
input.
However, it memoizes the results of parsing to avoid reparsing repeatedly.
To make this possible, alternatives are ordered: instead of rules like A |
B,
where the first token has to be enough to tell you if you have an A or a B,
you have rules like A / B, which means "assume it's an A, and only if it
fails, assume it's a B".  If A and B overlap, non-PEG parsing has to treat
A | B as a grammar ambiguity and recover, but A / B is never ambiguous.

-- 
John Cowan          http://vrici.lojban.org/~cowan        address@hidden
You cannot enter here.  Go back to the abyss prepared for you!  Go back!
Fall into the nothingness that awaits you and your Master.  Go! --Gandalf