7.1.3.5 Reverse Order Sequences ¶

A reverse order sequence is a sequence with a FIRST set determined by the last element of the sequence. In the notation of a reverse order sequence, its last element goes first:

ElementN <- ... <- Element2 <- Element1

The operator ‘<-’ has greater precedence compared to the operator ‘|’.

A reverse order sequence is a means of parsing a nonterminal symbol sequence defined by a bottom-up template grammar. This parsing involves the use of #d specifier described in Deferring a Terminal Symbol.

In a top-down template grammar, to the nonterminal symbol sequence there corresponds a terminal symbol sequence consisting of virtual nonterminal symbols—terminal symbols with names consisting of ‘_’ followed by a nonterminal symbol name. A set of alternatives represented by reverse order sequences for parsing a set of alternatives represented by nonterminal symbol sequences defined by a bottom-up template grammar has the form:

  C ( VN1,1 VN1,2 ... VN1,m1 <- #d C1,2 #d ... Cm1 #d
    | VN2,1 VN2,2 ... VN2,m2 <- #d C2,2 #d ... Cm2 #d
    | ...
    | VNn,1 VNn,2 ... VNn,mn <- #d Cn,2 #d ... Cmn #d
    )

Here a nonterminal symbol C outputs a virtual nonterminal symbol belonging to a virtual nonterminal symbol class VN_1,1, VN_2,1, …, or VN_n,1. A parser selects an alternative i matching the virtual nonterminal symbol and executes an expression #d Ci,2 #d … Cmi #d at the right-hand side of ‘<-’. The specifier #d at the beginning of that right-hand side defers the virtual nonterminal symbol until finishing processing the right-hand side. A nonterminal symbol C_i,2 outputs the second virtual nonterminal symbol deferred by the second #d. The parser repeats calling nonterminal symbols and deferring output virtual nonterminal symbols until finishing processing a nonterminal symbol C_mi and #d at the end of the right-hand side. After that, the parser converts a sequence of deferred virtual nonterminal symbols to a sequence of input virtual nonterminal symbols consumed by an expression VNi,1 VNi,2 … VNi,mi at the left-hand side of ‘<-’.

Example

To the bottom-up template grammar

S: A A
 | B B C
 | C B B
;

A: "a" . ;
B: "b" . ;
C: "c" . ;

there corresponds the top-down template grammar

S: C1 ( "_A" "_A" <- #d C2 #d
      | "_B" "_B" "_C" <- #d C3 #d C4 #d
      | "_C" "_B" "_B" <- #d C3 #d C3 #d
      )
;

C1: "%a" . < "_A" >
  | "%b" . < "_B" >
  | "%c" . < "_C" >
;

C2: "%a" . < "_A" > ;
C3: "%b" . < "_B" > ;
C4: "%c" . < "_C" > ;

The terminal symbols "%a", "%b", and "%c" are virtual terminal symbols for the terminal symbols "a", "b", and "c" in the bottom-up template grammar. The terminal symbols "_A", "_B", and "_C" are virtual nonterminal symbols for the nonterminal symbols A, B, and C in the bottom-up template grammar.