recursive-descent-parser-javascript/parser.js at main · FabrizioDeSantis/recursive-descent-parser-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * Expression = Term (("+" | "-") Term)*
 * Term = Factor (("*" | "/") Factor)*
 * Factor = Primary ("^" Factor)*
 * Primary = Parenthesis | NUMBER | UnaryExpression
 * Parenthesis = "(" Expression ")"
 * UnaryExpression = "-" Factor
 */

import Tokenizer from "./tokenizer.js"
import {TokenTypes} from "./tokenizer.js"

export default class Parser{

    parse(input){

        this.input = input;
        this.tokenizer = new Tokenizer(input);
        this.lookhead = this.tokenizer.getNext();

        return this.Expression();
    }

    consume(tokenType){
        const token = this.lookhead;

        if(token == null){
            throw new SyntaxError(`Unexpected EOF, expected: "${tokenType}"`);
        }

        if(token.type !== tokenType){
            throw new SyntaxError(`Unexpected token: "${token.value}", expected "${tokenType}"`);
        }

        this.lookhead = this.tokenizer.getNext();

        return token;
    }

    /**
     * this method accepts 4 parameters: leftRule, rightRule, operator1 and operator2
     * both leftRule and rightRule are Term rules
     */

    BinaryExpr(leftRule, rightRule, operator1, operator2){

        let x = leftRule();

        while(
            this.lookhead && (this.lookhead.type === operator1 || this.lookhead.type === operator2)
        ){
            const operator = this.consume(this.lookhead.type).type;
            switch (operator){
                case TokenTypes.PLUS:
                    x = x + rightRule();
                    break;
                case TokenTypes.MINUS:
                    x = x - rightRule();
                    break;
                case TokenTypes.MULTIPLY:
                    x = x * rightRule();
                    break;
                case TokenTypes.DIVIDE:
                    x = x / rightRule();
                    break;
                case TokenTypes.EXP:
                    x = x ** rightRule();
                    break;
            }
        }

        return x;

    }


    Expression() {

        return this.BinaryExpr(
            () => this.Term(),
            () => this.Term(),
            TokenTypes.PLUS,
            TokenTypes.MINUS
        );
    }

    Term(){

        return this.BinaryExpr(
            () => this.Factor(),
            () => this.Factor(),
            TokenTypes.MULTIPLY,
            TokenTypes.DIVIDE
        );

    }

    Factor(){

        return this.BinaryExpr(
            () => this.Primary(),
            () => this.Factor(),
            TokenTypes.EXP
        );

    }

    Primary() {

        if(this.lookhead.type === TokenTypes.PARENTHESIS_LEFT){
            return this.Parenthesis();
        }
        if(this.lookhead.type === TokenTypes.MINUS){
            return this.UnaryOp();
        }
        const token = this.consume(TokenTypes.NUMBER);

        return Number(token.value);
    }

    Parenthesis(){

        this.consume(TokenTypes.PARENTHESIS_LEFT);
        const expr = this.Expression();
        this.consume(TokenTypes.PARENTHESIS_RIGHT);

        return expr;
    }

    UnaryOp(){
        this.consume(TokenTypes.MINUS);
        return -this.Factor();
    }
}