A Context-Free Grammar Tutorial

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!