1 files changed, 149 insertions, 0 deletions
diff --git a/21sh/ll-expr/src/parser/parser.c b/21sh/ll-expr/src/parser/parser.c
new file mode 100644
index 0000000..d1a1526
--- /dev/null
+++ b/21sh/ll-expr/src/parser/parser.c
@@ -0,0 +1,149 @@
+#include "parser.h"
+
+#include <stdio.h>
+
+struct ast *parse(enum parser_status *status, struct lexer *lexer)
+{
+    struct token t = lexer_peek(lexer);
+    *status = PARSER_OK;
+    if (t.type == TOKEN_EOF)
+    {
+        lexer_pop(lexer);
+        return NULL;
+    }
+    else
+    {
+        struct ast *exp = parse_exp(status, lexer);
+        if (*status != PARSER_OK)
+        {
+            return NULL;
+        }
+        struct token t = lexer_pop(lexer);
+        if (*status == PARSER_OK && t.type == TOKEN_EOF)
+        {
+            return exp;
+        }
+        else if (t.type != TOKEN_EOF)
+        {
+            *status = PARSER_UNEXPECTED_TOKEN;
+            fprintf(stderr, "parser: unexpected token\n");
+        }
+        ast_free(exp);
+        return NULL;
+    }
+}
+
+struct ast *parse_exp(enum parser_status *status, struct lexer *lexer)
+{
+    struct ast *left = parse_sexp(status, lexer);
+    if (*status == PARSER_UNEXPECTED_TOKEN)
+        return NULL;
+    struct token t = lexer_peek(lexer);
+    if (t.type != TOKEN_PLUS && t.type != TOKEN_MINUS)
+    {
+        *status = PARSER_OK;
+        return left;
+    }
+    else
+    {
+        struct ast *root = left;
+        do
+        {
+            left = root;
+            t = lexer_pop(lexer);
+            if (t.type == TOKEN_PLUS)
+                root = ast_new(AST_PLUS);
+            else
+                root = ast_new(AST_MINUS);
+            root->left = left;
+            root->right = parse_sexp(status, lexer);
+            if (*status == PARSER_UNEXPECTED_TOKEN)
+            {
+                ast_free(root);
+                return NULL;
+            }
+            t = lexer_peek(lexer);
+        } while (t.type != TOKEN_EOF
+                 && (t.type == TOKEN_PLUS || t.type == TOKEN_MINUS));
+        return root;
+    }
+}
+
+struct ast *parse_sexp(enum parser_status *status, struct lexer *lexer)
+{
+    struct ast *left = parse_texp(status, lexer);
+    if (*status == PARSER_UNEXPECTED_TOKEN)
+        return NULL;
+    struct token t = lexer_peek(lexer);
+    if (t.type != TOKEN_MUL && t.type != TOKEN_DIV)
+    {
+        *status = PARSER_OK;
+        return left;
+    }
+    else
+    {
+        struct ast *root = left;
+        do
+        {
+            left = root;
+            t = lexer_pop(lexer);
+            if (t.type == TOKEN_MUL)
+                root = ast_new(AST_MUL);
+            else
+                root = ast_new(AST_DIV);
+            root->left = left;
+            root->right = parse_texp(status, lexer);
+            if (*status == PARSER_UNEXPECTED_TOKEN)
+            {
+                ast_free(root);
+                return NULL;
+            }
+            t = lexer_peek(lexer);
+        } while (t.type != TOKEN_EOF
+                 && (t.type == TOKEN_MUL || t.type == TOKEN_DIV));
+        return root;
+    }
+}
+
+struct ast *parse_texp(enum parser_status *status, struct lexer *lexer)
+{
+    struct token t = lexer_pop(lexer);
+    if (t.type == TOKEN_NUMBER)
+    {
+        struct ast *res = ast_new(AST_NUMBER);
+        res->value = t.value;
+        return res;
+    }
+    else if (t.type == TOKEN_MINUS)
+    {
+        t = lexer_peek(lexer);
+        if (t.type != TOKEN_NUMBER && t.type != TOKEN_LEFT_PAR)
+        {
+            *status = PARSER_UNEXPECTED_TOKEN;
+            fprintf(stderr, "parser: unexpected token\n");
+            return NULL;
+        }
+        struct ast *unary = ast_new(AST_NEG);
+        unary->left = parse_texp(status, lexer);
+        return unary;
+    }
+    else if (t.type == TOKEN_LEFT_PAR)
+    {
+        struct ast *exp = parse_exp(status, lexer);
+        t = lexer_pop(lexer);
+        if (t.type != TOKEN_RIGHT_PAR)
+        {
+            *status = PARSER_UNEXPECTED_TOKEN;
+            fprintf(stderr, "parser: expected closing parenthesis\n");
+            ast_free(exp);
+            return NULL;
+        }
+        return exp;
+    }
+    else
+    {
+        *status = PARSER_UNEXPECTED_TOKEN;
+        fprintf(stderr, "parser: unexpected token\n");
+        return NULL;
+    }
+}