I.1

LRGrep

Selecting Error Messages for LR Parsers

Python:

from calendar import weekday, SUNDAY

[year for year in range(2008, 2122)
    if weekday(year, 12, 25) == SUNDAY]

Lua:

require("date")

for year=2008,2121 do
   if date(year, 12, 25):getweekday() == 1 then
      print(year)
   end
end

Javascript:

for (var year = 2008; year <= 2121; year++) {
    var xmas = new Date(year, 11, 25)
    if ( xmas.getDay() === 0 )
        console.log(year)
}

If the rules are broken?

example.ml

¹ let x = 5;
² let y = 6
³ let z = 7

ocamlc example.ml

File "example.ml", line 3, characters 0-3:
3 | let z = 7
    ^^^
Error: Syntax error

A frustrating experience for developers!

Plan

Problems with (LR) parsing and errors

LRGrep for grammar authors

Applications

A technical look at LRGrep

1. Problems with (LR) parsing and errors

Context-Free Grammars

S e n t e n c e \to S u b j e c t V e r b C o m p l e m e n t

$\begin{aligned} S u b j e c t & \to & Jerry & | Mary \\ V e r b & \to & eats & | drinks \\ C o m p l e m e n t & \to & pizza & | coffee \end{aligned}$

Terminals: $Jerry$ , $Mary$ , $eats$ , $drinks$ , $pizza$ , $coffee$

Nonterminals: $S e n t e n c e, S u b j e c t, V e r b, C o m p l e m e n t$

$\begin{array}{r} Jerry eats pizza \end{array}$

$\begin{array}{r} \frac{Jerry}{S u b j e c t} eats pizza \end{array}$

$\begin{array}{r} \frac{Jerry}{S u b j e c t} \frac{eats}{V e r b} pizza \end{array}$

$\begin{array}{r} \frac{Jerry}{S u b j e c t} \frac{eats}{V e r b} \frac{pizza}{C o m p l e m e n t} \end{array}$

$\begin{array}{r} \frac{\frac{Jerry}{S u b j e c t} \frac{eats}{V e r b} \frac{pizza}{C o m p l e m e n t}}{S e n t e n c e} \end{array}$

Second example: minimal arithmetic

How could we recognize an expression like: $1 + 2$

$\begin{aligned} E & \to T \\ E & \to T + E \\ T & \to n \\ T & \to (E) \end{aligned}$ Terminals: $+$ , $($ , $)$ , $n$

Nonterminals: $E$ (expression), $T$ (term)

$\begin{array}{r} \frac{\frac{1}{T} + \frac{\frac{2}{T}}{E}}{E} \end{array}$

$\Rightarrow$ Constructing these trees is the job of a parser

Generating parsers from grammars

Hand-writting parsers quickly appeared to be problematic: this process was tedious and error-prone.
This motivated a long line of research on parsing algorithms.

In this thesis, I worked on the family of LR parsers:

They are generated automatically from a grammar.
They are good at processing programming languages.

Yet, mainstream compilers tend to abandon generated parsers:

GCC moved away from generated parsers in 2006 for C and in 2004 for C++
Go in 2015
Ruby in 2023
...

Why?

"Error tolerance ..." (Ruby)
"Better error reporting with a hand-written parser" (C#)

Parsing 1/2: Shift-Reduce Parsing

We can recognize any sentence by repeating two actions:

Shift reads the next symbol
Reduce recognizes a rule

Let us write $stack ▸ input$ for a step, where:

$stack$ is a partially recognized prefix
$input$ is the suffix of the input that has not been read yet

$▸ 1 + 2$

$⇓ Shift$

$n ▸ + 2$

$⇓ Reduce T \to n$

$T ▸ + 2$

$⇓ Shift$

$T + ▸ 2$

$⇓ Shift$

$T + n ▸$

$⇓ Reduce T \to n$

$T + T ▸$

$⇓ Reduce E \to T$

$T + E ▸$

$⇓ Reduce E \to T + E$

$E ▸$

Parsing 2/2: LR(0) states and automaton

Question: How do we know which actions are applicable?

Idea: Keep track of the grammar rules have been partially recognized.

An item mark a position in a rule with a $∙$ .

For instance, $E \to ∙ T + E$ is an item.

When starting, we want to recognize an expression.

$\begin{aligned} E & \to ∙ T \\ E & \to ∙ T + E \end{aligned}$

$\begin{aligned} E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned}$

This is the initial state.

A state is a set of items, representing the candidates applicable to a situation.

Let's repeat the parsing process while tracking states:

\begin{aligned} E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned}

$▸ 1 + 2$

$⇓ Shift$

\begin{aligned} T & \to n ∙ \end{aligned}

$n ▸ + 2$

$⇓ Reduce T \to n$

\begin{aligned} \begin{aligned} E & \to T ∙ \\ E & \to T ∙ + E \end{aligned} \\ T ▸ + 2 \end{aligned}

$⇓ Shift$

$\dots$

Two kinds of actions are sufficient to recognize every sentence:

$Shift$ consumes one input symbol
$Reduce A \to β$ replaces suffix $β$ by $A$ in the stack

An item, written $A \to β ∙ γ$ , represents a position in a rule.
A state tracks active items and gives the applicable actions.

What happens on invalid input?

Let us look at examples of incomplete input.

First example: " $1 +$ "

We would like to report: "Expecting a number".

$▸ 1 +$

$⇓ Shift$

$n ▸ +$

$⇓ Reduce T \to n$

$T ▸ +$

$⇓ Shift$

$T + ▸$

T + ▸

\begin{aligned} E & \to T + ∙ E \\ E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned}

T + ▸

We get stuck with a stack and a state.

Second Example: " $(1$ "

We would like to report: "Unclosed parenthesis".

$▸ (1$

$⇓ Shift$

$(▸ 1$

$⇓ Shift$

$(n ▸$

(n ▸

\begin{aligned} \begin{aligned} T & \to n ∙ \end{aligned} \\ (n ▸ \end{aligned}

$⇓ Reduce T \to n$

\begin{aligned} \begin{aligned} E & \to T ∙ \\ E & \to T ∙ + E \end{aligned} \\ (T ▸ \end{aligned}

$⇓ Reduce E \to T$

\begin{aligned} \begin{aligned} T & \to (E ∙) \end{aligned} \\ (E ▸ \end{aligned}

The input is invalid if actions do not permit reaching the goal.

The position of failure is well-defined (after the last shift).

The concept of "failing configuration" is slippery because of reductions.

Negative Space of Grammars

Could we also specify the handling of errors?

Connecting a Failure to an Error Message

How to specify the association between a failure and a message?

How to realize this specification efficiently?

How to help author this specification?

We focus on the technical aspect and not the human aspect:

LRGrep extract information from failures.
It is up to the grammar author to make use of this information.

State-of-the-Art

If error looks like "1+"

report "Expecting a number"

If error looks like "(1"

report "A parenthesis has not been closed"

\begin{aligned} "1+" & \to & \begin{aligned} E & \to T + ∙ E \\ E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned} & \to & "Expecting a number" \end{aligned}

\begin{aligned} "1+" & \to & \begin{aligned} E & \to T + ∙ E \\ E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned} & \to & "Expecting a number" \\ "(1" & \to & {\begin{matrix} \begin{aligned} T & \to n ∙ \end{aligned} ? \\ \begin{aligned} E & \to T ∙ \\ E & \to T ∙ + E \end{aligned} ? \\ \begin{aligned} T & \to (E ∙) \end{aligned} ? \end{matrix}} & \to & "A parenthesis has not been closed" \end{aligned}

State-based identification using examples
No control over reductions: undefined behaviors

Used in earlier versions of Go.

In case of error, reduce T and E (if possible)

If error looks like "1+"

report "Expecting a number"

If error looks like "(1"

report "A parenthesis has not been closed"

\begin{aligned} "1+" & \to & \begin{aligned} E & \to T + ∙ E \\ E & \to ∙ T \\ E & \to ∙ T + E \\ T & \to ∙ n \\ T & \to ∙ (E) \end{aligned} & \to & "Expecting a number" \\ "(1" & \to & \begin{aligned} T & \to (E ∙) \end{aligned} & \to & "A parenthesis has not been closed" \end{aligned}

Coarse-grained control of reductions
Exhaustivity check
State-based enumeration of counter-examples

Used in Compcert C, Catala, ...

LRGrep

Selecting Error Messages for LR Parsers

If the rules are broken?

Plan

1. Problems with (LR) parsing and errors

Context-Free Grammars

Second example: minimal arithmetic

Generating parsers from grammars

Parsing 1/2: Shift-Reduce Parsing

Parsing 2/2: LR(0) states and automaton

What happens on invalid input?

First example: "1+"

Second Example: "(1"

Negative Space of Grammars

Connecting a Failure to an Error Message

State-of-the-Art

First example: " $1 +$ "

Second Example: " $(1$ "