LPeg and PEG practices

Those who have read my previous blog might know that I have become a Luar. Lua is now my second language and the first language in my spare time. The most commonly used language in my work is JavaScript because I am a front-end programmer. Before mentioning LPeg, I still have to mention a part that is almost necessary for all languages today, that is, pattern matching.

Since I didn’t major in computer science, I did not learn about pattern matching in the classroom at university. Let’s first look at what pattern matching is:

Pattern matching in computer science is the checking and locating of specific sequences of data of some pattern among raw data or a sequence of tokens.

— techopedia

I also read the definitions on Wikipedia and Baidu Baike, but I didn’t understand them very clearly, so I just looked for definitions from other sources. In modern programming, the most common way of pattern matching should be regular expressions. Everyone should have heard of this. In the process of my work, I should have used regular expressions frequently. In JS, regular expressions are used to search and replace strings.

Lua’s string library also supports a syntax similar to regular expressions. However, Lua’s built-in pattern matching is much more streamlined than our commonly used regular expressions, and there will be many patterns that are difficult to express. Of course, I am not saying that Lua is not good. From a minimalist point of view, this is excellent. After all, the mode that comes with Lua can meet most of the needs. And it is said that as long as Lua’s built-in pattern matching can match, the efficiency is faster than PCRE (a regular expression standard). So I can use the built-in one in the program.

But I have always known that Lua has a powerful matching library, which is also developed by the author of Lua — Roberto Ierusalimschy, called LPeg, which can not only make up for the deficiencies of Lua’s native matching, but also has a stronger expressivity than regular expressions. But to be honest, its documentation is not well written. There are few examples and it is not clear how to use the functions. So I chose to avoid it. However, as you all know, I started using an editor a few months ago called Textadept. All syntax highlighting of this editor is written with LPeg. And you can write a lexer of a language with a very small amount of code. This is very interesting.

Take a small piece of code that parses Markdown syntax that I wrote as an example to show you how LPeg works.

[embed]

This code appears in the Markdown lexer of Textadept, so some Textadept is used, which is defined in lexer.lua . This code describes the italic and bold syntax in Markdown. If you are familiar with Markdown, you should know that * can be used in words, but _ can’t. According to the Markdown specification, there will be the following:

• foo*bar* produces foobar，but foo_bar_ produces foobar
• a * foo bar* won’t produce italic, foo-_(bar)_ will produce italic，_foo_bar_baz_ will italicize the whole foo_bar_baz
• _(bar)_? has punctuation in the end, but underline can be used for this case (bar)?

To be honest, I have seen a lot of people who claim to implement Markdown parsing, and they do not meet the standard here. But with such a few lines of Lua code combined with LPeg, it can be very close to the standard (because it is a code editor, I did not consider nested bolding and slanting).

Since my purpose is not to write a tutorial, the above example is not to show you the most basic things. Let’s talk about LPeg again. So what exactly is LPeg? We need to understand PEG first, that is, parsing expression grammar. We quote Wikipedia:

In computer science, a parsing expression grammar (PEG), is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

Why is it analytical? It is mentioned that analytical grammar is a different system from the well-known Chomsky hierarchy. Analytical grammar pays more attention to the correspondence with the structure and semantics of the parser. I can also feel it when I use it. Its thinking is more direct than CFG. When you use PEG to define a grammar, you will naturally bypass some of the circular definitions in CFG, and PEG itself will also ensure that the grammar will not be ambiguous. At the same time, its actual expressivity is at least beyond regular expressions.

I used to think that LPeg does not support lazy matching for a while. This problem has always been a factor preventing me from continuing to explore LPeg. In the early stage of using LPeg, I always looked at the official documents. And as I said earlier, the examples of official documents are limited, so some key parts are not understood. It wasn’t until I recently opened a paper on PEG in order to implement auto-completion of JS for Textadept that I really understood a bit. This paper is at the top of the LPeg official website, but I have been looking at the document and haven’t read this. I realized from reading the paper that if you want to really know how to use LPeg, you can’t just read the documentation, you have to understand PEG. This paper is *A Text Pattern-Matching Tool based on Parsing Expression Grammars*, written by Roberto, and involves the knowledge of PEG and the specific implementation of PEG in LPeg.

There are two keywords I think about PEG: restricted backtracking and ordered choice.

• Restricted backtracking means that PEG only performs partial backtracking, that is, it only backtracks where there are multiple options within a rule. As long as one of the options matches successfully, then even if the rule is unsuccessful, it will not return to the next option, or shorten the match length of a * or + to try to match. This is different from the longest matching principle followed by regular expressions and Lua’s native pattern matching.
• Ordered choice means that the rules for multiple options in PEG use the / operator, which is called the ordered choice operator. This is essentially different from the | operator in CFG. If you choose the first one, you won’t consider the second one.

At first, such a rule may feel that it limits the expression of our meaning. But in fact, its expressive ability is still very powerful, which is sufficient for programming languages. And the benefits it brings can be known after a little thought. Compared with CFG, it avoids ambiguity. Compared with regular expressions, its matching time is predictable because of its strict performance model. Although Wikipedia says that it is speculated that there are context-free languages that cannot be processed with PEG, it has not been confirmed after all. As far as I know, Lua itself, JavaScript, CSS, and many kinds of data have implemented PEG parsing.

The paper mentioned above shows us how to achieve greedy matching, lazy matching, positive and negative lookahead without any extension to PEG.

I used to have the question that LPeg does not support lazy matching. This is because I don’t know much about PEG. I could only do blind greedy matching at that time, which is also a greedy matching without backtracking. It is very simple to blindly match as many E1 as possible, and then follow the rule of matching E2, which is

To be honest, blind matching is enough for simple situations. In the case that E1 is not a prefix of E2, blind and non-blind greedy matching are equivalent.

The non-blind greedy match multiple E1 followed by E2 is written as

This rule will keep trying to match E1 until it fails to match E1. If E2 is not matched at this time, the matching will not end there, because we have selected the first option at each level of recursion, and we have not matched successfully, so we are still in the scope of partial backtracking. The PEG engine will go back to the previous layer and try to select the second option E2. If it does not match again, it will go back to the previous layer recursively until the match is successful. At this time, the matching result must be the largest number of E1, followed by an E2.

Let’s talk about lazy matching. Lazily match multiple E1, then followed by E2 is written as

This rule will recurse layer by layer, each time it matches E2 first, and if it doesn’t match, it tries to match one more E1. As long as an E2 is matched, the recursion will end. So this rule matches the least number of E1, followed by an E2.

Another thing to note is that the standard PEG does not support left recursion. So what is left recursion? We quote Wikipedia again

Left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right).

And left recursion can be divided into direct left recursion and indirect left recursion. I will simply give an example of direct left recursion so that everyone can understand its meaning

Although many papers have studied the systematic elimination of left recursion in recent years, neither LPeg nor PEG.js supports left recursion. I think that maybe Roberto doesn’t want to support left recursion. He wants to encourage people to write well-formed PEGs instead of programming methods to resolve left recursion.

I also saw the magical usage above and regained my confidence in LPeg. And then I saw another paper *From regexes to parsing expression grammars*, this paper describes in detail how to convert regular expressions to PEG, with strict proofs. This also confirms what I said earlier that it has expressiveness beyond regular expressions.

LPeg has two styles, one is like my previous example, the author likes to call it SNOBOL style, but I prefer to call it “programming” style; the other, the author likes to call it regular style, but I prefer to call it a “standard” style (because this style is used in the thesis). Both have their advantages. The programming style is convenient for programming and expansion, and some functions can be defined to handle capture, which is more extensible. As for the standard style, I think it is easy to understand the meaning of PEG grammar, because, plus sign + I think it makes people Can’t feel the meaning of orderly choice. I haven’t clearly realized for a long time that LPeg makes an orderly selection. And there are too many types of programmatic captures, such as Cb, Cc, Cf, Cg, Cp, which makes people look dizzy, but in the standard style, I feel much better. Let me take the JS auto-completion grammar I wrote as an example again. Although it is not necessarily perfect, it is really easy to use.

js_line      <- {| js_expr !. / js_expr_nonstart |}
js_expr_nonstart <- ([^a-zA-Z0-9_$] js_expr / . js_expr_nonstart) !. / . js_expr_nonstart
js_expr      <- ((jq_selector / prev_token) '.' / '') {:part: %a* :}
jq_selector  <- {:symbol: '$' balanced -> 'jQuery.fn' :} func*
func         <- '.' %a+ balanced
prev_token   <- {:symbol: [a-zA-Z0-9_$/'"`]+ :} balanced?
balanced     <- '(' ([^()] / balanced)* ')'

Briefly explain what this grammar does. The purpose of this grammar is to match the form of a symbol.part. Since jQuery is a function-by-function style, and the return value is jQuery.fn, if you only match the previous symbol, you can’t tell whether it’s jQuery, so it should be consistent with the jQuery logo (that is, the $ symbol ) To start matching. We see that the jq_selector rule is for this, it will match the form of $(...).fn1(...).fn2(...).part; and the matching of prev_token is a simple symbol.part or symbol(…).part form. To perform code completion as needed. The balanced rule is the sample code used by PEG to match paired parentheses. It is very easy to use. Of course, Lua’s built-in pattern matching also supports paired parentheses matching, but it is too weak. Paired parentheses cannot add ? or * operations, which directly prevents me from using Lua native matching to complete this matching.

Since we start the match from the first character of a line, but if we want to complete the code, it will always match to the last character, so we have processed it in js_line and js_expr_nonstart. If it is matched, it is found that it is not the last character. , Then try again with the wrong one. The idea is very straightforward. The completion of this match also made me full of confidence in PEG. I even had the idea of parsing SQL some time ago, and I did it. It only took two or three days to realize the analysis of the main functions of SQL, and also wrote my own AST output function, because I felt that using the ready-made inspect output too affected understanding, and it took up too much space and affected human reading.

For a simple SQL:

SELECT DISTINCT a, b FROM c JOIN d ON c.id = d.id
WHERE todo IN(1,2,3)
ORDER BY b ASC

The output looks like this

{sql_select:
    {
        SELECT, DISTINCT, 
        {select_elements:
            {select_expr:
                {expr:
                    {condition:
                        {operand:
                            {column_expr: a}
                        }
                    }
                }
            },
            {select_expr:
                {expr:
                    {condition:
                        {operand:
                            {column_expr: b}
                        }
                    }
                }
            }
        }
    },
    {
        FROM, 
        {table_ref:
            {table_factor:
                {table_name: c}
            },
            {join_expr:
                JOIN, 
                {table_factor:
                    {table_name: d}
                },
                ON, 
                {expr:
                    {condition:
                        {operand:
                            {column_expr: c.id}
                        },
                        =, 
                        {operand:
                            {column_expr: d.id}
                        }
                    }
                }
            }
        }
    },
    {
        WHERE, 
        {expr:
            {condition:
                {operand:
                    {column_expr: todo}
                },
                IN, 
                {value: 1},
                {value: 2},
                {value: 3}
            }
        }
    },
    {
        ORDER BY, 
        {order:
            {column_expr: b},
            ASC
        }
    }
}

Can you imagine how such a structure is matched with LPeg? To put it simply is to repeatedly use simple matching { p } and table matching {| p |}, which is powerful enough. Because we need to have a tag, we can add one more named match {:name: p:} at most. I think I will definitely not write a huge regular expression to match this, of course, no one will do it. General parsing grammar will use special tools, such as bison. Of course, handwriting is also a way, but how to say it, with such formal grammar to support you, you will be more assured, and the readability is also good. With a hand-written parser, you will see one or more long switch statements. At this point, I really admire the people who invented automata. Behind LPeg is an automaton. As long as I compile my pattern, I can always use it to match.

Using LPeg to create a parser can integrate lexical analysis and grammatical analysis. I only discovered this after using it for a while. I used LPeg to analyze SQL with reference to several other implementations. One of them is tclh123/lpeg-sql, which I think is of great reference value. But his grammar doesn’t consider too many situations. I think using his grammar may only match extremely simple SQL. Since I have a bigger goal, I plan to use SQL parsing to do something, so I used my grammar to test the actual SQL in the current company project to ensure that they can pass my parsing, instead of matching half of it. There is no match.

As I said before, when you write a PEG grammar, you will pay attention to precedence issues. Then arrange a rule in order of priority. For example, the precedence of the function must be higher than column_expr. Because whether it is column_expr or table_factor, there is a dispensable alias behind them, and once the match is considered successful in PEG, it will not consider the next option at all, but perhaps, what is encountered is a set of parentheses. That is our function, but it was too late and the match failed. Also, if you don’t limit the rules, there will be many cases where the reserved words and name will match incorrectly. Because if you don’t have the rules for reserved words, then name can be made up of reserved words, judging from the character composition. Fortunately, negative predicates can be used in PEG. I just thought that if it is in the regularity, it should be called negative lookahead. Pass the following rule

name <- !reserved ([0-9a-zA-Z$_]+ / ["`] [^"`]+ ["`])

That’s it. I once imagined that without this, I might have to use ordered selection, and also need to rewrite some rules to ensure that the name does not get the identifier. But fortunately, there is this “advanced” operator. Since I see that the grammar of JOIN in other reference tables is not well written, I refer to the grammar in the official MySQL documentation, but it is here that I encountered the legendary left recursion for the first time. Let me extract a slightly simplified grammar of the official definition, which is obviously a CFG:

table_references:
    table_reference [, table_reference] ...

table_reference:
    table_factor
  | joined_table

table_factor:
    tbl_name [PARTITION (partition_names)]
        [[AS] alias] [index_hint_list]
  | table_subquery [AS] alias [(col_list)]
  | ( table_references )

joined_table:
    table_reference {[INNER | CROSS] JOIN | STRAIGHT_JOIN} table_factor [join_specification]
  | table_reference {LEFT|RIGHT} [OUTER] JOIN table_reference join_specification
  | table_reference NATURAL [INNER | {LEFT|RIGHT} [OUTER]] JOIN table_factor

join_specification:
    ON search_condition
  | USING (join_column_list)

I didn’t know much about left recursion at the time, so I directly translated it into PEG. As everyone expected, LPeg reported an error. So obediently went through blogs and papers for a long time. You can find that the above grammar involves the indirect left recursion of joined_table that is not easy to transform. Let’s take a look at why this is left recursion.

joined_table <- table_reference ... <- joined_table ...

My solution is to not use the joined_table rule. If you don’t get rid of this rule, it may be difficult to eliminate this left recursion. But we need to understand what this grammar wants to express, because we have experience in SQL, we know that this is a table that can JOIN several tables continuously, so I modified the definition of table_ref, this definition is not recursive, just mentioned above The obtained “blind” greedy match, greedily matched all the following join_expr all at once, very concise.

table_refs   <- table_ref (%s* ',' %s* table_ref)*
table_ref    <- table_factor (%s+ join_expr)*
table_factor <- (table_name / subquery) (%s+ (AS %s+)? alias)? / '(' %s* table_refs %s* ')'
join_expr    <- (( (LEFT / RIGHT) (%s+ OUTER)? / INNER / CROSS / NATURAL) %s+)?
                JOIN %s+ table_factor (%s+ join_spec)? |}
join_spec    <- ON %s+ expr / USING %s* '(' %s* name (%s* ',' %s* name)* %s* ')'

One of the reasons why I wrote this blog is that I have seen very few Chinese materials about PEG and not many English materials. I very much hope that my practice can help you so that you can try the grammar of PEG. As you may know, on July 2, 2019, Cloudflare caused a significant increase in the CPU usage of a key component of its service due to regular expressions, and there was a global outage. The following is the regularity written by Cloudflare, which will lead to catastrophic backtracking.

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

Regular expressions are hard to read, right? At least for the complex pattern. It is not only difficult to read, but also difficult to debug. As stated on the rosie-lang webpage, if it is converted into a PEG grammar, there will be no such problem.

Originally published at brynne8.github.io.