On the concept of syntax escaping

Syntax escaping is a fundamental primitive in formal grammars. Whenever you embed one syntax into another, you need syntax escaping mechanisms. Since programmers and writers have to apply these mechanisms, you want to design them in a usable manner. Be aware that more often than desired grammars are embedded in grammars embedded in grammars embedded in grammars. With increasing recursion depth, the rules become more and more difficult for the programmer to maintain in his brain.

In this post, I want to devise a model to derive escaping rules and then reason about usability of escaping. The post is very long, but very exhaustive on the topic.

Why is escaping necessary? If I show you the string let text = "Hello my world";; and you are a programmer, you might immediately conclude that variable text will be assigned the string of characters Hello my world (this is OCaml syntax, BTW). This is fine, but what happens, if I want to assign Hello "my" world to variable text? The immediate solution let text = "Hello "my" world";; will yield invalid code, because you might recognize that " acts as initializer and terminator of the string in-between. As such to denote the string Hello "my" world you need to escape the syntactical rules surrounding this context.

This was a programmer’s example. But it is not difficult to find examples from literature. Consider a direct quote:

The said statement is wrapped in single apostrophes, but if the statement itself uses an apostrophe, you run into a problem. Only by context and reading ahead, you will be able that she heard Sofia’s gate! and not Sofia. Funny enough, my blog software replaces the apostrophe before s with the typographically correct version and thus renders a visual difference.

Let the alphabet of a formal grammar be {A, B, X}. In order to talk about escaping, we need to assign one of the three characters a special meaning. Let X be that character. Consider some string of the grammar. If the special character occurs, the string that follows can really have any kind of semantics:

But usually we want to return to the original semantics and continue with {A, B} characters:

How can we get back from the special semantics of X to the regular semantics? There are two preferred strategies:

But many other strategies are possible. As one example, the character following X could act as terminator. As another one, the sequence of As following X replaced by B could act as terminator. These examples could continue to arbitrary complexity.

An ordered, finite sequence of rules described by case (A) or (B) gives an escaping mechanism:

Coming back to the OCaml [subset] example, OCaml uses let text = "Hello \"my\" world";; for the assignment of Hello "my" world to text. The escaping rules are pretty simple:

Why do we need two rules? Because the second one satisfies the fifth requirement. Another interesting example is XML. Once more, we consider the sequence Hello "my" world. How does one escape double quotation marks in XML?

Apparently, the difference is just that we use variadic- instead of fixed-length S. You might wonder, why we need case (B). One example is CSV, where " is often escaped as "". More specifically, any sequence of quotation marks is replaced by the same sequence concatenated with another quotation mark. As a result, one would have to list an arbitrary sequence of " repetitions for R. As a result, the set of rules is infinite. Since this is not practical, I added the word finite to the model together with Case (B):

Since R equals C here, only one rule is required.

In essence, we can distinguish 3 styles here:

I have to admit that from an information-theoretic perspective, the approaches allow roughly (26, 1, unlimited) number of escape sequences respectively. Calling them out as equal approaches might not be fair.

From the algorithmic point of view, all three are pretty trivial to implement. You need to distinguish between encoding (“give me its escaped version”) and decoding (“give me its original text”). Variadic-length syntax decoding is a little bit more computationally intense in the sense that the entire string “"” must be collected. Once the entire string is available, we can replace it with its corresponding text version.

But one interesting question arises. Often you have functionalities available which allow you to replace all occurences of a string with some replacement (a replace operation taking two strings as argument). Can the syntax escaping mechanism be fully described by successive application of replacements?

Why does it fail for CSV? Fundamentally, because it uses case (B) which requires infinite application. Replacing " by "" would result in doubling the number of double quotes (i.e. con"tr""ived becomes con""rt""""ived because each double quote is handled individually). You would need to start with the longest double-quotes sequence. But what is its longest sequence? You can evaluate the longest sequence and adjust replace-operations accordingly. But then it is not just a successive application of replace operations anymore.

For the other two cases, this is possible. I provided an pure/trivial implementation of the three escaping mechanisms in Lua for UTF-8 strings in the next blogpost.

But can’t we just avoid syntax escaping? The grammar outside dictates which sequences need to be escaped. Can we not adjust strings required be to replaced not to occur in the actual string? Because we modify the syntax outside, we don’t have the same scenario as above. This is avoidance, not escaping.

Let us take an example. I think, UNIX coreutil sed is most famous for it: s/home/tmp/ denotes that home shall be replaced by tmp. In this syntax, obviously U+002F SOLIDUS is the delimiter. So how can we use tmp/typho as replacement instead? Yes, there are escaping rules, but sed allows us to use a different delimiter to avoid collisions. s$home$tmp/typho$ would avoid the use of escape sequences.

Can we name more examples?

Indeed, this is very useful. However, I would like to emphasize that strings delimited by " or """ must not start with ". You need a second notation with ' and '' to make it possible without using syntax escaping rules. In conclusion, you want to have for each delimiting character a sequence of this character as delimiter as well (so you can use this individual character inside text). On the other hand, you also need a different character, because the string must not start with this former character without using syntax escaping.

In the end, syntax escaping avoidance is possible, but has some complexity in itself.

I think syntax escaping has two different requirements:

The second requirement is vague, I call it usability and let us go into the details.

Many programming languages replace " by \" together with \ as \\. However, additionally they might support \u{…} where … is some hexadecimal ID for the Unicode scalar. As such the system is not purely (1) or (2). XML prefers variadic lengths and CSV is an example for successive syntax escaping. We come back to the idea that the escape character starts a new formal grammar and anything can happen. But how do we need to design syntax escaping to make it usable?

Naturally, most grammar only use one character for the first criterion and thus are already small. The second requirement is more difficult. Do you remember \n more easily or &newline;? Do you prefer single-letters or keywords? This is a question difficult to answer and only solvable with tradeoffs.

By having the rough understanding of usability, I want to revisit language’s escape mechanisms:

We can conclude that fixed-length syntax escaping with various lengths is very popular among programming languages. For data serialization (CSV/XML), different approaches are popular. But let us get back to our usability criteria:

Naturally, most grammar only use one character for the first criterion and thus are already small. The second requirement is more difficult. Do you remember \n more easily or &newline;? Do you prefer single-letters or keywords? This is a question difficult to answer and only solvable with tradeoffs.

What I find interesting are the following 2 thoughts with the languages above:

I would like to call out two bad examples here as well:

In this post, I wanted to provide a formal basis to reason about usability. But a problem arised. You can define the model (c.f. Conceptual view on syntax escaping), you can look at approaches and examples (c.f. Examples) and you can identify requirements. But in the end, the notion of usability is very difficult to reason about. Simply put, syntax escaping has a formal basis and practically, all different approaches are mixed up and occur simultaneously, because all concepts address different users. For example, \n is a historic relict of C, \u{00A0} is an obvious result of Unicode, "" is a trivial approach resulting from synactic minimality of CSV and XML prefers keywords. So the question “which escaping rules are easiest to remember” do not have an clear winner but must be answered as “depends on which mechanisms the user already knows”.

However, putting all experiences aside, I do personally think we have some winner. Some mechanism easiest to remember for unbiased users:

My point:

And thus we have a new escaping mechanism. It breaks conventions. Use with care. Here be dragons.