From 89c8c3a395e738f2c55644774c61a7d304093aa0 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Mon, 3 Apr 2023 10:14:55 +0300 Subject: [blog/seoc] Renamed title and finished parsing algorithms section --- .../index.md | 573 -------------------- src/blog/sane-explanation-of-compilers/index.md | 580 +++++++++++++++++++++ 2 files changed, 580 insertions(+), 573 deletions(-) delete mode 100644 src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md create mode 100644 src/blog/sane-explanation-of-compilers/index.md (limited to 'src') diff --git a/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md b/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md deleted file mode 100644 index 9a551eb..0000000 --- a/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md +++ /dev/null @@ -1,573 +0,0 @@ -# Sane explanation of compilers and lex+yacc - -## Contents - -1. [Preface](#preface) -2. [1. How do we understand code?](#1.-how-do-we-understand-code) - 1. [Math](#math) - 1. [Regular expressions](#regular-expressions) - 2. [Grammars](#grammars) - 2. [Lexers and parsers](#lexers-and-parsers) - 1. [Implementational difficulties with grammars](#implementational-difficulties-with-grammars) - 2. [Usage in the real world](#usage-in-the-real-world) - 3. [Parsing algorithms](#parsing-algorithms) - 4. [Abstract syntax tree](#abstract-syntax-tree) -3. [Implementing a front-end](#implementing-a-front-end) - 1. [lex](#lex) - 1. [Example 1](#example-1) - 2. [Example 2](#example-2) - 2. [yacc](#yacc) -4. [2. How can we improve the code?] -5. [3. Virtual machines] -6. [Compilation schemes] - 1. [AOT] - 2. [JIT] - - -Recently I signed up for a small university course about compilers. -The resources and lectors were really good, but when I sat down to study, I struggled finding simple understandable explanations for a lot of basic stuff. -Most material out there deals with specific issues or subparts, but nobody seemed to talk about the overall topic in a concise and simple manner. -Before I've forgotten everything, I'll try doing that. - -*P.S.* The course resources are available on [sofiacpp.github.io/IPL](https://sofiacpp.github.io/IPL/) with the underlying repo being [SofiaCPP/IPL](https://github.com/SofiaCPP/IPL). - -## Preface - -Processors work with numbers, every action (instruction) a processor can do is defined by numbers. -However, writing code only with numbers is tedious, error-prone and requires a lot of manhours for not a lot of functionality. -That is why, over time, programmers have tried to abstract sets of instructions into words and text constructions that are easier to work with. - -Thanks to abstraction, programmers have been able to create more and more complicated projects with less and less work, that is more portable and compatible with different machines. -The tradeoff is that we need to translate our nice programmer code to numbers a CPU would understand. -This job is delegated to a special type of program, called a compiler[^how-did-we-get-here]. - -Though calling a compiler a "program" isn't necessaraly true, you could easily split it into it's main components and run each separately, feeding the output from one program to another. -Since it is more useful, I'll be talking about a compiler in the split sense, where each "layer" (and parts of layers) are separated into seprate programs. - -There are three main layers to a compiler: - -1. Front-end: it understands the program, what the code is trying to do -2. Middle: does optimizations and simplifications -3. Back-end: generates the actual machine instructions - -## 1. How do we understand code? - -Syntax in current programming languages can be quite sophisticated and ambiguous. A weird example (taken from [wikipedia](https://en.wikipedia.org/wiki/Most_vexing_parse)) with C++ would be: - -``` -void f(double d) { - int i(int(d)); -} -``` - -since it could be interpreted either as a: - -1. declaration of variable `i`, which is initialized with the value of `int(d)` (which just casts `d` to an integer), or -2. function declaration, since superfluous parenthesis around function parameter declarations are allowed (meaning it is treated as `int i(int d)`) - -Note that I'm talking about syntax, the valid selection and layouts of characters, and not semantics, the underlying meaning. -Compiled programming languages associate specific templates of code (text) to their corresponding machine instructions, there isn't anything special you need to understand in a piece of code. -In natural languages, you could construct a sentence which follows all gramatical rules, but is absolute nonsence, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously). - -The problem of semtantics is extremely difficult, however in our case we only care about syntax. -And this is where math comes into play. - -### Math - -A word of caution, I'll use a decent amount of fancy names, so I have a way to more easily refer to different concepts. -Don't be scared and skip over them if they're confusing you. - -There is a special field in mathematics that deals with syntactical analysis: [formal language theory](https://en.wikipedia.org/wiki/Formal_language). -Although learning even the basics merits a whole university course, I'll still try to roughly explain what's important. -This field works primarily with strings via the help of two (relevant for our purposes) instruments: regular expressions and grammars. - -#### Regular expressions - -You might've heard or even already used regexes in a text editor. -They're small text expressions which specify a text pattern. -When a word can be "generated" from the pattern, we say the regex matches the word. - -At their very base, such a pattern is created with the following rules: - -- [concatenation](https://en.wikipedia.org/wiki/Concatenation) - you can put characters next to each other to form strings, so a normal string like `accent` is also a regex. - With braces we can group stuff. - For example, in `a(cc)ent` the two cs are grouped together. - This is used to form more sophisticated structures later on, but currently it doesn't alter anything, like the braces in `(1+2)+3` and `1+(2+3)` don't alter the result sum. -- [alternation](https://en.wikipedia.org/wiki/Alternation_%28formal_language_theory%29) - allow different (alternative) strings in the same spot. - We do so with vertical bars (which signify an "or" relationship), the group can be "replaced" with either value. - For example `acce(n | p)t`, matches both "acce**n**t" or "acce**p**t". - There is no limit on how many alternatives you can have and what their lengths are: - - ```regex - acc(ordingly | ent | urate) - ``` - - matches - - + "acc**ordingly**" - + "acc**ent**" and - + "acc**urate**". - - There is no limit on how many groups (with alternation) you can have: - - ```regex - ac(quirem | c | hievem)en(t | ts) - ``` - - matches - - + "ac**quirem**en**t**" - + "ac**quirem**en**ts**" - + "ac**c**en**t** - + "ac**c**en**ts** - + "ac**hievem**en**t**" and - + "ac**hievem**en**ts**". - -- [Kleene star](https://en.wikipedia.org/wiki/Kleene_star) - repeat the preceding letter or group, 0 or more times. - An asterisk is used to mark this operation (hence the name, "Kleen **star**"). - - ```regex - accents* - ``` - will match - - + "accent" - + "accent**s** - + "accent**ss** - + "accent**sss** - + and so on - - Of course, the asterisk could also be in the middle of the regex, like - - ```regex - ac*ent - ``` - - which matches - - + "acent" - + "ac**c**ent" - + "ac**cc**ent" - + ... - - With a group we can repeat entire strings, - - ```regex - acc(ent)*s - ``` - - matches - - + "accs" - + "acc**ent**s" - + "acc**entent**s - + "acc**ententent**s" - + ... - - An alternation allows any alternative to be chosen at any point, so - - ```regex - acce(n | p)*t - ``` - - matches - - + "accet" - + "acce**n**t - + "acce**p**t - + "acce**nn**t - + "acce**np**t" - + "acce**pn**t" - + "acce**pp**t" - + "acce**nnn**t" - + ... - -In the modern day, regular expressions permit [additional constructions](https://en.wikipedia.org/wiki/Regular_expression#Syntax) like matching the start or end of a string, matching character groups or character classes. -There are also sometimes features which significantly increase the matching capabilities of normal regexes, like [lookahead and lookbehind assertions](https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages). - -#### Grammars - -However, even then regular expressions are fairly weak, they can't match recursive structures. -Let's say you want to be able to have math expressions in your language, you can have braces inside braces as much as you like, but in a certain manner: - -- `1+2` is a valid expression -- `(9-8)+2` also is valid -- `((3*3)-(2^3))+2` is too -- however `()3*3)-(2^3()+2` isn't valid - -Such a structure is recursive, because it can contain "itself", `1+2` can be a standalone math expression, but it can also be contained in another expression, like `(1+2)*3`, which itself could be inside another bigger expressions and so on. -For this task we have a whole separate tool: grammars. - -The syntax is different from regexes: a grammar is divided into (production) rules, each rule is named and specifies an expression. -Expressions are a concatenation of strings and/or names[^terminals-and-nonterminals]. -Names won't appear in our matched strings, the idea is that a name will be replaced with it's expression, kind of like a placeholders. -Additionally, there can be multiple rules with the same name, meaning a rule can be replaced by different stuff at any point of the string generation. - -Always one name is chosen to be the starting point, and generation continues from there. -In math literature, generally we write rules in the form `Name -> Expression`[^grammar-syntax], and often names are a single capital letter. -Additionally, often the starting name is called `S`. -Finally, in future examples, I'll use the thick arrow `🡆` to show derivations, how the generated string looks after one or two replacements of the name with one of it's expressions. - -For an example, with the grammar - -```grammar -S -> aSb -S -> cc -``` - -we can generate the string `aaaaccbbbb` (remember, our starting point is `S`): - -```grammar+ -S 🡆 aSb 🡆 aaSbb 🡆 aaaSbbb 🡆 aaaaSbbbb 🡆 aaaaccbbbb -``` - -or `accb`: - -```grammar+ -S 🡆 aSb 🡆 accb -``` - -where a, b and c are just english characters. -To simplify our lives, often rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`). -This is practically alternation but in a different context. - -As for our math expressions, we could create something like this: - -```grammar -N -> 0 | 1 | 2 | ... all possible numbers -E -> N | (E) | E + E | E - E | E * E | E / E | E ^ E -``` - -which will sucessfully be able to match (generate) `((3 * 3) - (2 ^ 3)) + 2`: - -```grammar+ -E 🡆 E + E 🡆 (E) + N 🡆 (E - E) + 2 🡆 ((E) - (E)) + 2 🡆 ((E * E) - (E ^ E)) + 2 🡆 ((N * N) - (N ^ N)) + 2 🡆 ((3 * 3) - (2 ^ 3)) + 2 -``` - -but there are no expressions (rules) that allow `()3+3()` or `)3(-6` to be "matched". - -### Lexers and parsers - -You might've noticed that for `N` I use three dots and the note "all possible numbers" to signify that N can be any positive whole number. -In practice we need formally define that grammar: - -```grammar -N -> 0 | 1 | 2 | ... | 9 | 0N | 1N | 2N | ... | 9N -``` - -With this you might've realised that grammars can do anything a regular expressions can: concatenation and alternation are "built-in", and the Kleene star can be done with another rule in the form `R -> strR | str`[^regular-grammars]. -The reason we use both is that grammars are significantly slower and more complicated in code than regexes. - -#### Implementational difficulties with grammars - -Implementing (very roughly) the regular expression `acce(n | p)*t` is quite easy: - -```cpp -bool matchesp(string str) { - string regex = "acce_t"; - - for (int si = 0, ri = 0; si < str.size() && ri < regex.size(); si++, ri++) { - while (regex[ri] == '_') - if (str[si] == 'n' || str[si] == 'p') - si++; - else - ri++; - } - - if (str[si] != regex[ri]) - return false; - } - return true; -} -``` - -In brief, for concatenated characters we do a simple comparison per character. -When we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex, we do comparisons with the characters n and p as much as we can, after which we continue as normal. - -Of course, this version only supports one regular expressions, however a "proper" implementation would look conceptually similar: a couple of different loops and equality checks, with maybe an additional array or two. -The huge benefit is that that loops and arrays are stupid fast, a (simple) C++ for loop could be translated into [a handful of processor instructions](https://godbolt.org/#g:!%28%28g:!%28%28g:!%28%28h:codeEditor,i:%28filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:%28endColumn:16,endLineNumber:6,positionColumn:16,positionLineNumber:6,selectionStartColumn:16,selectionStartLineNumber:6,startColumn:16,startLineNumber:6%29,source:'//+Type+your+code+here,+or+load+an+example.%0Aint+f%28int+num%29+%7B%0A++++for+%28int+i+%3D+1%3B+i+%3C+100%3B+i%2B%2B%29+%7B%0A++++++++num+*%3D+100%3B%0A++++%7D%0A++++return+num%3B%0A%7D'%29,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29,%28g:!%28%28h:compiler,i:%28compiler:g122,deviceViewOpen:'1',filters:%28b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'%29,flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!%28%29,options:'',selection:%28endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1%29,source:1%29,l:'5',n:'0',o:'+x86-64+gcc+12.2+%28Editor+%231%29',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29%29,l:'2',n:'0',o:'',t:'0'%29%29,version:4). - -On the other hand, usually grammars are more complicated and resource-intensive. -Certain ones are simple enough to implement, like `S -> aSb | cc`: - -```cpp -bool matchesp(string str) { - if (str == "cc") - return true; - else if (str[0] == 'a' && str[str.size() - 1] == 'b') - return matchesp(str.substr(1, str.size() - 2)); - else - return false; -} -``` - -However think about more complicated cases[^context-free-grammars], like `S -> aSbSa | cc`. -Implementing this one is quite a bit more difficult, since we don't know where `b` is located on the first iteration, it could either be the 4th character `accb...a` or the 9th `aaccbccab...a`. -Searching for it is also complicated, it could be the first, the last or any other `b` in the middle of the string. - -Another difficulty with grammars is ambiguity, let's look at - -```grammar -E -> E + E | E * E | n -``` - -how would it generate `n + n * n`? -There are two completely valid ways to do so: - -```grammar+ -E 🡆 E + E 🡆 n + E * E 🡆 n + n * n -``` - -```grammar+ -E 🡆 E * E 🡆 E + E * n 🡆 n + n * n -``` - -How exactly we deal with these problems comes later, for now the takeaway is that we have to try and use regular expressions wherever we can, and leave grammars as a bit of a last resort. - -#### Usage in the real world - -Let's think a bit more about what grammars are supposed to do: they're really good at handling structure, especially recursive structure, so it's best if we use them only for that. -What I'm trying to say is, our math expression grammar (from [here](#grammars)) shouldn't really care if we're trying to sum integers or floats or chars[^static-typing], it's important how everything is layed out and that our operations are done with numbers. - -This is why we're going to separate and generalize the code into [tokens](https://en.wikipedia.org/wiki/Lexical_analysis#Token), basically into building blocks. -As a rough example, we want `1 + (2 * 3)` to be transformed into `NUMBER + (NUMBER * NUMBER)`, `int var = 13;` into `TYPE NAME = NUMBER;` and so on, where "TYPE", "NUMBER" and "NAME" are tokens. -Now we're reducing the amount of "objects" our grammars need to work on: from all characters to many (but significantly fewer) tokens and some really small amount of characters. -Of course, each token will contain it's name (NUMBER, TYPE, ...) and it's value, since we aren't trying to change the code, but our grammars will work with the token names directly and just output the values at the very end. -Usually we identify at least six token types: - -- identifiers: variable and function names for example -- keywords: `if`, `while`, `for`, `return`, ... -- separators: braces, `;` -- operators: `+`, `-`, `<=` -- literals: numbers, strings, characters -- comments - -As you might've noticed, here we can use regular expressions, grouping consequtive characters is what regexes are good for. -Additionally, we're going to be reading the file, a decently slow operation, only once and for a comparatively very little time. - -In the compiler front-end, the part that implementes our regular expressions is called the "lexer", and the part that implements our grammars - the "parser". -In the last section we already talked about how easy implementing regexes (lexers) is and how difficult implementing grammars (parsers) is, but we didn't talk about actual impelementations of parsers. - -#### Parsing algorithms - -Proper algorithms that "implement" grammars are kind of complicated, and most can handle only specific types of grammars. -Generally we categorize them into: - -- [top-down](https://en.wikipedia.org/wiki/Top-down_parsing) algorithms, which work in the way we've been talking about grammars: start with a name and replace it with it's expression, and continue replacements until we have no more names -- [bottom-up](https://en.wikipedia.org/wiki/Bottom-up_parsing) algorithms, where we do the opposite: for each substring we find from which rule it could've come from, replace it with the corresponding name, and continue upwards like that, until we reach the starting name - -Furthermore, if our algorithms allow for ambiguity (meaning we can replace a name with any one of multiple expressions), we divide them into: - -- left-most derivation algirithms, where we choose the left-most valid expression -- right-most derivation algorithms, where we chose the right-most valid expression - -The advantage and disadvantages of every type kind of depend on the exact algorithm and grammar. -Looking at some of the more famous ones: - -1. [LL](https://en.wikipedia.org/wiki/LL_parser): top-down left-most derivations algorithm that can parse only specific types of grammars. - In these grammar, every expression is uniquely identifiable by just looking at the characters (tokens) in the very beginning. - If an LL(k) algorithm can parse the given grammar, we say the grammar is a "LL(k) grammar". - An "LL(k)" grammar, by extension, is any grammar where each expression is uniquely identifiable by just looking at the first k tokens. - As an example, the grammar: - - ```grammar - F -> a - S -> F | (S + F) - ``` - - is LL(1). - With the input `(a + a)`: - - - we start with S, we peek one symbol forward, to the `(`, and we find we need to match with the second expression for S - - after matching the one symbol, we peek at `a`, we find that only the first expression for S works - - and so on - - The grammar - - ```grammar - B -> b - C -> c - S -> aaB | aaC - ``` - - is LL(3). - For the input `aab`, if we look at the first two "a"s, we still don't know which rule to use: `aaB` or `aaC`. - However if we look at the third symbol, "b", then we can determine that we need `aaB`. - -2. [LR](https://en.wikipedia.org/wiki/LR_parser): bottom-up right-most derivations algorithm. - It is slightly reminiscent to LL, parsing only specific grammars and needing to peek forward (lookahead; which also means LR(k) is similarly defined), but is significantly more powerful. - However, the "normal" LR parser requires a lot of memory, which spurred it's variations - the [SLR](https://en.wikipedia.org/wiki/Simple_LR_parser), [CLR](https://en.wikipedia.org/wiki/Canonical_LR_parser) and most importantly: - -3. [LALR](https://en.wikipedia.org/wiki/LALR_parser) - These memory optimizations, however, came at a cost: lower grammar parsing power, though LALR can work with the most grammars out of all the alternatives and still beats LL. - -#### Abstract syntax tree - -We already decided that the lexer will output tokens (and characters) to the parser, but we didn't talk about what the parser is supposed to output. - -## Implementing a front-end - -If you want, you could implement your own lexer and parser manually, but few people do, there are already very well made tools for that. -Furthermore, at the end of the day, we want our compiler to be a singular program, or at least every layer to be a singular program. -[Compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler) are tools that create parsers (and more) from their normal formal definition. - -The two popular ones from the old days are lex and yacc. -lex is a lexer generator and yacc is a LALR parser generator, both of which generate a corresponding C implementation of the given regular expressions and grammars. - -### lex - -Lex is the original program, from 1975, in the modern day it's successor/implementation is the opensource [flex](https://github.com/westes/flex). - -A lex source file is divided into three parts: - -``` -%{ -// C code that will be put in the program verbatim -%} - -/* Definitions */ - -%% - - /* Rules */ - -%% - -// C code -``` - -where `%{%}` is used for includes and declarations, the rules are your regular expressions and the C code is the general logic of the lexer. -Usually you wouldn't write anything in the C code section, the defaults are fine, but you'll probably need to do one or two includes in the `%{%}` section. - -Rules are in the form `regex { C_code }`. -To simplify your life, you can write only the regex or a part of it inside the "definitions" part of the file, and give it a name to use later. -Referencing those names in later regexes is done by surrounding them in curly braces. -Usually the `C_code` in the regex would be a return (more commonly called "emit") of a token, which will be available in a header file, but more on that later. - -#### Example 1 - -Let's look at a very simple example program: every whole number is printed as "NUMBER", while everything else is printed as-is: - -```lex -%{ -%} - -%% - -[0-9]+ { printf("NUMBER"); } -[A-z]+ { printf("%s", yytext); } - -%% -``` - -The syntax `[0-9]` is the same as `(0 | 1 | ... | 9)`, it is available in all modern regexes. -Note that inside every regex's "body" you have an assortment of variables already set, one of them being `yytext` which is just the whole match. -Additionally lex matches the longest possible match, so if we had a rule `[0-z]`, only it will be matched. - -If this file is located in `lexer.l`, we can compile it into a working lexer like this: - -```bash -flex lexer.l && gcc lex.yy.c -lfl -``` - -Of course, you can use your lex implementation or C compiler of choice. -Now, if you run `./a.out` you would get a prompt, every line you write will be lexically analyzed and in our case, everything will be printed out. -Entering - -``` -The number 10 changed to 8, 38, and 19 sequentially, before becoming 0. -``` - -will output - -``` -The number NUMBER changed to NUMBER, NUMBER, and NUMBER sequentially, before becoming NUMBER. -``` - -#### Example 2 - -Now let's try something more sophisticated, let's surround numbers and strings in HTML tags, the stuff that power webpages. -We would want numbers to be in the format: - -``` -number -``` - -and strings: - -``` -string -``` - -We'll define numbers as both whole digits and floating point numbers (with sign) and strings can be surrounded in either single or double quotes. - -```lex -%{ -%} - -/* Only multiline comments are supported, not comments that start with // */ -/* This is a definition, it's in the format "NAME regex" */ -DIGIT [0-9] - -%% - /* Comments in here have to be indented, otherwise you'll get an error */ - /* ? means 0 or 1 of the preceding group*/ - /* + means 1 or more of the preceding group*/ - /* the backward slashes are used because . and + have special meaning in regexes*/ -[\+-]?{DIGIT}+(\.{DIGIT}+)? { printf("%s", yytext); } - - /* [^] is a group of characters, like [], however it specifies "all characters except the ones given"*/ - /* this way if we have "This is a string with " three quotes" it's not going to match the whole thing*/ -\"[^"]*\"|'[^']*' { printf("%s", yytext); } - -%% -``` - -With the input - -``` -John said 10 times "2 + 2 = 5" but '2 + 2 = 4'! -``` - -we'll get - -``` -John said 10 times "2 + 2 = 5" but '2 + 2 = 4'! -``` - -You've probably already noticed that the number inside the strings aren't matched, because the string rule results in a longer match. -In programming languages this is fine, since strings are quite often "self-contained" objects, there isn't anything in them that you would need to match. - -### yacc - -Similarly to lex, yacc originates from 1975, and it's modern replacement is [GNU Bison](https://www.gnu.org/software/bison/). - -A yacc file looks very similar to a lex one: - -```yacc -%{ -// C code that will be put in the program verbatim -%} - -/* Settings */ - -%% - - /* Rules */ - -%% - -// C code -``` - -[^how-did-we-get-here]: Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *all* programming was done with CPU instructions. - -[^terminals-and-nonterminals]: Formally, we call the rule "names" nonterminals, the idea being that all normal characters, that could appear in our string, are called terminals, since they would terminate replacement and string generation. For the purposes of this post, I won't use the formal names, with the hope that using less terminology will increase understandability. - -[^grammar-syntax]: This is pretty much the mathematical notation, often in CS the Backus-Naur form is used, but I find that a bit harder to read. You might also make the argument that I should use a proper unicode arrow symbol, like `→`, but `->` is way more convinient. - -[^regular-grammars]: Such grammars are called [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar), more formally, every rule has to contain at most one name and that name must be at the start or end of the string characters. - -[^context-free-grammars]: Be careful about cases that are too complicated, the grammar I'm showing is "context-free", but that topic is way beyond the scope of this post. - -[^static-typing]: Yeah yeah, in a statically typed language you might not be able to do operations on doubles and integers at the same time, but you get the point. diff --git a/src/blog/sane-explanation-of-compilers/index.md b/src/blog/sane-explanation-of-compilers/index.md new file mode 100644 index 0000000..bfd4eeb --- /dev/null +++ b/src/blog/sane-explanation-of-compilers/index.md @@ -0,0 +1,580 @@ +# Sane explanation of compilers + +## Contents + +1. [Preface](#preface) +2. [1. How do we understand code?](#1.-how-do-we-understand-code) + 1. [Math](#math) + 1. [Regular expressions](#regular-expressions) + 2. [Grammars](#grammars) + 2. [Lexers and parsers](#lexers-and-parsers) + 1. [Implementational difficulties with grammars](#implementational-difficulties-with-grammars) + 2. [Usage in the real world](#usage-in-the-real-world) + 3. [Parsing algorithms](#parsing-algorithms) + 4. [Abstract syntax tree](#abstract-syntax-tree) +3. [Implementing a front-end](#implementing-a-front-end) + 1. [lex](#lex) + 1. [Example 1](#example-1) + 2. [Example 2](#example-2) + 2. [yacc](#yacc) +4. [2. How can we improve the code?] +5. [3. Virtual machines] +6. [Compilation schemes] + 1. [AOT] + 2. [JIT] + + +Recently I signed up for a small university course about compilers. +The resources and lectors were really good, but when I sat down to study, I struggled finding simple understandable explanations for a lot of basic stuff. +Most material out there deals with specific issues or subparts, but nobody seemed to talk about the overall topic in a concise and simple manner. +Before I've forgotten everything, I'll try doing that. + +*P.S.* The course resources are available on [sofiacpp.github.io/IPL](https://sofiacpp.github.io/IPL/) with the underlying repo being [SofiaCPP/IPL](https://github.com/SofiaCPP/IPL). + +## Preface + +Processors work with numbers, every action (instruction) a processor can do is defined by numbers. +However, writing code only with numbers is tedious, error-prone and requires a lot of manhours for not a lot of functionality. +That is why, over time, programmers have tried to abstract sets of instructions into words and text constructions that are easier to work with. + +Thanks to abstraction, programmers have been able to create more and more complicated projects with less and less work, that is more portable and compatible with different machines. +The tradeoff is that we need to translate our nice programmer code to numbers a CPU would understand. +This job is delegated to a special type of program, called a compiler[^how-did-we-get-here]. + +Though calling a compiler a "program" isn't necessaraly true, you could easily split it into it's main components and run each separately, feeding the output from one program to another. +Since it is more useful, I'll be talking about a compiler in the split sense, where each "layer" (and parts of layers) are separated into seprate programs. + +There are three main layers to a compiler: + +1. Front-end: it understands the program, what the code is trying to do +2. Middle: does optimizations and simplifications +3. Back-end: generates the actual machine instructions + +## 1. How do we understand code? + +Syntax in current programming languages can be quite sophisticated and ambiguous. A weird example (taken from [wikipedia](https://en.wikipedia.org/wiki/Most_vexing_parse)) with C++ would be: + +``` +void f(double d) { + int i(int(d)); +} +``` + +since it could be interpreted either as a: + +1. declaration of variable `i`, which is initialized with the value of `int(d)` (which just casts `d` to an integer), or +2. function declaration, since superfluous parenthesis around function parameter declarations are allowed (meaning it is treated as `int i(int d)`) + +Note that I'm talking about syntax, the valid selection and layouts of characters, and not semantics, the underlying meaning. +Compiled programming languages associate specific templates of code (text) to their corresponding machine instructions, there isn't anything special you need to understand in a piece of code. +In natural languages, you could construct a sentence which follows all gramatical rules, but is absolute nonsence, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously). + +The problem of semtantics is extremely difficult, however in our case we only care about syntax. +And this is where math comes into play. + +### Math + +A word of caution, I'll use a decent amount of fancy names, so I have a way to more easily refer to different concepts. +Don't be scared and skip over them if they're confusing you. + +There is a special field in mathematics that deals with syntactical analysis: [formal language theory](https://en.wikipedia.org/wiki/Formal_language). +Although learning even the basics merits a whole university course, I'll still try to roughly explain what's important. +This field works primarily with strings via the help of two (relevant for our purposes) instruments: regular expressions and grammars. + +#### Regular expressions + +You might've heard or even already used regexes in a text editor. +They're small text expressions which specify a text pattern. +When a word can be "generated" from the pattern, we say the regex matches the word. + +At their very base, such a pattern is created with the following rules: + +- [concatenation](https://en.wikipedia.org/wiki/Concatenation) - you can put characters next to each other to form strings, so a normal string like `accent` is also a regex. + With braces we can group stuff. + For example, in `a(cc)ent` the two cs are grouped together. + This is used to form more sophisticated structures later on, but currently it doesn't alter anything, like the braces in `(1+2)+3` and `1+(2+3)` don't alter the result sum. +- [alternation](https://en.wikipedia.org/wiki/Alternation_%28formal_language_theory%29) - allow different (alternative) strings in the same spot. + We do so with vertical bars (which signify an "or" relationship), the group can be "replaced" with either value. + For example `acce(n | p)t`, matches both "acce**n**t" or "acce**p**t". + There is no limit on how many alternatives you can have and what their lengths are: + + ```regex + acc(ordingly | ent | urate) + ``` + + matches + + + "acc**ordingly**" + + "acc**ent**" and + + "acc**urate**". + + There is no limit on how many groups (with alternation) you can have: + + ```regex + ac(quirem | c | hievem)en(t | ts) + ``` + + matches + + + "ac**quirem**en**t**" + + "ac**quirem**en**ts**" + + "ac**c**en**t** + + "ac**c**en**ts** + + "ac**hievem**en**t**" and + + "ac**hievem**en**ts**". + +- [Kleene star](https://en.wikipedia.org/wiki/Kleene_star) - repeat the preceding letter or group, 0 or more times. + An asterisk is used to mark this operation (hence the name, "Kleen **star**"). + + ```regex + accents* + ``` + will match + + + "accent" + + "accent**s** + + "accent**ss** + + "accent**sss** + + and so on + + Of course, the asterisk could also be in the middle of the regex, like + + ```regex + ac*ent + ``` + + which matches + + + "acent" + + "ac**c**ent" + + "ac**cc**ent" + + ... + + With a group we can repeat entire strings, + + ```regex + acc(ent)*s + ``` + + matches + + + "accs" + + "acc**ent**s" + + "acc**entent**s + + "acc**ententent**s" + + ... + + An alternation allows any alternative to be chosen at any point, so + + ```regex + acce(n | p)*t + ``` + + matches + + + "accet" + + "acce**n**t + + "acce**p**t + + "acce**nn**t + + "acce**np**t" + + "acce**pn**t" + + "acce**pp**t" + + "acce**nnn**t" + + ... + +In the modern day, regular expressions permit [additional constructions](https://en.wikipedia.org/wiki/Regular_expression#Syntax) like matching the start or end of a string, matching character groups or character classes. +There are also sometimes features which significantly increase the matching capabilities of normal regexes, like [lookahead and lookbehind assertions](https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages). + +#### Grammars + +However, even then regular expressions are fairly weak, they can't match recursive structures. +Let's say you want to be able to have math expressions in your language, you can have braces inside braces as much as you like, but in a certain manner: + +- `1+2` is a valid expression +- `(9-8)+2` also is valid +- `((3*3)-(2^3))+2` is too +- however `()3*3)-(2^3()+2` isn't valid + +Such a structure is recursive, because it can contain "itself", `1+2` can be a standalone math expression, but it can also be contained in another expression, like `(1+2)*3`, which itself could be inside another bigger expressions and so on. +For this task we have a whole separate tool: grammars. + +The syntax is different from regexes: a grammar is divided into (production) rules, each rule is named and specifies an expression. +Expressions are a concatenation of strings and/or names[^terminals-and-nonterminals]. +Names won't appear in our matched strings, the idea is that a name will be replaced with it's expression, kind of like a placeholders. +Additionally, there can be multiple rules with the same name, meaning a rule can be replaced by different stuff at any point of the string generation. + +Always one name is chosen to be the starting point, and generation continues from there. +In math literature, generally we write rules in the form `Name -> Expression`[^grammar-syntax], and often names are a single capital letter. +Additionally, often the starting name is called `S`. +Finally, in future examples, I'll use the thick arrow `🡆` to show derivations, how the generated string looks after one or two replacements of the name with one of it's expressions. + +For an example, with the grammar + +```grammar +S -> aSb +S -> cc +``` + +we can generate the string `aaaaccbbbb` (remember, our starting point is `S`): + +```grammar+ +S 🡆 aSb 🡆 aaSbb 🡆 aaaSbbb 🡆 aaaaSbbbb 🡆 aaaaccbbbb +``` + +or `accb`: + +```grammar+ +S 🡆 aSb 🡆 accb +``` + +where a, b and c are just english characters. +To simplify our lives, often rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`). +This is practically alternation but in a different context. + +As for our math expressions, we could create something like this: + +```grammar +N -> 0 | 1 | 2 | ... all possible numbers +E -> N | (E) | E + E | E - E | E * E | E / E | E ^ E +``` + +which will sucessfully be able to match (generate) `((3 * 3) - (2 ^ 3)) + 2`: + +```grammar+ +E 🡆 E + E 🡆 (E) + N 🡆 (E - E) + 2 🡆 ((E) - (E)) + 2 🡆 ((E * E) - (E ^ E)) + 2 🡆 ((N * N) - (N ^ N)) + 2 🡆 ((3 * 3) - (2 ^ 3)) + 2 +``` + +but there are no expressions (rules) that allow `()3+3()` or `)3(-6` to be "matched". + +### Lexers and parsers + +You might've noticed that for `N` I use three dots and the note "all possible numbers" to signify that N can be any positive whole number. +In practice we need formally define that grammar: + +```grammar +N -> 0 | 1 | 2 | ... | 9 | 0N | 1N | 2N | ... | 9N +``` + +With this you might've realised that grammars can do anything a regular expressions can: concatenation and alternation are "built-in", and the Kleene star can be done with another rule in the form `R -> strR | str`[^regular-grammars]. +The reason we use both is that grammars are significantly slower and more complicated in code than regexes. + +#### Implementational difficulties with grammars + +Implementing (very roughly) the regular expression `acce(n | p)*t` is quite easy: + +```cpp +bool matchesp(string str) { + string regex = "acce_t"; + + for (int si = 0, ri = 0; si < str.size() && ri < regex.size(); si++, ri++) { + while (regex[ri] == '_') + if (str[si] == 'n' || str[si] == 'p') + si++; + else + ri++; + } + + if (str[si] != regex[ri]) + return false; + } + return true; +} +``` + +In brief, for concatenated characters we do a simple comparison per character. +When we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex, we do comparisons with the characters n and p as much as we can, after which we continue as normal. + +Of course, this version only supports one regular expressions, however a "proper" implementation would look conceptually similar: a couple of different loops and equality checks, with maybe an additional array or two. +The huge benefit is that that loops and arrays are stupid fast, a (simple) C++ for loop could be translated into [a handful of processor instructions](https://godbolt.org/#g:!%28%28g:!%28%28g:!%28%28h:codeEditor,i:%28filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:%28endColumn:16,endLineNumber:6,positionColumn:16,positionLineNumber:6,selectionStartColumn:16,selectionStartLineNumber:6,startColumn:16,startLineNumber:6%29,source:'//+Type+your+code+here,+or+load+an+example.%0Aint+f%28int+num%29+%7B%0A++++for+%28int+i+%3D+1%3B+i+%3C+100%3B+i%2B%2B%29+%7B%0A++++++++num+*%3D+100%3B%0A++++%7D%0A++++return+num%3B%0A%7D'%29,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29,%28g:!%28%28h:compiler,i:%28compiler:g122,deviceViewOpen:'1',filters:%28b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'%29,flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!%28%29,options:'',selection:%28endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1%29,source:1%29,l:'5',n:'0',o:'+x86-64+gcc+12.2+%28Editor+%231%29',t:'0'%29%29,k:50,l:'4',n:'0',o:'',s:0,t:'0'%29%29,l:'2',n:'0',o:'',t:'0'%29%29,version:4). + +On the other hand, usually grammars are more complicated and resource-intensive. +Certain ones are simple enough to implement, like `S -> aSb | cc`: + +```cpp +bool matchesp(string str) { + if (str == "cc") + return true; + else if (str[0] == 'a' && str[str.size() - 1] == 'b') + return matchesp(str.substr(1, str.size() - 2)); + else + return false; +} +``` + +However think about more complicated cases[^context-free-grammars], like `S -> aSbSa | cc`. +Implementing this one is quite a bit more difficult, since we don't know where `b` is located on the first iteration, it could either be the 4th character `accb...a` or the 9th `aaccbccab...a`. +Searching for it is also complicated, it could be the first, the last or any other `b` in the middle of the string. + +Another difficulty with grammars is ambiguity, let's look at + +```grammar +E -> E + E | E * E | n +``` + +how would it generate `n + n * n`? +There are two completely valid ways to do so: + +```grammar+ +E 🡆 E + E 🡆 n + E * E 🡆 n + n * n +``` + +```grammar+ +E 🡆 E * E 🡆 E + E * n 🡆 n + n * n +``` + +How exactly we deal with these problems comes later, for now the takeaway is that we have to try and use regular expressions wherever we can, and leave grammars as a bit of a last resort. + +#### Usage in the real world + +Let's think a bit more about what grammars are supposed to do: they're really good at handling structure, especially recursive structure, so it's best if we use them only for that. +What I'm trying to say is, our math expression grammar (from [here](#grammars)) shouldn't really care if we're trying to sum integers or floats or chars[^static-typing], it's important how everything is layed out and that our operations are done with numbers. + +This is why we're going to separate and generalize the code into [tokens](https://en.wikipedia.org/wiki/Lexical_analysis#Token), basically into building blocks. +As a rough example, we want `1 + (2 * 3)` to be transformed into `NUMBER + (NUMBER * NUMBER)`, `int var = 13;` into `TYPE NAME = NUMBER;` and so on, where "TYPE", "NUMBER" and "NAME" are tokens. +Now we're reducing the amount of "objects" our grammars need to work on: from all characters to many (but significantly fewer) tokens and some really small amount of characters. +Of course, each token will contain it's name (NUMBER, TYPE, ...) and it's value, since we aren't trying to change the code, but our grammars will work with the token names directly and just output the values at the very end. +Usually we identify at least six token types: + +- identifiers: variable and function names for example +- keywords: `if`, `while`, `for`, `return`, ... +- separators: braces, `;` +- operators: `+`, `-`, `<=` +- literals: numbers, strings, characters +- comments + +As you might've noticed, here we can use regular expressions, grouping consequtive characters is what regexes are good for. +Additionally, we're going to be reading the file, a decently slow operation, only once and for a comparatively very little time. + +In the compiler front-end, the part that implementes our regular expressions is called the "lexer", and the part that implements our grammars - the "parser". +In the last section we already talked about how easy implementing regexes (lexers) is and how difficult implementing grammars (parsers) is, but we didn't talk about actual impelementations of parsers. + +#### Parsing algorithms + +Proper algorithms that "implement" grammars are kind of complicated, and most can handle only specific types of grammars. +Generally we categorize them into: + +- [top-down](https://en.wikipedia.org/wiki/Top-down_parsing) algorithms, which work in the way we've been talking about grammars: start with a name and replace it with it's expression, and continue replacements until we have no more names +- [bottom-up](https://en.wikipedia.org/wiki/Bottom-up_parsing) algorithms, where we do the opposite: for each substring we find from which rule it could've come from, replace it with the corresponding name, and continue upwards like that, until we reach the starting name + +Furthermore, if our algorithms allow for ambiguity (meaning we can replace a name with any one of multiple expressions), we divide them into: + +- left-most derivation algirithms, where we choose the left-most valid expression +- right-most derivation algorithms, where we chose the right-most valid expression + +The advantage and disadvantages of every type kind of depend on the exact algorithm and grammar. +Looking at some of the more famous ones: + +1. [LL](https://en.wikipedia.org/wiki/LL_parser): top-down left-most derivations algorithm that can parse only specific types of grammars. + In these grammars, every expression is uniquely identifiable by just looking at the characters (tokens) in the very beginning. + The amount of token we need to look for is very important, so we usually define LL(k) as an LL grammar that needs to look at k amount of tokens. + An "LL(k) grammar" is, by extension, a grammar which can be parsed with an LL(k) parser. + As an example, the grammar: + + ```grammar + F -> a + S -> F | (S + F) + ``` + + is LL(1). + With the input `(a + a)`: + + - we start with S, we peek one symbol forward, to the `(`, and we find we need to match with the second expression for S + - after matching the one symbol, we peek at `a`, we find that only the first expression for S works + - and so on + + The grammar + + ```grammar + B -> b + C -> c + S -> aaB | aaC + ``` + + is LL(3). + For the input `aab`, if we look at the first two "a"s, we still don't know which rule to use: `aaB` or `aaC`. + However if we look at the third symbol, "b", then we can determine that we need `aaB`. + +2. [LR](https://en.wikipedia.org/wiki/LR_parser): bottom-up right-most derivations algorithm. + Also parses only specific grammars and needs to peek forward (lookahead; which also means LR(k) is similarly defined), but is significantly more powerful. + However, the "normal" LR parser requires a lot of memory, which spurred it's variations - the [SLR](https://en.wikipedia.org/wiki/Simple_LR_parser), [CLR](https://en.wikipedia.org/wiki/Canonical_LR_parser) and most importantly: + +3. [LALR](https://en.wikipedia.org/wiki/LALR_parser). + These memory optimizations, however, came at a cost: lower grammar parsing power, though LALR can work with the most grammars out of all the alternatives and still beats LL. + +Unfortunately, these algorithms are way out of my area of knowledge, and furthermore a lot of parsers are custom-tailored for their language. +If you want to dive deeper, I would suggest: + +- [LL and LR Parsing Demystified](https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html) and [LL and LR in Context: Why Parsing Tools Are Hard](https://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html) by [Josh Haberman](https://blog.reverberate.org/about/) +- [Which Parsing Approach?](https://tratt.net/laurie/blog/2020/which_parsing_approach.html) by [Laurence Tratt](https://tratt.net/laurie/) +- [A Guide to Parsing: Algorithms and Terminology](https://tomassetti.me/guide-parsing-algorithms-terminology/) by [Gabriele Tomassetti](https://inre.me/) + +#### Abstract syntax tree + +We already decided that the lexer will output tokens (and characters) to the parser, but we didn't talk about what the parser is supposed to output. + +## Implementing a front-end + +If you want, you could implement your own lexer and parser manually, but few people do, there are already very well made tools for that. +Furthermore, at the end of the day, we want our compiler to be a singular program, or at least every layer to be a singular program. +[Compiler-compilers](https://en.wikipedia.org/wiki/Compiler-compiler) are tools that create parsers (and more) from their normal formal definition. + +The two popular ones from the old days are lex and yacc. +lex is a lexer generator and yacc is a LALR parser generator, both of which generate a corresponding C implementation of the given regular expressions and grammars. + +### lex + +Lex is the original program, from 1975, in the modern day it's successor/implementation is the opensource [flex](https://github.com/westes/flex). + +A lex source file is divided into three parts: + +``` +%{ +// C code that will be put in the program verbatim +%} + +/* Definitions */ + +%% + + /* Rules */ + +%% + +// C code +``` + +where `%{%}` is used for includes and declarations, the rules are your regular expressions and the C code is the general logic of the lexer. +Usually you wouldn't write anything in the C code section, the defaults are fine, but you'll probably need to do one or two includes in the `%{%}` section. + +Rules are in the form `regex { C_code }`. +To simplify your life, you can write only the regex or a part of it inside the "definitions" part of the file, and give it a name to use later. +Referencing those names in later regexes is done by surrounding them in curly braces. +Usually the `C_code` in the regex would be a return (more commonly called "emit") of a token, which will be available in a header file, but more on that later. + +#### Example 1 + +Let's look at a very simple example program: every whole number is printed as "NUMBER", while everything else is printed as-is: + +```lex +%{ +%} + +%% + +[0-9]+ { printf("NUMBER"); } +[A-z]+ { printf("%s", yytext); } + +%% +``` + +The syntax `[0-9]` is the same as `(0 | 1 | ... | 9)`, it is available in all modern regexes. +Note that inside every regex's "body" you have an assortment of variables already set, one of them being `yytext` which is just the whole match. +Additionally lex matches the longest possible match, so if we had a rule `[0-z]`, only it will be matched. + +If this file is located in `lexer.l`, we can compile it into a working lexer like this: + +```bash +flex lexer.l && gcc lex.yy.c -lfl +``` + +Of course, you can use your lex implementation or C compiler of choice. +Now, if you run `./a.out` you would get a prompt, every line you write will be lexically analyzed and in our case, everything will be printed out. +Entering + +``` +The number 10 changed to 8, 38, and 19 sequentially, before becoming 0. +``` + +will output + +``` +The number NUMBER changed to NUMBER, NUMBER, and NUMBER sequentially, before becoming NUMBER. +``` + +#### Example 2 + +Now let's try something more sophisticated, let's surround numbers and strings in HTML tags, the stuff that power webpages. +We would want numbers to be in the format: + +``` +number +``` + +and strings: + +``` +string +``` + +We'll define numbers as both whole digits and floating point numbers (with sign) and strings can be surrounded in either single or double quotes. + +```lex +%{ +%} + +/* Only multiline comments are supported, not comments that start with // */ +/* This is a definition, it's in the format "NAME regex" */ +DIGIT [0-9] + +%% + /* Comments in here have to be indented, otherwise you'll get an error */ + /* ? means 0 or 1 of the preceding group*/ + /* + means 1 or more of the preceding group*/ + /* the backward slashes are used because . and + have special meaning in regexes*/ +[\+-]?{DIGIT}+(\.{DIGIT}+)? { printf("%s", yytext); } + + /* [^] is a group of characters, like [], however it specifies "all characters except the ones given"*/ + /* this way if we have "This is a string with " three quotes" it's not going to match the whole thing*/ +\"[^"]*\"|'[^']*' { printf("%s", yytext); } + +%% +``` + +With the input + +``` +John said 10 times "2 + 2 = 5" but '2 + 2 = 4'! +``` + +we'll get + +``` +John said 10 times "2 + 2 = 5" but '2 + 2 = 4'! +``` + +You've probably already noticed that the number inside the strings aren't matched, because the string rule results in a longer match. +In programming languages this is fine, since strings are quite often "self-contained" objects, there isn't anything in them that you would need to match. + +### yacc + +Similarly to lex, yacc originates from 1975, and it's modern replacement is [GNU Bison](https://www.gnu.org/software/bison/). + +A yacc file looks very similar to a lex one: + +```yacc +%{ +// C code that will be put in the program verbatim +%} + +/* Settings */ + +%% + + /* Rules */ + +%% + +// C code +``` + +[^how-did-we-get-here]: Though it's obvious, I would like to point out that modern compilers are most often written in languages that are themselves compiled. You might ask yourself "where did the first compiler come from?" The answer is simple: it was written with "numbers", with direct instructions to the processor, from the time when computers were simple enough that *all* programming was done with CPU instructions. + +[^terminals-and-nonterminals]: Formally, we call the rule "names" nonterminals, the idea being that all normal characters, that could appear in our string, are called terminals, since they would terminate replacement and string generation. For the purposes of this post, I won't use the formal names, with the hope that using less terminology will increase understandability. + +[^grammar-syntax]: This is pretty much the mathematical notation, often in CS the Backus-Naur form is used, but I find that a bit harder to read. You might also make the argument that I should use a proper unicode arrow symbol, like `→`, but `->` is way more convinient. + +[^regular-grammars]: Such grammars are called [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar), more formally, every rule has to contain at most one name and that name must be at the start or end of the string characters. + +[^context-free-grammars]: Be careful about cases that are too complicated, the grammar I'm showing is "context-free", but that topic is way beyond the scope of this post. + +[^static-typing]: Yeah yeah, in a statically typed language you might not be able to do operations on doubles and integers at the same time, but you get the point. -- cgit v1.3.1-26-gb76a