Skip to content

Instantly share code, notes, and snippets.

@tkrs
Created February 13, 2018 05:31
  • Star 7 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save tkrs/23ab96cf84284ec6848c1c0a16611e21 to your computer and use it in GitHub Desktop.
goyacc tutorial
%{
package main
import (
"text/scanner"
"strconv"
"strings"
"fmt"
)
type Expression interface{}
type ParenExpr struct {
SubExpr Expression
}
type Token struct {
token int
literal string
}
type NumExpr struct {
literal string
}
type BinOpExpr struct {
left NumExpr
operator string
right NumExpr
}
type AssocExpr struct {
left Expression
operator string
right Expression
}
type UnaryExpr struct {
operator string
right Expression
}
%}
%union{
token Token
expr Expression
}
%type<expr> program
%type<expr> expr
%token<token> NUMBER NOT AND OR IS
%left IS
%left '<' GE '>' LE
%left AND
%left OR
%right NOT
%%
program
: expr
{
$$ = $1
yylex.(*Lexer).result = $$
}
expr
: NUMBER
{
$$ = NumExpr{literal: $1.literal}
}
| NOT expr
{
$$ = UnaryExpr{operator: "!", right: $2}
}
| expr AND expr
{
$$ = AssocExpr{left: $1, operator: "&&", right: $3}
}
| '(' expr ')'
{
$$ = ParenExpr{SubExpr: $2}
}
| expr OR expr
{
$$ = AssocExpr{left: $1, operator: "||", right: $3}
}
| NUMBER '<' NUMBER
{
$$ = BinOpExpr{left: NumExpr{literal: $1.literal}, operator: "<", right: NumExpr{literal: $3.literal}}
}
| NUMBER '>' NUMBER
{
$$ = BinOpExpr{left: NumExpr{literal: $1.literal}, operator: ">", right: NumExpr{literal: $3.literal}}
}
| NUMBER IS NUMBER
{
$$ = BinOpExpr{left: NumExpr{literal: $1.literal}, operator: "=", right: NumExpr{literal: $3.literal}}
}
| NUMBER GE NUMBER
{
$$ = BinOpExpr{left: NumExpr{literal: $1.literal}, operator: ">=", right: NumExpr{literal: $3.literal}}
}
| NUMBER LE NUMBER
{
$$ = BinOpExpr{left: NumExpr{literal: $1.literal}, operator: "<=", right: NumExpr{literal: $3.literal}}
}
%%
type Lexer struct {
scanner.Scanner
Vars map[string]interface{}
result Expression
}
func (l *Lexer) Lex(lval *yySymType) int {
token := l.Scan()
lit := l.TokenText()
tok := int(token)
switch tok {
case scanner.Int:
tok = NUMBER
default:
switch lit {
case "IS":
tok = IS
case "NOT":
tok = NOT
case "AND":
tok = AND
case "OR":
tok = OR
case "<=":
tok = LE
case ">=":
tok = GE
default:
if v, ok := l.Vars[lit]; ok {
switch v.(type) {
case int:
tok = NUMBER
lit = strconv.Itoa(v.(int))
}
}
}
}
lval.token = Token{token: tok, literal: lit}
return tok
}
func (l *Lexer) Error(e string) {
panic(e)
}
func EvalN(e Expression) int {
switch t := e.(type) {
case NumExpr:
num, _ := strconv.Atoi(t.literal)
return num
}
return 0
}
func Eval(e Expression) bool {
switch t := e.(type) {
case ParenExpr:
fmt.Println("Sub")
return Eval(t.SubExpr)
case UnaryExpr:
fmt.Println(t.operator)
right := Eval(t.right)
switch t.operator {
case "!":
return ! right
}
case AssocExpr:
fmt.Println("Assoc")
left := Eval(t.left)
right := Eval(t.right)
switch t.operator {
case "||":
return left || right
case "&&":
return left && right
}
case BinOpExpr:
fmt.Println("BinOp")
left := EvalN(t.left)
right := EvalN(t.right)
switch t.operator {
case ">":
return left > right
case "<":
return left < right
case "=":
return left == right
}
default:
fmt.Printf("unsuported expr[%+v]", t)
}
return false
}
func Parse(exp string, vars map[string]interface{}) bool {
l := new(Lexer)
l.Vars = vars
l.Init(strings.NewReader(exp))
yyParse(l)
return Eval(l.result)
}
func main() {
vars := map[string]interface{}{
"A": 1,
"B": 1,
}
f := Parse("NOT (A IS B)", vars)
fmt.Printf("%t\n", f) // false
t := Parse("A IS B", vars)
fmt.Printf("%t\n", t) // true
}
@tkrs
Copy link
Author

tkrs commented Feb 13, 2018

goyacc-tut λ goyacc parser.go.y
Parse table entries: 105 of 368, x 8 bits == 105 bytes
goyacc-tut λ ls
parser.go.y y.go        y.output
goyacc-tut λ go run y.go
!
Sub
BinOp
false
BinOp
true

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment