I recently came across a tutorial on context-free grammars with several examples of common patterns you can find in those grammars and I thought to myself — why not implement some of those examples as an exercise?
I first had to choose the language, Java, and the tools to implement the examples with, JFlex and Jacc. The pair is sufficiently similar to Flex and Bison and the grammars hopefully won’t get obscured by implementation.
I got myself familiar with JFlex and Jacc and made three notes about working with them:
- Meet JFlex — an intro to JFlex with a small example of a standalone lexer,
- Use JFlex to Count Words — another standalone lexer example, this time a bit more involved,
- Use JFlex and Jacc Together — how to make JFlex and Jacc cooperate, also with a rudimentary example.
If you are interested in CFGs and parsing, the tutorial I mentioned is not a bad place to get some practical experience implementing them. You can find it here and I also uploaded it to Github (hoping not to have broken any copyright laws).
The grammar I used to demonstrate how JFlex and Jacc work together is actually the grammar from the section 2.1 of the tutorial (“A grammar for a language that allows a list of X’s “) so I’ve actually already started going through the exercises. Yay.
Using Graphviz you can get a visual representation of your grammars. First export the grammar as a dot file:
jacc -d Parser.jacc
This creates Parser.dot. Then
dot -Tjpg Parser.dot -o Parser.jpg
and you end up with Parser.jpg. It’s very simple:
It is a state machine represented as a directed graph. Creating grammar visual representations is just one of the tools Jacc provides to help you debug your grammars. You can export a grammar to a text file:
jacc -v Parser.jacc
This creates Parser.output:
// Output created by jacc on Wed Mar 13 09:15:29 CET 2019 state 0 (entry on sentence) $accept : \_sentence $end X shift 2 . error sentence goto 1 state 1 (entry on sentence) $accept : sentence\_$end sentence : sentence\_X (2) $end accept X shift 3 . error state 2 (entry on X) sentence : X\_ (1) $end reduce 1 X reduce 1 . error state 3 (entry on X) sentence : sentence X\_ (2) $end reduce 2 X reduce 2 . error 4 terminals, 1 nonterminals; 2 grammar rules, 4 states; 0 shift/reduce and 0 reduce/reduce conflicts reported.
or into a html file:
jacc -h Parser.jacc
This creates ParserMachine.html:
Generated machine for Parser
// Output created by jacc on Wed Mar 13 09:20:03 CET 2019
state 0 (entry on sentence) $accept : _sentence $end X shift 2 . error sentence goto 1
state 1 (entry on sentence) $accept : sentence_$end sentence : sentence_X (2) $end accept X shift 3 . error
state 2 (entry on X) sentence : X_ (1) $end reduce 1 X reduce 1 . error
state 3 (entry on X) sentence : sentence X_ (2) $end reduce 2 X reduce 2 . error 4 terminals, 1 nonterminals; 2 grammar rules, 4 states; 0 shift/reduce and 0 reduce/reduce conflicts reported.
You can actually go through the machine states by clicking the links.
Jacc also supports tracing your grammar on sample inputs and embedding custom error productions in grammars — that’s it. ttfn!