diff options
1 files changed, 37 insertions, 34 deletions
| -rw-r--r-- | src/blog/sane-explanation-of-compilers/part-1/index.du | 71 |
diff --git a/src/blog/sane-explanation-of-compilers/part-1/index.du b/src/blog/sane-explanation-of-compilers/part-1/index.du index 125c778..39d1a15 100644 --- a/src/blog/sane-explanation-of-compilers/part-1/index.du +++ b/src/blog/sane-explanation-of-compilers/part-1/index.du @@ -65,7 +65,7 @@ In this post, we'll be looking only at the first one. Syntax in current programming languages can be quite sophisticated and ambiguous. For example (taken from {url wikipedia;https://en.wikipedia.org/wiki/Most_vexing_parse}) this C++ snippet -``` +```cpp void f(double d) { int i(int(d)); } @@ -458,7 +458,8 @@ It all boils down to using a whole bunch of conditional statements and tracing w We need to track the current state of the string, because imagine we've just read an "a", it could either be from the left or right handside of "a + a", and that changes what character to expect next. We're going to track the state with different numbers, defined like this: - .table_2 + .table + .2 |= State (number) |= Current expression ends with |: 0 @@ -531,7 +532,8 @@ It all boils down to using a whole bunch of conditional statements and tracing w It's also helpful to put what we do in different situations in another table: - :table_4 + :table + :4 |= State |= If ends on |= Change state to @@ -583,6 +585,7 @@ It all boils down to using a whole bunch of conditional statements and tracing w |: Replace "(S + F)" with "S" + where, if there is a value in "If ends on", we read the next character, while otherwise we don't and we just execute "Change state to" and "Also do". - You're probably wondering why the table works so weird, like why on state 3 we don't directly replace "a" with "S" and change to state 5 for example. @@ -703,34 +706,34 @@ Let's look at the input string {` 2 * (1 + 3)}, while abstracting ourselves from :unordered - we read the {` 2}, that is a number, we add it as a node - .p {img ./img/tree-building-1.svg} + {img ./img/tree-building-1.svg} - then we read the {` *}, we now know our expression is in the form {` E* E}. If you think about it, up to this point, we've basically been building a tree for the left handside. {b If} the topmost element in that tree is a brace, - .p {img ./img/tree-building-ex1.svg} + {img ./img/tree-building-ex1.svg} we connect it to the left handside of {` *}: - .p {img ./img/tree-building-ex2.svg} + {img ./img/tree-building-ex2.svg} {b Otherwise} (when it's {` +} or {` *} or a number), because of precedence, we'll attach the latest number to the left handside. However we have to be careful, if something connects to the number, we now need it to connect to the {` *}.\n For example, let's say we had {` 1 + 2 * 3}, and we've just read the {` *}. The tree up to this point would look like, - .p {img ./img/tree-building-ex3.svg} + {img ./img/tree-building-ex3.svg} where the latest number we've found was {` 2}, but the {` +} connects to it. So, we need to make the {` 2} connect to the left handside of {` *}, and make {` +} connect to {` *} instead of {` 2} - .p {img ./img/tree-building-ex4.svg} + {img ./img/tree-building-ex4.svg} In our original case, nothing connects to the {` 2} in {` 2 * (1 + 3)}, so we can just connect it to the left handside of {` *} - .p {img ./img/tree-building-2.svg} + {img ./img/tree-building-2.svg} where the three dots signify there isn't anything there (but we expect there to be). Somewhere we'll store that the next element we find has to be connected to the right handside. @@ -738,7 +741,7 @@ Let's look at the input string {` 2 * (1 + 3)}, while abstracting ourselves from - now we read {` (}, we cannot have it by itself, so we directly decide we're working with {` (E)} (in our full algorithm we would need a check for existance of matching brace). We'll create a {` ()} node and because of the last step, we'll connect it to the right handside. - .p {img ./img/tree-building-3.svg} + {img ./img/tree-building-3.svg} Now, moving forward, we'll be creating a subtree, essentially making a second tree, and after that is done, we'll connect it's topmost element (root) to the {` ()} node. @@ -763,7 +766,7 @@ Lex is the original program, from 1975, in the modern day it's successor/impleme A lex source file is divided into three parts: -'def LANG lex +'def LANG c ``` 'snippet 1 $ ./template.l @@ -777,7 +780,7 @@ Usually the {` C_code} in the regex would be a return (more commonly called "emi Let's look at a very simple example program: every whole number is printed as "NUMBER", while everything else is printed as-is: -'def LANG lex +'def LANG c ``` 'snippet 1 $ ./example_lex/lexer.l @@ -809,7 +812,7 @@ There are three ways to fix this problem: 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. - 'def LANG lex + 'def LANG c ``` int yywrap() { return 0; } @@ -839,7 +842,7 @@ and strings: 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. -'def LANG lex +'def LANG c ``` 'snippet 1 $ ./example_lex/numbers_html.l @@ -862,7 +865,7 @@ Similarly to lex, yacc originates from 1975, and it's modern replacement is {url A yacc file looks very similarly to a lex one: -'def LANG yacc +'def LANG y ``` 'snippet 1 $ ./template.y @@ -870,7 +873,7 @@ however rather than definitions you have declarations, and the rules are in a co Token names are defined in {` declarations}, in the format -'def LANG yacc +'def LANG y ``` %token NAME1 NAME2 ... @@ -879,14 +882,14 @@ There are also other options you can set, like the start name with {` %start}. Grammars are in the form -'def LANG yacc +'def LANG y ``` name : TOKEN1 TOKEN2 ... ; where alternation is defined like -'def LANG yacc +'def LANG y ``` name : TOKEN1 | TOKEN2 @@ -896,7 +899,7 @@ name : TOKEN1 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 -'def LANG yacc +'def LANG y ``` name : TOKEN1 { C code here } | TOKEN2 @@ -924,7 +927,7 @@ S -> N | (S M S) First, we need to make our {` lexer.l}, it is going to be very simple: -'def LANG lex +'def LANG c ``` 'snippet 1 $ ./example_yacc/lexer.l @@ -934,7 +937,7 @@ This file is in the format {` FILENAME.tab.h}, where {` FILENAME.y} is our sourc Second, we need to make our {` parser.y}: -'def LANG yacc +'def LANG y ``` 'snippet 1 $ ./example_yacc/parser.y @@ -969,7 +972,7 @@ The way we created that lexer and parser worked, but it wasn't very useful and h 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}: - 'def LANG lex + 'def LANG c ``` . { yy_fatal_error("Bad character"); } @@ -983,7 +986,7 @@ The way we created that lexer and parser worked, but it wasn't very useful and h By default it's type is {` int} (in Bison), but usually you would want it to be a {url 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. \n - 'def LANG yacc + 'def LANG y ``` %union { int num; @@ -992,7 +995,7 @@ The way we created that lexer and parser worked, but it wasn't very useful and h Now, inside our lexer, rules would look like: - 'def LANG yacc + 'def LANG y ``` RULE1 { yylval.num = 129; return TOKEN; } RULE2 { yylval.chr = 'a'; return TOKEN; } @@ -1000,14 +1003,14 @@ 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: - 'def LANG yacc + 'def LANG y ``` rule : ( A B ) rule ; You can set rule "return" values by setting the variable {` \$$}: - 'def LANG yacc + 'def LANG y ``` rule : LBRACE rule RBRACE { $$ = 10; } @@ -1015,7 +1018,7 @@ rule : LBRACE rule RBRACE { $$ = 10; } 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): - 'def LANG yacc + 'def LANG y ``` %token <num> NUMBER <chr> MATHOP <chr> LBRACE <chr> RBRACE @@ -1023,7 +1026,7 @@ rule : LBRACE rule RBRACE { $$ = 10; } 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: - 'def LANG yacc + 'def LANG y ``` start : expr | expr start @@ -1035,14 +1038,14 @@ start : expr 4. We're getting input from the user, but our source text (code) will be in a file. First, our {` main} function needs to take program parameters: - 'def LANG yacc + 'def LANG y ``` 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: - 'def LANG yacc + 'def LANG y ``` FILE* input = fopen(argv[1], "r"); if (input == NULL) { @@ -1054,13 +1057,13 @@ if (input == NULL) { 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: - 'def LANG yacc + 'def LANG y ``` extern FILE* yyin; and then put in our {` main}: - 'def LANG yacc + 'def LANG y ``` yyin = input; @@ -1100,13 +1103,13 @@ All in all, we'll have 4 source files for our simple front-end: :unordered - {` lexer.l} - 'def LANG lex + 'def LANG c ``` 'snippet 1 $ ./proper/lexer.l - {` parser.y} - 'def LANG yacc + 'def LANG y ``` 'snippet 1 $ ./proper/parser.y |