Balisage Paper: Converting typesetting codes to structured XML

Phase 1 — Lexical

The first phase is the lexical phase, which assigns distinct tokens to locators (sometimes a set of locators), page breaks, comments, and text.

Sample:

< DEFAULT, STATE5804, ACT, TOCACT, PUBL, STATUTESATLARGE, PROX, INDEX, IN_TABLE_BODY > TOKEN :
  {
    < PAGEBREAK : "\u0007A"  | ("\u0007\u00AEMD" (~["\u00AF", "\u0007"])* "\u00AFA") > 
  }
        
< DEFAULT, STATE5804, ACT, PUBL, TOCACT > TOKEN :
  {
    < TITLEROOT : "\u0007R01" >
    | < APPENDIXROOT : "\u0007R05" >
    | < ABOVESECTION  : "\u0007R"["0"-"9"]["0"-"9"] >
    | < I81  : "\u0007I81" >
    | < STARTTABLE : (" ")* "\u0007c" > { stateBeforeTable = curLexState; } : DEFAULT 
  }
        
< DEFAULT, STATE5804, ACT, PUBL, TOCACT, STATUTESATLARGE > TOKEN :
  {
    < GRAPHICFILE : "\u0007gs"(",il")?(",w"(["0"-"9"])+)?",d"(["0"-"9"])+(",rl")?("\r"|"\n")*"\u0007I9"("1"|"4"|"5")(" ")*>
  }

The < DEFAULT> or < ACT> part are what is called the "lexical state" of the parser. A lexical state is usually set by the <bell>F[0-9]+ or <bell>S[0-9]+ styles found in the input, so that when the parser recognizes a <bell>S used in Public Laws it sets the PUBL state.

Let us look at the first three lines of lexical definitions above:

< DEFAULT, STATE5804, ACT, TOCACT, PUBL, STATUTESATLARGE, PROX, INDEX, IN_TABLE_BODY > are the states for which the following token is defined.

<PAGEBREAK> is the lexical token being defined, following the ":" is a JavaCC regular expression matching the token. That is either a bell 0x07 followed by an ASCII "A" or a sequence made from a 0x07 (a bell) followed by 0x0AE, itself followed by the ASCII string "MD", then a series of bytes containing neither a 0xAF nor a 0x07 byte and closed by a 0xAF byte followed by an ASCII "A".

The textual content of the token is available to further phases. We will see how this is done later.

Phase 2 — Syntactical

The second phase is the syntactical phase. It uses and analyzes the tokens produced by the lexical phase according to a formal grammar defined in JavaCC. This grammar is defined by the syntactic specification of the input.

When a token specified in the lexical analysis is matched, it is returned into a Token variable which may be used by the syntactical parser. The Token contains several fields, notably:

So, in the syntactic specification, the code t = < I15STATS > means that if the input stream matches the < I15STATS > lexical token, t will contain a Token object containing the fields mentioned above. t.image will contain "\u0007I15" since the token I15STATS was defined as:     < I15STATS : "\u0007I15" >.

A syntactical code snippet may look like the sample below which handles Front Matter Notes in Statutes:

   
[< PAGEBREAK > { ipi = new InlineProcessInstruction("page", new ArrayList<TextRun >()); ipi.generate(gen); }]
              
  {
    gen.println("<note>");
  } 
                
  (
    t = < I15STATS >  formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I20STATS >  formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I21STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I22STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I23STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I24STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I25STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I26STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I27STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < I37STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    t = < PAGEPUBL > { ipi = new InlineProcessInstruction("page", extractPagePubl(t)); ipi.generate(gen);}
    |
    t = < I39STATS > formattedLine() { gen.genericP(getCurrLoc(t), t.beginLine, ctrl); }
    |
    < F9787 >
  ) +
                
  {
    gen.println("</note>");
  }

This can be read as follows:

a note may be preceded by an optional PAGEBREAK token, if a PAGEBREAK is encountered then the code between the braces "{...}" is executed: an InlineProcessInstruction of type "page" is created and immediately generated (added to the output file). Then follows the note itself, which may contain I15/I20/I21/... locators (in the STATS [statutes] state) as well as page numbers or F9787 format codes, which are ignored.

Each of these IxxSTATS (where xx indicates a number such as the 20 in the locator code I20) line may be followed by what is known as a formattedLine() itself a set of rules. These formattedLine contain text which maybe styled (include italics, bold characters, etc.) A series of characters styled the same way is called a Text Run. The formattedLine() methods returns a set of text runs stored in a global variable called ctrl (current text run list).

Each of these IxxSTATS will generate a <P> in the note opened. The gen.genericP() method has three arguments: the locator saved in the t variable, the line where the IxxStats locator was encountered in the input file (for debugging purposes) and the set of Text Runs returned by the formattedLine().

Some notes may also contain an image file, the parser then adds these lines in that case:

t = < GRAPHICFILE > formattedLineNoQ() {
  Graphic g = new Graphic(getCurrLoc(t), t.beginLine, t.image, ctrl);
  g.generate(gen);
}
                

which can be read as follows: when a GRAPHICFILE token is encountered and followed by a formattedLine containing no <bell>Q, save this token and its associated data in the t variable. Then, execute the code between the braces {...}, viz. create a Graphic object, where t.image corresponds to the actual string which matches the GRAPHICFILE token defined as a regular expression. Then the graphic object is generated in the output file. We will see how this is done in phase 4.

When an unexpected character is parsed, the parser will raise an error, complaining of an "illegal" sequence. This is almost always triggered by either an unknown locator code, or one that is unexpected in that particular context. Pure ASCII text is allowed almost anywhere by the parser.

This "unexpected character" error was a deliberate design decision to ensure that we properly analyzed the input file and did not drop or ignore semantically important constructs. This creates a strict and rigorous parser, which is important since the locator files do not have a well-defined grammar. In fact, since there are potentially many ways to create the same apparent output (whether print or PDF), it is important to catch any potential errors so that the parser does not miss any important structures. The approach chosen was one of slow refinement of the parser to remove successive "illegal" sequence exceptions. However, the parser may handle input we do not want to interpret in detail by using the "lexical state" mentioned in the lexical parser phase.

The lexical definition below states that in the STATE5804 state (typically, this means the last <bell>S encountered was a S8504) any unknown locator (<bell> I [0-9][0-9]) will be treated as a S5804LOCATOR token.

< STATE5804 > TOKEN :
  {
    < S5804LOCATOR : "\u0007I"["0"-"9"]["0"-"9"] >
  }

The dumpLine() method consumes such S5804LOCATORs and the text runs following them and simply adds them to a RawContent. These will later be generated as a series of <P> elements each containing the text found after that locator.

      
void dumpLine(RawContent rc) throws ParserInternalException :
  {
    Token t;
    int lineNo;
  }
  {
    ...
    |
    (t = < S5800LOCATOR >  formattedLineFN() { rc.addText(getCurrLoc(t), t.beginLine, ctrl);} )
    |
    ...
  }

Let's look at another snippet of code from the syntactical phase: an extract of the parser for Sections. The code snippet in {...} calls the generation phase using the internal structures produced during the parsing

  void section() throws ParserInternalException :
  {
      // local variables
      Token format,headerTok;
      List<TextRun> sectionTr;  
      SectionLevel s;
      escapeNotes = false;
  }
  {
    // grammar

    format = < SECTIONLEVEL > formattedLineFN()    
        // a section starts with a section level token (🔔I80) followed by a formatted line (a list of Text Runs).
        {
          sectionTr = ctrl;
          // if I80 was matched, execute this Java code. It saves the global current text run list
         // to a local copy called sectionTr
        }
   
    headerTok = < SECTIONHEADER >  formattedLineFN()  
        // a section header starts with (I89)
        {
          s = new SectionLevel(getCurrLoc(format), format.beginLine, sectionTr, getCurrLoc(headerTok), ctrl);
          // create a new section Level object, pass it sectionTr, and the text runs after 🔔I89
          s.generateBegin(gen);
          // call the generation of start of the section (<section><num><heading>)
        }
     
    [
      LOOKAHEAD(2) sectionContent(s)  
      // look ahead a couple of lexical tokens, to know if this section has content rather than only notes,
      // if so call sectionContent() method which parses all the section content and stores it inside
      // the SectionLevel s object.
      { s.generateSectionContent(gen); }
      // at the end of the section content parsing, generate and thus decompose the section level's content
    ]
     
    notesAndSourceCredit(s)
    // gather notes and sourceCredit into s
     
    {
      s.generateEnd(gen); // generate end of section level
      escapeNotes = false;
    }
  }

Phase 3 — Decomposition (optional)

The decomposition phase is an optional first step of the generation. It is only necessary for structures which may be nested such as sections or quoted content which may itself contain parts of sections. For other constructs such as images which may not be nested, the XML output can be generated without any decomposition of the object being necessary.

Let's assume we have this locator input corresponding to the start of a section:

🔔I80 ÿ1A309
      
🔔I89. Application for license
      
🔔I19(a) Considerations in granting application
      
🔔I11Subject to the provisions...
      
🔔I19(b) Time of granting application
      
🔔I11Except as provided in subsection (c) of this section, no such application_
      
🔔I12(1) for an instrument of authorization in the case of a station in the broadcasting or common carrier services, or
      
🔔I12(2) for an instrument of authorization in the case of a station in any of the following categories:
      
🔔I13(A) industrial radio positioning stations for which frequencies are assigned on an exclusive basis,
      
🔔I13(B) aeronautical en route stations,
      
🔔I13(C) aeronautical advisory stations, ...

by the end of the syntactical phase (phase 2) we have produced an internal structure equivalent to

<section style="-uslm-lc:I580080">
  <num value="309">§ 309.</num>
  <heading style="-uslm-lc:I580089"> Application for license</heading>
  <content>
    <p style="-uslm-lc:I580019" class="indent2 firstIndent-2">(a) Considerations in granting
        application</p>
    <p style="-uslm-lc:I580011" class="indent0">Subject to the provisions...</p>
    <p style="-uslm-lc:I580019" class="indent2 firstIndent-2">(b) Time of granting
                        application</p>
    <p style="-uslm-lc:I580011" class="indent0">Except as provided in subsection (c) of this
                        section, no such application—</p>
    <p style="-uslm-lc:I580012" class="indent1">(1) for an instrument of authorization in the
                        case of a station in the broadcasting or common carrier services, or</p>
    <p style="-uslm-lc:I580012" class="indent1">(2) for an instrument of authorization in the
                        case of a station in any of the following categories:</p>
    <p style="-uslm-lc:I580013" class="indent2">(A) industrial radio positioning stations for
                        which frequencies are assigned on an exclusive basis,</p>
    <p style="-uslm-lc:I580013" class="indent2">(B) aeronautical en route stations,</p>
    <p style="-uslm-lc:I580013" class="indent2">(C) aeronautical advisory stations,</p>
    ...     </content>
</section>
        

This is the XML output we would produce at this stage without any further processing.

But large constructs such as sections, quotedBlock, or tables are not immediately generated. The parser adds all the components of such constructs (usually as P's for sections) to an internal structure representing the said construct.

The raw internal structure of sections is then analyzed and the list of P's is transformed into a hierarchy with internal structure (subsections, paragraphs, subparagraphs, continuations, clauses, etc.) according to a set of rules mostly based on the leading <num> of each such level but not exclusively since these may be ambiguous, inconsistent or even incorrect.

This process is recursive since sections may contain quoted content (up to three levels) which may themselves contain hierarchical levels.

The decomposition phase is usually called as an optional first step of the generation. A syntactical phase might for instance have between braces :

{
  s.generateSectionContent(gen)
}
      

where s is a SectionLevel object (an instance of a Java class).

SectionLevel.generateSectionContent() then calls the decomposition phase.

Phase 4 — Generation

Finally, the generation phase is invoked to generate the XML. It always operates on internal structures created by the second or third phases.

Let's take the example of Graphic generation seen above. The generation phase is called by g.generate(gen); where g is a Graphic object and gen is the "generator" an object encapsulating the output style (USLM here, it could in theory be HTML or XSL:FO) and the output destination (a file or output stream in this case).

a) So, if the input file contained

🔔gs,w318,d386,r1
🔔I25ED04JA07.005

the lexical token < GRAPHICFILE : "\u0007gs"(",il")?(",w"(["0"-"9"])+)?",d"(["0"-"9"])+(",rl")?("\r"|"\n")*"\u0007I9"("1"|"4"|"5")(" ")*> matches this first line and the following 🔔I25.

b) The parser then consumes t = < GRAPHICFILE > formattedLineNoQ()

As seen above we then instantiate a new Graphic object (new Graphic(getCurrLoc(t), t.beginLine, t.image, ctrl);)

t.image contains 🔔gs,w318,d386,r1\n🔔I25 while ctrl contains ED04JA07.005.

c) the generation phase then produces this in the output file, by calling Graphic.generate() with these two parameters

<figure style="-uslm-lc:gs,w318,d386,r1"><img src="file:///ED04JA07.005" style="width:318pt; height:386pt; "/></figure>

Notice how the XML output produced preserves as much of the original input information as possible in the figure/@style attribute. This is useful for debugging and ensuring that no information is inadvertently lost during the transformation from locator code to XML.