[blog/seoc] Explained parsing algorithms in more detail and started work on AST

1 files changed, 276 insertions, 42 deletions

diff --git a/src/blog/sane-explanation-of-compilers/index.md b/src/blog/sane-explanation-of-compilers/index.md
index 9fe11af..eb65f9c 100644
--- a/src/blog/sane-explanation-of-compilers/index.md
+++ b/src/blog/sane-explanation-of-compilers/index.md
@@ -25,9 +25,8 @@
 
 
 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.
+The resources and lectors were good, but when studying I found most material online either deals with something on a very surface level or a very deep level.
+Before I've forgotten everything, I'll try to hit that middle spot, generally covering the most important corners of the subject.
 
 *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).
 
@@ -39,12 +38,7 @@ That is why, over time, programmers have tried to abstract sets of instructions
 
 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:
+This job is delegated to a special type of program, called a compiler[^how-did-we-get-here], which is separated into three main layers/components:
 
 1. Front-end: it understands the program, what the code is trying to do
 2. Middle: does optimizations and simplifications
@@ -52,7 +46,7 @@ There are three main layers to a compiler:
 
 ## 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:
+Syntax in current programming languages can be quite sophisticated and ambiguous. For example (taken from [wikipedia](https://en.wikipedia.org/wiki/Most_vexing_parse)) this C++ snippet
 
 ```
 void f(double d) {
@@ -60,13 +54,13 @@ void f(double d) {
 }
 ```
 
-since it could be interpreted either as a:
+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.
+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.
@@ -78,7 +72,7 @@ A word of caution, I'll use a decent amount of fancy names, so I have a way to m
 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.  
+Although learning even the basics merits a whole university course, I'll still try to roughly explain what's important, for those that haven't studyied it.  
 This field works primarily with strings via the help of two (relevant for our purposes) instruments: regular expressions and grammars.
 
 #### Regular expressions
@@ -91,7 +85,7 @@ 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.
+  For example, in `a(cc)ent` the two "c"s 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.
@@ -364,45 +358,273 @@ Furthermore, if our algorithms allow for ambiguity (meaning we can replace a nam
 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:
+##### LL
+
+[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.
+
+So, the way we'll check if an expression matches our grammar, is by starting with the start name and reading the next k character from the input.
+We check the first k character of all expressions, and if anyone of them is a name, we try with substitution for every possibility with that name, essentially peeking into the name's possibilities.
+
+- As an example, the grammar:
+
+  ```grammar
+  F -> a
+  S -> F | (S + F)
+  ```
 
-   ```grammar
-   F -> a
-   S -> F | (S + F)
+  is LL(1).
+  Let's read the input `(a + a)` (the "v" points to the symbol we're looking/peeking at):
+
+   ```
+   I      v
+   Input: (a + a)
+
+   I           v
+   Production: S
    ```
 
-   is LL(1).
-   With the input `(a + a)`:
+  we start with `S`, we peek and get the `(`, in our production we're looking at a name, S.
+  Let's check the first character of every expression of S.
+  In the first expression, the first "character" is `F`, a name, so we look at every expression for F.
+  There is only one, which is "a", different than "(", no dice.
+  Now we check the second expression for S, it's first character is "(", success!
+  We replace:
 
-   - 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
+   ```
+   I      v
+   Input: (a + a)
+   
+   I           v 
+   Production: (S + F)
+   ```
 
-   The grammar
+  Now the first symbol in our production is also `(`, so we incremenet the symbols we're looking/peeking at
 
-   ```grammar
-   B -> b
-   C -> c
-   S -> aaB | aaC
    ```
+   I       v
+   Input: (a + a)
+   
+   I            v 
+   Production: (S + F)
+   ```
+
+  we peek and get the `a`, in our production the second "character" is the name `S`, `S` has to become `a`.
+  We check and the second expression won't do, so we replace with the first
+
+   ```
+   I       v
+   Input: (a + a)
+   
+   I            v
+   Production: (F + F)
+   ```
+
+  We're still peaking at `a`, in the current production we're looking at the name `F`, which can be replaced with `a` (or a string that starts with `a`, we only check the first character of each rule).
+  We replace, then incremenet the symbols, matches the middle characters, when at the second `F` we do the same, replace with `a`, then match `)` and we're done.
+
+  Another LL(1) example can be found in [Karl R. Abrahamson notes](http://www.cs.ecu.edu/karl/5220/spr16/Notes/Top-down/LL1.html).
+
+- 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`.
+
+- Usually parsers that implement this procedure are called [recursive descent parsers](https://en.wikipedia.org/wiki/Recursive_descent_parser)
+
+##### LR
 
-   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`.
+[LR](https://en.wikipedia.org/wiki/LR_parser): bottom-up right-most derivations algorithm.
+Conceptually, LR works in the exact opposite way to LL: for every character in the input, we find a rule that substitutes it (or that substitutes the current collection of names and character) and do so until we've reached the starting name.
 
-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:
+Figuring out an approach isn't as intuitive and easy as with LL, but it still isn't too hard.
+It all boils down to using a whole bunch of conditional statements and tracing where we "came" from.
 
-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.
+- Let's look at the first LL example.
+  We need to track "how the current string looks", because if we read an "a", it could either be from the left handside of the "a + a" or from the right handside.
+  We're going to track where we came from with numbers, which I will define like this:
 
-Unfortunately, these algorithms are way out of my area of knowledge, and furthermore most parsers are custom-tailored for their language.
-If you want to dive deeper, I would suggest:
+  |Number|Current expression ends with|
+  |------|---------------|
+  |0     |Nothing; this is the start|
+  |1     |The name `S`; the final number should be this|
+  |2     |The name `F`|
+  |3     |The character "("|
+  |4     |The character "a"|
+  |5     |"(S"|
+  |6     |"(S + "|
+  |7     |"(S + F"|
+  |8     |"(S + F)"; this is the one before the final|
+
+  You can think of every number as the valid, but "unfinished" state of the current string.
+  It's important to note that this table is the most compact one possible, you could make a table for literally every valid state: "(", "(a", "(F", "(S", ...  
+
+  Keep in mind that the way I'll show the algorithm step by step isn't really correct, but will suffice for the current moment.
+  We'll be working with a string, where reading a character from the input means putting the latest one in the String:
+  
+  ```
+  String : (
+  Number : 0
+  ```
+
+  We're reading "(", so our string "ends" on a "("
+
+  ```
+  String : (a
+  Number : 3
+  ```
+
+  We've read "a", our string "ends" on an "a".
+
+  ```
+  String : (a
+  Number : 4
+  ```
+
+  Here comes the clever bit, for certain numbers, we'll stop reading forward and do something else.
+  If we're on the number 4, our string ends on an "a", so we're going to go backward and replace it with an F, meaning now the number is 2.
+
+  ```
+  String : (F
+  Number : 2
+  ```
+
+  Here is another such rule, if our number is 2, our string ends with an "F" and we replace it with an S, now the number is 5.
+  That's why we have a different number for "(S + F", if we didn't, our number would become 2 and we would make "(S + S", which isn't valid.
+  So, think of 2 as "this is the first F".
+
+  ```
+  String : (S
+  Number : 5
+  ```
+
+  We have a different number for "(S", because if we didn't, we would've gone to number 1, and could've ended the algorithm then and there, without reading the rest of the input.
+  Otherwise, we continue as normal, we read the `+` and the spaces around it, going to number 6.
+
+  ```
+  String : (S + a
+  Number : 6
+  ```
+
+  Now, our string ends with an "a", so we should change our number to 4, but we shouldn't, this would remove our progress so far!
+  Better yet, this number will also be special, if we have a 6 and we end with "a", rather than going to 4, we'll substitute "a" with F now and change number to 7.
+
+  ```
+  String : (S + F
+  Number : 7
+  ```
+
+  And now it's trivial, we read ")", so we go to number 8.
+  But if we're at number 8, don't continue reading, replace with number 1.
+  Now that we're at number 1, if we read any character (including end of string), we'll say the string upto now matches.
+ 
+  It's also helpful to put what we do in different situations in another table:
+
+  |Number|If ends on|Change number to|Also do|
+  |------|----------|----------------|-------|
+  |0     |"("       |3               |       |
+  |1     |          |                |Finished|
+  |2     |          |5               |Replace "F" with "S"|
+  |3     |"a"       |4               |Decrement reading|
+  |4     |          |2               |Replace "a" with "F"|
+  |5     |" + "     |6               |       |
+  |6     |          |7               |Replace "a" with "F"|
+  |7     |")"       |8               |       |
+  |8     |          |1               |Replace "(S + F)" with "S"|
+
+- What you might notice is that
+  
+  1. this "isn't" the smallest amount of number that work, we could remove 2 and in rule 4 directly replace "a" with "S", and
+  2. we're replacing "a" with "F" in two different rules, isn't there a way to do it in only one?
+
+  The reason for both is that the way I showed the algorithm isn't exactly the way it normally works.
+  Rather than tracing the current number in a variable, we trace it with a stack, essentially an array.
+
+  When you read the character and have to go to another number, the number is now added to the array (this operation is called "shift").
+  When we have to change characters from String (without reading anything), with a string (expression) of length j, we remove the last j added numbers and do a normal shift from the last number and character in String (this operation is called "reduce").
+
+- Let's look at the same example, done with shift and reduce operations (without me showing the table):
+  
+  ```
+  String : (
+  Number : [0]
+  ```
+
+  We've read "(", add 3 on top of the stack aka shift(3).
+  Then we read the "a", shift(4).
+
+  ```
+  String : (a
+  Number : [0, 3, 4]
+  ```
+
+  With 4 we'll do a reduction, "a" gets replaced by F, 4 is removed:
+
+  ```
+  String : (F
+  Number : [0, 3]
+  ```
+
+  If last number is 3 and last character is "F", we're doing shift(2).
+
+  ```
+  String : (F
+  Number : [0, 3, 2]
+  ```
+
+  Now, we'll be doing a reduction, where F is replaced by S:
+
+  ```
+  String : (S
+  Number : [0, 3]
+  ```
+
+  If last number is 3 and last character is "S", we're dong shift(5).
+
+  And so on, we continue.
+  As you can see, we go back and forth, from 3 to 4, back to 3, then to 2, back to 3, then to 5.
+  This is how we avoid doing the same thing on different numbers and why the initial amount of numbers is the smallest amount.
+
+- As for the complete table, you can view it on the [Context Free Grammar Checker](https://smlweb.cpsc.ucalgary.ca/lr0.php?grammar=S+-%3E+F+%7C+%28+S+%2B+F+%29.%0AF+-%3E+a.&substs=) by [](TODO), or with a more pretty styling on [Grammophone](https://mdaines.github.io/grammophone/#/), where you input on the left:
+
+  ```
+  S -> F | "(" S "+" F ")".
+  F -> a.
+  ```
+
+  press "Analyze", then click the link "Parsing table" at the bottom, on the row "LR(0)".
+
+  To read the table, remember that:
+
+  - our numbers are formally called states
+  - on every row you have each state
+  - on every column you have each possible value in the string and "$" which signifies the end of the string
+  - with sr or shift (or just with a number) you go to another state
+  - with r or reduce you make the substitution in the current string and go back one state
+  - acc or accept means you've reached the end
+
+##### LR's family
+
+LR is more of a family of algorithms, because what I didn't touch on and is very important was generation of the table.
+This subject is really big can of beans, but generally there are 3 often used types: [CLR](https://en.wikipedia.org/wiki/Canonical_LR_parser), [SLR](https://en.wikipedia.org/wiki/Simple_LR_parser) and [LALR](https://en.wikipedia.org/wiki/LALR_parser).
+
+CLR is an LR parser with 1 character lookahead (LR(1)), following [Knuth](TODO)'s original theory.
+It requires a lot of memory for table generation, so Frank DeRemer created two simplifications, the SLR and LALR, which use singificantly less memory but work with a bit less grammars.
+
+LALR is the most commonly used LR parser, however most compilers are custom-tailored pieces of software that very loosely follow the methods of LL and LR.
+
+##### More info
+
+If you want to learn more, I would highly 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/)
 - [Parsing: Top-down versus bottom-up](http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2014/11/ll.html) by [Jeffrey Kegler](https://jeffreykegler.github.io/personal/)
@@ -414,6 +636,18 @@ If you want to dive deeper, I would suggest:
 #### 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.
+It definetly has to be some sort of structural representation of the overall code, for example, for `1 * 2 + 3` we have to be able to easily find out what the left and right handsides of the `+` and `*` are.
+Drawing out this relationship, where the left line connects to the left handside and the right accordingly:
+
+```
+    +
+   / \
+  *   3
+ / \
+1   2
+```
+
+We notice it looks awfully a lot like a tree!
 
 ## Implementing a front-end