Computing Reviews

Precedences in specifications and implementations of programming languages
Aasa A. Theoretical Computer Science142(1):3-26,1995.Type:Article
Date Reviewed: 03/01/96

Aasa presents a parser-independent definition of languages generated by a subclass of context-free grammars with precedence rules. He then develops an algorithm that transforms such a grammar into an unambiguous one. Apart from its theoretical interest, this algorithm can be used to parse a language with a precedence grammar when one employs a method that cannot handle precedence rules.

The grammars considered, called distfix precedence grammars, contain infix, postfix, prefix, and closed operators together with both precedence and associativity rules. The author introduces the notion of a precedence correct syntax tree and then establishes the uniqueness of such a tree for each sentence generated by a distfix grammar. He then proves that these trees generate the correct language by showing that an operator precedence parser gives as a result exactly the precedence correct trees.

The transformation algorithm uses the above-defined terms in order to generate a grammar that has more than one nonterminal symbol for each syntax tree. These nonterminals indicate which operators are allowed to occur in the derived syntax trees. The author then refers to an application of the algorithm in the implementation of an experimental language.

Although the paper is technical, the examples and figures make it easy to read and comprehend. The definitions and algorithm presented are new, and they extend the power of parsing techniques in programming languages.

Reviewer:  Spiros Diamantis Review #: CR119438 (9603-0197)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy