umx_compiler

UMX virtual machine "Monkey" interpreter / bytecode compiler
git clone git://bsandro.tech/umx_compiler
Log | Files | Refs

commit 6632cd6350f82b751a0f6c4e720b8c216e1d4dad
parent ec7026cf5c8286da007b17f2dda38a32050fbb14
Author: bsandro <email@bsandro.tech>
Date:   Wed, 15 Jun 2022 01:48:19 +0300

operator precedence parsing

Diffstat:
Mast/ast.go | 22++++++++++++++++++++++
Mparser/parser.go | 61++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
Mparser/parser_test.go | 75+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 155 insertions(+), 3 deletions(-)

diff --git a/ast/ast.go b/ast/ast.go @@ -39,6 +39,28 @@ func (pe *PrefixExpression) String() string { return out.String() } +type InfixExpression struct { + Token token.Token + Left Expression + Operator string + Right Expression +} + +func (ie *InfixExpression) expressionNode() {} +func (ie *InfixExpression) TokenLiteral() string { + return ie.Token.Literal +} +func (ie *InfixExpression) String() string { + var out bytes.Buffer + out.WriteString("{") + out.WriteString(ie.Left.String()) + out.WriteString(" " + ie.Operator + " ") + out.WriteString(ie.Right.String()) + out.WriteString("}") + return out.String() + +} + type Identifier struct { Token token.Token Value string diff --git a/parser/parser.go b/parser/parser.go @@ -19,6 +19,17 @@ const ( CALL // myFunction(x) ) +var precedences = map[token.TokenType]int{ + token.EQUAL: EQUALS, + token.NOT_EQUAL: EQUALS, + token.LT: LESSGREATER, + token.GT: LESSGREATER, + token.PLUS: SUM, + token.MINUS: SUM, + token.SLASH: PRODUCT, + token.ASTERISK: PRODUCT, +} + type prefixParseFn func() ast.Expression type infixParseFn func(ast.Expression) ast.Expression @@ -46,6 +57,16 @@ func New(l *lexer.Lexer) *Parser { p.registerPrefix(token.SHRIEK, p.parsePrefixExpression) p.registerPrefix(token.MINUS, p.parsePrefixExpression) + p.infixParseFns = make(map[token.TokenType]infixParseFn) + p.registerInfix(token.PLUS, p.parseInfixExpression) + p.registerInfix(token.MINUS, p.parseInfixExpression) + p.registerInfix(token.SLASH, p.parseInfixExpression) + p.registerInfix(token.ASTERISK, p.parseInfixExpression) + p.registerInfix(token.EQUAL, p.parseInfixExpression) + p.registerInfix(token.NOT_EQUAL, p.parseInfixExpression) + p.registerInfix(token.LT, p.parseInfixExpression) + p.registerInfix(token.GT, p.parseInfixExpression) + return p } @@ -124,10 +145,18 @@ func (p *Parser) parseExpression(precedence int) ast.Expression { if prefix == nil { p.noPrefixParseFnError(p.curToken.Type) return nil - } else { - leftExp := prefix() - return leftExp } + leftExp := prefix() + + for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() { + infix := p.infixParseFns[p.peekToken.Type] + if infix == nil { + return leftExp + } + p.nextToken() + leftExp = infix(leftExp) + } + return leftExp } func (p *Parser) parseIdentifier() ast.Expression { @@ -169,6 +198,20 @@ func (p *Parser) peekError(t token.TokenType) { p.errors = append(p.errors, msg) } +func (p *Parser) peekPrecedence() int { + if p, ok := precedences[p.peekToken.Type]; ok { + return p + } + return LOWEST +} + +func (p *Parser) curPrecedence() int { + if p, ok := precedences[p.curToken.Type]; ok { + return p + } + return LOWEST +} + func (p *Parser) registerPrefix(tokenType token.TokenType, fn prefixParseFn) { p.prefixParseFns[tokenType] = fn } @@ -191,3 +234,15 @@ func (p *Parser) parsePrefixExpression() ast.Expression { expression.Right = p.parseExpression(PREFIX) return expression } + +func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression { + expression := &ast.InfixExpression{ + Token: p.curToken, + Operator: p.curToken.Literal, + Left: left, + } + precedence := p.curPrecedence() + p.nextToken() + expression.Right = p.parseExpression(precedence) + return expression +} diff --git a/parser/parser_test.go b/parser/parser_test.go @@ -207,6 +207,55 @@ func TestParsingPrefixExpressions(t *testing.T) { } } +func TestParsingInfixExpressions(t *testing.T) { + infixTests := []struct { + input string + leftValue int64 + operator string + rightValue int64 + }{ + {"1 + 2", 1, "+", 2}, + {"3 - 4", 3, "-", 4}, + {"5 * 6", 5, "*", 6}, + {"7 / 8", 7, "/", 8}, + {"9 > 0", 9, ">", 0}, + {"1 < 2", 1, "<", 2}, + {"3 == 3", 3, "==", 3}, + {"4 != 5", 4, "!=", 5}, + } + + for _, tt := range infixTests { + l := lexer.New(tt.input) + p := New(l) + prg := p.ParseProgram() + checkParserErrors(t, p) + + if len(prg.Statements) != 1 { + t.Fatalf("prg.Statements length is not 1 but %d", len(prg.Statements)) + } + + statement, ok := prg.Statements[0].(*ast.ExpressionStatement) + if !ok { + t.Fatalf("statement is not ExpressionStatement but %T", prg.Statements[0]) + } + + expr, ok := statement.Expression.(*ast.InfixExpression) + if !ok { + t.Fatalf("Statement.Expression is not Infix but %T", statement.Expression) + } + + if !testIntegerLiteral(t, expr.Left, tt.leftValue) { + return + } + if expr.Operator != tt.operator { + t.Fatalf("expr.Operator is not %s but %s", tt.operator, expr.Operator) + } + if !testIntegerLiteral(t, expr.Right, tt.rightValue) { + return + } + } +} + func testIntegerLiteral(t *testing.T, il ast.Expression, value int64) bool { integ, ok := il.(*ast.IntegerLiteral) if !ok { @@ -223,3 +272,29 @@ func testIntegerLiteral(t *testing.T, il ast.Expression, value int64) bool { } return true } + +func TestOperatorPrecedenceParsing(t *testing.T) { + tests := []struct { + input string + expected string + }{ + {"-a*b", "{{-a} * b}"}, + {"!-a", "{!{-a}}"}, + {"a+b+c", "{{a + b} + c}"}, + {"a*b*c", "{{a * b} * c}"}, + {"a*b/c", "{{a * b} / c}"}, + {"a+b*c+d/e-f", "{{{a + {b * c}} + {d / e}} - f}"}, + {"5>4==3<4", "{{5 > 4} == {3 < 4}}"}, + } + + for _, tt := range tests { + l := lexer.New(tt.input) + p := New(l) + prg := p.ParseProgram() + checkParserErrors(t, p) + actual := prg.String() + if actual != tt.expected { + t.Errorf("expected %q but got %q", tt.expected, actual) + } + } +}