Qtask Markup Language - parser and other common code

1. TODO

• sections (in source...)
• get-anchors, get-links etc.
• debug colors: olivedrab limegreen lavenderblush greenyellow goldenrod blueviolet aquamarine
• fix "=c =1 something"

2. Introduction

QML is a markup language designed by Baron R.K. von Wolfsheild for Qtask. This program parses a string of QML text into a QML document tree (that can then be converted to, say, XHTML with an appropriate "emitter").

Parsing is done with a pipeline made of three stages. The first stage uses parse on the input string and sends QML commands to the second stage; the second stage, whose main function is greatly simplifying the implementation of the third stage, ensures command balancing ("open" commands must be followed by "close" commands in the correct order, and correctly nested; also there are two levels of commands, "block" and "inline", that must nest properly), preprocessing and translating commands, and then sends them to the third stage; the third stage converts the stream of commands into a QML document tree.

The second and third stages are implemented as finite state machines (FSMs). The document tree that comes out of the third stage is optimized with a tree rewriting engine before returning it. The three rewriting rules also process the =repeat and =data commands; after the document has been completely expanded and optimized (which may require more than one pass), any table of contents is created and headers are numbered; numbers for enum lists are calculated too. (Numbering and TOC creation has to be done last because of =repeat.)

3. Overview

This section is the one users of this scanner are interested the most, because it shows the "interface".

The QML scanner uses a stack-based finite state machine interpreter and a data structure matching and rewriting engine, so we include them here. The qml-scanner object is defined, which contains all the code for the scanner.

Two functions are available for users: scan-doc and search. scan-doc takes a string as its argument and returns a QML document tree (a block). Please note that scan-doc is not reentrant and you cannot call it recursively (not that there is any way for you to do so). You can use the /with refinement to provide a block of pairs of strings, to set default options for commands such as =box and =table. (See the 〈Example usage〉.) It is also possible to use the /keep refinement to stop scan-doc from resetting default options, so that you can use the ones that have been set in a previous session; note that if you use /keep, /with is ignored, so you should not provide both. (There is also a limitation, in that /keep does not actually keep the default value for "alias".)

search takes a string and a QML document tree; it performs a simple substring search inside the document (ignoring formatting etc.). A block is returned, with pairs of header and text snippet (with one exception explained below); the text snippet is a string of about 100 characters around the substring match, and the header is a QML header node (a block) for the "section" that contains the text (i.e., the last header encountered before the string was found). The returned block contains a pair of header and snippet for each occurrence of the substring in the document. If the substring is found before encountering any header in the document, the result block will contain the word 'doc-start in place of a header block.

Note that the text snippet does not contain any formatting (but paragraphs are separated with a newline).

search also returns anchor name exact matches: if the document contains an anchor whose name matches the text string exactly, then the first pair in the result block will be the header for the section that contains the anchor (or 'doc-start), and the anchor node. (You can distinguish this case because the "snippet" is a block instead of a string; also, this can only happen for the first pair in the result block, and since anchor names need to be unique only one can match.)

3.1 Example usage

To scan a document, just call scan-doc with the document text; you can use the /with refinement to set default options for commands. (Commands that support default options are: =toc (sets the default number style), =alias (sets the default "magic" sequence), =table, =row, =column, =cell, =box and =image.) You can pass the resulting document tree to an emitter (such as the XHTML emitter) to generate a document that the user can read.

To search a substring in a document just call search passing the document tree and the substring to search for.

4. The parser (stage 1)

The first stage of the pipeline is the parser. The parse-qml function just uses parse on the text string.

4.1 The parse rules

The parse-qml function uses qml-rule to parse the text; everything that is not a command, is considered text and is handed over to the second stage (with the stage2 function, see 〈Balancing (stage 2): the stage2 function〉).

The txt-chars charset is initialized by the set-magic function (see 〈The set-magic function〉).

4.2 parse rule for commands

The heart of the parser is the commands rule.

The newline character is treated like a command (produces the "^/" command); spaces at the end and at the beginning of lines are ignored. (As already noted, the stage2 function is used to hand the commands over to the second stage of the pipeline; see 〈Balancing (stage 2): the stage2 function〉.)

Other commands are introduced by magic-char (set by the set-magic function, see 〈The set-magic function〉); there are some special commands that require their own parse rules, but most commands are parsed by the rule shown here. This parses normal opening commands (like "=cmd"), opening commands with options ("=cmd[...]" or "=cmd{...}"), and ending commands ("=cmd." or "=cmd/"); commands with options eat at most one space following them (i.e., "=cmd[...]text" is exactly the same as "=cmd[...] text"; if you need a space after a command with options, use two spaces); ending commands do not eat any space (so "=cmd.text" is not the same as "=cmd. text"); commands without options require at least a space following them and will eat all spaces following them. Note that the mk: magic-char :mk construct allows putting commands one after another without spaces between them (e.g., "=b=i"). Note that this rule also parses the dot command "=.".

As you can see each command is sent to the second stage as a pair of values: the command as a string, and the command's options (which can be none). As you have already seen in 〈The parse rules〉, this is also true for text, which is sent as the text: (a set-word!) command with the text as options (a set-word! is used so that there is no clash with other commands, e.g. if we ever need to add a =text command and so on).

4.2.1 Special commands

Some command require custom parse rules. I've tried to keep this to a minimum, but Reichart loves special cases. ;-)

• magic-char followed by magic-char allows inserting magic-char in the text;
• magic-char followed by a space or a newline is the space command (i.e., " ");
• "alias" is special for two reasons: first, its option is not enclosed in braces, but follows the =alias command (like "=alias ~"); second, it does not produce a command, but calls the set-magic function, which changes the value of magic-char and other things; (note, that since we are using some cmd-chars to parse the new magic-char, you cannot write something like "=alias =", which is probably ok, but maybe should be fixed);
• "csv" is similar to an escape command (see below), in that text between "=csv" and "=csv." is not processed as QML text, but as CSV text; however, "=csv." must happen at the beginning of a line (it also eats spaces and one newline). The CSV data is sent as the command's options;
• escape commands are used to include non-QML text in a QML document; you can specify an ending sequence for the escaped text using braces, otherwise the respective ending command is used as the ending sequence (e.g., "=html ... =html." or "=html[END] ... END"); note that one newline is eaten;
• the horizontal ruler command "-" allows any number of dashes to be used (i.e., "=-" is the same as "=---" and so on) and eats one newline;
• the indent command ">" takes as option the amount of indentation, but this is specified by the number of ">" characters following magic-char (e.g., "=>>>" becomes ">" 3);
• the empty command ("=[...]" or "={...}" which become ["" "..."]) is special because it does not eat any following space;
• the comma command is special because it does not eat any following spaces (behaving like the space and dot commands);
• the repeat command is special because its options are parsed as REBOL block; this is the only case where you can have a "]" inside options created with "[" or a "}" inside options created with "{"; the rebol-options rule is used to parse its options.

4.2.2 Words used by the commands rule

The commands parse rule uses a number of words that we need to make local. It also uses the rebol-options subrule which we define here.

cmd-chars and magic-char are initialized by the set-magic function (see 〈The set-magic function〉); escape-cmd is the list of escape commands.

rebol-options uses the load-next function to parse the options as REBOL values; in turn it uses load/next to parse the text and tries to recover in case of errors.

4.3 The set-magic function

This function initializes the values of magic-char, cmd-chars and txt-chars. cmd-chars is a charset containing the characters that are valid in command names; txt-chars contains the characters that are valid for text outside commands.

5. Balancing (stage 2): the stage2 function

The second stage of the pipeline is meant to simplify the third stage by "normalizing" the command stream. It takes care of ensuring command balancing, and handles the space, dot and comma commands ("= ", "=." and "=,"). Parsing of command options is also done in the stage2 function (just because this is a convenient place to do it, even though conceptually it belongs to the first stage).

This stage uses a Finite State Machine, handling each command as an event. Please see the documentation of the FSM interpreter for more informations (linked in from 〈Overview〉).

As seen in the first stage, the stage2 function is invoked with a command and its options. A command can be a string! or a set-word!; for simplicity set-words can be passed in a block (as in stage2 [text:] txt), so if cmd is a block we just extract the first value. The options are parsed with the parse-command-options function; the cmd and opts words are then set in the stage2-ctx object, so that they are available to the FSM rules, and cmd is issued as an event for the state machine. (stage2 needs to do another thing after this, we'll discuss this later on.)

6. Command options parsing

Command options (also called "refinements" in the code) are parsed by the parse-command-options function, which is called by the stage2 function (although, conceptually options parsing belongs to the first stage; the stage2 function parses the options before actually processing the command in the FSM).

Only some commands need their options to be parsed; if cmd is one of them, and options is a string, then the parse-arg-string function is used. Otherwise options is returned as-is.

6.1 Option values' types

Options are parsed as a list of values; option values can be of a number of different types, each recognized by syntax (like in REBOL) and parsed by a specific parse rule. Values can be of one of the following types: flag!, set-word!, color!, string!, integer!, url!, percent!, pair! and comma-pair!; after being parsed, each value is represented by a REBOL value, and each type is mapped to a REBOL type: flag! is mapped to word!; set-word!, string!, integer!, url! and pair! are mapped to the respective REBOL types; color! is mapped to one of issue!, refinement! or tuple! (depending on how the color was specified, if as a hex string, a color name or a tuple); percent! is mapped to money!; comma-pair! is mapped to block!.

The types object holds the parse rules for the option types. The flag-word and set-word rules are set dynamically based on the command that is being parsed. Note that strings can be specified even without quotes, so the string! rule must be applied last (other types need to be tried first); also note that we only allow integer percent values, even tough we use money! to represent them; also, comma-pair! can contain integers or percents, so the block representing it can contain integer! or money! values.

6.1.1 Subrules and other words used by the parse rules

As already said above, flag-word and set-word are dynamically set to a command-specific rule. See 〈Rules for flag!〉 and 〈Rules for set-word!〉.

6.1.2 Rule for parsing a generic value

The rule value-rule can be used to parse a generic (non flag or set-word) value; the order of the rules is significant. (Note that it's written this way for compatibility with older REBOLs.)

6.1.3 Rules for color!

6.1.4 Rules for flag!

Each command has a list of available flags. Note that order is important (because of the way the bold and italic rules are defined, for example).

We have only specified the parse rules for a small set of flags; all the others are generated automatically: for example, [dashed] becomes ["dashed" (value: 'dashed)]. This is done by processing the flag-words block using parse.

6.1.5 Flag actions

By default, a flag sets the respective word to true in the object that represents the parsed options. Some flags, however, do something different; for example, the dashed flag sets the word outline-style to 'dashed. The flag-actions object contains the flags that do something different from the default.

6.1.6 Rules for set-word!

Set-words are parsed in a way similar to flags. Each command has a list of set-words that are accepted.