Preface

Again I'm thinking back on my examination nightmare. The worst thing to do by hand probably is to calculate Follow-sets. These are complicated, and when they are finally done, you realize that something is wrong with you grammar, and you have to do it all over again. You get impatient, you need a cool parser for a neat projects you are working on. You get sweaty, you get itchy and start drumming a pencil down the table in front of you to great annoyance of anyone around you. But not any more.

This is my second project in the series of let the computer do the tedious work. We need to calculate Nullable, First and Follow sets. And when we can do that, we can pretty easily make LL(1) parsers of LL(1) grammars. Furthermore combined with the NFA to DFA converter we can explore SLR parsers as well.

If you are taking some Compiler course at you university, it would probably be a good idea for you to learn to do these things by hand. In this case you might benefit from this application by using it to check you answers.

This rapport contains, besides this introduction, a walk through of creating a parser for the application. Then the algorithms used to calculate the sets. And finally the implementation that can be run online.

The sets the application can calculate, are used to create parsers from what is called CFG's or Context Free Grammars. These grammars have a recursive nature and are more expressible than regular expressions. A CFG is capable of describing matching of nested opening and closing parentheses, quotes and so on. Furthermore precedence and associativity can be described with a CFG. In math we have the rule that we multiply before we plus. Observe the problem 2 + 2 \cdot 2, this equals 6 because of precedence: multiply binds tighter than plus. This can be described with the CFG:

Exp \rightarrow Exp + Exp' | Exp' Exp' \rightarrow Exp' \cdot Exp'' | Exp'' Exp'' \rightarrow num

In this grammar both plus and multiply are left-associative. When you get used to it, this notations is quite convenient, I think. By calculate the Nullable, First and Follow set of a grammar, we can obtain what is called a LookAhead set and with this we can implement a LL(1) parser. Or we can combine this application with the NFA to DFA converter to create a SLR parser. The grammar needs be non-ambiguous, it can't contain left-recursion and it has to be left factorized in order to be transformed into an LL(1) parser. These steps are not covered in this rapport.

Hope you will enjoy.