Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Precedences for conctypes
Aasa A.  Functional programming languages and computer architecture (Proceedings of the conference, Copenhagen, Denmark, Jun 9-11, 1993)83-91.1993.Type:Proceedings
Date Reviewed: Nov 1 1994

The notion of concrete datatypes (conctypes) was worked out in earlier papers. Briefly, such a conctype looks like a context-free grammar where the nonterminals correspond to types. In the first part of the paper, the author considers this idea. Easy arithmetical examples show that systematic use of unambiguous conctypes would lead to complicated syntax and, therefore, to complicated computations.

How can we take notice of ambiguity? The second part of the paper deals with the use of precedences to solve recursive ambiguity, an extension of the ambiguity in parsing arithmetical expressions. More precisely, the author suggests a technical definition of precedence grammars, for which some parse trees will be legal and others illegal. The correct parse trees can be characterized through an associate attribute grammar, which is formally described. Finally, the author shows how to incorporate precedence rules in the general context-free parsing algorithm of Earley.

The paper is part of the proceedings of a conference, so the author had no room to give full particulars, and it is difficult to assess the effectiveness of the approach. I hope for a more detailed account.

Reviewer:  F. Aribaud Review #: CR117964
Bookmark and Share
 
Data Types And Structures (D.3.3 ... )
 
 
Classes Defined By Grammars Or Automata (F.4.3 ... )
 
 
Parsing (F.4.2 ... )
 
 
Type Structure (F.3.3 ... )
 
 
Formal Languages (F.4.3 )
 
 
Grammars And Other Rewriting Systems (F.4.2 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Data Types And Structures": Date
Advances in database programming languages
Bancilhon F. (ed), Buneman P., ACM Press, New York, NY, 1990. Type: Book (9780201502572)
Aug 1 1991
Pascal and beyond
Fisher S., Reges S., John Wiley & Sons, Inc., New York, NY, 1992. Type: Book (9780471502616)
Sep 1 1992
On the exact complexity of string matching
Galil Z., Giancarlo R. SIAM Journal on Computing 21(3): 407-437, 1992. Type: Article
Mar 1 1993
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