zyguan
4/14/2016 - 8:27 AM

An example of go yacc

An example of go yacc

// Copyright 2011 Bobby Powers. All rights reserved.
// Use of this source code is governed by the MIT
// license that can be found in the LICENSE file.

// based off of Appendix A from http://dinosaur.compilertools.net/yacc/

// original work: https://github.com/golang-samples/yacc

%{

package main

import (
	"fmt"
	"unicode"
)

%}

// fields inside this union end up as the fields in a structure known
// as ${PREFIX}SymType, of which a reference is passed to the lexer.
%union{
	val  int
        expr *Expr
}

// any non-terminal which returns a value needs a type, which is
// really a field name in the above union struct
%type <expr> expr
%type <val> number

// same for terminals
%token <val> DIGIT

%left '+'  '-'
%left '*'  '/'  '%'
%left UMINUS      /*  supplies  precedence  for  unary  minus  */

%%

stat	:    expr
		{ yylex.(*CalcLexer).ast = $1 }
	;

expr	:    '(' expr ')'
		{ $$ = $2 }
	|    expr '+' expr
		{ $$ = &Expr{op: "add", result: $1.result + $3.result, e1: $1, e2: $3} }
	|    expr '-' expr                  
		{ $$ = &Expr{op: "sub", result: $1.result - $3.result, e1: $1, e2: $3} }
	|    expr '*' expr                  
		{ $$ = &Expr{op: "mul", result: $1.result * $3.result, e1: $1, e2: $3} }
	|    expr '/' expr                  
		{ $$ = &Expr{op: "div", result: $1.result / $3.result, e1: $1, e2: $3} }
	|    expr '%' expr                  
		{ $$ = &Expr{op: "mod", result: $1.result % $3.result, e1: $1, e2: $3} }
	|    '-'  expr        %prec  UMINUS
		{ $$ = &Expr{op: "neg", result: -$2.result, e1: $2} }
	|    number
		{ $$ = &Expr{op: "num", result: $1} }
	;

number	:    DIGIT
		{ $$ = $1 }
	|    number DIGIT
		{ $$ = 10 * $1 + $2 }
	;

%%      /*  start  of  programs  */

type Expr struct {
	op string
        result int
	e1, e2 *Expr
}

type CalcLexer struct {
	s string
	pos int
        ast *Expr
}

func (l *CalcLexer) Lex(lval *yySymType) int {
	var c rune = ' '
	for c == ' ' {
		if l.pos == len(l.s) {
			return 0
		}
		c = rune(l.s[l.pos])
		l.pos += 1
	}

	if unicode.IsDigit(c) {
		lval.val = int(c) - '0'
		return DIGIT
	}
	return int(c)
}

func (l *CalcLexer) Error(s string) {
	c := "EOF"
	if l.pos < len(l.s) {
		c = l.s[l.pos:l.pos+1]
	}
	fmt.Printf("%s at '%s' (pos: %d)\n", s, c, l.pos)
}

func printExpr(e *Expr) {
	if e == nil || e.op == "num" {
		return
	}
	printExpr(e.e1)
	printExpr(e.e2)
	if e.op == "neg" {
		fmt.Println(e.op, e.e1.result, "\t\t->", e.result)
	} else {
		fmt.Println(e.op, e.e1.result, e.e2.result, "\t->", e.result)
	}
}

func main() {
	lexer := &CalcLexer{s: "-1 + 2 * 3 - 4"}
	yyParse(lexer)
	fmt.Println("result: ", lexer.ast.result)
        printExpr(lexer.ast)
}