Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ohm: Parsing Made Easy

nextjournal.com

Post reply on HN
Print view View original

41–50 of 100 posts

Re: Ohm: Parsing Made Easy

#41

Post by tomp »

shalabhc wrote: post #30
yxhuvud wrote: post #25

Earlier quoted context omitted.

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.

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 ahe…

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

#42

Post by CalChris »

In many parser generators (e.g. Yacc and ANTLR), a grammar author can specify the language semantics by including semantic actions inside the grammar. A semantic action is a snippet of code — typically written in a different language —that produces a desired value or effect each time a particular rule is matched.

Actually, the need for that went away with ANTLR4. The grammar is now all grammar (and lexer) and the semantic actions are listeners or walkers written separately calling or overriding methods and classes generated from the grammar.

Much cleaner that way.

Re: Ohm: Parsing Made Easy

#43

Post by haberman »

chrisseaton wrote: post #26
tomp wrote: post #10

Earlier quoted context omitted.

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…

> 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 giv…

> 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

#44

Post by BoppreH »

jwiley wrote: post #9
pdubroy wrote: post #6

Hi HN, I'm a researcher at HARC ( https://harc.ycr.org/ ) and one of the authors of Ohm. We've used it to power several of our programming language investigations, such as Seymour (which was on HN yesterday: https://news.ycombinator.com/item?id=15471954 ) and Chorus ( http://www.chorus-home.org/ ). If you're interested, here's the grammar for the language used in the Seymour demo: https://github.com/harc/seymour/blob…

Nice project, thanks for sharing. One interesting application that comes to mind is creating a "safe" subset of Javascript, that could be run in an end-users browser without requiring a sandbox. One definition of safe might be: not allowing access to the DOM or global variables. Is this a reasonable use case? Is Ohm's executing environment appropriate for this usecase?

Javascript is too dynamic to have a safe subset. For example, using only the six characters ()+ []! you can write arbitrary code. The main culprits are the weak typing, permissive attribute access, and large runtime environment with lots of surface area. This is unlikely to be fixable by changing the language grammar.

See http://www.jsfuck.com/

    JSFuck is an esoteric and educational programming style
    based on the atomic parts of JavaScript. It uses only six
    different characters to write and execute code.
    It does not depend on a browser, so you can even run it on
    Node.js.

Re: Ohm: Parsing Made Easy

#45

Post by chrisseaton »

haberman wrote: post #43
chrisseaton wrote: post #26

Earlier quoted context omitted.

> 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 giv…

> 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-wit…

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

#46

Post by bd82 »

dman wrote: post #12

Any thoughts on how to handle parsing for the IDE use case where a document is being edited that might have errors in it. I would usually expect an area around the cursor that is an area that receives edita and hence contains errors. I would also expect a header and footer surrounding the edited area that would be okay structurally since its unchanged from a previously sound definition of the file.

One option would be to use a Parser that supports fault tolerance and error recovery.

In hand crafted parsers this error recovery may be added manually (but resulting in a-lot of work...) For example: search for the word "recovery" in the TypeScript parser which is used to provide Language Services for the VSCode IDE. https://github.com/Microsoft/TypeScript/blob/master/src/comp...

Automatic Error Recovery using heuristics can also be implemented by parsing Libraries. In the world of JavaScript I'm familiar with two libraries that support Error Recovery:

Antlr4 - https://github.com/antlr/antlr4

Chevrotain - https://github.com/SAP/chevrotain (disclaimer - I'm the author of Chevrotain)

Re: Ohm: Parsing Made Easy

#47

Post by victorNicollet »

shalabhc wrote: post #8
tomp wrote: post #7

> 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…

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

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

#48

Post by haberman »

chrisseaton wrote: post #45
haberman wrote: post #43

Earlier quoted context omitted.

> 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-wit…

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?

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

#49

Post by scroot »

pdubroy wrote: post #6

Hi HN, I'm a researcher at HARC ( https://harc.ycr.org/ ) and one of the authors of Ohm. We've used it to power several of our programming language investigations, such as Seymour (which was on HN yesterday: https://news.ycombinator.com/item?id=15471954 ) and Chorus ( http://www.chorus-home.org/ ). If you're interested, here's the grammar for the language used in the Seymour demo: https://github.com/harc/seymour/blob…

Are you guys working on (or have you considered) WASM text format as a target language?

Re: Ohm: Parsing Made Easy

#50

Post by chrisseaton »

haberman wrote: post #48
chrisseaton wrote: post #45

Earlier quoted context omitted.

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?

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 usef…

> 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!

Post reply on HN