News for hackers. Stuff that matters.
Re:Ohm: Parsing Made Easy by shalabhc on Tuesday October 17, 2017 @12:01PM (#15492035)
Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?
Re:Ohm: Parsing Made Easy by victorNicollet on Tuesday October 17, 2017 @01:12PM (#15492686)
Ambiguity means different things to CF and PE grammars. For CF it is obvious: two derivations are possible for a given string (or prefix, depending on your flavor).

But for a PE grammar, it's harder to define. It's not "an ambiguity in the equivalent CF grammar" because what does equivalent mean ? Same derivations ? Then it's not ambiguous, because PEG only allows single derivations. Same rules ? It's obvious that you can't treat a PE grammar as if it were CF and still expect it to work.

I believe the actual problem isn't ambiguity, but rather brittleness. What transformations can be applied to a grammar while keeping the same meaning ? In other words, how easily can it be refactored ?

Consider this small grammar:

    STATEMENT -> DEF | EXPR | VARDEF
    DEF    -> ('int' | 'bool') ID ('=' EXPR)?
    VARDEF -> 'var' ID '=' EXPR
    
In a context-free grammar, you have mathematical proof that you can convert the above to this cleaner version without altering the meaning:

    STATEMENT -> DEF | DECL | EXPR 
    DECL -> ('int' | 'bool') ID
    DEF  -> ('int' | 'bool' | 'var') ID '=' EXPR
In a parsing expression grammar, this conversion might change the meaning, depending on what EXPR can recognize.

Personally, I'd rather deal with shift/reduce conflicts than try to determine, by hand, whether a minor refactoring of my grammar will cause some obscure edge case to be parsed differently.

Re:Ohm: Parsing Made Easy by tomp on Tuesday October 17, 2017 @12:06PM (#15492077)
Possible? Maybe.

But the problem is more that, (according to Wikipedia), the choice operator in PEGs (i.e. e1 | e2) is in fact defined as ordered choice, i.e. it prefers the first alternative.

They try to sell this as a "solution" to ambiguous grammars, as an advantage, but they're just ... wrong. It's as if Java, when resolving method overloading, arbitrarily prefered the method that's declared first in the source file, instead of refusing to compile ambiguous code, as it does now.

Re:Ohm: Parsing Made Easy by chrisseaton on Tuesday October 17, 2017 @12:31PM (#15492312)
> They try to sell this as a "solution" to ambiguous grammars

But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other. There's no need for scare quotes! It is a solution that removes ambiguity. There is no longer any ambiguity, and there's nothing 'vague' at all about a rule as simple and clear as this.

> but they're just ... wrong

You'll have to give a more convincing argument than that if you want to persuade people!

> It's as if Java, when resolving method overloading, arbitrarily prefered the method that's declared first in the source file, instead of refusing to compile ambiguous code, as it does now

But if you had this rule, then the code isn't ambiguous any more is it? It has a well-defined way to decide which method to use, which everyone can understand and implement.

Re:Ohm: Parsing Made Easy by haberman on Tuesday October 17, 2017 @01:02PM (#15492584)
> But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other.

Sure it's no longer ambiguous to the computer. But the important question is: is it ambiguous to a human?

Take the "dangling else" problem. What does this mean in C?

   if (a)
   if (b) f();
   else g();
If you defined your grammar with a PEG, the answer is: whichever alternative you put first (if-with-else or if-without-else). But that answer doesn't help someone actually trying to use your language unless they go and read your PEG. What user wants to do that?

Worse, it keeps language designers from being aware when they accidentally put gotchas like this into their languages. The PEG tools can't warn you, because to a PEG tool there is no problem. As a real-world example of this, it was not discovered that ALGOL 60 had a "dangling else" ambiguity until the language had already been published in a technical report. A CFG-based tool could have warned the designers about the ambiguity, but with PEG-based tools you are designing blind.

Re:Ohm: Parsing Made Easy by victorNicollet on Tuesday October 17, 2017 @01:27PM (#15492809)
Ambiguity of a grammar is rather unrelated to how surprising it can be to a human. Something like TypeScript:

    var a = { label: f() };
    () => { label : f() };
These constructs look similar, but one is an object literal and the other is a block with a useless label. All of this can be implemented as an unambiguous context-free grammar.

Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective, if only because of the difference between how a human understands the grammar (pattern-based) and how EBNF expresses it (prefix-based).

Re:Ohm: Parsing Made Easy by haberman on Tuesday October 17, 2017 @01:47PM (#15492988)
This is a red herring. Context-free grammar tools don't solve the problem of keeping a language from ever being confusing. However they do solve the problem of allowing literal ambiguity into your language.

Ambiguity is strictly worse than confusion. Ambiguity means you have to communicate more information to your users: when two parses are both syntactically valid, which one does the language actually choose?

Re:Ohm: Parsing Made Easy by tomp on Tuesday October 17, 2017 @05:15PM (#15495021)
> Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective

Well yeah, obviously, that's like relying on unittests and type system to keep your program bug free... I mean, neither can guarantee your program is going to work, but either failing means that it almost certainly won't work (well).

Re:Ohm: Parsing Made Easy by chrisseaton on Tuesday October 17, 2017 @01:05PM (#15492614)
Your example seems to support my argument, not yours!

Dangling else's are solved by formally expressing a fixed priority in the grammar.

> unless they go and read your PEG

Well yes they need to read the documentation for the language... how else were they managing to write a program in it? How is it any difference from having to read the documentation to understand the precedence of different operators?

Re:Ohm: Parsing Made Easy by haberman on Tuesday October 17, 2017 @01:17PM (#15492718)
Dangling else is solved by changing the definition of the language. Newer languages don't have the dangling else problem, because we learned the hard way in the 60s how to avoid it.

PEG-based tools invite more mistakes like this, because they can prevent the discovering of ambiguities until it is too late to fix them.

Yes, operator precedence is another example of ambiguity: we live with it because infix math is useful enough that we live with the fact that you have to learn the precedence rules. But with PEG-based tools, you can accidentally introduce ambiguities that might be easy to avoid if you just knew about them at the design stage.

I would never design a language with PEG-based tools, because I would have no idea where I might be introducing pointless ambiguity.

Re:Ohm: Parsing Made Easy by chrisseaton on Tuesday October 17, 2017 @01:20PM (#15492755)
> prevent the discovering of ambiguities

But there are no ambiguities to discover if you use a PEG! A language grammar defined using PEG cannot be ambiguous!

Re:Ohm: Parsing Made Easy by haberman on Tuesday October 17, 2017 @01:40PM (#15492919)
It's very strange that you keep returning to this. "Dangling else" is a problem regardless of how you write down your grammar or implement your parser.

It's like sweeping a mound of dirt under the rug and then saying "by definition, there is no dirt on the rug!"

Re:Ohm: Parsing Made Easy by chrisseaton on Tuesday October 17, 2017 @01:48PM (#15493003)
I guess I just can't understand where you are coming from then.

Someone said that PEGs don't solve ambiguous grammars. I said that's wrong - they do - they are no longer ambiguous. Now people are arguing about having to understand the grammar and how languages should be designed and things like that? Seems irrelevant to me.

I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous. If you define your language using a PEG you will never have any ambiguity in your grammar. Seems solved to me!

Re:Ohm: Parsing Made Easy by tomp on Tuesday October 17, 2017 @05:27PM (#15495137)
> do PEGs make solve the problem of ambiguous grammars. Yes they do

That's a problem noone ever had.

By this definition, even grammars generated by yacc and Bison (LR parser generators) aren't ambiguous - even if there are conflicts a working parser will be produced. They even resolve conflicts in a "sensible" way - shift/reduce conflicts are resolve in favour of shift (i.e. longest match - like regexes) whereas reduce/reduce conflicts are resolved in favour of the earlier rule (like PEGs). Hell, I even left one shift/reduce conflict unresolved in a parser I wrote a few days ago (amply documented, of course), because I know precisely where the ambiguity, no, confusion stems from, and I decided that rewriting the grammar to resolve the conflict explicitly would be too much work and would make the grammar much less readable.

So I really see no point in PEGs (except possibly ease of use). LR parser generators apply more-or-less the same conflict resolution, except that they will proactively warn you about where your grammar is, or could be, confusing.

Re:Ohm: Parsing Made Easy by haberman on Tuesday October 17, 2017 @01:55PM (#15493073)
> I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous.

Everyone understands that. We all agree that this is formally true: PEG grammars have no ambiguity. No one is disputing that.

The question is whether the convention of ordered choice is useful. Does it solve conceptual ambiguities?

Take tomp's example: imagine that we changed Java to resolve overloaded functions differently. Right now Java will throw an error if two overloaded functions both match a call site. Imagine that Java was changed to successfully compile the file, and resolved the ambiguity by arbitrarily picking the first matching function.

Now there is no ambiguity! Just like PEGs! But is this behavior useful? I would rather know about the ambiguity, and have the compile fail.

Re:Ohm: Parsing Made Easy by yxhuvud on Tuesday October 17, 2017 @12:54PM (#15492510)
It is a "solution" because it becomes unobvious what language it will parse, not because it doesn't resolve the ambiguity.
Re:Ohm: Parsing Made Easy by chrisseaton on Tuesday October 17, 2017 @12:56PM (#15492536)
I can't see why that would be the case. When I read the grammar I can see the choice operators and I know they have priority. What is unobvious about that?
Re:Ohm: Parsing Made Easy by shalabhc on Tuesday October 17, 2017 @12:21PM (#15492213)
I'm aware of ordered choice in PEGs. I'm not entirely convinced that's a real problem in practice (or am missing some compelling example). E.g. regular expressions can be ambiguous too, but are still used very extensively and people tend to not complain about them. Is longest match - a common resolution to multiple matches in regexps - also problematic?

I'm also wondering if this specific complaint wrt ambiguity can be easily addressed by just implementing an analyzer that identifies ambiguities in a PEG grammar by evaluating `|` as alternative choice.

Re:Ohm: Parsing Made Easy by yxhuvud on Tuesday October 17, 2017 @12:30PM (#15492300)
Regarding your regexp question, it depends on what implementation of regexp you use. If you go by the formal definition and the state machine parsers optimized for that, then multiple matches is not problematic for finding the longest match. It can be if using some common extensions though, that change the running time to exponential. See https://blog.codinghorror.com/regex-performance/ for example.
Re:Ohm: Parsing Made Easy by shalabhc on Tuesday October 17, 2017 @12:42PM (#15492407)
I'm not talking about performance though. I'm talking about the fact that when given an ambiguous regexp, most engines match it happily and return the longest match, instead of erroring out saying 'ambiguous input provided'. This is not considered problematic in practice (or I don't hear criticisms about this at least).

Contrast with the the criticism of PEGs - that they don't report 'ambiguous input' but just go ahead and match using ordered choice.

Re:Ohm: Parsing Made Easy by yxhuvud on Tuesday October 17, 2017 @12:57PM (#15492547)
Ah, that is what you mean.

Then the answer is that they are used for different things. PEGs are typically used to parse a string, while regexps are typically used to recognize a pattern.

Where regexps are used for parsing, then ambiguity is definitely a problem that very often will have to be resolved by rewriting the regexp to be less accepting.

Re:Ohm: Parsing Made Easy by tomp on Tuesday October 17, 2017 @01:00PM (#15492574)
In practice, most Regexes fit on a line, and while not trivial to read, they don't involve a deep tree-like structure. Grammars, on the other hand, do, and ambiguity can be very sublte.
Re:Ohm: Parsing Made Easy by nerdponx on Tuesday October 17, 2017 @02:31PM (#15493444)
Is ordered a choice a necessary property for PEG parsing? Maybe PEG parser generators should have an "unordered mode".
Re:Ohm: Parsing Made Easy by victorNicollet on Wednesday October 18, 2017 @03:49AM (#15497566)
In practice, they should distinguish between / (I meant this alternative to be ordered, because I care about something) versus | (no ordering required, because I know only one choice will ever be picked), and come up with a way to determine that a | generates an ambiguity.
Re:Ohm: Parsing Made Easy by yxhuvud on Tuesday October 17, 2017 @12:19PM (#15492199)
Yes. https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi... have some discussion on it, and references for further reading (and a whole lot of making his own parser look powerful in comparison. It certainly is. I just wish the code of his parser was closer to the C I've seen before).