A computer program implements two extensions of ANTLR (Another Tool for Language Recognition), which is a set of software tools for translating source codes between different computing languages. ANTLR supports predicated-LL(k) lexer and parser grammars, a notation for annotating parser grammars to direct tree construction, and predicated tree grammars. [“LL(k)” signifies “left-right, leftmost derivation with k tokens of look-ahead,” referring to certain characteristics of a grammar.]

One of the extensions is a syntax for tree transformations. The other extension is the generation of tree grammars from annotated parser or input tree grammars. These extensions can simplify the process of generating source-to-source language translators and they make possible an approach, called “polyphase parsing,” to translation between computing languages. The typical approach to translator development is to identify high-level semantic constructs such as “expressions,” “declarations,” and “definitions” as fundamental building blocks in the grammar specification used for language recognition. The polyphase approach is to lump ambiguous syntactic constructs during parsing and then disambiguate the alternatives in subsequent tree transformation passes. Polyphase parsing is believed to be useful for generating efficient recognizers for C++ and other languages that, like C++, have significant ambiguities.

This program was written by Loring Craymer of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Software category.

This software is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (818) 393-2827. Refer to NPO-30565.

This Brief includes a Technical Support Package (TSP).

Unfortunately the TSP ANTLR Tree Grammar Generator and Extensions (reference NPO-30565) appears to be missing from our system.

Please contact This email address is being protected from spambots. You need JavaScript enabled to view it. for assistance in retrieving it.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the September, 2005 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.