[blog/seoc] Finished yacc section

1 files changed, 141 insertions, 6 deletions

diff --git a/src/blog/sane-explanation-of-compilers/part-1.md b/src/blog/sane-explanation-of-compilers/part-1.md
index 3fa79c8..712bebe 100644
--- a/src/blog/sane-explanation-of-compilers/part-1.md
+++ b/src/blog/sane-explanation-of-compilers/part-1.md
@@ -850,20 +850,20 @@ John said <span class="num">10</span> times <span class="str">"2 + 2 = 5"</span>
 ```
 
 You've probably already noticed that the number inside the strings aren't matched, because the string rule results in a longer match.
-In certain programming languages, that don't have [string interpolation](https://en.wikipedia.org/wiki/String_interpolation) this is fine, but for the others our regexes have to be a lot more complicated.
+In certain programming languages, that don't have [string interpolation](https://en.wikipedia.org/wiki/String_interpolation) this is fine, but for others our regexes have to be a lot more complicated.
 
 #### 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:
+A yacc file looks very similarly to a lex one:
 
 ```yacc
 %{
 // C code that will be put in the program verbatim
 %}
 
-/* Settings */
+/* Declarations */
 
 %%
 
@@ -874,12 +874,145 @@ A yacc file looks very similar to a lex one:
 // C code
 ```
 
-however rather than definitions you have settings, and the rules are in a completely different format (because they're grammars).
+however rather than definitions you have declarations, and the rules are in a completely different format (because they're grammars).
+
+Token names are defined in `declarations`, in the format
+
+```yacc
+%token NAME1 NAME2 ...
+```
+
+You can also define precedence with `%left` and `%right`.
+There are also other options you can set, like the start name with `%start`.
+
+Grammars are in the form
+
+```yacc
+name : TOKEN1 TOKEN2 ...
+     ;
+```
+
+where alternation is defined like
+
+```yacc
+name : TOKEN1
+     | TOKEN2
+     | TOKEN3
+     ;
+```
+
+and it always must end with a `;`.
+On each alternation, you can (should) specify a body, which will contain C code to be executed, if this rule is reached
+
+```yacc
+name : TOKEN1 { C code here }
+     | TOKEN2
+     | TOKEN3 { C code here }
+     ;
+```
+
+Another difference is that, since the parser needs a list of tokens, you cannot run it by itself, you'll also need to setup a lexer.
+
+Let's implement a parser for the grammar[^shift-reduce-conflicts]:
+
+```grammar
+N -> 1 | 2 | 3
+S -> N | (S + S) | (S * S)
+```
+
+First, our tokens, we want to replace all characters with a token.
+For 1, 2 and 3, let's use the token name "NUMBER", for "(" and ")", LBRACE and RBRACE accordingly, and since there is no precedence with this grammar, we don't actually care if we have `(S + S)` or `(S * S)`, so we can assign both `+` and `*` to the token MATHOP.
+Meaning, our grammar would behave more like this:
+
+```grammar
+N -> 1 | 2 | 3
+M -> + | *
+S -> N | (S M S)
+```
+
+First, we need to make our `lexer.l`, it is going to be very simple:
+
+```lex
+%{
+#include "parser.tab.h"
+%}
+
+%%
+
+    /* Remember, [] is a group, [abcd] behaves like "(a | b | c | d)" and "\" escapes characters */
+[123]  { return NUMBER: }
+[\+\*] { return MATHOP; }
+\(     { return LBRACE; }
+\)     { return RBRACE: }
+
+%%
+```
+
+Now, tokens (names) are defined inside grammars, however our lexer needs to emit (return) them.
+That's why, when running bison on our `parser.y`, we'll also create a C header file, which contains those names already defined, so they're accessible inside `lexer.l`.
+This file is in the format `FILENAME.tab.h`, where `FILENAME.y` is our source yacc file.
+
+Second, we need to make our `parser.y`:
+
+```yacc
+%{
+#include "stdio.h"
+int yylex();
+int yyerror(char *s);
+%}
+
+%token NUMBER MATHOP LBRACE RBRACE
+
+%%
+
+expr : NUMBER
+	 | LBRACE expr MATHOP expr RBRACE
+	 ;
+
+%%
+
+int yyerror(char *s) {
+	printf("Error: %s\n", s);
+	return 0;
+}
+
+int main() {
+	yyparse();
+}
+```
+
+A quirk with GNU Bison is that you need to declare the function `yylex` and `yyerror` beforehand, manually define `yyerror` and run `yyparse` in the main function.
+These are precisely the first 5 and the last 8 lines of code, but for now you don't need to think about them.
+
+Let's get to compiling.
+First, the lexer:
+
+```bash
+flex lexer.l
+```
+
+then our parser:
+
+```bash
+bison -d parser.y
+```
+
+where the `-d` option means we'll also output the `parser.tab.h` header file.
+Finally, we compile both of them together into one executable:
+
+```bash
+gcc lex.yy.c parse.tab.c -lfl
+```
+
+Now when you run `./a.out`, if you enter a valid string, you'll see a blank line, but if it isn't valid, you'll get "Error: syntax error".
 
 #### Using them together
 
-Let's now make our own "proper" front-end.
-The lexer will need to return (emit) it's token to the 
+The way we created that lexer and parser worked, but it wasn't very useful.
+Ideally, we want the lexer to also return the exact value the regex matched and we need to be creating our AST in the parser.
+
+Regarding the first problem, we've already returned a value, we could return some sort of structure, but that wouldn't work with the way our code is generated.
+What we can do is set a variable
 
 ## Appendix
 
@@ -902,3 +1035,5 @@ I want to thank [Dimitar Tagarev](https://github.com/dtagarev) for his review an
 [^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.
 
 [^nomnoml]: The graphics are made with [nomnoml](https://nomnoml.com/) by [Daniel Kallin](https://github.com/skanaar)
+
+[^shift-reduce-conflicts]: You might be tempted to try and make one for the grammar inside the [AST](#abstract-syntax-tree) section, but that one is ever so slightly problematic, because it's ambiguous (I showed why at the end of [Implementational difficulties with grammars](#implementational-difficulties-with-grammars)). Bison [can handle ambiguity by always choosing to shift](https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html), but I didn't want to complicate things.