
This semester, I'll be teaching the course "Einführung in die Programmierung" (Introduction to Programming) at ETH Zürich. One idea that has been on my mind for quite some time is to create an EBNF verifier, along with an editor that provides basic EBNF language support. Given that I've already been working with it a few years ago, I decided to use Monaco editor, Microsoft's web-based editor, which also powers Visual Studio Code.

> You may find the editor at [gassmann.dev/ebnf](/ebnf).

*Note: Much of the grammar simplification and the CYK algorithm have been adapted from [github.com/JM4ier/parsley](https://github.com/JM4ier/parsley).*

## Syntax

The EBNF parser mostly follows the EBNF syntax as discussed in the "Einführung in die Programmierung" course taught at ETH Zürich. Some things to be aware of include:

- The input is evaluated against the **last** rule
- Each EBNF rule occupies exactly one line
- Comments can be created using `#`
- Empty lines are skipped
- Sequences bind stronger than selections, i.e. `<r> <= [+|-] 0|2|4|6|8` is interpreted as `<r> <= ([+|-] 0)|2|4|6|8` and not as `<r> <= [+|-] (0|2|4|6|8)`. This also coincides with the rules of the lecture, see [slide 10 of this document](https://ethz.ch/content/dam/ethz/special-interest/infk/inst-cs/lst-dam/documents/Education/Classes/Fall2023/0027_Intro/Slides/01B_ebnf_23.pdf). Always set parentheses to avoid confusion.
- You won't be able to use `ε` to match an empty sequence, use `""` instead. The following rule matches the empty string:
  ```bnf
  <empty> <= ""
  ```

The tool consists of an EBNF verifier and an EBNF producer. The verifier checks if a given input conforms to the defined EBNF rules, while the producer generates words based on the rules, incrementally increasing their length.

## Verify

The verifier provides a simple editor where you can input text to validate against the EBNF rules. Each line in the lower half is evaluated against the EBNF ruleset separately. If a line matches the EBNF ruleset, the line is highlighted green, if a line does not match the EBNF ruleset, the line is highlighted red.

You can try the EBNF verifier down below with the EBNF rules from the [HS22 exam](https://exams.vis.ethz.ch/exams/e2r7jb0u.pdf#zjzj01o1yy7lyfqr):

<EbnfBlogWrapper initialRules={`
<identifier> <= a | b | y | z | 7 | x | c | k | m | n

<unary_expression> <= <unary_operator> <primary_expression>
<postfix_expression> <= <primary_expression> | <postfix_expression> ++ | <postfix_expression> --
<primary_expression> <= "(" <special_expression> ")" | <identifier>
<unary_operator> <= * | !
<assignment_expression> <= <expression>" "<assignment_operator>" "<special_expression>
<assignment_operator> <= = | +=
<special_expression> <= <primary_expression> | <special_expression>" "<binary_operator>" "<expression>
<binary_operator> <= * | / | + | %
<expression> <= <assignment_expression> | <postfix_expression> | <unary_expression>
`.trim()} initialContent={`
*(a + b)
z = *(a + b)
y += (z / 7)
x = (a = b)
(b++) += ((a + c))
a = (*b * *c)
y++ * 7
k = m = n
`.trim()} height={'250px'} initialTab={'verify'} />

Note that this EBNF verifier is whitespace-sensitive. For instance, the EBNF ruleset above matches expressions like `*(a + b)` but not `*(a+b)`. To faciliate things, you might consider adding a rule akin to `<whitespace> <= {" "}`.

With an additional `whitespace` rule as suggested above, we'd have a ruleset similar to the one below (which now also matches `*(a+b)`):

<EbnfBlogWrapper initialRules={`
<identifier> <= a | b | y | z | 7 | x | c | k | m | n

<whitespace> <= {" "}
<unary_expression> <= <unary_operator> <primary_expression>
<postfix_expression> <= <primary_expression> | <postfix_expression> ++ | <postfix_expression> --
<primary_expression> <= "(" <special_expression> ")" | <identifier>
<unary_operator> <= * | !
<assignment_expression> <= <expression> <whitespace> <assignment_operator> <whitespace> <special_expression>
<assignment_operator> <= = | +=
<special_expression> <= <primary_expression> | <special_expression> <whitespace> <binary_operator> <whitespace> <expression>
<binary_operator> <= * | / | + | %
<expression> <= <assignment_expression> | <postfix_expression> | <unary_expression>
`.trim()} initialContent={`
*(a + b)
*(a+b)
z = *(a + b)
z=*(a+b)
y += (z / 7)
y+=(z/7)
x = (a = b)
x=(a=b)
(b++) += ((a + c))
(b++)+=((a+c))
a = (*b * *c)
a=(*b**c)
y++ * 7
y++*7
k = m = n
k=m=n
`.trim()} height={'270px'} initialTab={'verify'} />

## Produce

The EBNF producer generates words that follow the defined rules. Words are sorted by length and then lexicographically. Words are produced on the UI thread, so performance may vary with complex rules. In the future, I may move this to web workers for better performance.

You can experiment with the producer here:

<EbnfBlogWrapper initialRules={'<hello> <= "Hi, "\n<world> <= 世界\n<ebnf> <= [<hello> <world> {! | ?}]'} initialContent={''} height={'80px'} initialTab={'produce'} />

Keep in mind that depending on your EBNF ruleset, the number of possible words may grow exponentially as a function of word length.

## Compare

In the compare tab, you can compare two EBNF grammars for equality. After having two valid EBNF grammars on both the left and the right side, you can check for counterexamples with increasing word length.

<EbnfBlogWrapper initialRules={`
<left> <= [hello] {world?}
`.trim()} initialComparison={`
<right> <= hello {world}
`.trim()} height={'250px'} initialTab={'compare'} />

Again, the number of produced words can grow exponentially.

## EBNF language support

Language support extends beyond syntax errors and also encompasses some semantic errors, such as referencing a non-existing rule, as illustrated in the example below:

<EbnfBlogWrapper initialRules={`
<invalid> <= [no brackets
<rule> <= <rule_does_not_exist>
`.trim()} initialContent={''} height={'60px'} initialTab={'produce'} />

All errors have squiggly lines with a description upon hovering over the offending token.

The EBNF verifier/producer view below the rule editor automatically update once the ruleset changes, i.e. the verifier reevaluates whether the input matches the EBNF rule and the producer resets itself.

The producer also detects whether a given ruleset can only produce the empty word. There is also a check in place to detect whether no more words can be produced from the given EBNF ruleset.

<EbnfBlogWrapper initialRules={'<hello> <= ""\n<world> <= ""\n<ebnf> <= [<hello> <world>]'} initialContent={''} height={'80px'} initialTab={'produce'} />

## Next steps

You can also find the EBNF parser [here](/eth/ebnf) outside the blog-post-context (or [here](/ebnf) for fullpage). There are still some things the editor could be extended with. This includes:

- Debounce input for rules, especially for larger rules
- Don't load monaco from an external CDN and use the webpack plugin
- Produce words in a web worker instead of doing it on the UI thread
  - Maybe don't produce words incrementally by word length but rather by some other useful incremental unit?
  - Also show produced words with virtual scroll
- Autocomplete using monaco's auto-complete API
- Add an escape character to e.g. allow matching quotation marks (`"`)
- serve as a PWA

**I do not guarantee the correctness of any results.** In case, you spot any errors, feel free to send me an [email](mailto:tgassmann@student.ethz.ch).

## Updates

<DetailsContainer>
<Details title="Update 2023-09-16">
You can now also use the above EBNF component as a web component:

```html
<ebnf-editor height="100px"></ebnf-editor>
<script type="module" src="https://thomasgassmann.com/widgets/ebnf.js"></script>
```

The `height` property is the only property that is currently exposed. It is required. The editor is going to take up the full width of its parent element.
</Details>

<Details title="Update 2023-09-20">

- Fixed some issues with the parser mistakenly accepting incomplete choice selections.
- Disallow creating empty rules (matched the empty string before)

</Details>

<Details title="Update 2023-09-22">

- Added fullscreen mode
- Moved share button to toolbar
- Show credits for parsely and docs in toolbar in all cases (not just when referenced via widget)
- Added [fullscreen page](/ebnf)

</Details>

<Details title="Update 2023-09-25">

- Added a neat easter egg for late-night EBNF enjoyers

</Details>

<Details title="Update 2023-09-27">

- Added full page mode support to EBNF widget. Use the fill property:
  ```html
  <ebnf-editor height="100px" fill="true"></ebnf-editor>
  <script type="module" src="https://thomasgassmann.com/widgets/ebnf.js"></script>
  ```
- Fixed an issue with CRLF / LF line breaks
- Added `Debug` button to print output of parser to console
- Clarify binding preference in documentation above (sequences bind stronger than selections)

</Details>

<Details title="Update 2023-09-30">

- Properly documented how to match empty sequences and emphasized that `ε` is not a keyword to do so within this editor

</Details>

<Details title="Update 2023-10-01">

- Do not show Debug button by default. Allow users to optionally enable it on the [debug page](/debug).

</Details>

<Details title="Update 2024-09-02">

- Add dark mode
- Update design to fit overall new website design.

</Details>

<Details title="Update 2024-09-24">

- Add feature to compare two EBNF grammars for equivalence

An example down below:

<EbnfBlogWrapper initialRules={`
<left> <= test{?}
`.trim()} initialComparison={`
<right> <= {test}
`.trim()} height={'250px'} initialTab={'compare'} />

</Details>
</DetailsContainer>


EBNF Lab: a web-based editor for EBNF grammars


I was recently having a discussion about password inputs! Most password fields out there mask their characters, i.e. they display "********" instead of "password". However, in some project I was involved there was a requirement to mask the input such that it would always display a static number of masked characters. I thought it would be somewhat unintuitive and questioned the benefit of it. But apparently there are also some well-known applications doing this as well. This made me wonder what advantage a brute-force attacker gains by knowing the length of the password.

Let $r(n,m)$ be the ratio of possible passwords you can eliminate from your search, with $n$ being the password length and $m$ being the number of valid characters. Then:

$$
\begin{align*}
r(n, m) & = \frac{\sum_{i=1}^{n-1} m^i}{m^n}\\
& = \frac{\frac{m^n - 1}{m - 1} - 1}{m^n}\\
& = \frac{m^n - m}{m^n(m - 1)}\\
& = \frac{1 - m^{1-n}}{m - 1}
\end{align*}
$$

Now, if we assume that $m, n \geq 2$ (notice that $m^{1-n}$ is decreasing in $[2, \infty) \times [2, \infty)$):

$$
\frac{1}{2(m - 1)} \leq \frac{1 - m^{1-n}}{m - 1} \leq \frac{1}{m - 1}
$$

One interesting observation here is the following: even if your password was infinitely long, an attacker would still get *some* benefit from knowing the length of your password, the benefit of which at this point only depends on the number of characters that are allowed.

In practice, we can almost always assume that $m \geq 62$ (26 lower-case, 26 upper-case, 10 digit characters), which gives us the following bounds:

$$
\left[ \frac{1}{122}, \frac{1}{61} \right] \approx \left[ 0.008197, 0.016393 \right]
$$

i.e. even in the worst-case scenario, an attacker would only have approx. 1.63% fewer options to try.


Welcome to my personal blog

Recent Posts

EBNF Lab: a web-based editor for EBNF grammars

Keeping password length secret