Contact me

Twitter  ⟐  LinkedIn
Christophe Delord


Fund my FUN book!

Would you like to fund my book on modelling with functionnal languages? FUN is a book on functional software specifications. More details here: http://fun.cdsoft.fr


News!

Friday 25. march 2016: Dear backers, unfortunately, the project was not successfully funded. I will now focus on FRP (Functional Reactive Programming) applied to real-time critical system specification and simulation.

Wednesday 24. february 2016: Kickstarter project now live!

Friday 19. february 2016: Kickstarter project submitted for review

Sunday 24. january 2016: slideshow updated with applications that will be covered by the book

Tuesday 1. september 2015: concept of executable specifications applied to tests

Friday 22 May 2015: model of the temporal aspect of real time softwares

Recherche d’emploi

ingénieur en informatique
actuellement en CDI mais à l’écoute du marché
Type de poste
poste à dominante R&D en informatique, architecture
Compétences
aéronautique, DO 178B, logiciel embarqué, simulation, vérification, certification, outillage, automatisation, intelligence artificielle, programmation fonctionnelle (Haskell, OCaml), programmation logique (PROLOG)… (CV : HTML ou PDF )
Localisation
région toulousaine ou télétravail (déplacements possibles)
Contact
Christophe Delord

CDSoft :: CV/Resume :: Free softwares Essays Haskell Handy Calc pp TPG BonaLuna Calculadoira todo pwd pi w :: AI tools in Prolog AI dialog

abstract

Toy Parser Generator is a lexical and syntactic parser generator for Python. This generator was born from a simple statement: YACC is too complex to use in simple cases (calculators, configuration files, small programming languages, …).

TPG can very simply write parsers that are usefull for most every day needs (even if it can’t make your coffee). With a very clear and simple syntax, you can write an attributed grammar that is translated into a recursive descendant parser. TPG generated code is very closed to the original grammar. This means that the parser works like the grammar. A grammar rule can be seen as a method of the parser class, symbols as method calls, attributes as method parameters and semantic values as return values. You can also add Python code directly into grammar rules and build abstract syntax trees while parsing.

The first application of TPG is TPG itself. The first (not released) version of TPG has been written by hand then was used to generate next versions. Now TPG can generate itself.

For an uptodate documentation, please read tpg.pdf.

Please let me know if you use TPG in one of your projects. I will add you in the list of projects using TPG.

Prerequisites

Python 2.2 or newer is required. TPG works with both Python 2 and 3.

How it works

Lexical scanner

The lexical scanner uses Python regular expressions. The text is split before being parsed by the grammar rules.

Syntactic parser

TPG isn’t based on predictive algorithms with tables like LL(k). The main idea was instead to try every possible choices and to accept the first choice that match the input. So when a choice point is reached - say A|B|C - the parser will first try to recognize A. If this fails it will try B and if necessary C. So contrary to LL(k) parsers the order of the branches of choice points is very important for TPG. In fact this method has been inspired from Prolog DGC parsers. But remember that when a choice has been done, even if their are more possible choices, it can’t be undone (in Prolog it can). The text to be parsed has to be stored in a string in memory (backtracking is simpler this way). During the parsing, the current position is stored in internal TPG variables for all terminal and non-terminal symbols.

So we can say that TPG uses a sort of very limited backtracking.

This algorithm is easily implementable. Any rule is translated into a class method without having to compute a prediction table. The main drawbacks of this method is that you have to be carefull when you write your grammar (as in Prolog).

Example

This page presents a well known example: a calculator.

More detailled examples are given in the documentation of TPG.

#!/usr/bin/env python

import math
import operator
import string
import tpg

if tpg.__python__ == 3:
    operator.div = operator.truediv
    raw_input = input

def make_op(op):
    return {
        '+'   : operator.add,
        '-'   : operator.sub,
        '*'   : operator.mul,
        '/'   : operator.div,
        '%'   : operator.mod,
        '^'   : lambda x,y:x**y,
        '**'  : lambda x,y:x**y,
        'cos' : math.cos,
        'sin' : math.sin,
        'tan' : math.tan,
        'acos': math.acos,
        'asin': math.asin,
        'atan': math.atan,
        'sqr' : lambda x:x*x,
        'sqrt': math.sqrt,
        'abs' : abs,
        'norm': lambda x,y:math.sqrt(x*x+y*y),
    }[op]

class Calc(tpg.Parser, dict):
    r"""
        separator space '\s+' ;

        token pow_op    '\^|\*\*'                                               $ make_op
        token add_op    '[+-]'                                                  $ make_op
        token mul_op    '[*/%]'                                                 $ make_op
        token funct1    '(cos|sin|tan|acos|asin|atan|sqr|sqrt|abs)\b'           $ make_op
        token funct2    '(norm)\b'                                              $ make_op
        token real      '(\d+\.\d*|\d*\.\d+)([eE][-+]?\d+)?|\d+[eE][-+]?\d+'    $ float
        token integer   '\d+'                                                   $ int
        token VarId     '[a-zA-Z_]\w*'                                          ;

        START/e ->
                'vars'                  $ e=self.mem()
            |   VarId/v '=' Expr/e      $ self[v]=e
            |   Expr/e
        ;

        Var/$self.get(v,0)$ -> VarId/v ;

        Expr/e -> Term/e ( add_op/op Term/t     $ e=op(e,t)
                         )*
        ;

        Term/t -> Fact/t ( mul_op/op Fact/f     $ t=op(t,f)
                         )*
        ;

        Fact/f ->
                add_op/op Fact/f                $ f=op(0,f)
            |   Pow/f
        ;

        Pow/f -> Atom/f ( pow_op/op Fact/e      $ f=op(f,e)
                        )?
        ;

        Atom/a ->
                real/a
            |   integer/a
            |   Function/a
            |   Var/a
            |   '\(' Expr/a '\)'
        ;

        Function/y ->
                funct1/f '\(' Expr/x '\)'               $ y = f(x)
            |   funct2/f '\(' Expr/x1 ',' Expr/x2 '\)'  $ y = f(x1,x2)
        ;

    """

    def mem(self):
        vars = sorted(self.items())
        memory = [ "%s = %s"%(var, val) for (var, val) in vars ]
        return "\n\t" + "\n\t".join(memory)

print("Calc (TPG example)")
calc = Calc()
while 1:
    l = raw_input("\n:")
    if l:
        try:
            print(calc(l))
        except Exception:
            print(tpg.exc())
    else:
        break

Documentation

The documentation is available online in PDF format.

You can read the ChangeLog for further version details.

Installation

Linux / Unix / Sources

Extract TPG-3.2.2.tar.gz and run python setup.py install.

Windows

The Windows installer is not available anymore because of a virus infection. I will now only distribute source packages.

Projects using TPG

TPG
Toy Parser Generator (itself ;-)
Tentakel
distributed command execution
Xoot
shorthand to XSLT
EZgnupy
a front-end for gnuplot written in python
Ize
python module providing a set of function decorators
Rugg
Flexible file system and hard drive crash testing
Osh
An Open-Source Python-Based Object-Oriented Shell

Links

Support

If you find these softwares useful, you are free to donate something to support their future evolutions. Thanks for your support.

You can use Flattr, PayPal, buy some CDSoft products or simply disable your ad-blocker to support these softwares.

Flattr PayPal Essays