SORCERER

SORCERER is the tree parser generator of ANTLR.

Papers

• TerenceParr. Language Translation Using PCCTS and CPP. A Reference Guide. Automata Publishing Company, San Jose, Ca. 1993. Availble from http://www.antlr.org/buybook.html

• TerenceParr. An Overview of SORCERER: A Simple Tree-Parser Generator. April, 1994. http://www.antlr.org/papers/sorcerer.ps

---

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