The Forlan toolset is a collection of tools for experimenting with formal languages. Forlan is implemented in the functional programming language Standard ML (SML), a language whose notation and concepts are similar to those of mathematics. Forlan is used interactively, in conjunction with the Standard ML of New Jersey (SML/NJ) implementation of SML. In fact, a Forlan session is simply an SML/NJ session in which the Forlan modules are pre-loaded. Users are able to extend Forlan by defining SML functions.
In Forlan, the usual objects of formal language theory—finite automata, regular expressions, grammars, labeled paths, parse trees, etc.—are defined as abstract types, and have concrete syntax. Instead of Turing machines, Forlan implements a simple functional programming language of equivalent power, but which has the advantage of being much easier to program in than Turing machines. Programs are also abstract types, and have concrete syntax. Although mainly not graphical in nature, Forlan includes the Java program JForlan, a graphical editor for finite automata and regular expression, parse and program trees. It can be invoked directly, or via Forlan.
Numerous algorithms of formal language theory are implemented in Forlan, including conversions between regular expressions and different kinds of automata, the usual operations (e.g., union) on regular expressions, automata and grammars, equivalence testing and minimization of deterministic finite automata, and a general parser for grammars. Forlan provides support for regular expression simplification, although the algorithms used are works in progress. It also implements the functional programming language used as a substitute for Turing machines.
This manual must be read in conjunction with the Forlan textbook, Formal Language Theory: Integrating Experimentation and Proof, by Alley Stoughton. The primary reference for mathematical definitions—including algorithms—is the textbook; the primary reference for the module specifications is the manual. Typically it will be necessary to consult the book to understand not only the input/output behavior of a function, but also how the function transforms its input to its output, i.e., the algorithm it is following.
The function useinput functions provided by various modules for loading Forlan objects from files, and the lexical analysis function Lex.lexFilegetWorkingDirectorygetSearchPathuse function re-loads the most recently loaded file, if called with the empty string, "".
The input functions and Lex.lexFile read from the standard input, when called with the empty string, "", instead of a filename. When reading from the standard input, Forlan prompts with its input prompt, "@", and the user signals end-of-file by entering a line consisting of a single period ("."). The function Lex.lexFile first strips the contents of a file (or the standard input) of all whitespace characters and comments, where a comment consists of a "#", plus the rest of the line on which it occurs. And the input functions work similarly, before beginning the process of parsing a Forlan object from its expression in Forlan's concrete syntax. Consequently, whitespace and comments may be arbitrarily inserted into files describing Forlan objects, without changing how the files will be lexically analyzed and parsed. An input function issues an error message if a file's contents doesn't describe the right kind of Forlan object, or if not all of the file's contents is consumed in the process of parsing such an object. The various fromString functions work similarly to the input functions, except that they operate on the contents of strings.
The output functions provided by various modules for pretty-printing Forlan objects to files create their files in the current working directory. When given a pre-existing file, they overwrite the contents of the file. They output to the standard output, when called with "" instead of a filename. The various toString functions work similarly to the output functions, except that they produce strings.
This section contains specifications of Forlan's modules. The Auxiliary Functions subsection describes modules providing auxiliary functions for some SML types. The Utilities subsection describes modules for querying and setting various Forlan parameters (e.g., the search path used by input functions, and the line length used by the pretty-printer), doing pretty-printing, issuing informational and error messages, loading SML files, and doing debugging. The Sorting, Sets, Relations and Tables subsection describes modules implementing sorting, the abstract type of finite sets, operations on finite relations, and the abstract type of finite tables. The Lexical Analysis subsection describes Forlan's lexical analysis module. The Symbols and Strings subsection describes modules relating to Forlan symbols and strings. The Regular Expressions and Finite Automata subsection describes modules relating to regular expressions and finite automata. The Grammars subsection describes modules relating to context-free grammars. And, the Programs subsection describes modules relating to programs—Forlan's alternative to Turing machines.
For convenience, some types and values are made available in Forlan's top-level environment. The Top-level Environment subsection lists those types and values as well as the modules that they come from.
Forlan Version 4.15
Copyright © 2022 Alley Stoughton