6 ms·

> The Ohm language is based on parsing expression grammars (PEGs), which are a formal way of describing syntax, similar to regular expressions and context-free

by tomp 9y ago

> The Ohm language is based on parsing expression grammars (PEGs), which are a formal way of describing syntax, similar to regular expressions and context-free grammars Uh-oh. I've voiced my concerns about PEGs (and LL parsers) before, but IMO any grammar "interpreter" that doesn't point out the ambiguities in grammar and instead relies on some vague, and ultimately arbitrary, notion of "precedence" (e.g. that rules declared first in the grammar file have priority), isn't a good foundation for a serious language (good for throwaway parsers and language experiments, though).

shalabhc 9y ago
Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?
- tomp 9y ago
  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.
  - shalabhc 9y ago
    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.
    - yxhuvud 9y ago
      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/ https://blog.codinghorror.com/regex-performance/ for example.
      - shalabhc 9y ago
        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.
        yxhuvud 9y ago
        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.
        tomp 9y ago
        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.
  - chrisseaton 9y ago
    > 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.
    - yxhuvud 9y ago
      It is a "solution" because it becomes unobvious what language it will parse, not because it doesn't resolve the ambiguity.
      - chrisseaton 9y ago
        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?
    - haberman 9y ago
      > 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.
  - nerdponx 9y ago
    Is ordered a choice a necessary property for PEG parsing? Maybe PEG parser generators should have an "unordered mode".
    - victorNicollet 9y ago
      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.
- yxhuvud 9y ago
  Yes. https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2015/03/peg.html 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).
- victorNicollet 9y ago
  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.
e12e 9y ago
I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: > 4.1. Left Recursion > Another interesting thing to note about the new definition of "Exp" above is that it is recursive — i.e., its body contains an application of "Exp" itself. More specifically, it is left recursive, meaning that the recursive application is the first expression in the branch. > Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Ed: -- Or are you making some other, more subtle point? If so, maybe you can give an example? Ed2: @yxhuvud's reply links to an article with some examples like: L1 = ("a"|"aa")"a" L2 = ("aa"|"a")"a"
- yxhuvud 9y ago
  > you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It can still be quadratic or worse on internal recursion, and on many ambiguous grammars).
  - e12e 9y ago
    I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right. But if the grammar and semantics allow (force) you to be explicit - I'm not sure I see it as a problem. I certainly see how allowing ambiguity with a warning/error would also be good. I'm on a cellphone now, and can't see if I can make useful/surprising grammar for the a/aa|a/aaa languages in ohm. Maybe it's just too minimal an example for me (why not: a|aaa or aa+ - or whatever one is trying to express? Is it, say about the language of pairs or triplets of "a"s?).
pdubroy 9y ago
I understand your concern, but can you tell me a bit more about how you think "serious" languages should be developed?
- bd82 9y ago
  That is a very good question because afaik many(most?) commercial (meaning "serious"...) programing languages are developed using hand crafted recursive decent parsers which usually mean that the first alternative takes precedence and that there are no grammar validations to detect ambiguities at all. I do agree that grammar validations and ambiguity detection is very important, but even if the semantics of a PEG grammar define that the first matching alternative should be taken, should it be possible to detect some cases such as unreachable alternatives as long as the grammar is structure is known in advance?
zzzcpan 9y ago
It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence. But I don't think the world of context-free grammars even matters that much.
- panic 9y ago
  Pointing out ambiguities in a context-free grammar is an undecidable problem (http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf).
  - zzzcpan 9y ago
    No, that's not what your link proves and not what we are talking about.
    - panic 9y ago
      Theorem 6.8.2 in the PDF: It is undecidable whether a context-free grammar is ambiguous. PEGs are unambiguous by construction, so I assumed we were talking about grammars which would be ambiguous as CFGs (replacing every ordered choice with a nondeterministic choice). What kind of ambiguity were you thinking about?
      - zzzcpan 9y ago
        Any ambiguity that manifests itself as unreachable alternatives in PEGs can be detected for example. Doesn't matter if it's undecidable whether the whole grammar is ambiguous.
groovy2shoes 9y ago
While PEGs necessarily impose a notion of "precedence" due to their construction, LL parsers don't necessarily impose any such notion. Any precedence that an LL parser might have is a consequence of its implementation. It's also possible to check an LL(1) grammar for ambiguities by computing an LL(1) parsing table and checking that any given (state, input) pair has at most one entry in the table. The process for other sorts of LL parsers is similar.

by tomp 9y ago

shalabhc 9y ago

Is this a limitation of the PEG syntax itself? IOW, is it possible to identify ambiguities in grammars defined as PEGs?

tomp 9y ago
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.
- shalabhc 9y ago
  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.
  - yxhuvud 9y ago
    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/ https://blog.codinghorror.com/regex-performance/ for example.
    - shalabhc 9y ago
      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.
      - yxhuvud 9y ago
        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.
      - tomp 9y ago
        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.
- chrisseaton 9y ago
  > 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.
  - yxhuvud 9y ago
    It is a "solution" because it becomes unobvious what language it will parse, not because it doesn't resolve the ambiguity.
    - chrisseaton 9y ago
      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?
  - haberman 9y ago
    > 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.
- nerdponx 9y ago
  Is ordered a choice a necessary property for PEG parsing? Maybe PEG parser generators should have an "unordered mode".
  - victorNicollet 9y ago
    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.
yxhuvud 9y ago
Yes. https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2015/03/peg.html 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).
victorNicollet 9y ago
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.

e12e 9y ago

I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: > 4.1. Left Recursion > Another interesting thing to note about the new definition of "Exp" above is that it is recursive — i.e., its body contains an application of "Exp" itself. More specifically, it is left recursive, meaning that the recursive application is the first expression in the branch. > Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Ed: -- Or are you making some other, more subtle point? If so, maybe you can give an example? Ed2: @yxhuvud's reply links to an article with some examples like: L1 = ("a"|"aa")"a" L2 = ("aa"|"a")"a"

yxhuvud 9y ago
> you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It can still be quadratic or worse on internal recursion, and on many ambiguous grammars).
- e12e 9y ago
  I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right. But if the grammar and semantics allow (force) you to be explicit - I'm not sure I see it as a problem. I certainly see how allowing ambiguity with a warning/error would also be good. I'm on a cellphone now, and can't see if I can make useful/surprising grammar for the a/aa|a/aaa languages in ohm. Maybe it's just too minimal an example for me (why not: a|aaa or aa+ - or whatever one is trying to express? Is it, say about the language of pairs or triplets of "a"s?).

pdubroy 9y ago

I understand your concern, but can you tell me a bit more about how you think "serious" languages should be developed?

bd82 9y ago
That is a very good question because afaik many(most?) commercial (meaning "serious"...) programing languages are developed using hand crafted recursive decent parsers which usually mean that the first alternative takes precedence and that there are no grammar validations to detect ambiguities at all. I do agree that grammar validations and ambiguity detection is very important, but even if the semantics of a PEG grammar define that the first matching alternative should be taken, should it be possible to detect some cases such as unreachable alternatives as long as the grammar is structure is known in advance?

zzzcpan 9y ago

It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence. But I don't think the world of context-free grammars even matters that much.

panic 9y ago
Pointing out ambiguities in a context-free grammar is an undecidable problem (http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf).
- zzzcpan 9y ago
  No, that's not what your link proves and not what we are talking about.
  - panic 9y ago
    Theorem 6.8.2 in the PDF: It is undecidable whether a context-free grammar is ambiguous. PEGs are unambiguous by construction, so I assumed we were talking about grammars which would be ambiguous as CFGs (replacing every ordered choice with a nondeterministic choice). What kind of ambiguity were you thinking about?
    - zzzcpan 9y ago
      Any ambiguity that manifests itself as unreachable alternatives in PEGs can be detected for example. Doesn't matter if it's undecidable whether the whole grammar is ambiguous.

groovy2shoes 9y ago

While PEGs necessarily impose a notion of "precedence" due to their construction, LL parsers don't necessarily impose any such notion. Any precedence that an LL parser might have is a consequence of its implementation. It's also possible to check an LL(1) grammar for ambiguities by computing an LL(1) parsing table and checking that any given (state, input) pair has at most one entry in the table. The process for other sorts of LL parsers is similar.