[blog/seoc] Finished lex and yacc sections

1 files changed, 353 insertions, 16 deletions

diff --git a/src/blog/sane-explanation-of-compilers/part-1.md b/src/blog/sane-explanation-of-compilers/part-1.md
index e949e39..da1b718 100644
--- a/src/blog/sane-explanation-of-compilers/part-1.md
+++ b/src/blog/sane-explanation-of-compilers/part-1.md
@@ -780,13 +780,34 @@ The syntax `[0-9]` is the same as `(0 | 1 | ... | 9)`, it works for any letters
 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:
+If this file is located in `lexer.l`, we can transform it into a C file with:
 
 ```bash
-flex lexer.l && gcc lex.yy.c -lfl
+flex lexer.l
 ```
 
-Of course, you can use your lex implementation or C compiler of choice.
+Usually the result file is always named `lex.yy.c`.
+Afterwards, we can compile the C code into a working compiler:
+
+```bash
+gcc lex.yy.c -lfl
+```
+
+Without the `-lfl` flag, we would get a linking error, because of the `main` and `yywrap` function, which are required but aren't defined in our generated code.
+There are three ways to fix this problem:
+
+1. The one I've opted for, use the `-lfl` flag to compile our C code with a (flex) library which provides both functions.
+   Usually the lexer isn't meant to be ran by itself, so for the current time being, `-lfl` is the best option, the other two are fine when we get to `yacc`.
+2. Put `%option noyywrap` in the definitions section, which means the lexer will only read one file.
+3. Define it ourselves.
+   It should return 0 if our lexer should continue with the next given file, after finishing with the current one, or 1 if it should stop execution.
+   The function could be written in either "C code" section, but I personally prefer the last one.
+
+   ```lex
+   int yywrap() { return 0; }
+   ```
+
+Of course, you can use your lex implementation or C compiler of choice, and there this might not be a problem.
 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
 
@@ -1006,24 +1027,338 @@ 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
+#### Making a proper front-end
+
+The way we created that lexer and parser worked, but it wasn't very useful and has multiple issues we have to address:
+
+1. When entering a string that isn't matched at all, it gets printed back like nothing happend.
+   For example, if we enter the letter `a` or any string which doesn't have `(`, `)`, `1`, `2`, `3`, `+` or `-` characters, it will just get printed back.
+   Ideally, we want to raise an error, so we're going to add one rule which catches any (non-special) character and throws an error with the built-in `yy_fatal_error`:
+
+   ```lex
+   . { yy_fatal_error("Bad character"); }
+   ```
+
+   This rule must be the last rule, since we don't want it to be matched, if there is another rule that matches.
+   Remember that lex matches the longest possible string and if there are multiple rules which match the same amount of characters, only the first one is matched.
+
+2. For every token name, returned by the lexer, we also need to have it's actual value.
+   We could make a `struct`, which holds both a token name and it's value, but there is another ["built-in" mechanism](https://www.gnu.org/software/bison/manual/html_node/Token-Values.html) for that in yacc/Bison.
+   We would set the global variable `yylval` to the token value, and it will be changed for every token.
+
+   By default it's type is `int` (in Bison), but usually you would want it to be a [union](https://en.wikipedia.org/wiki/Union_type#C/C++).
+   Let's make it a union of int and char, though the first part is kind of useless, since we're only working with single digit numbers.
+   
+   ```yacc
+   %union {
+        int num;
+        char chr;
+   }
+   ```
+
+   Now, inside our lexer, rules would look like:
+
+   ```yacc
+   RULE1 { yylval.num = 129; return TOKEN; }
+   RULE2 { yylval.chr = 'a'; return TOKEN; }
+   ```
+
+   Inside C blocks for grammar rules we can reference the token values with `$i`, where `i` is the i'th "token" in the expression.
+   For example, in this rule, `$1` would be `(`, `$3` would be value of token `B` and `$5` would be the value of the rule name:
+
+   ```yacc
+   rule : ( A B ) rule
+         ;
+   ```
+
+   You can set rule "return" values by setting the variable `$$`:
+
+   ```yacc
+   rule : LBRACE rule RBRACE { $$ = 10; }
+   ```
+
+   The way you set it's type is discussed later.
+   However, `$i` isn't of type union, we cannot do something like `$i.num`, it is the precise value that was set for the token.
+   Therefore, we also need to define which value from the union every token will set, which is done by adding `<PROPERTY>` before every defined token (and `PROPERTY` is a property name inside the union):
+
+   ```yacc
+   %token <num> NUMBER <chr> MATHOP <chr> LBRACE <chr> RBRACE
+   ```
+
+3. If we enter one valid math expression, we'll get no error, but when we enter another, we'll get a "syntax error"[^better-bison-errors].
+   That is because we try to match only one expression, after it is matched our parser is waiting for an end of file character.
+   Let's make it so we would try to match an expression on every line:
+
+   ```yacc
+   start : expr
+          | expr start
+          ;
+   ```
+
+   A rule like `expr : expr expr` will produce shift/reduce conflicts.
+   Another option is duplicating our `expr` rules and adding `expr` in the beginning or end, but that is cumbersome if we want to make changes.
+
+4. We're getting input from the user, but our source text (code) will be in a file.
+   First, our `main` function need to take program parameters:
+
+   ```yacc
+   int main(int argc, char* argv[])
+   ```
+
+   Then we need to take the first argument, and open a file.
+   Additionally, we have to check if the file was successfully opened, and print an error and stop execution if so:
+
+   ```yacc
+   FILE* input = fopen(argv[1], "r");
+   if (input == NULL) {
+        yyerror("cannot read input file!");
+        return 1;
+   }
+   ```
+
+   Now for the clever bit, actual parsing in generated code is done on the file `yyin`, which by default is the standard user input.
+   To read a file, all we need to do is change the value of that variable.
+   Also, that variable is defined externally, so first we need to add to (the top) C section:
+
+   ```yacc
+   extern FILE* yyin;
+   ```
+
+   and then put in our `main`:
+
+   ```yacc
+   yyin = input;
+   ```
+
+   On \*NIX systems (Linux, MacOS, OpenBSD, ...) you can still use user input by passing the file `/dev/stdin`.
+   If you want your front-end to support multiple files, you would just need to wrap the whole body of main in a `for` loop, iterating over the whole `argv` array (remember that `argc` is the length of the array).
+
+5. We need to construct an AST.
+   Since the exact tree structure depends on your needs, I'll make the simplest possible tree in pure C that works for this grammar.
+   I won't explain this in much detail, since it is just normal C code.
+
+   ```c
+   #include <stdlib.h>
+   #include <stdio.h>
+
+   typedef struct node {
+        char val;
+        struct node *left;
+        struct node *right;
+   } node;
+
+   node* newNode(char val, node *left, node *right) {
+        node* out = malloc(sizeof(node));
+        out->val = val;
+        out->left = left;
+        out->right = right;
+        return out;
+   }
+   
+   void printTree(node *n, int level) {
+        if (n == NULL) return;
+        // %*s will add level amounts of spaces (but with the "" string)
+        printf("%*s|-%c\n", level, "", n->val);
+        printTree(n->left, level + 1);
+        printTree(n->right, level + 1);
+   }
+   
+   void freeNode(node *n) {
+        if (n == NULL) return;
+        freeNode(n->left);
+        freeNode(n->right);
+        free(n);
+   }
+   ```
+
+   However, all of this is quite a lot, and it would take a lot of space in `parser.y`, so let's separate it into `tree.c` and add a header file `tree.h` which contains the definitions:
+
+   ```c
+   #include <stdlib.h>
+   #include <stdio.h>
 
-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.
+   typedef struct node {
+        char val;
+        struct node *left;
+        struct node *right;
+   } node;
 
-Regarding the first problem, we've already returned a value, we could return some sort of `struct`, but that wouldn't work with the way our code is generated.
-Since everything is compiled into one program, we could use a global variable, which we set in the lexer and use in the parser code.
-That variable is [already defined](https://www.gnu.org/software/bison/manual/html_node/Token-Values.html) and is called `yylval`.
+   node* newNode(char val, node *left, node *right);
+   void printTree(node *n, int level);
+   void freeNode(node *n);
+   ```
+
+   Of course, we should add some ifndef-def precompiler code, but that isn't relevant for now.
+
+   The way we're going to use trees in our grammar is as follows: for the `NUMBER` expression of `expr`, we'll create a node with the (char) value of the number and "return" it.
+   For the expression of `expr` we'll "return" a node with the value of the math opeartor and left and right will be the returned values.
+   Inside start, after we've parsed an `expr`, we'll print out the "returned" tree and free it's memory.
+
+   I'm putting returned in quotes, because (as mentioned), we'll just be setting the value of `$$`.
+   `$$`'s type is set with the `%type` option, which works exactly like `%token`, but with grammar rule names.
+   However, this means that `node` must be available in `%union`, which is unfortunate but isn't a problem, we'll just add it.
+
+   Now, finally, it's time to include our `tree.h` in `parser.y`, but we'll also need to include it in `lexer.l`.
+   The reason is that the `%union` appears in `parser.tab.h`, which means our node structure is referenced in `parser.tab.h`, but `tree.h` isn't included there.
+
+All in all, we'll have 4 source files for our simple front-end:
+
+- `lexer.l`
+
+  ```lex
+  %{
+  #include "tree.h"
+  #include "parser.tab.h"
+  %}
+  
+  %option noyywrap
+  
+  %%
+  
+  [123]  { yylval.num = atoi(yytext); return NUMBER; }
+  [\+\*] { yylval.chr = yytext[0]   ; return MATHOP; }
+  \(     { yylval.chr = '('         ; return LBRACE; }
+  \)     { yylval.chr = ')'         ; return RBRACE; }
+  \      { } /* Don't do anything on spaces */
+
+  . { yy_fatal_error("Bad character"); }
+  
+  %%
+  ```
+
+- `parser.y`
+
+  ```yacc
+  %{ 
+  #include <stdio.h>
+  #include "tree.h"
+
+  extern FILE* yyin;
+
+  int yylex();
+  int yyerror(const char *s);
+  %}
+  
+  %union {
+        int num;
+        char chr;
+        node *n;
+  }
+  %token <num> NUMBER <chr> MATHOP <chr> LBRACE <chr> RBRACE
+  %type <n> expr
+  
+  %%
+  
+  start : expr       { printTree($1, 0); freeNode($1); }
+          | expr start { printTree($1, 0); freeNode($1); }
+          ;
+  
+  expr : NUMBER                         { $$ = newNode($1 + '0', NULL, NULL); }
+         | LBRACE expr MATHOP expr RBRACE { $$ = newNode($3, $2, $4); }
+         ;
+  
+  %%
+  
+  int yyerror(const char *s) {
+        printf("Error: %s\n", s);
+        return 0;
+  }
+  
+  int main(int argc, char* argv[]) {
+        FILE* input = fopen(argv[1], "r");
+        if (input == NULL) {
+            yyerror("reading input file!");
+            return 1;
+        }
+  
+        yyin = input;
+        yyparse();
+  }
+  ```
 
-As with everything else, we define it's properties inside our grammar (yacc/bison) file.
-By default it's type is `int` (in Bison), but usually you would want it to be a [union](https://en.wikipedia.org/wiki/Union_type#C/C++).
-For now let's simplify our lives and make it a union of int and char[^yylval-type].
+- `tree.h`
 
-Second, we need to make a tree.
-I'll not go into details, but we'll use a normal C `struct`ure for a node, and every node has it's value (a character) and two pointers, one to the left and one to the right.
-After we've matched a string, I'll print the tree in a nice to view format.
+  ```c
+  #ifndef TREE
+  #define TREE
+  
+  #include <stdlib.h>
+  #include <stdio.h>
+  
+  typedef struct node {
+        char val;
+        struct node *left;
+        struct node *right;
+  } node;
+  
+  node* newNode(char val, node *left, node *right);
+  void printTree(node *n, int level);
+  void freeNode(node *n);
+  
+  #endif
+  ```
+
+- `tree.c`
+
+  ```c
+  #include "tree.h"
+
+  node* newNode(char val, node *left, node *right) {
+        node* out = malloc(sizeof(node));
+        out->val = val;
+        out->left = left;
+        out->right = right;
+        return out;
+  }
+  
+  void printTree(node *n, int level) {
+        if (n == NULL) return;
+        printf("%*s|-%c\n", level, "", n->val);
+        printTree(n->left, level + 1);
+        printTree(n->right, level + 1);
+  }
+  
+  void freeNode(node *n) {
+        if (n == NULL) return;
+        freeNode(n->left);
+        freeNode(n->right);
+        free(n);
+  }
+  ```
+
+We compile everything:
+
+```bash
+flex lexer.l && bison parser.y && gcc lex.yy.c parse.tab.c tree.c
+```
+
+Now, let's create the file `test.txt`:
+
+```
+((1+1) * ((3+3) * 2))
+```
+
+and run our front-end on it:
+
+```bash
+./a.out test.txt
+```
 
-All in all, we'll have:
+Our output will be:
+
+```
+|-*
+ |-+
+  |-1
+  |-1
+ |-*
+  |-+
+   |-3
+   |-3
+  |-2
+```
+
+Perfect, we have a good looking tree!
 
 ## Appendix
 
@@ -1048,3 +1383,5 @@ I want to thank [Dimitar Tagarev](https://github.com/dtagarev) for his review an
 [^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.
+
+[^better-yacc-errors]: You can add `%define parse.error verbose` inside definitions of your yacc file, and it will tell you what character was expected and what character was read.