• Documents have (information in general has) structure worth exposing to software.
• Non-XML resources often have implicit structure.

• Authors can work in non-XML notations.
• XSLT / XQuery programmars can read and process non-XML resources.

    <transitive-sentence>
      <np>
        <det>the</det>
        <n>cows</n>
        <pp>
          <prep>on</prep>
          <np>
            <det>the</det>
            <n>hill</n>
          </np>
        </pp>
      </np>
      <vp-t>
        <v-t>ate</v-t>
        <np>
          <n>grass</n>
        </np>
      </vp-t>
      <stop>.</stop>
    </transitive-sentence>    

td {
    vertical-align: top;
}
img {
    text-align: center;
}

<css>
    <rule selector="td">
        <property name="vertical-align" value="top"/>
    </rule>
    <rule selector="img">
        <property name="text-align" value="center"/>
    </rule>
</css>

• list of numbers
• s-expressions
• arithmetic expressions

• grammar notation
• hiding nonterminals, terminals
• attributes or elements

• proof of concept, not industrial code
• (he means: it's slow and not well debugged)
• (I mean, like, really kind of slow ...)
• (sooooooo slow ...)

• It need not be LL(1).
• It need not be LL(k).
• It need not be LALR(1).
• It need not be unambiguous.

• aparecium:parse-string()
• aparecium:compile-grammar-from-string()
• aparecium:parse-string-with-compiled-grammar()

-sentence: transitive-sentence; intransitive-sentence.
transitive-sentence:  np, vp-t, stop.
intransitive-sentence:  np, vp-i, stop.

np: pn; det?, n, pp*; pron.
vp-t:  v-t, np, pp*.
vp-i:  v-i, pp*.
pp: prep, np.
    

• Compile EBNF rules to (recursive) BNF.
• Extend notion of rule position.

• symbol (non-terminal or terminal)
• E?
• E*
• E+

• E*F (zero or more E, separated by F)
• E+F (one or more E, separated by F)
• (E)

• Let states be the primitive symbols of the RE.
• For each sub-expression E, calculate (bottom up)
  • first(E) (initial states of E)
  • last(E) (final states of E)
  • for each state q in E, and each symbol s in alphabet, also
    follow(q, s, E) (transitions in q within E)

expression: term, (s, addop, s, term)*.

• assigns an ID to each symbol (state)
• decorates each expression with first, last, nullable, and follow:* attributes.
  Aparecium needs the ones on the outermost definition.

  <rule name="expression"
	xmlns:follow="http://example.com/followset">
    <def xml:id="exp_def_1"
	 nullable="false"
	 first="term_1"
	 last="term_1 term_2"
	 follow:term_1=" s_1"
	 follow:s_1=" addop_1"
	 follow:addop_1=" s_2"
	 follow:s_2=" term_2"
	 follow:term_2="s_1">
       ...
     </def>
  </rule>

• A: A; "a".
  Unbounded depth (‘vertically infinite’):

  • <A>a</A>
  • <A><A>a</A></A>
  • <A><A><A>a</A></A></A>
  • ...
• S: X*.
  X: "x"; {nothing}.
  Unbounded width (‘horizontally infinite’). Parses for the empty string include:

  • <S><X/></S>
  • <S><X/><X/></S>
  • <S><X/><X/><X/></S>
  • ...

• Loop detection.
  • <A>a</A>
  • <S><X/></S>
• Parse-forest grammars (grammatical representation of parse tree).
  • A: A_0_1.
    A_0_1: A_0_1; "a".
  • S: S_0_0.
    S_0_0: X_0_0*.
    X_0_0: {nothing}.

• PP attachment ambiguity: “the cows eat the grass on the hill”.
• infinite tree sets
  • S: S; 'a'.
  • S: X*. X: 'x'; {}.

• As element:

  <item from="0" to="20" ri="term_2">
    <rule name="expression">
      ...
    </rule>
  </item>

• As map:

    map {
      'from' : $From,
      'to' : $To,
      'rule' : $r,
      'ri' : $ri
    }

• Invisible XML:
  • XML::Invisible Perl package (“Ed J”)
  • Functional invisible XML parser (John Snelson)
  • Earley parsers in ABC, C (Steven Pemberton)
  • Jay Parser (Tom Hillman)
• Parsing in XSLT, XQuery:
  • REx (Gunther Rademacher)
  • FXSLT LR-1 parser (Dimitre Novatchev)
• Exposing non-XML resources in XML (‘XML lenses’):
  • DFDL Data Format Definition Language (Open Grid Forum)
  • Data Direct Connectors
  • Regular fragmentation (Simon St. Laurent 2001)
  • STnG (Ari Krupnikov 2003)