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.