About the X-SAIGA Project

The goal of the X-Saiga project is to create algorithms and implementations which enable the construction of language processors (recognizers, parsers, interpreters, translators, etc.) to be constructed as modular and efficient embedded executable specifications of grammars.

To achieve modularity, we have chosen to base our algorithms on top-down parsing. To accommodate ambiguity, we implement inclusive choice through backtracking search. To achieve polynomial complexity, we use memoization. We have developed an algorithm which accommodates direct left-recursion using curtailment of search. Indirect left recursion is also accommodated using curtailment together with a test to determine whether previously computed and memoized results may be reused depending on the context in which they were created and the context in which they are being considered for reuse.

We have implemented our algorithms, at various stages of their development, in Miranda (up to 2006) (more info. here) and in Haskell (from 2006 onwards) (more info. here ).

Project Members

• Dr. Richard Frost, University of Windsor
• Dr. Paul Callaghan, University of Durham
• Rahmatullah Hafiz, University of Windsor

Acknowledgements

The X-SAIGA project has been supported by University of Windsor , University of Durham , Natural Science and Engineering Research Council of Canada ( NSERC ) and Ontario Graduate Scholarship ( OGS ).

About the name X-SAIGA

The name stands for eXecutable SpecificAtIons of GrAmmars. Saigas are interesting animals which once lived in England and Canada but are now found only in Central Asia. More information can be found in this site.