Grammars with attributes and their implementation as smart parsers in ocaml

• Using the camlp4o "parser" syntax and its automatic translation to ocaml
  1. A simple example (and many refinments): anbn_parser.ml, its translation into pure ocaml: anbn.ml
  2. Arithmetic expressions: expr_parser.ml, expr.ml
  3. Declarations of variables in C: decl_parser.ml, decl.ml
  4. More realistic examples (require extStream.ml)
     1. A stream parser that skip spaces and returns a token (=typed word) stream: token_parser.ml
     2. A translation from Pascal assignments to optimized Ocaml code: assignement_parser.ml
        (requires the previous token_parser)
• Without camlp4o: Parsers that return the remaining sequence of chars
  A simple example (and many many refinments): anbn.ml
• The Wizard level: Parser combinators that can deal with ambigous grammars
  A simple ambigous grammar and its simple parser: as_many_as.ml

Automata: infinite languages finetely represented

• Visual Automata Simulator
• An ocaml library on automata: main.ml
  1. Representation of Finite State Automata: automata.ml
  2. Language of a Finite State Automaton: language.ml, test.ml
  3. Determinization of Finite State Automata: determinization.ml, test.ml
  4. Complementary of Finite State Automata: complementary.ml, test.ml
  5. Product of Finite State Automata: product.ml, test.ml
  6. Minimization of Finite State Automata: minimization.ml, test.ml
  7. Thompson's constructions: thompson.ml, test.ml
  8. Elimination of epsilon transitions: epsilon.ml, test.ml
  9. Applications:
     • exo-AEF-modelisation-protocoles-medicaux.ml
     • exo-AUT-construction-reconnaisseur-avec-implication-2.ml

Student Projects

• projet 2011 - Implantation d'un gestionnaire de processus à base d'automate (ocaml): multi-threading.ml
• projet 2010 - Réalisation de l'interface d'un téléphone portable à l'aide d'automate à pile (C)
  Implantation du cas particulier des automates avec mémorisation de l'état de retour: stack-dfa.c
• projet 2009 - Implantation des automates à espace d'états fini:
  • Deterministic Finite Automata (C): dfa.c
  • Non-Deterministic Finite Automata (C): ndfa.c