Ressources


Moodle

Access to the course’s Moodle at Enseeiht, for those with the right registration.

Tools and API

  • VCSN: a platform dedicated to the computation of finite state machines. (C++, Python)

  • available as a Docker image, with Jupyter: docker run -d -p 8888:8888 lrde/vcsn:2.8

  • The MIT Finite-State Transducer Toolkit

  • DFKI finite-state machine toolkit (C++)

  • couchbase/vellum: A Go library implementing an FST (finite state transducer)

  • BurntSushi/fst: Represent large sets and maps compactly with finite state transducers. (Rust)

  • JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.

Bookmarks and such

References

Parser Generators

  • ANTLR, or Another Tool For Language Recognition is a parser generator for LL(*). Based on an EBNF syntax.

  • Yacc, the “original” Compiler Compiler for UNIX. It is a Look Ahead Left-to-Right (LALR) parser generator. For modern usage, look at Bison, the GNU version of Yacc, or the pair camllex and camlyacc. Yacc is based on attribute grammars, mixing C code with rules definitions, and a separate program for the lexical analyzer part (e.g. flex).

  • Menhir, another parser generator for OCaml, that supports LR(1) grammar specifications.

  • Packrat Parsing an alternative to the use of context-free grammars based on the idea of ordered choice operator, which removes the problems related with ambiguities.

  • Parser Combinators provide another way to build parsers from specifications; see e.g. Higher-order functions for parsing. G. Hutton. Journal of Functional Programming. 2(3). 1992.

Everything is on Wikipedia

Applications of Formal Language Theory