5

I am working with a custom, fairly simple DSL for specifying how various scripts will be run. The DSL takes the form of config files that are very simple and easy for humans to read. They define what scripts must be executed in what order and how. I have a program that parses such a config file, and executes the steps.

The config files are sometimes authored by other developers who are not familiar with the parser. They only need to know what rules the grammar has. These rules are simple, which reduces the learning curve for writing these config files.

The de facto definition of the grammar is of course my parser code. However, this is obviously not accessible to new developers. So the logical next step is to write a succinct description of the grammar, for example as an EBNF. However, as I augment the grammar with new features, the EBNF document will become obsolete, and I will have to remember to manually update it after every relevant code change. Worse yet, I may inevitably forget to update the EBNF document, leading to developers being surprised that the actual parser behaves differently than what the documentation claims.

What strategy can I use to maintain documentation of my parser's grammar? My priorities are DRY and minimal investment of developer time (both mine and others').

  • Is it a good idea to try to write the EBNF as the ground truth grammar, and then somehow generate the parser logic automatically from this EBNF? How can I avoid making the parser much more complex and difficult to maintain?
  • Can I automatically spit out the EBNF from the code logic? Is this practical in Python?
  • Am I overthinking it? Maybe the best option is to just be disciplined about manually updating the docs after all.
  • 2
    The typical approach would indeed be to write BNF and use a parser generator to generate the code for your parser. Unfortunately, these BNF dialects are effectively yet another programming language to learn, and can have non-obvious restrictions. My preferred alternative is to use a thorough integration test suite (incl. examples from docs) as the canonical grammar description, and check for ~100% branch coverage in the hand-written parser. (Not perfect, but works well in practice) – amon Oct 9 at 21:03
  • Can you illustrate why you expect the new developers programmers to be better at reading EBNF than at reading you parser code that is presumably written in fairly clean python? I feel like your average programmer has only had a few run ins with EBNF, like maybe a lecture on it in undergrad and maybe seeing snippets of it in a language spec. Where as most programmers write (and more importantly read) in the language of choice every day. But maybe that doesn't apply as you work in some area where EBNF is supper common. So please clarify in your question. – Lyndon White Oct 9 at 22:58
  • @LyndonWhite I disagree with "I feel like your average programmer has only had a few run ins with EBNF". – Donentolon Oct 10 at 0:17
  • I'm suprised you did a manual grammar, I generally find writing EBNF parsing to be far easier than trying to manually create my own grammar in code. Generating the parser from EBNF makes changes much easier, and formal verification of the language much easier (which to you means less parsing bugs). – opa Oct 10 at 15:55
4

The easiest way would be disciplined manual update of your manual.

Extracting the grammar from an implemented parser seems to be a very difficult analysis algorithm, that would have to detect how you are parsing. I don't know if such an intelligent tool exists.

Depending on how you designed your parser, you could imagine to misuse an code analysis tool. The extraction of a call graph is straightforward. If for every different grammatical token, you'd have a function to parse it, the call graph could give a nice overview. But it's very far from an EBNF. And it would only work for a very specific style of coding.

If you want true DRY, the right way would be the opposite way: write an EBNF grammar and generate the parser based on this grammar. lark could be an interesting tool in that regard. But you would have to rewrite completely what you already have. Other suggestions and alternatives can be found here.

3

First things first, I would like to re-iterate Christophe's suggestion: if you can, somehow, re-architect your code so that the grammar description you use in the documentation is also the parser (or the parser is generated from it), that would be the safest way going forward to make sure they never get out of sync.

Going the other way is probably not going to be possible. In the general case, deriving the grammar from the parser is going to be equivalent to solving the Halting Problem.

So, you will have to restrict the way you write your parser by following strict naming conventions, maybe use decorators or annotations hidden in comments to help the documentation generator along.

An alternative to trying to automatically generate the grammar description from the parser code that is much more tractable is to put the grammar description into decorators, comments, or docstrings of the parser methods themselves. That way, the grammar fragments are documented right next to the code that implements that part of the grammar, and thus the "mental distance" is reduced and it is much easier to edit the code and the grammar at the same time, if they are only 2-3 lines away from each other and clearly visible on screen.

A last method that can both be applied to your current solution as well as combined with any of Christophe's or my suggestions, would be instead of generating a parser from the grammar description, to generate a test harness from the grammar description with both positive and negative test cases and make sure that

  • all of the generated positive test cases are accepted (giving you confidence there are no valid programs that are rejected by your parser)
  • the positive test cases exercise 100% of your parser code (giving you confidence that the positive test cases explore the space of legal programs thoroughly)
  • none of the generated negative test cases are accepted

If you combine this with mutation testing, you can be reasonably sure that your parser and your grammar match.

Note, however, that generating a program that generates valid utterances in your grammar from the grammar description may be as hard as or even harder than generating a parser in the first place.

As an alternative (or in addition to any or all of the above), you could hand-write instead of generate plenty of positive and negative examples in your documentation, and automatically extract those into a test suite.

An extreme example of this kind of "doctest" testing is the book Agile Web Development with Rails. A couple of years ago, Sam Ruby spent several months (if not more than a year) re-architecting how the book is written so that the entire book can be "run" cover to cover as a gigantic system test suite for Ruby on Rails. For example, all terminal commands in the book are marked up explicitly, and the test harness extracts the commands and the output from the book, runs the commands and compares their output with the captured output from the book. The same applies to code on the interactive Ruby REPL.

Basically, the test harness will follow the book in the same way a reader would, execute all the steps a reader would take, and make sure that the results are as described in the book.

This can be used in two "directions" (in addition to simply making sure that there are no bugs in the book):

  • When a new major release of Rails comes out, it documents all the cases where behavior has changed and the book needs updating. (In fact, the test harness can actually be run in a mode where it updates the terminal outputs and interactive REPL return values automatically.)
  • When a new minor release comes out, it can serve as a regression test for Rails to make sure the behavior hasn't changed. (The book is considered to be the "canonical" in-depth tutorial for Rails and almost like specification of Rails' features.)

You can apply those same ideas to the examples in your documentation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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