Reversed iXML grammars

During some discussion yesterday about the possibility of running an 
Earley parser in a reverse direction across the input string, I 
suggested that by 'reversing' an iXML grammar and running across a 
reversal of the input text, you should get a parse tree which is a 
mirror image of the normal parse tree. Using the following steps on an 
iXML grammar:

 1. Children of only an *alt *are reversed in order
 2. the characters of *@string* of a *literal* are reversed

produces a new grammar. E.g. for the *address* sample:

address: person, lf, street, lf, postcode, city, lf, country, lf;
          person, lf, street, lf, city, postcode, lf, country, lf.
person: (title, S?)?, (initials; given, S), surname, S?.
title: "Mr."; "Mrs."; "Dr."; "Ms.".
initials: initial+.
initial: LETTER, ".", S?.
surname: name.
given: name.
-name: LETTER, letters.
street: no, S?, streetname; streetname, S?, no, S?.
streetname: name, S; name, S, name.
city: name, S; name, S, name, S.
country: name, S?; name, S, name, S?.
postcode: digits, S, LETTER, LETTER, S?;
           LETTER, LETTER, digits, S, digit, LETTER, LETTER, S?.
no: digits.
-LETTER: ["A"-"Z"].
-letters: ["a"-"z"]*.
-digit: ["0"-"9"].
-digits: ["0"-"9"]+.
-S: " "+.
-lf: -#a | -#d, -#a .

we get a new grammar:

    address: lf, country, lf, city, postcode, lf, street, lf, person |
             lf, country, lf, postcode, city, lf, street, lf, person.
     person: S?, surname, (initials; S, given), (S?, title)?.
      title: ".rM"; ".srM"; ".rD"; ".sM".
   initials: initial+.
    initial: S?, ".", LETTER.
    surname: name.
      given: name.
      -name: letters, LETTER.
     street: streetname, S?, no |
             S?, no, S?, streetname.
streetname: S, name |
             name, S, name.
       city: S, name |
             S, name, S, name.
    country: S?, name |
             S?, name, S, name.
   postcode: S?, LETTER, LETTER, S, digits |
             S?, LETTER, LETTER, digit, S, digits, LETTER, LETTER.
         no: digits.
    -LETTER: ["A"-"Z"].
   -letters: ["a"-"z"]*.
     -digit: ["0"-"9"].
    -digits: ["0"-"9"]+.
         -S: " "+.
        -lf: -#a |
             -#a, -#d.

Running /backwards /over the sample:

Steven Pemberton
21 Sandridge Road
St Albans AL1 4BY
United Kingdom

Produces a tree:

<address>
     <country>modgniK detinU</country>
     <postcode>YB4 1LA</postcode>
     <city> snablA tS</city>
     <street>
         <streetname>daoR egdirdnaS</streetname>
         <no>12</no>
     </street>
     <person>
         <surname>notrebmeP</surname>
         <given>nevetS</given>
     </person>
</address>

which is an exact mirror image (document order, modulo attribute order, 
reversed *text()|attribute()*) of the normal result:

<address>
    <person>
       <given>Steven</given>
       <surname>Pemberton</surname>
    </person>
    <street>
       <no>21</no>
       <streetname>Sandridge Road</streetname>
    </street>
    <city>St Albans </city>
    <postcode>AL1 4BY</postcode>
    <country>United Kingdom</country>
</address>

This suggests that programmatic exploration of a bidirectional Earley 
parser (working from both ends towards a join somewhere in the middle) 
could be possible.

-- 
*John Lumley* MA PhD CEng FIEE
john@saxonica.com