Synx: Integrated Compiler Construction Kit

Overview

Project Synx has the aim of writing an integrated compiler construction kit. Currently, the toolbox contains a scanner & parser generator, and tools for abstract syntax tree representation. From a single integrated grammar file, the Synx tool generates:

• a regular scanner
• a context-free parser, according to the following classes of grammars:
  • SLL(k)
  • LR(1)
  • LALR(1)
  • nondeterministic parser (fallback solution)

In particular, you do not need to know the class of the grammar in advance before choosing a parser generator tool but have all choices at the tip of your fingers. Still, Synx is a research prototype and not as mature as other tools. Next, I plan to provide generators for PAG attribute grammar evaluators on the abstract syntax tree. Synx has been implemented in the functional logic programming language Mercury. An α-version of Synx is available for download. For a brief motivating description of what scanners and parser do, take a look at the HTML Parser-Example.

Example

For a very simple example of an expression grammar, take a look at the following Synx grammar description file.

E --> E "+" T.
E --> T.
T --> T "*" F.
T --> F.
F --> identifier.
F --> "{" E "}".
identifier --> "[a-z]([a-z])*".
<SKIP> :--> " ".

This grammar declares three nonterminals E (short for expression), T (short for term) and F (short for factor). Automatically it declares some terminals, first for each explicit string like "+", and second Synx will detect that the nonterminal identifier can be reduced to a synonym for a terminal token type. The regular expression of the string defining the terminal identifier matches any non-empty sequence of small letters a to z.

The special <SKIP> production is additional syntax for declaring what characters the generated scanner should simply skip and ignore.

After Synx generates a scanner and a parser from the above integrated grammar description file, expressions like the following can be parsed.

1. a + b * c
2. a + {b + c} * d
3. a + b * {c + dag}
4. a*{b +c}*d+ff*eff
5. {a*{b+c}*{{d+xyz}+z}}

For example, Synx can produce a (simplified) abstract syntax tree for the example 2 that looks like this (excuse the preliminary ascii arts version)

  a + { b + c } * d
  | | | | | | | | |
  | |  \ \|/ /  | F
  | |   \ E /   | |
  | |    \|/    | |
  | |     F     | |
  | |      \    | |
  | |       \   | |
  | |        \  | |
  | |         \ | |
  | |          \|/
  | |           T
  | |         _/
  | |       _/
  | |     _/
  | |   _/
  | | _/
   \|/
    E

Download

If you want to give the Synx compiler construction kit a try,

• download Synx and its source code in Mercury