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

This semester I am going to 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.

*First of all, I'd like to point out that the vast majority of the grammar simplification/normalization, as well as the CYK algorithm, has been adapted from [github.com/JM4ier/parsley](https://github.com/JM4ier/parsley).*

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)`. Always set parentheses to avoid confusion. 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).
- You won't be able to use `ε` to match an empty sequence, use `""` instead. The following rule matches the empty string:
  ```bnf
  <empty> <= ""
  ```

Currently there is an EBNF verifier and an EBNF producer. The EBNF verifier checks whether a given input matches the EBNF rules, while the EBNF producer incrementally generates words that conform to the EBNF rules, with increasing word length.

## Verifier

The verifier provides a basic editor where input to check against the rules can be entered. Some things to keep in mind:

- Each line 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'} />

There are also some deviations to EBNF as it is being taught at ETH Zürich. 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> <= {" "}`. In general:

- This parser is sensitve to whitespace
- For string literals containing whitespace or that themselves contain EBNF tokens, use quotation marks

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'} />

## Producer

Now, regarding the EBNF producer:

- Words are sorted by length first, then lexicographically
- Currently, words are generated on the UI thread, so the performance may vary depending on your ruleset
  - I will probably use web workers for this if I find the time

Again, you can try the EBNF producer down below, just repeatedly press `Produce words of length [...]` until you see more words that conform to these EBNF rules:

<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.

Integrating basic EBNF language support into Monaco Editor has proven remarkably straightforward, especially if you already have an EBNF parser in place. Things like commenting using `Ctrl + K, Ctrl + C` or uncommenting using `Ctrl + K, Ctrl + U` also require very little configuration.

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 are also some heuristics 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'} />

## TODOs

You can also find the EBNF parser [here](/eth/ebnf) outside the blog-post-context. There are still many things the editor could be extended with. Some TODOs include:

- Dark mode (main problem here is finding the colors for syntax highlighting)
  - Dark mode on this website is still very basic in general, only the Polyring widget supports it, I'm bad at choosing colors
- 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 (`"`)

**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

<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>


EBNF tooling


> Note that these are only some rough calculations based on a set of strong assumptions I made at 1am. The same is not going to hold for techniques other than brute force.

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 that would be quite unintuitive and questioned the benefit of it. But apparently, there are also some well-known applications that are doing this. This made me wonder how much easier it would be to guess a password if you already knew its length.

Let's assume a very basic brute force approach. 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 possible characters.

$$
\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 strictly 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.


Keeping password length secret


[Digital Design and Computer Architecture](https://safari.ethz.ch/digitaltechnik/spring2023/doku.php) has been one of the more interesting courses I took at ETH this semester. Even if there were a lot of [readings](https://safari.ethz.ch/digitaltechnik/spring2023/doku.php?id=readings), learning how a computer works from the ground up and building a simple single-cycle MIPS processor has been a very rewarding experience (I am not including Vivado here!). 

While solving old exams and the not-so-optional optional homeworks I came across some of the "cache reverse-engineering" tasks. In my opinion, they can be a bit confusing, especially in the beginning, because the search space of cache parameters is quite large and it's not always immediately obvious which configuration one should try at first. Thus, the main purpose of this post is to provide a basic cache simulator where one can try inputting a cache access sequence and get immediate feedback on e.g. the hit rate. I will only give a very brief introduction of how set-associative caches work and of how the cache reverse-engineering tasks are structured.

## Set-associative caches

Set-associative caches are a compromise between direct-mapped and fully associative cache designs. They divide the cache into multiple sets, each containing a fixed number of cache lines or ways (called the associativity). Each cache line within a set can hold a memory block from main memory. The number of ways (i.e. the associativity) in a set is typically a power of two.

When a memory request is made by the processor, the address gets split into three parts: the tag, the index, and the offset. The index bits select the set, the offset bits determine the position within a cache line/block and the tag differentiates blocks that are mapped to the same cache set.

During a lookup the cache controller can perform a parallel search across all ways within the selected set using the index bits. It compares the tag bits of each cache line with the tag bits extracted from the memory address. If a match is found, we have a cache hit.

There are also different strategies determining how cache conflicts are handled. Here we will consider LRU and FIFO:

- LRU: the cache line (in the corresponding set) that hasn't been accessed for the longest time is evicted
- FIFO: the cache line that was first introduced to the set is evicted

The selected cache line is then overwritten with the new data fetched from the main memory.

To illustrate this, consider the following figure from the [Harris and Harris book "Digital Design and Computer Architecture"](http://pages.hmc.edu/harris/ddca/ddca2e.html).

![image](/static/blog/caching/set-associative-cache.png)

The above figure shows a two-way set associative cache of size 8. One clearly sees the four sets, each having two entries (the associativity). Each cache line also has a `V` bit determining whether something is currently stored in the block. When a cache lookup is performed, the two set bits index into the corresponding set while the tag bits are used to compare which of the two cache blocks in the set match (or whether any of them matches at all). Depending on the $Hit_1$ or $Hit_0$ signal we can then use a multiplexer to select the correct cache block from the set (or fetch it from memory if $Hit$ is low).

A good overview of the modular arithmetic involved in set-associative caches can also be found [here](https://chluebi.com/posts/thecacheformula/), but in short the relationship between associativity $A$, cache size $C$, block size $B$ and number of sets $S$ is given by:

$$
S = \frac{C}{A \cdot B}
$$

Since the number of sets $S$ is uniquely determined by $C, A, B$, these are the only variables one can specify in the simulator. To learn more about set-associative caches I recommend reading the Harris & Harris book or watch the [lecture (a very high-bandwidth lecture, that is) here on YouTube](https://www.youtube.com/live/1zXDoDDkICQ?feature=share).

## Reverse engineering the cache configuration

Now for the reverse-engineering part. The basic idea is that given a sequence of accesses one can reverse-engineer the above cache parameters. Let's say you are given the following sequence of cache accesses:

| Access number                    | #0  | #1  | #2  | #3  | #4   | #5  | #6  | #7  |
| -------------------------------- | --- | --- | --- | --- | ---- | --- | --- | --- |
| address                          | 0   | 16  | 24  | 25  | 1024 | 255 | 110 | 305 |
| block number (for block size 16) | 0   | 1   | 1   | 1   | 64   | 15  | 6   | 19  |
| block number (for block size 32) | 0   | 0   | 0   | 0   | 32   | 7   | 3   | 9   |

Also assume that the cache is empty before this access pattern is executed. Let's say we have a hit rate of 2/8 after the sequence is executed. What can we say about e.g. the block size?

Assume our options are $B \in \{16, 32\}$. If $B = 32$, #0 would miss, but #1, #2 and #3 would hit, giving us a hit rate greater than (or equal to) 3/8. Therefore $B = 32$ is not the configuration we are looking for. On the other hand, if $B = 16$, we get exactly two hits (accesses #2 and #3), which is what we're looking for. So we've just determined the cache block size based on the access sequence and the corresponding hit rate above.

The same can also be done for the associativity, (total) cache size and the replacement policy. Since I just wanted to give the basic idea of how properties of a cache can be determined, I won't describe how to do this for other cache configuration properties here.

To learn more about how to determine them, I personally found the [problem solving sessions](https://www.youtube.com/live/mDOFtTfG1GQ?feature=share&t=13264) quite useful. Some useful resources were also shared on the ETH D-INFK Discord server.

## The simulator

Unfortunately, to be entirely sure that a given cache configuration matches the the access pattern and its associated hit rate a lot of probing can be required. This is especially true because different parameters can influence each other. The cache simulator below can be used to play around with different configurations and see whether a given access pattern produces the desired hit rate:

<CacheOutline />

The above cache simulator is quite basic and I didn't thoroughly test its functionality, but hopefully it helps visualizing some of the tasks that were given in the optional homeworks. There's also a nice (comparatively more feature-rich) cache simulator [from the University of Washington](https://courses.cs.washington.edu/courses/cse351/cachesim/) I discovered after writing the above cache simulator.


Home

Recent posts