SORCERER

Program-Transformation.Org: The Program Transformation Wiki
SORCERER is the tree parser generator of ANTLR.

Papers


Review

SORCERER is the tree parser generator for the ANTLR language processing system. SORCERER generates tree walkers from tree grammars. A tree grammar is a BNF like notation for the definition of tree structures. For example, the grammar

exp : #(PLUS exp exp)
    | INT
describes expression trees composed from integers and addition.

Tree translations and transformations are achieved by associating actions with the grammar productions. Translations to textual output are achieved by printing actions. For example, the following grammar prints expressions using infix notation.

exp : #(PLUS exp <<printf("+");>> exp)
    | i:INT <<printf("%d", i);>>
Tree transformations are achieved by reconstructing trees and returning them as results. For example the following grammar transforms expressions by swapping the arguments of the \texttt{PLUS} operator.
exp :! #(PLUS l:exp r:exp) <<#exp = #(PLUS r l);>>
    | INT

Grammar non-terminals can have arguments that can be used in the actions in productions. Non-terminals can also return results. A tree grammar gives rise to a set of mutually recursive functions, one for each non-terminal, that together define a one-pass traversal over a tree. Patterns can be nested and can use regular tree expressions with optionals, alternatives and lists.

Transformation rules in tree grammars are embedded in grammar productions. Separation of rules and strategies and generic tree traversals are not supported in SORCERER.

-- EelcoVisser - 30 Apr 2001


CategorySystem