[Wikitext-l] On tokenizing wikitext

[Andreas Jonsson]

The parser I am writing follows a four layered design:

- client application
- parser context
- parser
- lexical scanner

In this post I will write about the lexical scanner and what the
special requirements are for wikitext.  Since all input is valid
wikitext, the lexer must never fail to accept a character in any
position or state.  Also, it is important that the lexer protects the
parser from spurious tokens.  The parser grammar will quickly become
very complex if it has to deal with unexpected tokens.  It is
therefore beneficial to make the lexer a bit more complex and make
sure that, for instance, a </li> tag appearing in a particular context
is really supposed to be a html tag token or if it should rather be
just the verbatim characters.  To accomplish this two things are
required: lookahead and the ability to selectively enable/disable
individual token productions.

== Basic tokens

At the very bottom of the lexer there are 7 kinds of tokens:

SPACE_TAB:      SPACE_TAB_CHAR+;
NEWLINE:        '\r\n' | NEWLINE_CHAR;
SPECIAL:        SPECIAL_SYMBOL;
APOS:           '\'';
ASCII_WORD:     ASCII_LETTER+;
WORD            
~(SPACE_TAB_CHAR|NEWLINE_CHAR|SPECIAL_SYMBOL|'\''|ASCII_LETTER|NON_PRINTABLE_CHAR)+
NON_PRINTABLE:  NON_PRINTABLE_CHAR+ {$channel = HIDDEN;}

These tokens types covers all characters in the Unicode set, any
character will match into exactly one of the above.  The SPECIAL rule
matches exactly one character out of a set of characters that may be
used to form more advanced tokens; it captures instances of such
characters that are not part of a token.  Other lexer rules may also
fall back to producing SPECIAL tokens, which may contain multiple
characters.  The apostrophes are handled by the parser, so we will
pass it as a token of its own.  The ASCII_WORD needs to be treated
separately in order to support internal link prefixes and trails.  A
word is very loosely defined as a sequence of characters that do not
fall into any other category of characters.  Non printable characters
are hidden from the parser.

If we would remove all other lexer rules except the above basic ones,
the result of the parsing would be a text split into paragraphs where
all markup is rendered verbatim and where non-printable characters
have been stripped away.  All other kinds of formatting are triggered
by the lexer producing a more complex token.

== Lookahead

Some tokens aren't tokens unless followed by a proper closing token.
Thus, we must sometimes perform a lookahead in the input stream before
accepting a token.

1. Syntactic predicates cannot be used for lookahead.  E.g., the rule
    ('ab')=> 'a' will match 'a' regardless of what follows.  The
    trailing 'b' in the lookahead is silently ignored by Antlr.

2. Using Antlr's builtin backtracking has two major problems:

    1. The DFA tables becomes extremely large.

    2. Passing arguments to lexer rule will not work.  (May be specific
       to the C target.)

Instead I am using the following pattern to perform lookahead:

RULE
@init{
     bool success;
}:
    MATCHING_CHARACTERS RULE_LOOKAHEAD[&success]
    {
        if (!success) {
            // Fall back to instead producing a SPECIAL token, or 
whatever else might be appropriate.
        }
    }
    ;

RULE_LOOKAHEAD[bool *success]
@init {
     ANTLR3_MARKER mark;
}:
    {
        mark = MARK();
    }
    (
       (ALTERNATIVE1 {*success = true;})
     | (ALTERNATIVE2 {*success = false;})
     | ...
    )
    {
        REWIND(mark);
    }
    ;

This is a bit clumsy syntactically, but it does the job.

When falling back to producing different tokens, it may sometimes be
convenient to be able to produce several tokens at once.  This is,
however, not supported by the C target.  I have provided a patch for
this, but Jim Idle said that it could not be included in the main
distribution of libantlr3c, since, I guess, it would break some other
things, so we may not want to rely on this.

== Selectively enabling and disabling token productions.

By maintaining a lexer context and using the semantic predicates in
Antlr, it is possible to completely avoid generating spurious tokens.
The basic pattern is as follows:

RULE: {!CX->ruleDisabled}?=> RULE_PATTERN { onRule(CX); }
     ;

So, there is a predicate 'ruleDisabled' that guards the rule, and a
method 'onRule' that reports to the context that the rule was taken.
To take a specific example:

BEGIN_TABLE:
     {BOL && !CX->wikitextTableOpenDisabled}?=> (SKIP_SPACE '{|')=> 
SKIP_SPACE
     BEGIN_TABLE_INTERNAL
     ;

fragment
BEGIN_TABLE_INTERNAL
@init{
     pANTLR3_VECTOR attrs = NULL;
}:
     '{|' {onWikitextTableOpen(CX);}
     ATTRIBUTE_LIST_TABLE[&attrs]
     { CUSTOM = attrs; }
     ;

The logic that governs the 'ruleDisabled' predicates is fairly complex
and writing the code for this directly is a very error prone process.
Instead, I have opted to write a table with a description of each
predicate and let a script generate the code.  For instance, the
description for wikitext table open and close predicates looks like
this:

     array(
           'name'              =>  'wikitextTableOpen',
           'close'             =>  'wikitextTableClose',
           'initiallyDisabled' =>  array(),
           'affects'           =>  array(new TypeEnable('wikitextTable', 
'WIKITEXTTABLE')),
           'mayNest'           =>  true,
           'haveNestingCount'  =>  true,
           'types'             =>  array('block', 'wikitextTable'),
           'pushesBlockContext'=>  true,
           ),

(Maybe not immediately clear what each attribute means, but I have
provided documentation for these in the source file.)  This is one of
the most complex predicates to describe.  The script would generate
the methods onWikitextTableOpen/Close and enable/disableWikitextTable.
They will look something like this:

static inline void onWikitextTableOpen(struct MWLEXERCONTEXT_struct 
*context) {
     context->wikitextTableOpenNestingLevel++;
     enableWikitextTable(context, DC_WIKITEXTTABLE);
     context->wikitextTableCloseDisabled &= ~ DC_OPENED;
     pushBlockContext(context, &context->wikitextTableOpenDisabled);
}

static inline void onWikitextTableClose(struct MWLEXERCONTEXT_struct 
*context) {
     context->wikitextTableOpenNestingLevel--;
     if (context->wikitextTableOpenNestingLevel == 0) {
         context->wikitextTableCloseDisabled |= DC_OPENED;
         disableWikitextTable(context, DC_WIKITEXTTABLE);
         context->wikitextTableOpenDisabled &= ~ DC_WIKITEXTTABLE;
     }
     popBlockContext(context, &context->wikitextTableOpenDisabled);
}

=== Block Context

The block context is a generalization of the table context concept
that I have mentioned in a previous email.

The option 'pushesBlockContext' that is visible in the above example
states that the opening token corresponding to a particular predicate
will create a new "block context" and push this to a stack.  The
corresponding end token will pop the stack and restore the previous
block context.

When a particular block context is activated, the corresponding
closing token will be activated, as well as any tokens internal to the
particular block context.  E.g., the '<ul>' token will enable the
'</ul>' and the '<li>' token.  Deactivating a block context will
disable the tokens again.

So, pushing a new block context includes deactivating the current
context and activating the new one; popping includes deactivating the
current block context and activating the previous one, if any.

As a consequence, the html tokens '<li>', '<td>', '<tr>' etc. and the
wikitext table tokens '|-', '|', '||' etc. will be disabled and the
corresponding text string rendered verbatim if occuring outside the
appropriate context.  Also, block elements that pushes the block
context must be closed with the correct end token.  For example:

<ul>
<li><div>text</li>
</ul>

will be rendered as:

<ul><li><div>text&lt;/li&gt; &lt;/ul&gt; </div></li></ul>

Since the <div> is still opened, the end tokens for the list will not
be active.  The tokens are instead closed at the end of the article.

By restricting the block contexts in this way, lots of problems are
avoided in the parser.  Since the behavior doesn't seem to be well
defined in the current parser, I would guess that this would be
acceptable.

To summarize this rather long post, the lexer is the most complex
part, but by letting it do a thorough filtering of the input, the
parser's job becomes much simpler.

Best regards,

Andreas Jonsson