Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Extending context-free grammars with permutation phrases
Cameron R. ACM Letters on Programming Languages and Systems2 (1-4):85-94,1993.Type:Article
Date Reviewed: Dec 1 1994

In this pithy and interesting paper, the author proposes the permutation phase as a notational extension for Backus-Naur form (BNF) grammars. Like optionality ([…]) and iteration ({…}), this extension improves the clarity and conciseness of grammars but does not increase their definitional power beyond the context-free level. A permutation phrase of the form ⟨⟨ e 1 ∥ e 2 ∥ ... ∥ e n ⟩⟩ is equivalent to an alternation of the n ! different concatenation sequences containing exactly one occurrence of each grammatical phrase e i. For example, the production rule X ::= ⟨⟨ b ∥ [ C ] ∥ d E ⟩⟩ is equivalent to

X::= b [ C ] d E | b d E [ C ] | [ C ] b d E | [ C ] d E b | d E [ C ] b | d E b [ C ]

The author uses the syntax of C language declarations to illustrate the expressive utility of permutation phrases and investigates the feasibility of constructing reasonable-sized, linear-time, top-down parses for grammars containing such phrases. He shows that recursive-descent-style parsing is possible whenever the following criteria are satisfied:

  • no optional constituent of any permutation phrase derives a string beginning with any terminal symbol a in the FOLLOW set of the phrase;

  • for no terminal symbol a do any pair of constituents of any permutation phrase derive strings beginning with a; and

  • the grammar is otherwise LL(1).

The paper will be readily understandable to readers with a good knowledge of grammars and parsers for programming languages. The relationship to earlier work is adequately documented by the references. From the perspective of language specification alone, the concept of the permutation phrase is of such evident worth that one might wonder why no one has proposed it before. From the perspective of parser construction, the author has done a creditable job as far as top-down analysis is concerned; the feasibility of bottom-up parsing for grammars with permutation phrases is, as suggested in the paper’s conclusion, the aspect for which further investigation is most obviously indicated.

Reviewer:  F. G. Pagan Review #: CR118401
Bookmark and Share
 
Syntax (D.3.1 ... )
 
 
Grammar Types (F.4.2 ... )
 
 
Parsing (D.3.4 ... )
 
 
Language Constructs and Features (D.3.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Syntax": Date
Formal syntax methods for natural language
Johnson D., Bryant B. Information Processing Letters 19(3): 135-143, 1984. Type: Article
Jun 1 1985
On the (non-) relationship between SLR(1) and NQLALR(1) grammars
Bermudez M., Schimpf K. ACM Transactions on Programming Languages and Systems 10(2): 338-342, 1988. Type: Article
Oct 1 1988
User-friendly syntax: design and presentation
Henno J. International Journal of Man-Machine Studies 28(5): 551-572, 1988. Type: Article
Jun 1 1989
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