Mixing various syntaxes – 2. Tokenizing/parsing generalities

You surely know the usual way a compiler works. You get a stream of characters, then transform it into tokens and then parse it according to some grammar. Of course real-life is usually not that simple and various deviations or hacks have to be applied. However, this won’t be discussed here. The first question should be:

So are we going to do it the same way? Tokenize the whole stream at once and then parse all tokens?

First, the languages are tokenized in different ways. For example “<<” might be tokenized as a single token “<<“, two tokens “<“, “<” or even an error because it would not be allowed depending on the language being tokenized.

Different languages, different tokenization processes and tokens. And this is of course the tip of the iceberg. A naive universal tokenizer/parser handling all languages would definitely explode in complexity and be unmaintainable.

…But before making something complicated, isn’t there a simple way?

Indeed, let us first observe the situation. We have the core language, and in it are embedded blocks written in another sub-language(s). These blocks are at some moment evaluated/run. This raises several questions.

-> Is it really needed to tokenize/parse it at all?

One could think that it would be sufficient to store the html-page-block or the shell-script-block or whatever sub-language block embedded as is in one big string in a variable. Of course, doing this is not what we meant to do. We want syntactic & semantic checks performed on it. That the compiler confirms our HTML structure is correct, that every opening tag has a closing tag, etc… Not that it breaks at runtime.

-> Why not simply take the big text block and give to an independent compiler/checker/interpreter?

Despite this sounds nice and simple, it has one big issue. The sub-languages can typicallly include core language expressions. Hence needing to call back the core language compiler/interpreter but also needing information about the context. If we pass the “big string html page” around in the program and at some time try to display it, then ${f(42)} must be evaluated. But this might not be available in the context of the current execution point of the program, or even point to a different function called “f”.

Hence, either we find a way to parse the whole at once. Either we make independent compilers/interpreters with a way of passing context and calling back each other.

So how do we do?

Let us use our imagination to try simplify things. First, it is reasonnable to assume that the delimitations of sub-languages are easy to detect. For example, it could be an indetend block, something in brackets, and so on. There should be no need for advanced parsing & semantics to detect the limits. Let’s call what’s inside 2 such limits a “block”. It is indeed advised that blocks are easely indentified, for human as well.

So perhaps we should make a kind of tokenizer which outputs either tokens or blocks, we will call this a b-tokenizer. The blocks have a given type and contain themeselves also blocks and tokens. And to each block type is associated to another b-tokenizer in charge to split its stream.

In fact, by doing this, we blur the line between tokenizing and parsing. Indeed, we could for example say that “(” is a symbol opening a new block and that inside the core language should be parsed. Parenthesis grouping can be done in both, wether it is done in the enhanced tokenizer or in the parser, the complexity is just shifted from one side to another. Which option is preferable is an open question.

There are 2 kind of b-tokenizers. Let us look again at the initial example.

Concerning the embedded HTML part, we now clearly where the block starts and ends based on the indentation. Even if the content is crap. Hence, the whole block stream can be passed to the html b-tokenizer as input, while independently the stream afterwards can be continued to be b-tokenized (by the core language).

On the opposite, inside the HTML block, we have a core language block. The beginning is indicated by “${” but where it ends is not known yet …indeed, there could be a “”bla bla :-}”” in the content where the bracket is part of a string expression and not the end of the block. Hence, we must b-tokenize the content which will result in two outputs: a block of tokens AND the remaining stream which will be continued to be parsed by the HTML b-tokenizer.

The first kind of b-tokenizer can be reduced to the second sort with an empty remaining. Why not use this simplification?

The first thing to understand is that the kind of output of the b-tokenizer, which can be made equivalent, is unimportant. What matters is the process of the master b-tokenizer. Either it is a parallel process where the sub b-tokenizer handles a sub-stream which is afterwards concatenated with the rest. Or it is a sequential process where the master b-tokenizer has to wait for the sub b-tokenizer to finish to know on what remaining stream it should operate.

So, if we want to take advantage of parallelization, we should keep these two distinct kind of processes.

Moreover, it has another advantage: error recovery …but we will see that later.

Can I have a summary please?

a bock == type + list of tokens and blocks

It exists a b-tokenizer per type of block:

• Input: a stream
• Output:
  • either error or list of (token or block)
  • remaining stream

Two kind of processes as master b-tokenizer when meeting a ” sub block opener”:

• call the adequate sub b-tokenizer on the stream, then continue the master with the remaining
• call the adequate sub b-tokenizer on a subset of the stream and concatenate it with the master applied on what’s afterwards

Cool, shall we lastly go to the implementation?!

Slow down, not yet. There are a little more things to take into account for a complete implementation. …Coming soon.