Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Precedences in specifications and implementations of programming languages
Aasa A. Theoretical Computer Science142 (1):3-26,1995.Type:Article
Date Reviewed: Mar 1 1996

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)
Bookmark and Share
 
Formal Languages (F.4.3 )
 
 
Grammars And Other Rewriting Systems (F.4.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Formal Languages": Date
The three subfamilies of rational &ohgr;-languages closed under &ohgr;-transduction
Timmerman E. Theoretical Computer Science 76(2-3): 243-250, 2001. Type: Article
Jul 1 1992
Introduction to formal languages
Révész G., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486666976)
Jan 1 1993
Fibonacci morphisms and Sturmian words
Séébold P. Theoretical Computer Science 88(2): 365-384, 1991. Type: Article
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy