Is there such thing as an example driven parser generator or ad-hoc DSL development?

Question

I'm intrested to know if there exists a tool that lets you input examples of valid documents and lets you then generalize from that to a reusable parser.

I can imagine this, but everytime i start learning about parsers it gets to the granularity of something like lex and yacc and it seems more complicated than my instincts say it should be.

So I'm left wondering if

a) it's just fundamentally that complicated and I need to see it or
b) there's a way to build ad-hoc DSLs for relatively simple tasks that I could learn about

Update: a simple example of an "ad hoc" dsl i might like to make quickly.

Instead of the XML

<foo>
  <item>bar</item>
  <item>bat</item>
</foo>

I might want something like:

foo
  bar
  bat

lines contain data items
indentation produces parent-child relations

My imaginary tool lets me convey the above information.

Then, in my imaginary tool, I might highlight "foo" above and right click, at which point it would prompt me to restrict the values to a choice list....

Then I might extend the first one to:

foo
  bar(5)
  bat

in a line, '(' and ')' surround a sub item

The above might be qualified with a boolean value that specifies recursion or not, if set to true then bar(lala(4)) might work...

This is the kind of train of thought I generally have that led me to ask the question. It's possible that now I've qualified it, the answer changes - if so I apologize in advance.

If I may be so bold, Haskell and Parsec make parsing by hand fun again. Not that this answers your question, and I’d be quite interested in a by-example parser generator, so much that if one does not exist, I will gladly write it. — Jon Purdy, Nov 10 '11 at 03:15
i've been pounding my procedural brain against the functional wall for a few months now - the light is starting to come, but i have to keep at it.. parsec sounds interesting - i'll take a look. — Aaron Anodide, Nov 10 '11 at 03:18
I've written at least one small tool which including a DSL with a hand-built parser; the parse was simply a loop that finds the regex to match each line and uses that to turn it into a data object. It was actually really easy. — configurator, Nov 10 '11 at 03:19
@JonPurdy, Gabriel: Parser combinators are very cool, but when I've tried to use them I always found their output format was a bit to similar to the input format for me. I haven't used the Haskell version though. — configurator, Nov 10 '11 at 03:20
How do you know your DSLs are "relatively simple"? What's your criteria? — Ira Baxter, Nov 10 '11 at 04:19
foo/bar/bat DSL example: So, what the tool sees are just the text characters . Where is there any idea that the letter is allowed? That more than 2 lines are allowed? This is just syntax; you've also imagined the tool could "guess" the semantics that you meant a tree with foo as the root and bar and bat as children. Guessing a grammer, even if you can do it, places no constraints on the *semantics*. How do you propose you tool wouold know that, too? How would I have guessed without the additional text you provided, with the XML background? — Ira Baxter, Nov 10 '11 at 04:44
i meant to imply that my DSL is a replacement of XML with no attributes - i don't want to create an xml parser — Aaron Anodide, Nov 10 '11 at 04:46
"I meant to imply..." this is the key problem with trying to produce anything from just examples. What else did you mean to imply, that you didn't (or can't!) say? — Ira Baxter, Nov 10 '11 at 04:47
If you ignore all the dark-corner stuff, XML parsers are pretty easy to write. You can simplify them further by moving to S-expressions (foo (bar) (bat)). You can implement your "indent-N means child of preceding line at indent M-less-than-N" quite easly with a completely ad hoc parser. No need to learn it, just *code* it. That's gotta be easier than hunting for a magic "learn it" approach. — Ira Baxter, Nov 10 '11 at 04:50
i think what you've made me realize is my thought is to start with a parser that incorporates the commonalities of every DSL I could ever imagine writing and let's me extend it from there... — Aaron Anodide, Nov 10 '11 at 04:50
ps: blame test driven development for this entire thread - its got me thinking in reverse :) — Aaron Anodide, Nov 10 '11 at 04:52
Wow. "Commonalities of every DSL"... if we stick just to DSLs written with text, the only commonality they all have that I can imagine is "made of characters". That's not a lot to build on. I think you meant to imply more here... — Ira Baxter, Nov 10 '11 at 04:52
... what I meant to imply with my answer was that if you wanted support for a broad variety of DSLs (and other computer languages such a Java and C++ which most people don't think of as DSLs but for me are just another specialized notation), then you want what I built as the DMS toolkit I described. It contains machinery for defining and manipulating DSLs. What's left is for you do write down what you want in a way that a tool like DMS understands, and I'll admit that isn't always easy because it hard to desribe semantics and how it is connected to syntax. But you need all of that to "DSL". — Ira Baxter, Nov 10 '11 at 04:56
again, the implication was lost... i was thinking about having a deterministic way to break input into statements combined with the mechanism to encode parent-child relations.. that would get me pretty far i think. i can imagine then adding to that with overrides based on a rule stack - i.e. you start with a set of parameters that define the parser, and when an override is triggered by something being recognized, the condition which to revert is also given... whew, i'm out of has on this one :) thanks for the info though! — Aaron Anodide, Nov 10 '11 at 04:57
@Gabriel, if you're thinking procedural, you'll find a manual Packrat parsing interesting. Another nice feature of the PEG-based parsers is that you can inherit and extend the existing parsing components. — SK-logic, Nov 10 '11 at 08:58
Lex / yacc are table based and hard to "manually" understand. I prefer Antlr. — Jacek Cz, Sep 23 '15 at 18:37

Ira Baxter · Accepted Answer · 2011-11-10T18:09:07.553

You cannot practically build a parser for a real computer language (or DSL) by just showing it examples. Learning anything by just positive examples is pretty hard (as is well known by the machine learning community); you need at least some negative examples. Pretty much you want parsers to be able to accept alternatives. If you allow them, a simple disjunctive generalization that accepts just the set of positive examples and rejects everything else works just fine but isn't useful (e.g., a "parser" for the strings "QA" "BZQ1" and "RQ" would be just "QA" | "BZQ1" | "RQ").

This article talks about machine learning to induce grammars from data. It doesn't say much about practicality. No tool I have ever seen has been effective at doing this in a general way, and the differences between "legal" and "not legal" can be incredibly subtle. Imagine trying to learn what were valid C++ programs according to the C++ standard, and rejecting the ones that MS allows that aren't legal. Even the programmers pretty much can't do this, and the C++ standards committee argues endlessly about the tricky cases.

Frankly, if you have EBNF, writing down a grammar for a DSL is generally fairly easy... if you know what the DSL should allow. Writing down a grammer that works for most parser generators is relatively hard, because they only accept limited versions of EBNF (eg., LL(k), LALR(1), ...). You can make this a lot easier by using a full context-free parsing engine such as a GLR parser which doesn't have such restrictions.

Our DMS Software Reengineering Toolkit has such a GLR parser generator, and easily accepts context free grammars. It seemingly does the impossible of parsing C++ with a straightforward BNF (the GNU folks had to build a terribly hacked LALR parser to do this for GCC); it is possible because there are context-free grammars for C++, just look in the standard!.

But parsing is just the easy part. You shouldn't spend your energy there. You need more machinery to process the DSL: building ASTs, inspecting for special cases, transforming to a target language, optimizing the code.

DMS is good for building DSLs not only because it can accept descriptions of DSLs relatively easily, but because it has most of that vast amount of machinery for processing (analyzing/transforming/...) that DSL that you will need, after you succeed in parsing.

i actually updated my question with a few examples - as noted, sorry if that changes the answer at all - i'll edit it if it's too off... — Aaron Anodide, Nov 10 '11 at 04:36
oh while i actually have someone's attention who knows this stuff - is there a type of parser that uses a set of competing recognizers and a state machine that takes recognition events as input and produces weights for the recognizers as outputs? so everything that can be recognized is always being looked for but only the things that are valid have non-zero weights? — Aaron Anodide, Nov 10 '11 at 04:42
I think what you are looking for is called a "lexer generator". These tools take a set of regular expressions which in effect define the "events" of interest ("this type of character string" for many types that you might define, e.g, numbers, names, ...) and combine them in an efficient finite state automaton that can tell which (or how many) of the regular expressions triggered at any point in the input stream. This is standard machinery that most parser generators use to recognize the tokens that make up the language the parser is trying to recognize. — Ira Baxter, Nov 10 '11 at 05:05

score 0 · Answer 2 · answered Sep 23 '15 at 18:32

DSL can be divided to 2 groups:

a) external like (mostly) write Ira Baxter: build NEW parser etc ... implement semantic

b) internal: use subset / over-set (library extensions) of real language. Then use have no-choice about syntax, must accept general syntax rule of hosting language.

Example of internal DSL in java. Copied from bigger project:

BackupService.open().setAdminEmail("aaa@yyy.ccc")
.setDatabase("xddasdas;user;pass").pefrorm().zip().transfer("sftp...).finish();

Read "evangelism" in Groovy Language community.

http://www.groovy-lang.org/dsls.html

and sample a. Xml Builder, is very near to Your idea

http://www.groovy-lang.org/processing-xml.html#_creating_xml

score 0 · Answer 3 · answered Sep 23 '15 at 19:23

Not in the general case, for the reasons given by Ira Baxter. However, this is a pretty good description of how docopt works: you give it examples of what valid command-line arguments to your program should look like, and it generates a command-line argument parser from those examples.

Is there such thing as an example driven parser generator or ad-hoc DSL development?

3 Answers3