On Thu, Jan 17, 2019 at 2:56 AM Zelphir Kaltstahl < zelphirkaltst...@gmail.com> 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 co...@ccil.org 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