[blog/seoc] Created initial structure and added most of the first two sections

1 files changed, 376 insertions, 0 deletions

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
new file mode 100644
index 0000000..816e59f
--- /dev/null
+++ b/src/blog/sane-explanation-of-compilers-and-lex-yacc/index.md
@@ -0,0 +1,376 @@
+# 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. [Regex](#regex)
+      2. [Grammars](#grammars)
+   2. [Using regular expressions and grammars in the real world](#using-regular-expressions-and-grammars-in-the-real-world)
+      1. [Practical problems with grammars](#practical-problems-with-grammars)
+      2. [A middle ground](#a-middle-ground)
+      3. [How do we use them for compiling code](#how-do-we-use-them-for-compiling-code)
+   3. [Lexers and parsers](#lexers-and-parsers)
+      1. [lex](#lex)
+      2. [yacc](#yacc)
+3. [2. How can we improve the code?]
+4. [3. How do you generate machine instructions?]
+   2. [Virtual machines]
+5. [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?
+
+The simplest programming languages would just assign names to different processor instructions, so writing "Store\_value\_from\_A\_into\_B" is actually instruction number 47, however this abstraction isn't high enough.
+
+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, not semantics.
+Compiled programming languages are meant to associate specific templates of code to their corresponding machine instructions, there is no underlying meaning to code.
+In natural languages, you could construct a sentence which follows all gramatical rules, but is absolute nonsence, devoid of any meaning, like ["Colorless green ideas sleep furiously"](https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously).
+The problem of semtantics, logical sense, is extremely difficult and isn't really "solved", however analyzing syntax is.
+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.
+
+#### Regex
+
+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.  
+  Considering the name, this is specified with an asterisk, `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.
+That is where grammars come into play, they allow us to define a structure which can "contain" itself.
+
+The syntax is different from regexes: a grammar is divided into rules, each rule is named and specifies an expression.
+Expressions are a concatenation of strings and/or names.
+Names aren't strings that will appear in our matched strings, the idea is that a name will be replaced with it's expression, they're a bit like 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.
+Generally we write rules in the form `Name -> Expression`.
+
+For an example, with the grammar
+
+```grammar
+S -> aSb
+S -> cc
+```
+
+we can generate the string `aaaaccbbbb` (`🡆` shows every step, where a name is replaced):
+
+```grammar+
+S 🡆 aSb 🡆 aaSbb 🡆 aaaSbbb 🡆 aaaaSbbbb 🡆 aaaaccbbbb
+```
+
+or `accb`:
+
+```grammar+
+S 🡆 aSb 🡆 accb
+```
+
+where a and b are just characters.
+To simplify our lives, usually rules with the same name are merged into one rule, separated by vertical bars (`S -> aSb | cc`), this is pretty much 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 (and rules) that allow `()3+3()` or `)3(-6` to be "matched".
+
+### Using regular expressions and grammars in the real world
+
+You might've noticed that for `N` we use three dots and the note "all possible numbers" to signify that N can be any positive whole number.
+If we want to be more precise, we really should formally define the 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 a lot harder to implement, harder to work with and slower than regexes.
+
+#### Practical problems 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, we loop over the given string and the regex at the same time, checking if character values match on every index.
+That is until we reach "\_", which I use to specify we're in the `(n | p)*` part of the regex.
+Here, we loop until we've matched all "n"s and "p"s, after which we skip over this part and continue checking for equal characters.
+
+Even a programming novice could implement something like this, and it's pretty quick, simple, doesn't use a lot of resources.
+Certain grammars have the same qualities too, `S -> aSb | cc` can be implemented with a very simple recursion:
+
+```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;
+}
+```
+
+The only caveat here could be making sure the code is a tail recursion, as to not cause any stack overflow problems.
+
+However lets discuss the grammar `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 🡆 E + E * E 🡆 n + n * n
+```
+
+```grammar+
+E 🡆 E * E 🡆 E + E * E 🡆 n + n * n
+```
+
+#### A middle ground
+
+#### How do we use them for compiling code
+
+
+#### Abstract syntax tree
+
+I briefly mentionted that grammers require more resources than regexes, why is that?
+Well, 
+
+### Lexers and parsers
+
+Now that we're armed with all of that math, we'll get to coding.
+The program/part of a compiler front-end that handles the regular expresions is called a lexer, and the one that handles grammars - parser.
+The job of the lexer is to split our code into strings the specify what it is (a string, a number, a type name, a function name, ...; those are called tokens) and then the grammar will use those strings in it's rules.
+
+So, our pipeline looks something like:
+
+```
+code -> LEXER -> tokens -> PARSER -> abstract syntax tree
+```
+
+#### lex
+
+How do we handle regular expressions?
+The manual way is with a loop, we're going over the code and the regex at the same time.
+We read both character by character, comparing them, but when we hit something special in the regex (`(,),*,|`), we handle it.
+For example if we hit an opening brace, rather than compare it to the current character, we would read the regex forward until the closing brace, finding what our next possible character (string) could be, then comparing every option with the current character.
+
+However nobody does that, and you shouldn't too.
+There is already a widely used tool called [lex](https://en.wikipedia.org/wiki/Lex_%28software%29), although usually [flex](https://en.wikipedia.org/wiki/Flex_%28lexical_analyser_generator%29) is used as an open-source alternative.
+
+A flex file is compiled into a C program, meaning if you want to change a regex you'll have to recompile.
+It 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 grammars and the C code is the general logic of the lexer.
+Usually you wouldn't write anything in the C code section, and do one or two includes in the `%{%}` section.
+
+Rules are in the form `regex { C_code }`.
+To simplify your life, you can write a regex or a part of a regex inside the definitions part of the file, and give it a name to use later (you'll need to surround them in curly braces when wanting to reference them).
+Usually the `C_code` in the regex would be a return for a token (more on that in yacc), which will be available in a header file, that you'll need to have included in the flex file.
+
+#### yacc
+
+[^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.
+
+[^empty-string-isnt-a-number]: The Kleene star specifies that something can be repeated **0** or more times, so in the case of this regex, the empty string "" will also be a number. In math, usually a plus as a supscript is defined, so 5* means 0 or more 5s, while 5^+ is 1 or more 5s. In regexes we just put a + next to the repeated string.