A Context-Free Grammar Tutorial
Tags: programming, interpreters, parsing, java
Published: 2019-03-13 10:35:36

---
title: A Context-Free Grammar Tutorial
published: true
tags: programming,interpreters,parsing,java
canonical_url: https://medium.com/@wurdlack/a-context-free-grammar-tutorial-2704cd8e239a
---

![](https://cdn-images-1.medium.com/max/1024/1*X769PvIY7YQN4lTge1Zt6A.jpeg)

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](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=2ahUKEwiv5YKW8vrgAhWriIsKHR3dAg4QFjAAegQIBRAC&url=https%3A%2F%2Fwww.jflex.de%2F&usg=AOvVaw1UsT-Zk-dlb95doMmPXcLF) and [Jacc](http://web.cecs.pdx.edu/~mpj/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](https://dev.to/wurdlack/meet-jflex-59gd) — an intro to JFlex with a small example of a standalone lexer,
- [Use JFlex to Count Words](https://dev.to/wurdlack/use-jflex-to-count-words-5ci4) — another standalone lexer example, this time a bit more involved,
- [Use JFlex and Jacc Together](https://dev.to/wurdlack/use-jflex-and-jacc-together-3nnd) — 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](http://marvin.cs.uidaho.edu/Handouts/) and I also uploaded it to [Github](https://github.com/Wurdlack/Medium/tree/master/cfg_tutorial) (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](https://www.graphviz.org/) 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:

![](https://cdn-images-1.medium.com/max/307/1*bFCKrWMJPtYDgJIIml8Agg.png)

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:
<h4>Generated machine for Parser</h4>
<pre>
// Output created by jacc on Wed Mar 13 09:20:03 CET 2019

<hr><a name="st0"><b>state 0 (entry on sentence)</b></a>
    $accept : _sentence $end

    X <a href="#st2">shift 2</a>
    . error

    sentence <a href="#st1">goto 1</a>

<hr><a name="st1"><b>state 1 (entry on sentence)</b></a>
    $accept : sentence_$end
    sentence : sentence_X    (2)

    $end accept
    X <a href="#st3">shift 3</a>
    . error

<hr><a name="st2"><b>state 2 (entry on X)</b></a>
    sentence : X_    (1)

    $end reduce 1
    X reduce 1
    . error

<hr><a name="st3"><b>state 3 (entry on X)</b></a>
    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.
</pre>

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!