\section{Introduction}

This short tutorial presents how to make a simple calculator.
The calculator will compute basic mathematical expressions (\verb|+, -, *, /|) possibly nested in parenthesis.
We assume the reader is familiar with regular expressions.

\section{Defining the grammar}

Expressions are defined with a grammar.
For example an expression is a sum of terms and a term is a product of factors. A factor is either a number or a complete expression in parenthesis.

We describe such grammars with rules. A rule describe the composition of an item of the language. In our grammar we have 3 items (Expr, Term, Factor). We will call these items `symbols' or `non terminal symbols'. The decomposition of a symbol is symbolized with $\to$.
The grammar of this tutorial is given in figure~\ref{tut:gramsymb_calc}.

\begin{tableau}
\caption{Grammar for expressions}                           \label{tut:gramsymb_calc}
\begin{tabular}{| l | p{7cm} |}
\hline
    Grammar rule & Description \\
\hline
\hline
    $Expr~\to~Term~(('+'|'-')~Term)*$
        & An expression is a term eventually followed with a plus ($'+'$) or a minus ($'-'$) sign and an other term any number of times ($*$ is a repetition of an expression 0 or more times). \\
\hline
    $Term~\to~Fact~(('*'|'/')~Fact)*$
        & A term is a factor eventually followed with a $'*'$ or $'/'$ sign and an other factor any number of times. \\
\hline
    $Fact~\to~number~|~'('~Expr~')'$
        & A factor is either a number or an expression in parenthesis. \\
\hline
\end{tabular}
\end{tableau}

We have defined here the grammar rules (i.e. the sentences of the language). We now need to describe the lexical items (i.e. the words of the language). These words - also called \emph{terminal symbols} - are described using regular expressions. In the rules we have written some of these terminal symbols ($+, -, *, /, (, )$). We have to define \emph{number}. For sake of simplicity numbers are integers composed of digits (the corresponding regular expression can be $[0-9]+$).
To simplify the grammar and then the Python script we define two terminal symbols to group the operators (additive and multiplicative operators). We can also define a special symbol that is ignored by TPG. This symbol is used as a separator. This is generaly usefull for white spaces and comments. The terminal symbols are given in figure~\ref{tut:token_calc}

\begin{tableau}
\caption{Terminal symbol definition for expressions}        \label{tut:token_calc}
\begin{tabular}{| l | l | l |}
\hline
    Terminal symbol & Regular expression & Comment \\
\hline
\hline
    number & $[0-9]+$ or $\backslash d+$ & One or more digits \\
\hline
    add & $[+-]$ & a $+$ or a $-$ \\
\hline
    mul & $[*/]$ & a $*$ or a $/$ \\
\hline
    spaces & $\backslash s+$ & One or more spaces \\
\hline
\end{tabular}
\end{tableau}

This is sufficient to define our parser with TPG. The grammar of the expressions in TPG can be found in figure~\ref{tut:recognizer}.

\begin{code}
\caption{Grammar of the expression recognizer}              \label{tut:recognizer}
\begin{verbatimtab}[4]
class Calc(tpg.Parser):
    r"""

    separator spaces: '\s+' ;
    token number: '\d+' ;
    token add: '[+-]' ;
    token mul: '[*/]' ;

    START -> Expr ;

    Expr -> Term ( add Term )* ;

    Term -> Fact ( mul Fact )* ;

    Fact -> number | '\(' Expr '\)' ;

    """
\end{verbatimtab}
\end{code}

\emph{Calc} is the name of the Python class generated by TPG. \emph{START} is a special non terminal symbol treated as the \emph{axiom}\footnote{The axiom is the symbol from which the parsing starts} of the grammar.

With this small grammar we can only recognize a correct expression. We will see in the next sections how to read the actual expression and to compute its value.

\section{Reading the input and returning values}

The input of the grammar is a string. To do something useful we need to read this string in order to transform it into an expected result.

This string can be read by catching the return value of terminal symbols. By default any terminal symbol returns a string containing the current token. So the token $'('$ always returns the string $'('$. For some tokens it may be useful to compute a Python object from the token. For example \emph{number} should return an integer instead of a string, \emph{add} and \emph{mul} should return a function corresponding to the operator. That why we will add a function to the token definitions. So we associate \emph{int} to \emph{number} and \emph{make\_op} to \emph{add} and \emph{mul}.

\emph{int} is a Python function converting objects to integers and \emph{make\_op} is a user defined function (figure~\ref{tut:make_op}).

\begin{code}
\caption{\emph{make\_op} function}                          \label{tut:make_op}
\begin{verbatimtab}[4]
def make_op(s):
    return {
        '+': lambda x,y: x+y,
        '-': lambda x,y: x-y,
        '*': lambda x,y: x*y,
        '/': lambda x,y: x/y,
    }[s]
\end{verbatimtab}
\end{code}

To associate a function to a token it must be added after the token definition as in figure~\ref{tut:tokens}

\begin{code}
\caption{Token definitions with functions}                  \label{tut:tokens}
\begin{verbatimtab}[4]
    separator spaces: '\s+' ;
    token number: '\d+' int ;
    token add: '[+-]' make_op;
    token mul: '[*/]' make_op;
\end{verbatimtab}
\end{code}

We have specified the value returned by the token. To read this value after a terminal symbol is recognized we will store it in a Python variable. For example to save a \emph{number} in a variable \emph{n} we write \emph{number/n}.
In fact terminal and non terminal symbols can return a value. The syntax is the same for both sort of symbols. In non terminal symbol definitions the return value defined at the left hand side is the expression return by the symbol. The return values defined in the right hand side are just variables to which values are saved. A small example may be easier to understand (figure~\ref{tut:ret_val}).

\begin{tableau}
\caption{Return values for (non) terminal symbols}          \label{tut:ret_val}
\begin{tabular}{| l | p{9cm} |}
\hline
    Rule & Comment \\
\hline
    \verb!X/x ->!           & Defines a symbol \emph{X}. When \emph{X} is called, \emph{x} is returned. \\
    \verb!Y/y!              & \emph{X} starts with a \emph{Y}. The return value of \emph{Y} is saved in \emph{y}. \\
    \verb!Z/z!              & The return value of \emph{Z} is saved in \emph{z}. \\
    \verb!$ x = y+z $!      & Computes \emph{x}. \\
    \verb!;!                & Returns \emph{x}. \\
\hline
\end{tabular}
\end{tableau}

In the example described in this tutorial the computation of a \emph{Term} is made by applying the operator to the factors, this value is then returned :

\begin{verbatimtab}[4]
    Expr/t -> Term/t ( add/op Term/f $t=op(t,f)$ )* ;
\end{verbatimtab}

This example shows how to include Python code in a rule. Here \verb!$...$! is copied verbatim in the generated parser.

Finally the complete parser is given in figure~\ref{tut:parser}.

\begin{code}
\caption{Expression recognizer and evaluator}               \label{tut:parser}
\begin{verbatimtab}[4]
class Calc(tpg.Parser):
    r"""

    separator spaces: '\s+' ;

    token number: '\d+' int ;
    token add: '[+-]' make_op ;
    token mul: '[*/]' make_op ;

    START -> Expr ;

    Expr/t -> Term/t ( add/op Term/f $t=op(t,f)$ )* ;

    Term/f -> Fact/f ( mul Fact/a $f=op(f,a)$ )* ;

    Fact/a -> number/a | '\(' Expr/a '\)' ;

    """
\end{verbatimtab}
\end{code}

\section{Embeding the parser in a script}

Since TPG 3 embeding parsers in a script is very easy since the grammar is the doc string\footnote{It may be a good pratice to use only raw strings. This will ease the pain of writing regular expressions.} of a class (see figure~\ref{tut:build_scheme}).

\begin{code}
\caption{Writting TPG grammars in Python}             \label{tut:build_scheme}
\begin{verbatimtab}[4]
import tpg

class MyParser(tpg.Parser):
    r""" # Your grammar here """

# You can instanciate your parser here
my_parser = MyParser()
\end{verbatimtab}
\end{code}

To use this parser you now just need to instanciate an object of the class \emph{Calc} as in figure~\ref{tut:calc}.

\begin{code}
\caption{Complete Python script with expression parser}     \label{tut:calc}
\begin{verbatimtab}[4]
import tpg

def make_op(s):
    return {
        '+': lambda x,y: x+y,
        '-': lambda x,y: x-y,
        '*': lambda x,y: x*y,
        '/': lambda x,y: x/y,
    }[s]

class Calc(tpg.Parser):
    r"""

    separator spaces: '\s+' ;

    token number: '\d+' int ;
    token add: '[+-]' make_op ;
    token mul: '[*/]' make_op ;

    START/e -> Term/e ;
    Term/t -> Fact/t ( add/op Fact/f $t=op(t,f)$ )* ;
    Fact/f -> Atom/f ( mul/op Atom/a $f=op(f,a)$ )* ;
    Atom/a -> number/a | '\(' Term/a '\)' ;

    """

calc = Calc()
expr = raw_input('Enter an expression: ')
print expr, '=', calc(expr)
\end{verbatimtab}
\end{code}

\clearpage

\section{Conclusion}

This tutorial shows some of the possibilities of TPG.
If you have read it carefully you may be able to start with TPG.
The next chapters present TPG more precisely.
They contain more examples to illustrate all the features of TPG.

Happy TPG'ing!
