Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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 3: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 3: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 3:19
1  
@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 3:20
    
How do you know your DSLs are "relatively simple"? What's your criteria? –  Ira Baxter Nov 10 '11 at 4:19

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
thanks for the informative answer –  Aaron Anodide Nov 10 '11 at 4:24
    
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 4: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 4: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 5:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.