[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Re parse-result

From: John Cowan
Subject: Re: Re parse-result
Date: Thu, 17 Jan 2019 14:47:59 -0500

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

Parser combinators are a facade over recursive-descent parsing, where you
a procedure corresponding to each rule in the parser, and you can only look
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
One character of lookahead isn't usually enough, so there is a lower-level
that uses (typically) regular expressions to aggregate things like numbers
identifiers into single parsing tokens.

PEG parsing allows *infinite* lookahead, all the way to the end of the
However, it memoizes the results of parsing to avoid reparsing repeatedly.
To make this possible, alternatives are ordered: instead of rules like A |
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        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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]