From 6cb929f1d70a5a832971b6d8c6558ea5376ecee8 Mon Sep 17 00:00:00 2001 From: onelin Date: Tue, 22 Sep 2026 22:46:56 +0200 Subject: docs: Update readme and roadmap --- README.md | 37 +++++++++++++++++++++++++++++-------- 1 file changed, 29 insertions(+), 8 deletions(-) (limited to 'README.md') diff --git a/README.md b/README.md index 7a79b05..5b8eca8 100644 --- a/README.md +++ b/README.md @@ -2,7 +2,9 @@ Tiny beginnings of a parser for a toy language, written in C99. -Currently only a lexer. +Currently only capable of parsing simple arithmetic expressions, limited to +positive numbers, addition, subtraction, multiplication, and division. + ## Compiling @@ -12,14 +14,33 @@ To build `frontend`: make ``` -## Running -Simply run `./frontend INPUT_FILE` and it should parse and print the abbreviated -tokens (ie. `+ => +`, instead of `+ => ADD`) with spacing around it. +## Running -Next baby steps is to make the token type store a line, column, and length of -the token, and the parser should ideally return an array of offsets into the -input string of each newline (or, ideally the character AFTER `\n`). Next is -constructing an AST of the arithmetic expression(s). +Simply run `./frontend INPUT_FILE` and it should parse and print the resulting +AST in polish notation with surrounding parenthesis, +ie. `1 + 2 * 3` turns into `( + 1 ( * 2 3 ) )`, +and `1 + 2 + 3` becomes `( + ( + 1 2 ) 3 )`. + +Example input can be found in the `program.input` file. + + +## Next steps + +* Allocating all memory up front, an inefficient but very simple use of memory + would exploit the fact that the number of lines and tokens is bounded by the total + number of bytes in `INPUT_FILE`, and the number of sub-expressions are bounded + by the number of tokens, so a naive approach is to allocate + `length(INPUT_FILE) * sizeof(char + line_t + expression_t)`. +* Streaming parsing; the implementation currently supports reading a limited + amount of input at each step, extending it to "pause-at-X" and resume once + more input is available should be a trivial feat. +* Fix precedence implementation, currently we just compare operators, which is + unmaintainable and inefficient once the grammar is extended. +* Extend the arithmetic grammar to support more operators. +* Boolean grammar parsing. +* Argument parsing to better control the output and debug different parts of the + implementation. +* Tests. Currently only simple arithmetic is implemented. -- cgit v1.3