Das Weltraumschaf

Parser and Image Generator for EBNF

2. Oct 2011 | 2 minutes read
Share this:

Parser and Image Generator for EBNF

Some days ago I searched for a tool which can visualizes EBNF grammars. I don’t care what kind of visualization: Desktop tool or a command line tool which generates images, PDF or such. The only tool I found was a Windows tool. That didn’t satisfy me because I don’t want to start my VM each time for only checking my grammar visually. But I found some moldy PHP code from Vincent Tscherter here which generates PNG or XML files from an EBNF grammar. That’s what I wanted: A visual of a grammar. But his implementation has some weakness: It does not support the whole feature set of EBNF (concatenation, comment, special sequence and exceptions) and more important, the error reporting sucks. If you have a syntax error the lexer/parser function reports the position of the error as an index in the input stream. No line! No column! It’s quite hard to go through a large grammar file to find character 10934 where the syntax error is. The original implementation does not have the possibility to extend it in an easy way to track the line number of a scanned lexical token. Not to mention the column. So I decided to port the whole code to PHP 5.3 and refactor it to standard LL(1) Recursive-Descent Lexer/Parser pattern. (For more information about these patterns I recommend the book „Language Implementation Patterns“ from Terence Parr, the inventor of ANTLR.) I also extended the lexer that way that it tracks the actual line and column of the scanned token for better error reporting on syntactic errors. This position information is part of the scanned token to improve the error reporting on semantic errors in the parser. You can find the code, of course, on GitHub. It offers you a class library for rendering EBNF grammars to GIF, JPG, PNG and XML and also a command line tool.