EasyCodeIt Update: Our hand-written parser is going away

TheDcoder

Hi everyone,

It has been roughly 2 months since I have provided any sort of update... certainly one of the longer gaps I took while working on this project.

I haven't done much work in this period, as I kept stumbling across little things that pop up while working on the parser, and that has been a major source of procrastination for me... and honestly, I didn't have the mental energy to deal with all of the small details involved in writing a parser by myself. All my mental energy was going towards other stuff in life, mainly my day job which puts food the my table... and the remaining I had to split on recreation and working on this project.

The problem is that this work has been more tedious than fun, so for that reason, I have decided to abandon the hand-written parser (for now at-least).

The sad part ends there, because I have no intention to stop work on this project, which is to finally bring a simple and easy to use scripting language to Linux 😁

After some discussion with more experienced members of the C community, I have come to know that I have been reinventing the wheel mostly with my parser. Initially I have been hesitant to use external tools to generate a parser, partly because I didn't want to learn how to use them.

Now after my raw experience with doing it the old straight-forward way, I have decided that being practical is more important... obviously I under-estimated what it would take to write a full parser by myself, it is task comparable to actually implementing the rest of the language, which actually does the work... and it is the fun bit, which parsing is not.

The tools I chose to use for the job are lex and yacc, these are the OG tools that were (and in some, still are) used in popular C compilers, so if those are good enough for that, they should definitely be more than sufficient for us!

And obviously, they are tightly integrated with C and produce C code for parsing, so that is easy to integrate them into our existing code.

I have been reading the book lex & yacc, 2nd Edition by John Levine, Doug Brown, Tony Mason to learn how to use them, the first chapter (available to read for free) gives a very good introduction, I was blown away at how simple it was, compared to reading all those technical research papers on parsing techniques 😵.

I regret not looking into it earlier, I probably would have made this decision sooner if I had.

I have still yet to get into the second chapter which explains it all in detail, and then I will start experimenting with code to replace our existing code (RIP).

Hopefully this means we can skip the hard parts of parsing and get into the meat, which is actually executing the code and making it do things.

I will keep you guys updated, hopefully the next one won't take another two months 🤭

TheDcoder

I have finished reading all of the main chapters of the book... except the Chapter about writing a parser for the whole SQL language, which was just repeating what the previous chapters already established anyway 😒

I glossed over the bits in the secondary chapters, so I guess I am an expert in Lex & Yacc now 🤠

Now to actually start writing something with all the knowledge I have amassed, LOL. Expect an update in the upcoming weekend 😁

TheDcoder

I just dumped my entire uncommitted code into a single commit for archival purposes: DcodingTheWeb/EasyCodeItf86e812

Now I can work with a clean working directory and start porting the lexer (tokenizer) into Lex and the rest of it into Yacc for parsing.

Wish me luck guys! 🤞

TheDcoder

I'd done a terrible thing, and I am cursing myself right now 🤬

Turns out there was a sequel to the "Lex & Yacc" book, called "flex & bison" which is 2 decades newer than the first book, which I read ☹️

I searched for a newer book, but couldn't find any... probably because I kept searching for "Lex" and "Yacc", not "Flex" and "Bison". I was aware of them, they are newer implementations of the old tools, but apparently they are now considered separate and people stopped calling bison grammar "yacc" 🤬

Geez, now I need to go through that book and find out what new stuff they added... it is probably for the best so that I can write a better parser.

Sorry guys but it looks like I need a couple more days before I can start work on the parser.

seadoggie

TheDcoder Sorry guys

Please don't be; you're doing the right thing. If I was you, I'd probably have ignored the new book, gotten two months in, been stuck, then decided to switch. At least you've only learned about the wrong thing for one week. Not to mention that a bunch of it will probably transfer over and be relevant.

Nobody here was expecting this process to be fast... well I hope not anyways 😉

TheDcoder

seadoggie Thanks for the encouragement 🙂

I finished the first chapter of the book, it was mostly the same stuff, but I see that there are a handful of new features added in the 2 decades (possible more, since the book itself is a decade old).

TheDcoder

Damn, another month already? I got way too caught up with work and never found the time to actually start writing code... until today 🙂

I started small, rewrote the OG version of the parser in flex:

%{
#include <stdlib.h>
#include <string.h>

char *token_str = NULL;
size_t token_len = 0;

#define YY_USER_ACTION free(token_str); token_str = strndup(yytext, token_len = yyleng);

enum { // Token Types
	UNKNOWN = 420,
	WS,
	COMMENT, DIRECTIVE,
	NUMBER, STRING, BOOL,
	WORD,
	MACRO, VARIABLE,
	OPERATOR, BRACKET, DOT, COMMA,
};

%}

WS	[ \t\r\n]+
NL	\r?\n?

COD [;#][^\r\n]*

%%

{WS} ;

[;#][^\r\n]* return *yytext == ';' ? COMMENT : DIRECTIVE;

.	return UNKNOWN;

%%

#include <stddef.h>
#include <stdio.h>

static void print_token(char *str, size_t len, int type) {
	puts("---### TOKEN ###---");
	char *token_type;
	switch (type) {
		case UNKNOWN:
			token_type = "Unknown";
			break;
		case WS:
			token_type = "Whitespace";
			break;
		case COMMENT:
			token_type = "Comment";
			break;
		case DIRECTIVE:
			token_type = "Directive";
			break;
		case NUMBER:
			token_type = "Number";
			break;
		case STRING:
			token_type = "String";
			break;
		case WORD:
			token_type = "Word";
			break;
		case MACRO:
			token_type = "Macro";
			break;
		case VARIABLE:
			token_type = "Variable";
			break;
		case OPERATOR:
			token_type = "Operator";
			break;
		case BRACKET:
			token_type = "Bracket";
			break;
		case DOT:
			token_type = "Dot";
			break;
		case COMMA:
			token_type = "Comma";
			break;
		default:
			token_type = "Unnamed";
			break;
	}
	fputs("Type: ", stdout);
	puts(token_type);
	fputs("Data: ", stdout);
	puts(str);
}

int main(void) {
	int type;
	for (;;) {
		type = yylex();
		if (!type) break;
		print_token(token_str, token_len, type);
	}
	return 0;
}

At the moment it only supports comments and directives (which are basically the same), I believe that this is exactly what I started with when I wrote the first parser. Will post updates as I expand on the parser, a grammar definition will come soon once I am satisfied with the amount of tokens I can scan, shouldn't be much effort since it is all just regex.

Here is how it works:

TheDcoder@arch /m/d/P/C/E/parser (master)> flex lexer.l && cc lex.yy.c -lfl
TheDcoder@arch /m/d/P/C/E/parser (master)> cat /tmp/comments.au3 | ./a.out
---### TOKEN ###---
Type: Directive
Data: #include <test>
---### TOKEN ###---
Type: Comment
Data: ; comment
---### TOKEN ###---
Type: Comment
Data: ; comment 2

First we call flex to generate the actual C program and then we call cc() C compiler) to compile the program, by default it reads from standard input so we pass the contents of our comments.au3 with a pipe.

Cheers everyone!