This section contains an overview on the Styx framework and a comparison with lex/yacc combination.
To give an idea what Styx is about, we first look on the overall compilation process (see diagram 1) as supported by this tool:
Source Rewrite Object
Derivation ------------------> Derivation
Tree Tree
^ |
| |
| |
Parse = Unparse
| |
| |
| V
Source - - - - - - - - - > Object
Code Translate Code
The diagram commutes, i.e. the following equation holds:
Translate(Source) = Unparse(Rewrite(Parse(Source)))
By this equation, the translation falls apart into a combination of three steps,
While both the source and the object are considered to be (textual or binary) strings, the intermediate forms within the compilation are trees, i.e. hierarchical subdivisions of their respective linear counterpart.
The first and the last step of a translation are string-to-tree and tree-to-string transformations, while the inner step is a tree-to-tree transformation, the heart-piece of the translation.
To simplify the inner translation, we are interested to have a simple structure, if possible, thereby not only omitting keywords but also other language features often referred to as "syntactic sugar".
Not only the internal representation of both the source and the object distinguishes itself from the external one. Referring to their grammars, we call the grammars of the string representations the surface grammar of the languages, while the simpler, internal grammar is called the depth grammar.
Also, while syntactical notions may apply well to the external strings, the rewriting can be further simplified if the trees are treated as terms, thereby allowing algebraic means and notions to be applied. By this, the depth grammar becomes a recursive system of the types of the terms.
In practice, having done the step from and to the linear forms is a substantial gain. By having abstracted from the surface properties of a concrete code to be translated, and having arranged things to be handable as subdivided parts, a reduction of the complication of the translation process is achieved.
The advantage of this construction may not be apparent to someone with few experience in compiler writing. Especially, having a derivation tree may not appear as a gain w.r.t. the "semantic actions" of yacc. Yacc's semantic actions have been designed to support one pass compilation, meaning the code generation intentionally happens during parsing and is in fact controlled by the parser.
While this approach was necessary in times when memory was extremely short, it has consequences on the language design. As soon as definitions become recursively, which is the case for every non-trivial language, a one pass compilation is not longer possible. This has lead to work-around constructions like forward-declaration and header-files.
Additionally, many constructions can not be compiled into code immediately or need to produce entries in so-called symbol tables. Typical examples are all sorts of definitions. The texts that constitutes these definitions has to be translated to some internal form anyway.
As soon as a derivation tree of the source becomes available, these complications and hand-crafted representations are not longer necessary. Because representations of the definitions are already present, one could simply refer to the definition's derivation tree. Dealing with recursive constructions, any number of passes can both easily and efficiently been done over the tree, i.e. collecting the recursive definitions in a first go only considering the headers and using them in the second, diving into to bodies.
The more complicated the compilation process would be with yacc the more substantial becomes the gain from using this framework. Practically, a compiler writer will therefore construct a derivation tree within yacc's semantic actions anyway. Generating this from the grammar, is the most substantial advantage of Styx over the lex/yacc combination.
The advantage of this framework becomes even more clear, if one thinks of an interpreted language. Because Styx also provides means to make the derivation tree persistent, the complete "compilation" of such languages may eventually been done by it. After writing down the grammar, the language designer can immediately concentrate on writing the interpreter, instead of being bothered with making an internal representation of the source, which is already provided by the Styx framework. Even in making such an interpreter, Styx gives some support by offering an appropriate interface to the source tree.
Styx is designed to handle the first and the last step of the translation, that is, both the parsing and unparsing, or the string-to-tree and tree-to-string transformations, both for the cases that the source or the object are textually or binary represented.
Given a surface grammar, it does not only produce a scanner and a parser, but also automatically derived the depth grammar, creates the derivation tree (term) and provides a versatile interface oriented on the abstract language.
The unparsing is done by means of a pretty printer, or, if a binary format is of interest, it supports making the tree persistent. This is especially useful for interpreted languages when not instruction code is produced, but the derivation tree is evaluated directly.
Additionally, the result of the parsing process still maintains all source information including keywords and comments. By this, source-source translations are easily implemented with this tool, too.
While lex and yacc were designed to cope with the many annormalities used in (surface) language design, Styx is somewhat more restrictive. It preferably supports languages designed by a canonical, two level model.
By this, the tokens separated by the scanner have to be in regular grammars, and the context-free language has to be deterministic (LALR(1)).
This excludes versatile support of some constructions that we considered to be weird. Examples are nested comments (non-regular) or languages that have no context-free grammar (like C, which comes with the context-dependent "typedef" construction).
This decision was be made because Styx has been used for internal language design, therefore it did not have to cope with all the oddities out. Now that we have released Styx to public use, this design decision may cause troubles to other people, although one can work around these restrictions.
lex and yacc follow a different concept. Basically, they do not even provide the first step of this framework. Instead of providing the generation of a derivation tree, the allow to add "semantic actions", which means in most cases, that the tree has to be hand-crafted and constructed manually within the action slots.
The central disadvantage of lex/yacc's approach is, that the burden of designing and making this structures is placed on the shoulders of the developers. Not only, that this costs quite a lot of time, it also typically leads to unsystematically constructed internal structures and a non-comformant interface to them, if any. Often, the raw implementation of the tree structure is used instead, making changes in it's representation a subtle task.
Styx's restriction mentioned in the previous section are not substantial. Styx provides means to cope with annormalities, but the slots where one can handle them are as weird as these language features are themselves. Since Styx is available in source form, one may additionally adjust it to strange needs. So, comparing to lex/yacc, the restrictions are minor. It only means that when one does weird things, the implementation may become weird in these places and the support less handy.
More substantial restrictions are both in the parser and scanner. The parser is LALR(1), which means that a look-ahead of only one token is supported. Likely the scanner. It does a look-ahead of only one character. This later restriction has been introduced to guarantee an effective scanner, which is linear by the length of the string, while lex provides an arbitrary look ahead, meaning that lex complexity can become quadratic for annormal token designs. Again, this is not real issue. The scanner generator would not be effected, and the scanner itself could be easily extended to lex' behavior.
Additionally, lex allows to switch between different sets of tokens (languages) to be able to do even more weird things. This is not supported by the Styx scanner at all. But like the lex/yacc combination, the scanner and parser are separated within Styx (also much more integrated), so one can plug-in any other, even a hand-crafted scanner, if nothing else helps. The disadvantage of doing so is again, that the many supports that Styx offers for the canonical design do not apply anymore. One has to write additional code, about to the amount that people applying the lex/yacc combination are already used to.