umx_compiler

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

parser.go (10313B)

      1 package parser
      2 
      3 import (
      4 	"fmt"
      5 	"umx_compiler/ast"
      6 	"umx_compiler/lexer"
      7 	"umx_compiler/token"
      8 	"strconv"
      9 )
     10 
     11 const (
     12 	_ int = iota
     13 	LOWEST
     14 	EQUALS      // ==
     15 	LESSGREATER // > or <
     16 	SUM         // +
     17 	PRODUCT     // *
     18 	PREFIX      // -X or !X
     19 	CALL        // myFunction(x)
     20 	INDEX       // array[index]
     21 )
     22 
     23 var precedences = map[token.TokenType]int{
     24 	token.EQUAL:     EQUALS,
     25 	token.NOT_EQUAL: EQUALS,
     26 	token.LT:        LESSGREATER,
     27 	token.GT:        LESSGREATER,
     28 	token.PLUS:      SUM,
     29 	token.MINUS:     SUM,
     30 	token.SLASH:     PRODUCT,
     31 	token.ASTERISK:  PRODUCT,
     32 	token.LPAREN:    CALL,
     33 	token.LBRACKET:  INDEX,
     34 }
     35 
     36 type prefixParseFn func() ast.Expression
     37 type infixParseFn func(ast.Expression) ast.Expression
     38 
     39 type Parser struct {
     40 	l         *lexer.Lexer
     41 	curToken  token.Token
     42 	peekToken token.Token
     43 	errors    []string
     44 
     45 	prefixParseFns map[token.TokenType]prefixParseFn
     46 	infixParseFns  map[token.TokenType]infixParseFn
     47 }
     48 
     49 func New(l *lexer.Lexer) *Parser {
     50 	p := &Parser{
     51 		l:      l,
     52 		errors: []string{},
     53 	}
     54 	p.nextToken()
     55 	p.nextToken()
     56 
     57 	p.prefixParseFns = make(map[token.TokenType]prefixParseFn)
     58 	p.registerPrefix(token.IDENT, p.parseIdentifier)
     59 	p.registerPrefix(token.INT, p.parseIntegerLiteral)
     60 	p.registerPrefix(token.SHRIEK, p.parsePrefixExpression)
     61 	p.registerPrefix(token.MINUS, p.parsePrefixExpression)
     62 
     63 	p.infixParseFns = make(map[token.TokenType]infixParseFn)
     64 	p.registerInfix(token.PLUS, p.parseInfixExpression)
     65 	p.registerInfix(token.MINUS, p.parseInfixExpression)
     66 	p.registerInfix(token.SLASH, p.parseInfixExpression)
     67 	p.registerInfix(token.ASTERISK, p.parseInfixExpression)
     68 	p.registerInfix(token.EQUAL, p.parseInfixExpression)
     69 	p.registerInfix(token.NOT_EQUAL, p.parseInfixExpression)
     70 	p.registerInfix(token.LT, p.parseInfixExpression)
     71 	p.registerInfix(token.GT, p.parseInfixExpression)
     72 
     73 	p.registerPrefix(token.TRUE, p.parseBoolean)
     74 	p.registerPrefix(token.FALSE, p.parseBoolean)
     75 	p.registerPrefix(token.LPAREN, p.parseGroupedExpression)
     76 	p.registerPrefix(token.IF, p.parseIfExpression)
     77 	p.registerPrefix(token.FUNCTION, p.parseFunctionLiteral)
     78 
     79 	p.registerInfix(token.LPAREN, p.parseCallExpression)
     80 
     81 	p.registerPrefix(token.STRING, p.parseStringLiteral)
     82 	p.registerPrefix(token.LBRACKET, p.parseArrayLiteral)
     83 
     84 	p.registerInfix(token.LBRACKET, p.parseIndexExpression)
     85 
     86 	p.registerPrefix(token.LCURLY, p.parseHashLiteral)
     87 
     88 	return p
     89 }
     90 
     91 func (p *Parser) Errors() []string {
     92 	return p.errors
     93 }
     94 
     95 func (p *Parser) nextToken() {
     96 	p.curToken = p.peekToken
     97 	p.peekToken = p.l.NextToken()
     98 }
     99 
    100 func (p *Parser) ParseProgram() *ast.Program {
    101 	program := &ast.Program{}
    102 	program.Statements = []ast.Statement{}
    103 	for p.curToken.Type != token.EOF {
    104 		statement := p.parseStatement()
    105 		if statement != nil {
    106 			program.Statements = append(program.Statements, statement)
    107 		}
    108 		p.nextToken()
    109 	}
    110 	return program
    111 }
    112 
    113 func (p *Parser) parseStatement() ast.Statement {
    114 	switch p.curToken.Type {
    115 	case token.LET:
    116 		return p.parseLetStatement()
    117 	case token.RETURN:
    118 		return p.parseReturnStatement()
    119 	default:
    120 		return p.parseExpressionStatement()
    121 	}
    122 }
    123 
    124 func (p *Parser) parseLetStatement() *ast.LetStatement {
    125 	statement := &ast.LetStatement{Token: p.curToken}
    126 	if !p.expectPeek(token.IDENT) {
    127 		return nil
    128 	}
    129 	statement.Name = &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
    130 	if !p.expectPeek(token.ASSIGN) {
    131 		return nil
    132 	}
    133 	p.nextToken()
    134 	statement.Value = p.parseExpression(LOWEST)
    135 	if p.peekTokenIs(token.SEMICOLON) {
    136 		p.nextToken()
    137 	}
    138 
    139 	return statement
    140 }
    141 
    142 func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
    143 	statement := &ast.ReturnStatement{Token: p.curToken}
    144 	p.nextToken()
    145 	statement.ReturnValue = p.parseExpression(LOWEST)
    146 	for p.peekTokenIs(token.SEMICOLON) {
    147 		p.nextToken()
    148 	}
    149 
    150 	return statement
    151 }
    152 
    153 func (p *Parser) parseExpressionStatement() *ast.ExpressionStatement {
    154 	statement := &ast.ExpressionStatement{Token: p.curToken}
    155 	statement.Expression = p.parseExpression(LOWEST)
    156 	if p.peekTokenIs(token.SEMICOLON) {
    157 		p.nextToken()
    158 	}
    159 	return statement
    160 }
    161 
    162 func (p *Parser) parseExpression(precedence int) ast.Expression {
    163 	prefix := p.prefixParseFns[p.curToken.Type]
    164 	if prefix == nil {
    165 		p.noPrefixParseFnError(p.curToken.Type)
    166 		return nil
    167 	}
    168 	leftExp := prefix()
    169 
    170 	for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
    171 		infix := p.infixParseFns[p.peekToken.Type]
    172 		if infix == nil {
    173 			return leftExp
    174 		}
    175 		p.nextToken()
    176 		leftExp = infix(leftExp)
    177 	}
    178 	return leftExp
    179 }
    180 
    181 func (p *Parser) parseIdentifier() ast.Expression {
    182 	return &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
    183 }
    184 
    185 func (p *Parser) parseIntegerLiteral() ast.Expression {
    186 	lit := &ast.IntegerLiteral{Token: p.curToken}
    187 	value, err := strconv.ParseInt(p.curToken.Literal, 0, 64)
    188 	if err != nil {
    189 		msg := fmt.Sprintf("error parsing %q as int64", p.curToken.Literal)
    190 		p.errors = append(p.errors, msg)
    191 		return nil
    192 	}
    193 	lit.Value = value
    194 	return lit
    195 }
    196 
    197 func (p *Parser) curTokenIs(t token.TokenType) bool {
    198 	return p.curToken.Type == t
    199 }
    200 
    201 func (p *Parser) peekTokenIs(t token.TokenType) bool {
    202 	return p.peekToken.Type == t
    203 }
    204 
    205 func (p *Parser) expectPeek(t token.TokenType) bool {
    206 	if p.peekTokenIs(t) {
    207 		p.nextToken()
    208 		return true
    209 	} else {
    210 		p.peekError(t)
    211 		return false
    212 	}
    213 }
    214 
    215 func (p *Parser) peekError(t token.TokenType) {
    216 	msg := fmt.Sprintf("token expected: %s, got: %s", t, p.peekToken.Type)
    217 	p.errors = append(p.errors, msg)
    218 }
    219 
    220 func (p *Parser) peekPrecedence() int {
    221 	if p, ok := precedences[p.peekToken.Type]; ok {
    222 		return p
    223 	}
    224 	return LOWEST
    225 }
    226 
    227 func (p *Parser) curPrecedence() int {
    228 	if p, ok := precedences[p.curToken.Type]; ok {
    229 		return p
    230 	}
    231 	return LOWEST
    232 }
    233 
    234 func (p *Parser) registerPrefix(tokenType token.TokenType, fn prefixParseFn) {
    235 	p.prefixParseFns[tokenType] = fn
    236 }
    237 
    238 func (p *Parser) registerInfix(tokenType token.TokenType, fn infixParseFn) {
    239 	p.infixParseFns[tokenType] = fn
    240 }
    241 
    242 func (p *Parser) noPrefixParseFnError(t token.TokenType) {
    243 	msg := fmt.Sprintf("no prefix parse function for %s", t)
    244 	p.errors = append(p.errors, msg)
    245 }
    246 
    247 func (p *Parser) parsePrefixExpression() ast.Expression {
    248 	expression := &ast.PrefixExpression{
    249 		Token:    p.curToken,
    250 		Operator: p.curToken.Literal,
    251 	}
    252 	p.nextToken()
    253 	expression.Right = p.parseExpression(PREFIX)
    254 	return expression
    255 }
    256 
    257 func (p *Parser) parseInfixExpression(left ast.Expression) ast.Expression {
    258 	expression := &ast.InfixExpression{
    259 		Token:    p.curToken,
    260 		Operator: p.curToken.Literal,
    261 		Left:     left,
    262 	}
    263 	precedence := p.curPrecedence()
    264 	p.nextToken()
    265 	expression.Right = p.parseExpression(precedence)
    266 	return expression
    267 }
    268 
    269 func (p *Parser) parseBoolean() ast.Expression {
    270 	return &ast.Boolean{Token: p.curToken, Value: p.curTokenIs(token.TRUE)}
    271 }
    272 
    273 func (p *Parser) parseGroupedExpression() ast.Expression {
    274 	p.nextToken()
    275 	expr := p.parseExpression(LOWEST)
    276 	if !p.expectPeek(token.RPAREN) {
    277 		return nil
    278 	}
    279 	return expr
    280 }
    281 
    282 func (p *Parser) parseIfExpression() ast.Expression {
    283 	expr := &ast.IfExpression{Token: p.curToken}
    284 	if !p.expectPeek(token.LPAREN) {
    285 		return nil
    286 	}
    287 	p.nextToken()
    288 	expr.Condition = p.parseExpression(LOWEST)
    289 	if !p.expectPeek(token.RPAREN) {
    290 		return nil
    291 	}
    292 	if !p.expectPeek(token.LCURLY) {
    293 		return nil
    294 	}
    295 	expr.Consequence = p.parseBlockStatement()
    296 	if p.peekTokenIs(token.ELSE) {
    297 		p.nextToken()
    298 		if !p.expectPeek(token.LCURLY) {
    299 			return nil
    300 		}
    301 		expr.Alternative = p.parseBlockStatement()
    302 	}
    303 	return expr
    304 }
    305 
    306 func (p *Parser) parseBlockStatement() *ast.BlockStatement {
    307 	block := &ast.BlockStatement{Token: p.curToken}
    308 	block.Statements = []ast.Statement{}
    309 	p.nextToken()
    310 	for !p.curTokenIs(token.RCURLY) && !p.curTokenIs(token.EOF) {
    311 		statement := p.parseStatement()
    312 		if statement != nil {
    313 			block.Statements = append(block.Statements, statement)
    314 		}
    315 		p.nextToken()
    316 	}
    317 	return block
    318 }
    319 
    320 func (p *Parser) parseFunctionLiteral() ast.Expression {
    321 	lit := &ast.FunctionLiteral{Token: p.curToken}
    322 	if !p.expectPeek(token.LPAREN) {
    323 		return nil
    324 	}
    325 	lit.Parameters = p.parseFunctionParameters()
    326 	if !p.expectPeek(token.LCURLY) {
    327 		return nil
    328 	}
    329 	lit.Body = p.parseBlockStatement()
    330 	return lit
    331 }
    332 
    333 func (p *Parser) parseFunctionParameters() []*ast.Identifier {
    334 	identifiers := []*ast.Identifier{}
    335 	if p.peekTokenIs(token.RPAREN) {
    336 		p.nextToken()
    337 		return identifiers
    338 	}
    339 	p.nextToken()
    340 	ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
    341 	identifiers = append(identifiers, ident)
    342 	for p.peekTokenIs(token.COMMA) {
    343 		p.nextToken()
    344 		p.nextToken()
    345 		ident := &ast.Identifier{Token: p.curToken, Value: p.curToken.Literal}
    346 		identifiers = append(identifiers, ident)
    347 	}
    348 	if !p.expectPeek(token.RPAREN) {
    349 		return nil
    350 	}
    351 	return identifiers
    352 }
    353 
    354 func (p *Parser) parseCallExpression(function ast.Expression) ast.Expression {
    355 	expr := &ast.CallExpression{Token: p.curToken, Function: function}
    356 	expr.Arguments = p.parseExpressionList(token.RPAREN)
    357 	return expr
    358 }
    359 
    360 func (p *Parser) parseExpressionList(end token.TokenType) []ast.Expression {
    361 	args := []ast.Expression{}
    362 	if p.peekTokenIs(end) {
    363 		p.nextToken()
    364 		return args
    365 	}
    366 	p.nextToken()
    367 	args = append(args, p.parseExpression(LOWEST))
    368 	for p.peekTokenIs(token.COMMA) {
    369 		p.nextToken()
    370 		p.nextToken()
    371 		args = append(args, p.parseExpression(LOWEST))
    372 	}
    373 	if !p.expectPeek(end) {
    374 		return nil
    375 	}
    376 	return args
    377 }
    378 
    379 func (p *Parser) parseStringLiteral() ast.Expression {
    380 	return &ast.StringLiteral{Token: p.curToken, Value: p.curToken.Literal}
    381 }
    382 
    383 func (p *Parser) parseArrayLiteral() ast.Expression {
    384 	array := &ast.ArrayLiteral{Token: p.curToken}
    385 	array.Elements = p.parseExpressionList(token.RBRACKET)
    386 	return array
    387 }
    388 
    389 func (p *Parser) parseIndexExpression(left ast.Expression) ast.Expression {
    390 	expr := &ast.IndexExpression{Token: p.curToken, Left: left}
    391 	p.nextToken()
    392 	expr.Index = p.parseExpression(LOWEST)
    393 	if !p.expectPeek(token.RBRACKET) {
    394 		return nil
    395 	}
    396 	return expr
    397 }
    398 
    399 func (p *Parser) parseHashLiteral() ast.Expression {
    400 	hash := &ast.HashLiteral{Token: p.curToken}
    401 	hash.Pairs = make(map[ast.Expression]ast.Expression)
    402 	for !p.peekTokenIs(token.RCURLY) {
    403 		p.nextToken()
    404 		key := p.parseExpression(LOWEST)
    405 		if !p.expectPeek(token.COLON) {
    406 			return nil
    407 		}
    408 		p.nextToken()
    409 		value := p.parseExpression(LOWEST)
    410 		hash.Pairs[key] = value
    411 		if !p.peekTokenIs(token.RCURLY) && !p.expectPeek(token.COMMA) {
    412 			return nil
    413 		}
    414 	}
    415 	if !p.expectPeek(token.RCURLY) {
    416 		return nil
    417 	}
    418 	return hash
    419 }