Grammar pattern: twin delimiters

This post describes a tricky point of Novelang’s grammar design: how to handle twin delimiters like // in a non-ambiguous manner for an ANTLR grammar. It’s a useful refresh before adding long-awaited ** (asterisk pair) delimiter.

The problem

For paired delimiters like ( and ) or [ and ] it’s easy to know when to “open” or “close” a block, and support nested blocks. In contrast, a twin delimiter is an opening one if not preceded by a closing one inside the same block, regardless of what happens in subblocks. This is a complicated way to say we support this kind of nesting:

// block-1 ( block-2 //block-3// ) //

+ block-inside-solidus-pairs
    block-1
  + block-inside-parenthesis
      block-2
    + block-inside-solidus-pairs
        block-3

We also support this:

block-1 // block-2 // block-3 // block-4 //

  block-1
+ block-inside-solidus-pairs
    block-2
  block-3
+ block-inside-solidus-pairs
    block-4

(We have only one level of nesting here. 2 levels of nesting is counter-intuitive and would have required very complex lookahead.)

The pattern

The pattern is to define special grammatical elements when inside a block defined by a twin delimiter, to propagate this element cannot appear again, unless inside some other subblock.

Taking “XXX” for the name of some twin delimiter, here is a simplified version of the grammar for spreadblocks. The term “spreadblock” stands for a block that may spread on several lines (containing single line breaks).

paragraph
  : ... mixedDelimitedSpreadblock
  ;

mixedDelimitedSpreadblock
  : word ( punctuationSign | delimitedSpreadblock ) ...

delimitedSpreadblock
  : xxxSpreadblock
  : parenthesizedSpreadblock
  | squareBracketsSpreadblock
  | doubleQuotedSpreadblock
  | hyphenPairSpreadblock
  ;

parenthesizedSpreadblock  
  : '(' spreadblockBody ')' // Same for other paired delimiters.
  ;

spreadblockBody
  : ... mixedDelimitedSpreadblock
  ;

xxxSpreadblock
  : XXX spreadblockBodyNoXxx XXX
  ;

spreadblockBodyNoXxx
  : ... mixedDelimitedSpreadblockNoXxx ...
  ;

mixedDelimitedSpreadblockNoXxx
  : ... delimitedSpreadblockNoXxx ...
  ;

delimitedSpreadblockNoXxx
  : parenthesizedSpreadblock
  | squareBracketsSpreadblock
  | doubleQuotedSpreadblock
  | hyphenPairSpreadblock
  ;

This is more or less the same for tightblocks. “Tightblocks” stand for blocks containing no line breaks, like cells and embedded lists.

acell  // Same for embedded list items.
  : ... mixedDelimitedTightblock ..
  ;

mixedDelimitedTightblock
  : word ( punctuationSign | delimitedTightblock | ... ) ...
  : word ( punctuationSign | delimitedSpreadblock | ... ) ...
  ;

delimitedTightblock
  : xxxTightblock
  | parenthesizedTightblock
  | squareBracketsTightblock
  | doubleQuotedTightblock
  | hyphenPairTightblock
  ;

xxxTightblock
  : XXX tightblockBodyNoXxx XXX
  ;

tightblockBodyNoXxx
  : ... mixedDelimitedTightblockNoXxx ...
  ;

mixedDelimitedTightblockNoXxx
  : word ( punctuationSign | delimitedTightblockNoXxx ) ...
  ;

delimitedTightblockNoXxx
  : parenthesizedTightblock 
  | squarebracketsTightblock
  | doubleQuotedTightblock
  | hyphenPairTightblock
  ; // That's all.

Thought it is over? There is another kind of block, the delimitedTightblockNoSeparator used inside the subblockAfterTilde which reflects each block inside ~x~y~z! But at this point you probably got the idea.

Yes this makes the grammar quite verbose, but factoring it would reduce ANTLR’s ability to check for inconsistencies. Anyways, the slightest addition brings the need of writing test cases for every logical path inside each ANTLR grammar rule.

Removing unwanted spaces (continued)

This is about some kind of brand new operator: it groups all words an blocks and punctuation signs which are not separated by space.

A great feature of Novelang is to apply standard typographic rules, especially when there is punctuation. The problem is, sometimes you can’t apply those rules in a blunt manner.

Consider these cases: on the left, what’s in the source document, and on the right default rendering.

Source document	Default rendering	Hack
imprimé(e)s	imprimé (e) s	`imprimé(e)s`
F.B.I.	F. B. I. (superfluous spaces)	`F.B.I`
computer//ing//	computer ing	No hack available

Default space insertion makes it all wrong. I tried to fix it by detecting proximity (lack of spaces) between casual words and blocks inside grave accents. But, if adding other cases like full stops, blocks inside solidus pairs and blocks inside parenthesis, we end up with many complex tranformations which just break existing whitespace addition for the common case.

The solution is something more generic. I’m thinking about a special character which groups everything that follows until there is a space, a line break or the end of the document. This character would be the tilde ~ because it looks like a kind of elastic ligature.

So, with source document like this:

~computer//ing//

We get an AST (Abstract Syntax Tree) like this:

+ block-after-tilde
  + word "computer"
  + block-inside-pair-of-solidus "ing"

But we still miss the feature of adding zero-width spaces when needed. How to express this? Since zero-width spaces only make sense inside a group with no space, we can reuse the tile character safely.

This:

~A.L.L.~O.F~'E.M.

… becomes:

+ block-after-tilde
  + subblock
    + word "A"
    + punctuation-sign full-stop
    + word "L"
    + punctuation-sign full-stop
    + word "L"
    + punctuation-sign full-stop
  + subblock
    + word "O"
    + punctuation-sign full-stop
    + word "F"
    + punctuation-sign full-stop
  + subblock
    + apostrophe-wordmate
    + word "E"
    + punctuation-sign full-stop
    + word "M"

And this is enough for the stylesheet to find where to insert zero-width spaces.

New beasts: delimiters and levels

To my average surprise, the renaming of all tree nodes went smoothly and all existing stylesheets were quickly put back to work, thanks to the XPath verifier. The token names are now beautifully consistent. Except a few ones, which I left out of scope until I get some insights about them. These are: CHAPTER, SECTION, TITLE. While Novelang claims to have no semantic markup, how to ignore the fact that chapters and section have highly structural effect? With a closer look, it appears that chapters and sections are quite not the same thing, depending we take them at parsing stage, or at rendering stage. At parsing stage, chapters and sections are delimiters which may be followed by some text (becoming the title). They exist at the same level as paragraphs. It’s only after the whole tree is parsed that Novelang creates the hierarchy by re-hierarchizing the tree before passing it to the rendering stage. At rendering stage, chapters and sections become containers (a source document declaring a chapter then a paragraph is not “flat” anymore, as the chapter now contains the paragraph). This all looks the same as parsing stage, except that a Book may define new chapters and sections on its own like with insert $createchapters. My guess is, with a rendering system supporting recursive processing, it would be a waste to limit ourselves to a fixed hierarchy.

Figure some big documents with numerous title levels, between five and fifteen. Creating a standard template under a tool like MS-Word doesn’t work well. When forcing each top-level title to appear on a blank page, this is a waste for small documents. But when allowing several top-level titles on the same page, big documents become unreadable and deep titles even smaller than the text body. It’s not a solution neither, to hack title depth by starting at, let’s say, the third level, because automatic numbering would cause our first chapter to be numbered “0.0.1”. On the other hand, a programmatic templating system like FOP would support such hacks.

With different names for nodes at parsing and rendering stage, we make the thing clearer. At parsing stage, we have delimiters. Delimiters are the new beast. They look like a list item but may contain less things (by now the only restriction is, they cannot contain a URL immediately following the equals signs). They will be processed in a different manner. Anyways, the “delimiter” name is not supposed to appear at rendering stage. Let’s use DELIMITER as a radix. Because we need to remain consistent with the rest we’ll continue the names with the characters it contains, so we have DELIMITER_DOUBLE_EQUAL_SIGN and DELIMITER_TRIPLE_EQUAL_SIGN. More levels is probably a bad news (you should split your text in smaller parts) but the naming scales up to “octuple”. We introduce a new convention: node names that don’t appear at rendering stage are suffixed by a low line (“_”). The low line as a prefix is already taken for node names which don’t appear in the parser. Finally our delimiter nodes are DELIMITER_TRIPLE_EQUAL_SIGN_ and so on. But what about the title? Even if its content is close to a paragraph’s, the title is structurally different. For its name, I’d like something like “text for a delimiter” but “text” carries no structural meanin. DELIMITING_TEXT_ is better but not so good as it suggests that the text itself is the delimiter. Let’s keep it until better. Now there is an obvious choice for the name of the nodes containing other nodes: _LEVEL (“level” is a palindrome, by the way). The title becomes _LEVEL_DESCRIPTION. Yes, this starts to look like semantic markup but it’s just reflecting the reality, because the processing of the delimiter gives something of a higher meaning. A consequence of dropping the chapter / section difference is some loss of information. Source documents which define top-level sections are now structurally undistinguishable from source documents defining top-level chapters with no section under. This looks like a good thing, because these differences are supposed to be managed at Book level.

Grammar refactoring complete!

Wow, I just checked the result of a major grammar refactoring into the master branch! Now I'll ship a new version with just those changes to get sure that nothing breaks in existing documents. But what's next? I've many options to consider. Split the project down to smaller pieces With one big project with lots of Java code depending on ANTLR-generated parser, playing with the grammar and deactivating some rules breaks the whole project, so it becomes difficult to find out what's wrong. During the refactoring, I splitted the sources in several projects: common stuff, parser stuff, rest of the stuff. Then I could focus on the grammar itself. Keeping such a split would be great for future experiments. On the other hand the Ant build would become increasingly complex. Maven is the tool for working with several subprojects but the migration has a cost. Maybe I should defer it until the next time I need it. Tree nodes renaming With usage, is appears that Novelang grammar has nothing to do with a semantic markup. It supports semantic-like markup (like "//foo//" where double solidus pictures slanted characters which are like italics) but the flexible nature of stylesheets definitely avoids to freeze the meaning of grammar constructs. For this reason, the tree node which is now named emphasis should be renamed into something like block-in-double-solidus-pair. Stylesheet consistency check Changing the name of the tree nodes will break existing stylesheets. But checking if stylesheets use correct node names would ease the pain a lot. Such a check could be made by parsing attributes like match="n:chapter" and raise errors when an unknown node name appears (in the "n:" namespace). Automatic detection of node names in the grammar It's the same principle as above, applied to Java code. By now tree node names defined in the grammar are duplicated in the NodeKind class. The NodeKind class is updated manually. By generating corresponding code, there would be no need to update it manually. Fix list of supported characters Class SupportedCharacters is broken because of changes introduced by ANTLR-3.1.1. The fix could get trivial if we generate some Java code in the same was as for node names (described above). List items That was one of the main features justifying this refactoring, remember? There are plenty of lists to be envisaged. There are two main families of lists: big lists, whose items behave like paragraphs with a special introducer, and small lists, whose items are separated by a single line breaks and therefore may appear inside a paragraph.

--- Big list item with hyphens

### Big list item with number signs

*** Big list item with asterisks

This is a paragraph.
- Small list item with hyphen
  - Some sub-item
  - Sub-item, again
Number sign hints the renderer to generate numbered list.
Interpreting indentation is left to tree-mangling and rendering.
  # Small list item with number sign
  # Number two
  # Number three
Asterisk mean almost the same as hyphens. Do we need them?
* Small list item with asterisk
* Yet another one item with asterisk

URL Another main feature is support for URL inside paragraphs and URL having title.

This is a paragraph embedding two URL. Here is the first:
http://foo1.com
  "This is the title of second URL"
http://foo2.com

Conclusion Adding code generation from ANTLR grammar then stylesheet checker seems the first thing to do in order to secure existing features and build on solid basis. Generating code from existing grammar (for enumerating supported node names and characters) may be complex as it may involve ancillary classes. This could be a reason to Mavenize the project.

Ongoing grammar refactoring

As refactoring goes on, it's time to answer some questions. The main new features (URLs and list items inside a paragraph) have a great on the whole design. Both may take place inside a paragraph; both start (and end) with a line break. That's a major change, as in former design the paragraph was a single piece as long as there were no two contiguous line breaks. While it's not a part of the grammar itself (as in the Novelang.g file), URLs support being "decorated" with a preceding double-quoted block, or an angled-bracketed block. So we should consider that URLs inherently spread over many lines and expose a double-quoted block. List items inside a paragraph are called "small list items". They cannot spread over more than one line (no break inside). For this reason, a small list item may not contain a paragraph. So we have a new beast: text blocks which don't contain line breaks as paragraphs do. For this reason, they cannot contain URLs or small lists. We'll call monoblock a text block with no line break. We'll call spreadblock a text with line breaks (as it may spread over several lines). We can't have URLs inside small lists. But's that's ok because there is another thing called "big list items" that's a plain paragraph with a special indicator at its start. By now (master branch), titles for sections and chapters are casual paragraphs. I wonder if it now makes sense to have URLs or small lists inside a title? Another limit I put arbitrarily is to forbid URLs and small lists inside double-quoted blocks. This sounds right for the URL because of the double-quoted block that may decorate a URL (it's logically impossible to have double-quoted block inside double-quoted block without an additional delimiter). For the small list, it's more for typographical sanity. Does it make sense to extend this to any asymmetrical delimiter (emphasis, interpolated clause...)? Sometimes it's useful to emphasize a whole paragraph, including its URLs and small lists. Because I'd like Novelang grammar to be twisted and abused in any technically-feasible way (for creating idioms), it doesn't make sense to forbid titles to be paragraphs, nor to forbid asymmetrically-delimited blocks (except double-quoted blocks) to spread over several lines and contain URLs and small list items. Depending on the stylesheet, things like this could make sense:

=== This is a section with embedded small list items:
- item1
- item2
- item3

This is a paragraph.

Rendering may look like:

This is a section with embedded small list items: item1, item2, item3.

Same for URLs. Because URL href must stand on its own line, this encourages adding a display text:

=== "This is URL display text"
http://foo.com

At the end, it seems that technically feasible things drive to well-designed grammar! Thanks to ANTLR for helping me to express the grammar so clearly.

Refactoring Novelang grammar

I started working on a refactoring of the Novelang grammar and it's a big job. By the way I switched to ANTLR-3.1.1, the latest version of ANTLR. The development occurs in the ANTLR-3.1.1 branch. ANTLR is the greatest tool for generating parsers. With version 3.1, it supports grammar imports, which means a complex grammar can split in smaller files. With careful design it would be possible to let third-party developers extend Novelang grammar, as ANTLR supports rule overriding. Alas, ANTLR-3.1.1 doesn't work well with multiple import levels so I'm keeping one huge grammar file for now. You can have a look at current Novelang grammar (master branch). For the end-user, the biggest feature brought by this refactoring is support for "monoline" text items. Basically this is for stuff delimited by a pair of line breaks and that may stand in the middle of a paragraph. By now, Novelang only recognizes URLs when delimited by two pairs of line breaks.

(This is some paragraph before the URL.)

http://novelang.sourceforge.net

(This is some paragraph after the URL.)

Recogninizing a URL as "monoline" text item would allow something like this:

This is a paragraph.
http://with-url-inside.com
...Same paragraph, continued.

That's a lot more natural. The URL still must start at the start of the line, because it's much easier to copy from the text editor. I previously discussed URL syntax here. Coding Horror blog has a nice post that should deter anyone to include URLs in plain text with no machine-understandable delimiter. The full-blown URL syntax supports URL decorations like this:

Go to 
  "Novelang website" 
  [Novelang website on Sourceforge.net]
http://novelang.sourceforge.net
and see all useful links.

The quoted and bracketed text blocks are optional and provide display text and alternate text. I can see no reasonable way to support them at grammar level. The best way to handle them is at tree-mangling stage (reordering the Abstract Syntax Tree generated by the parser). This means, the parser-generated AST should include nodes describing whitespace and line breaks. Support for monoline items is helpful (necessary?) for supporting lists. As previously discussed, here is how I want to write a list:

Here is a list on two levels:
* First item
* Second item
  * First subitem
  * Second subitem
* Third item
...And the paragraph continues here.

As for URL decoration, the grouping of list items is made at tree-mangling stage. Because identation matters, whitespaces in AST should tell how big they are. A list which can appear inside a paragraph will be called a small list. There is the need for another kind of list where items are paragraphs, to be called big list. The symbols for designating list items ("*", "#", "-", "---",...) are left to another discussion.

Some ideas for Novelang syntax extensions

Just some ideas here and here.

Here is some text ++- striked out -++.

Oh, yeah, looks like the ''++'' radix is powerful as it cleanly expresses strike. It can be composed with other characters, and supports symmetrical delimiters! I like the plus sign for designating the strike family, as it is a vertical line (figuring some character) with an horizontal strike.

Here we get ++= double strike =++.
Here we get ++$ highlight one $++.
Here we get ++£ highlight two £++.
This is a sample of ++/ oblique strike /++.

The same approach fits for underline. The _ (low-line) character is fine for underline (that was its purpose on mechanical typewriters).

Same for __- underlining -__.
So we have double __= underlining =__.
So we have waved __~ underlining ~__.

Novelang syntax already uses a low line for the "silent end" of interpolated clauses. In order to keep a strong meaning to the low line maybe we should revisit the silent end.

New silent end for interpolated clauses -- like this -<.

And now I've found what double circumflex accent is good for: small caps. Small caps sometimes carry a strong meaning, like for quoting a shouting person, or for names for which case matters (like Charles De Gaulle).

And this is for ^^ Small Caps ^^.

Talking about circumflex I was thinking about superscript those days and according to my researches superscript text is always the last part of a compound text, before a space or a punctuation sign.

Like: 2^nd.

Subscript will work the same way with a single underscore. Ayways I'll have to think a lot about all of this. I must take care of not losing the focus on content-oriented text and not invent a messy markup.

Novelang syntax for Parts

I haven't documented the Novelang syntax yet but there are already plenty of things to change. WikiCreole's reasoning and Markdown give a great start for yet another discussion on Wiki markup.

In this document, character names refer to Unicode specification.

Headings

The chapter should be a double equals, and the section a triple one. There is a single character to know about and it's dedicated (asterisk are used by bold and unordered lists, see below). And it's eye-catching without the crippling effect of many asterisks.

== Chapter

=== Section

This makes the markup "scalable" in the sense it becomes easy to support a subsection level (though it may reflect that Parts are becoming too complex).

Identifiers and Tags may decorate Headers as they appear just below Header declaration (one linebreak away). Header identifiers are prefixed by an ampersand. Tags are prefixed by a commercial at.

== Chapter
  &identifier @tag

Paragraphs

Paragraphs are just lines of text. They are delimited from the rest by two linebreaks or more (aka hardbreak). They support identifiers and tags immediately above (one linebreak away no more). Paragraph identifiers are prefixed with a plus sign immediately followed by a commercial at, to indicate they don't work the same as Header identifiers, which are global.

This is one paragraph, continuing
on this line.

  +&identifier
This is another paragraph with an identifier.

Words are any sequence of letters and numbers. There can be a single dash between two letters or number. Apostrophe is a word delimiter.

C'mon, just a two-worded word!

There are some combinations which require character escaping, like acroynyms with dots. That looks messy but trying to turn this into a generic case seems to make things even worse.

I want my T~.~L~.~A (Three-Letter Acronym)!

Character escaping

I've been discussing character escaping and now I think that there should be no difference between single and multiple character escape, in order to avoid confusion. 

Ampersand: ~&~
O and E ligatured: ~OE~ 
Tilde: ~tilde~ 

Backslash character was an option but I like the tilde character as it carries the meaning of something linked to the rest.

Inline litteral

Inline litteral requires a delimiter with reduced visual cripple, available on most keyboard, generating minimal conflict with casual use. The grave accent (backquote) is such a gem.

 This is double slash `//` delimiter.

Tilde was a serious candidate but it has a better meaning for escaping, while the grave accent looks more like quotation. 

Bold

Double asterisk looks good and is consistent with italics' double slash. 

This is **bold**.

Subscript and superscript

A delimiter made of a single character is more concise than a double one. As it takes less visual space it reflects semantically weaker meaning. Circumflex means superscript and low line (underscore) means subscript. 

L^A^T_E_X is expected to render as L^AT_EX.

Supporting subscript and superscript will be a mess because wether it is attached to a word or not does matter for the rendering.

Links

Often I got annoyed when copying an URL in the middle of the line. Now I'm reinventing a better world and I want to force the URL to appear at the beginning of the line. 

Many Wikis have messy syntax for URLs / URIs because of related title and text. This can be avoided by some contextualization like the quotes immediately following an URL become the text to show. Same for the link title that could be a parenthesized block.

The URL here belongs to current paragraph:
http://novelang.sf.net "Go there" (Novelang home page)

Then HTML output is expected to look like this :

The URL here belongs to current paragraph: Go there

If the quoted text really should appear as quoted text then a line break cuts it away from the URL while keeping it inside the paragraph.

URLs are an easy case as its starts with a scheme ("http:" or "file:") but URIs are harder to handle. They are left out for the moment.

Lists

Unordered lists have items starting with an asterisk.

Ordered lists have items starting with a number sign.

Sublevels could repeat the list item sign but a level 2 unordered list item marker would clash with the bold marker. The trick is to use indentation.

* Item 1
  * Item 1.1
  * Item 1.2
* Item 2

And it goes the same for ordered lists. Some text editors recognize intentation and perform wrapping under the first indented character.

Blockquotes

A pair of angled brackets look fine for defining blockquotes. They must be on the start of the line and alone on the line where they appear.

<< 
This is a blockquote. 
>>

I try to avoid closing delimiter whenever possible, but the alternative approach, which is to use a special character at the beginning of a paragraph, would require to edit each paragraph when pasting foreign text.

Litteral

Litteral is text appearing the same as in the Novelang markup. It appears inside triple angled brackets, opening and closing brackets must be on the very beginning of the line and their trailing space is not rendered. To render triple angled brackets at the beginning of a line, character escaping is required. But such combination is quite rare and shouldn't be a hassle.

<<< 
This is litteral, 
  preserving indentation.
>>>

The need of a closing delimiter is a no-brainer here.

Tables

As the Book feature supports including other file's content there should be a function to read a CSV or whatever and display it nicely. So we don't pollute the markup with a feature bloating other wiki's syntax with more and more complex style stuff.

Features I'm happy with

Interpolated clauses must be more than a special character like —. They must be declared as blocks (with opening and closing), so rendering can insert non-breakable spaces after opening dash and before closing dash. And the closing may be hinted to be not-renderable.

Interpolated clause delimiter is double dash. A dash then a low line define a non-renderable ("silent") closing.

Interpolated clauses -- like this one -- do rock.

Silent ends rock, too -- yeah-_.

Parenthesis, brackets and quotes are blocks, too, using conventional character.

(parenthesis) [brackets] "quotes"

Italics use double slash delimiter. A double character looks "big" so it refrains from overuse.
This is //italics//.

Punctuation signs come with no surprise.
Question mark ? Exclamation mark ! Colon : Semicolon; Comma, Ellipsis... Full stop.

Comments. Because of italics, the double slash made popular by Java and C++ is not an option. In order to reduce confusion, corresponding slash-asterisk combination cannot be used because for most people, they are both parts of the same set of conventions.
So line comments starts with a double percent sign, and block comments are delimited with double accolades.
%% Single-line comment.

{{ Block 
   comment }}

Single accolades may have a special meaning but they are free for now.