[HN Gopher] The Packrat Parsing and Parsing Expression Grammars ...
___________________________________________________________________
The Packrat Parsing and Parsing Expression Grammars Page
Author : gjvc
Score : 38 points
Date : 2022-02-19 09:50 UTC (2 days ago)
(HTM) web link (bford.info)
(TXT) w3m dump (bford.info)
| frabert wrote:
| I think PEG let people think they can get away from the
| complexities of grammars because there are no ambiguities when
| you express them using PEGs. This is not true: the ambiguities
| are still there, and you still have to think about them,
| otherwise PEGs will generate "garden path" parses that make no
| sense. I think the sweet spot for parsing medium and high
| complexity languages is autogenerated lexer + handwritten
| recursive descent.
| chrisseaton wrote:
| > people think they can get away from the complexities of
| grammars because there are no ambiguities when you express them
| using PEGs. This is not true: the ambiguities are still there
|
| It's literally impossible to write a PEG with an ambiguity. So
| I don't know what you mean?
| frabert wrote:
| Just because the PEG doesn't have ambiguities doesn't mean
| the grammar you _meant_ to recognize doesn 't have one. What
| I mean is: PEGs give you a false sense of confidence by
| making you feel like you solved all your grammar's issues. In
| reality, you need to think really carefully about what your
| PEG is doing, because it's not going to warn you. As you
| said, PEGs are never ambiguous.
| chrisseaton wrote:
| Well yeah if the grammar you wrote doesn't match what you
| intended to write then it's not going to work.
|
| Not sure how that's saying anything useful though? If you
| write the wrong grammar with any parsing system it's also
| not going to work.
| frabert wrote:
| Most other parser generator systems give you indication
| that what you're writing is probably wrong, by stating
| e.g. that a grammar is ambiguous.
|
| S := A '+' A | A '*' A
|
| A := ...
|
| If you do that in most PEG systems I've tried, you're
| just going to get the wrong result with no indication of
| what might have gone wrong, unless you know where to
| look.
| chrisseaton wrote:
| But that's the point - other parsing systems let you
| design an ambiguous language and then tell you about it.
| PEGs _don 't let you design an ambiguous language in the
| first place_. Unambiguous by construction.
| HelloNurse wrote:
| Ambiguities in the intended language aren't literally "still
| there" in the PEG, but realistically they are "still there"
| as a source of problems: naive PEGs can remove ambiguities
| incorrectly in less than obvious ways, and figuring out
| what's wrong can be more difficult than hitting a brick wall
| with other parsing approaches.
| jules wrote:
| PEGs are a compact notation for recursive descent and they
| compile to recursive descent parsers. What would be the
| advantage of writing the compiled code by hand?
| vidarh wrote:
| Few parser generators do well on things like error reporting
| in a human friendly manner. In effect production parsers
| tends to end up being hand written or extensively hand-
| modified for that reason. I wish more work on parser
| generators would involve focusing on better diagnostics (for
| end users, not the parser developer) and reporting rather
| than making them easier to use for the parser writers, as
| "just" writing the parser is rarely the hard part.
|
| EDIT: Even making it easier to annotate the parser
| specifications to improve error reporting would be an
| improvement for many parser generators. In the past I've
| experimented with parser generators that included a prolog-
| inspired "cut" like operator that stops further backtracking,
| and that'd take an error message to output if nothing further
| can be matched without backtracking. It'd prevent the parser
| from "escaping" out of a likely human error and end up
| reporting a failure to match productions much higher up. It
| worked fairly well, and mimics what human parser writers
| tends to do in recursive descent parsers - we'll often guess
| at the likely error based on context deep down and bail out.
| convolvatron wrote:
| why would you recommend using a generated lexer? the machinery
| is so simple thats its generally not worth trying to deal with
| the plumbing, esp around types.
| orlp wrote:
| If you think PEG parsers are a good idea and we should use them,
| comment below which strings this PEG grammar matches:
| Str = "a" Str "a" / "a"
|
| If you get it right and you understand the logic, by all means
| use them. If you get it wrong or can't wrap your head around how
| it works despite knowing the answer, maybe reconsider.
|
| EDIT: since my point was too subtle and I have been misunderstood
| and downvoted as a result of it, allow me to give a hint. If you
| believe the above grammar matches aaaaa you fall in the latter
| category. It does not. Yes, aaa matches, aaaaaaa matches, but
| aaaaa does not. Yes, this is mind-boggling.
| yortus wrote:
| Why not just write it more simply as Str =
| "a" "aa"*
|
| Most languages allow writing tortured and hard to understand
| logic where simpler alternatives can also be written. I'm not
| sure why that should make people consider not using them.
| bruce343434 wrote:
| The parse tree from that would be different, though it would
| match the same strings.
| orlp wrote:
| Incorrect, it does not match the same strings.
| orlp wrote:
| Because that does not recognize the same set of strings. That
| matches aaaaa, but my example above does not. That is exactly
| the point I'm trying to make.
| tonyg wrote:
| Well, if you wanted all odd-length strings, you'd write
| what GP wrote. If you wanted whatever it was your grammar
| accepted, you'd write what you wrote :)
| orlp wrote:
| > If you wanted whatever it was your grammar accepted
|
| It is one-line, two-rule PEG grammar. What does it
| accept, and why? If we can't state this with confidence
| in such a tiny example, what makes us have any confidence
| in larger, more complex grammars? We should understand
| our tools. PEG pretends to be simple and understandable,
| but it's much less so than it might seem on the surface.
| tonyg wrote:
| Simple rules can give surprising, complex behaviour.
|
| That's a good point. Unfortunately, it's also true not
| only of PEGs and recursive-descent parsing, but also of
| essentially every parsing formalism out there. So it
| doesn't seem to disqualify PEGs in particular.
|
| (It's also true of programming languages generally: For
| which inputs does Collatz halt, and why?)
| bmn__ wrote:
| I contest that. The parsers based on the formalism of CFG
| do not have that problem. The straightforward mental
| model of the user always matches their behaviour, no
| complexity, no surprises.
| tonyg wrote:
| This is a good example of a theoretical problem with PEGs. It
| also applies (of course) to recursive descent parsers. I don't
| think this problem is a practical issue, though; I can't speak
| for others, but this kind of problem hasn't come up in practice
| for me. PEGs do cause other headaches from time to time, but
| are still head-and-shoulders easier to get right than other
| styles of working with grammars.
| jules wrote:
| This is a good point in favour of context free grammar based
| parser generators. I think the trade-off is a bit more subtle
| though.
|
| CFG semantics is nice and declarative when we specify which
| strings belong to the language, but a parser is a function from
| strings to parse results, and then the nice semantics stops
| working due to ambiguities. The PEG semantics on the other hand
| naturally expresses such a function, and the function you get
| with PEG semantics is almost always the function you want.
|
| When we look at character level grammars, the CFG formalism
| doesn't work well either. They fundamentally rely on greedy
| lexical token matching.
|
| Extensions such as indentation sensitive parsing and user
| defined operators quite naturally fit into PEG style semantics,
| and are more difficult to integrate into CFGs.
|
| CFG based parser generators are way more complicated internally
| than PEG based parser generators, which are extremely simple.
| orlp wrote:
| > The grammar may not be exactly what you want to illustrate
| your point (I think you want to swap the two sides of the /)
|
| No, I think you might be misunderstanding my point. For
| example, if you think the grammar I posted matches aaaaa,
| you'd be wrong.
| jules wrote:
| Yes you're right, I had already edited that while you were
| posting your reply. I thought you wanted to point out the
| usual simple "a" / "aa" problem.
| myrmidon wrote:
| This is a really nice example, but I feel that it comes to an
| unfair conclusion.
|
| I'll concede that this appears counterintuitive, but I feel
| that cases like this most often just pop up because people have
| been "overexposed" to EBNF/CFGs before and write PEG grammars
| with wrong preconceptions (also often ending in "left
| recursion" confusion, but that at least gives early errors).
|
| But I still think that it is much preferable to debug/rewrite a
| questionable PEG grammar than e.g. a cobbled-together mess of
| conditionals and regular expressions...
|
| But now I'm really interested in what you're advocating for
| instead? CFG parser frameworks? Or learning how to write the
| parser by hand? Or learning about PEGs until your example is
| understood?
| samatman wrote:
| I work with PEGs every working day of my life. When I saw your
| example, it immediately gave me a chuckle, so thank you for
| that.
|
| Does that mean I'd spot the same gotcha deep in some grammar I
| was working on? No of course not, that would never happen. It's
| going to be some other mistake that makes me feel like an idiot
| after staring at the screen for several hours.
|
| Parsers are designed around data, not conundrums. For
| structured languages, PEGs are a sharp and simple tool for
| slicing them up. But they're not great at solving the Liar's
| Paradox.
| bruce343434 wrote:
| Well, it seems simple. But from your tone I'm guessing it's
| not? a: (a) aaa: (a(a)a)
| aaaaa: (a(a(a)a)a) etc
| jules wrote:
| I think it will parse "a", it will parse "a a a", and "aaa a
| aaa", and "aaaaaaa a aaaaaaa" and so on, but nothing else.
| edflsafoiewq wrote:
| The problem for aaaaa is it gets to this parse
| (a(a(a(a)a)
|
| and can't complete the (aXa) parse for the second a, so it
| backtracks to try the (a) parse (a(a)
|
| The issue is since the parse of the third a as (a(a)a)
| succeeded, it will never try the (a) parse for the third a.
| orlp wrote:
| That is incorrect. Feel free to try it here:
| https://pegjs.org/online, you will see that aaaaa is not a
| match. And no, that is not a bug in pegjs.
| drothlis wrote:
| I can't wrap my head around it. Why doesn't it work?
|
| It parses this: a a aaa a a But not this: a aaa a
| jules wrote:
| The right mental model for PEGs is not whether or not it
| will parse the entire string. PEGs will attempt to parse
| some prefix of the string and then stop and leave the
| cursor there. Here is a list of strings and how far it
| will parse (hopefully correct): a|
| a|a aaa| a|aaa aaa|aa
| aaaaa|a aaaaaaa| a|aaaaaaa
| aaa|aaaaaa aaaaa|aaaaa aaaaaaa|aaaa
| aaaaaaaaa|aaa aaaaaaaaaaa|aa
| aaaaaaaaaaaaa|a aaaaaaaaaaaaaaa|
| a|aaaaaaaaaaaaaaa aaa|aaaaaaaaaaaaaa
| aaaaa|aaaaaaaaaaaaa aaaaaaa|aaaaaaaaaaaa
| aaaaaaaaa|aaaaaaaaaaa
|
| Consider your example aaaaa. The PEG will parse the first
| a, and then the recursive call will parse from a|aaaa.
| Now the next recursive call will eventually fail.
| Therefore the first recursive call will only parse one a,
| and then return back to the initial call which will parse
| another a. So the final state is aaa|aa.
|
| At a high level, the reason for this behaviour is that
| PEGs are greedy. The inner recursive calls will always
| parse as much as they can, without regard for the outer
| calls that still want to parse more a's.
| drothlis wrote:
| > The PEG will parse the first a, and then the recursive
| call will parse from a|aaaa. Now the next recursive call
| will eventually fail.
|
| Thanks for taking the time & effort to explain! I know
| you're right because I have reproduced this behaviour in
| 2 parser generators now (pegjs & grako).
|
| Why does the next recursive call fail? (Don't answer, I
| think I've worked it out.)
|
| Isn't it supposed to backtrack: 1. a|a
| a a a 2. a a|a a a 3. a a a a a| <-
| "succeeds" but doesn't leave any more input for the outer
| parses 3. a a a|a a <- doesn't it backtrack and
| try the other choice? 2. a a a a|a 1. a a
| a a a|
|
| I guess it's because the backtracking doesn't happen at
| recursion level 3 (because it already thinks it
| succeeded) but at level 2: 1. a|a a a a
| 2. a a|a a a 3. a a a a a| 2. a a|a a a
| <- tries the other choice 1. a a a|a a
|
| Let's see if my explanation holds for aaaaaaa:
| 1. a|a a a a a a 2. a a|a a a a a 3. a a
| a|a a a a 4. a a a a|a a a 5. a a a a a a
| a| <- "succeeds" but doesn't leave any more input for
| the outer parses 4. a a a a|a a a <- tries the
| other choice 3. a a a a a|a a 2. a a a a
| a a|a 1. a a a a a a a|
|
| Geez.
|
| Well, now I'm grateful I've never had to implement a
| parser for anything more complicated than a Lucene-style
| query syntax.
| jules wrote:
| Yes I think that's right :) I think I have a way to
| visualize what's happening more clearly than the |
| notation I used above.
|
| We have grammar: S -> 'a' S 'a' / 'a'
|
| I'm going to put (aSa) around parses of the first
| alternative and <a> for the second alternative. So a
| successful parse would look like (a(a<a>a)a).
|
| Here's what the PEG parser will do for aaaaa. It will
| first recurse all the way down, trying the first
| alternative at every point: (a(a(a(a(a
| ^
|
| The choice indicated by ^ will fail because it is
| expecting another 'a', so that choice will be
| backtracked, and it will replace the ( with < at that
| position: (a(a(a(a<a> ^
|
| Now it will backtrack over that ^ choice and replace the
| ( with < at that position: (a(a(a<a>a)
| ^
|
| Now comes the key point: the next thing it backtracks
| over is the second ( and NOT the third (, because the
| third ( actually succeeded. So it has skipped over one
| extra layer.
|
| Now it will parse: (a<a>a)aa
|
| This one succeeded, and consumed 3 characters. The rest
| of the input is then still to be parsed by productions
| further up the stack, but since this S is the main
| production of the grammar, we declare failure because the
| whole input was not consumed.
|
| In general, after backtracking, a bunch of ('s may
| initially seem to succeed, and then when it fails it will
| backtrack over all those, rather than over just one of
| them.
|
| For your larger example: (a(a(a(a(a(a(a
| ^ (a(a(a(a(a(a<a> ^
| (a(a(a(a(a<a>a) ^
| (a(a(a<a>a)a)a)
|
| So this one does parse the whole input.
|
| > Well, now I'm grateful I've never had to implement a
| parser for anything more complicated than a Lucene-style
| query syntax.
|
| Interestingly, these problems don't seem to come up in
| practice. But things like this are still a good argument
| for LR/GLR parsers: LR parsers will report the conflict
| at grammar compilation time, and GLR parsers will
| backtrack with all possible choices, so they will parse
| the way you'd expect. They are certainly the more
| principled choice. But in practice it may not matter that
| much in practice because people don't seem to use these
| kind of grammars, at least not for programming languages.
| bmh wrote:
| I love PEGs, but their error messages are usually vague, because
| it will backtrack out of a deep tree (where it should have
| discovered the actual error), and then presents an error much
| higher up ("computer says no").
|
| Is there a mechanism that works well for improving errors in PEGs
| (i.e. something like a non-returnable node), and how does one
| practically implement that?
| tolmasky wrote:
| In an implementation I made ages ago, I created a different
| operator, the "naughty or", which defines "invalid" syntax
| paths (for example, if the entire parse fails, allow going into
| the branch that _does_ match identifiers that start with a
| number). This adds a language-level facility for a strategy I
| see most hand-rolled parsers end up in, which is to start
| parsing common mistakes to be able to provide better errors.
| It's basically "free" because those paths are only explored if
| the parse is known to fail, so performance of successful parses
| isn't affected, and allows the same level of "craft" in error
| messages as a hand-rolled one. It also allows people to easily
| submit patches to improve confusing errors they've gotten.
|
| https://github.com/tolmasky/language
| drothlis wrote:
| > Is there a mechanism that works well for improving errors in
| PEGs (i.e. something like a non-returnable node)
|
| Yes, it's called the "cut operator".
|
| > how does one practically implement that?
|
| Pick a parser generator that supports it natively. ;-) If
| you're talking about implementing the parser generator yourself
| then you probably already know more about it than I do.
| bmh wrote:
| Thanks! I see the <cut> operator is actually explained in an
| older HN post: https://news.ycombinator.com/item?id=20502032
| vidarh wrote:
| It's fascinating how many times the Prolog cut operator has
| been borrowed into parsing. It shouldn't be surprising,
| probably, given how easily lookahead leads people down the
| path of some backtracking mechanism or other for ease of
| implementation, and how ingrained the idea of a cut to stop
| backtracking is if you've ever been exposed to Prolog...
| throwaway81523 wrote:
| I think CPython (as of 3.10?) uses a PEG parser now. That is not
| mentioned on the page.
___________________________________________________________________
(page generated 2022-02-21 23:02 UTC)