Josh Haberman has a good 2013 blog post discussing LL & LR parsers, theory vs practice, context-free grammars & Parsing Expression Grammars (PEGs): https://blog.reverberate.org/2013/09/ll-and-lr-in-context-wh...
Ohm's Peg-to-WASM Compiler
11–19 of 19 posts
Re: Ohm's Peg-to-WASM Compiler
#12Earlier quoted context omitted.
I had the impression that PEG and Earley/GLR all fully solved the parsing problem, but in different ways. But then recently, I found this guy's blog: https://www.oilshell.org/blog/tags.html?tag=parsing#parsing Now I don't know what to think. The author's got a ton more experience than me. It seems there's a big enough market out there for people wanting non-ambiguity proofs and linear running-time proofs. Then again,…
The issue with Regex for parsing is it can't handle balanced parentheses. https://en.wikipedia.org/wiki/Regular_expression . More generally, they can't handle nested structure. Context free grammars are the most natural extension that can. It adds a substitution operator to Regex that makes it powerful enough to recognize nested structure. So, Regex would be reinvented if history was rerun, but so would Context Free…
I understand what a CFG is and why Dyck's language (matching parens) is not a regular language. My point was that CFG/CFL is less motivated by a reasonable and uniquely characterising constraint - such as making memory usage independent of the size of an input string - than regex is.
Then again, you are right that CFGs are very natural. And they do admit a few easy O(n^3) parsing algorithms, like Earley and CYK.
I think your last sentence relates to Visible Pushdown Grammars. See also Operator Precedence Grammars.
Re: Ohm's Peg-to-WASM Compiler
#13The precursor to Ohm, Ometa [1,2] was created at the Viewpoints Research Institute some more papers at [3].
[1] https://en.wikipedia.org/wiki/OMeta
[2] https://tinlizzie.org/VPRIPapers/tr2008003_experimenting.pdf
[3] https://tinlizzie.org/IA/index.php/Papers_from_Viewpoints_Re...
Re: Ohm's Peg-to-WASM Compiler
#14I have been very curious to try Ohm. I'm currently using a hand-rolled parser combinator library, but Ohm looks slick. The online editor is nice too https://ohmjs.org/editor/
Re: Ohm's Peg-to-WASM Compiler
#15The only thing I prefe peggyjs over ohm is runtime deps, I thinkg this might let ohm aot the grammar to avoid the deps.
Re: Ohm's Peg-to-WASM Compiler
#16It seems decent.
Re: Ohm's Peg-to-WASM Compiler
#17I'd be interested to know some applications of ohm. What have people built with it?
From https://ohmjs.org —
Here are some awesome things people have built using Ohm:
- Shopify's theme-tools (https://github.com/Shopify/theme-tools/), used in their online code editor and the official VS code extension.
- Seymour (https://github.com/harc/seymour), a live programming environment for the classroom.
- Shadama (https://tinlizzie.org/~ohshima/shadama2/live2017/), a particle simulation language designed for high-school science.
- Slang (http://slang.kylestetz.com/), a browser-based audio programming language, and turtle.audio, a music sequencer inspired by turtle graphics programming.
- Simpletalk (https://github.com/dkrasner/Simpletalk) is an expressive, programmable authoring system inspired by Hypercard and Smalltalk. (See also the StrangeLoop talk).
- Wildcard (https://www.geoffreylitt.com/wildcard/), a browser extension that empowers anyone to modify websites to meet their own specific needs, uses Ohm for its spreadsheet formulas.
- JAMScript (https://citelab.github.io/JAMScript/) is a programming language for edge-based IoT applications.
- Bruno (https://github.com/usebruno/bruno) is an open source IDE for exploring and testing APIs.
It has also been used in a number of projects by Ink & Switch (https://inkandswitch.com), including Potluck (Dynamic documents as personal software: https://www.inkandswitch.com/potluck/), the Deja Vu project at MIT (https://sdg.csail.mit.edu/project/deja-vu/), ...
Re: Ohm's Peg-to-WASM Compiler
#18I’ve been following the Ohm project for years and it’s the best way to build parsers I’ve ever seen. I’ve used it to parse many program languages and even markdown. I’m happy to see it get even faster. https://joshondesign.com/2021/07/16/ohm_markdown_parser
What is great about the Ohm approach compared to typical lex/yacc/ANTLR parsers is that it avoids ambiguity by using ordered choice (the first matching rule wins), instead of requiring you to resolve conflicts explicitly. This makes working with Ohm/PEGs less painful in the initial phase of a project. It's also important to highlight that this makes the parsing process slower.
> it avoids ambiguity by using ordered choice (the first matching rule wins)
PEG parsing tool authors often say that ordered choice solves the problem of ambiguity, that's very misleading.
Yes, ordered choice is occasionally useful as a way to resolve grammatic overlap. But as a grammar author, it's more common for me to want to express unordered choice between two sub-grammars. A tool that supports unordered choice will then let you know when you have an unexpected ambiguity.
PEG-based tools force you to use ordered choice for everything. You may be surprised later to find out that your grammar was actually ambiguous, and the ambiguity was "resolved" somewhat arbitrarily by picking the first sub-grammar.
> This makes working with Ohm/PEGs less painful in the initial phase of a project.
I do agree with this. But then what happens in the later phases? Do you switch to a tool that supports unordered choice to see if you have any ambiguities? And potentially have to change your grammar to fix them?
Re: Ohm's Peg-to-WASM Compiler
#19Unfortunately it still unable to handle to context sensitive language which is a deal breaker for me (like C++ raw string as an example).