goyaccでparserを生成しLispのcons,car,cdrの式を評価する

2019-10-15 golang language lisp

GoでLispのcons,car,cdrの式を評価したい。流れとしては字句解析器(lexer, tokenizer, scanner)でソースコードを分割しtoken列にして、構文解析器(parser)で構文木を作るなりして評価できるようにする。

$ brew install clisp
$ clisp
> (cons 1 ())
(1)
> (cons () 1)
(NIL . 1)
> (car (cons 1 (cons 2 3)))
1
> (cdr (cons 1 (cons 2 3)))
(2 . 3)

Goの字句解析器と構文解析器

Goの字句解析器と構文解析器がGoが実装されているので見てみる。

go/scanner

ソースコードを分割してgo/tokenにする。

package main

import (
	"fmt"
	"go/token"
	"go/scanner"
)

func main() {
	var sc scanner.Scanner
	src := []byte(`("A" + "B") + "C"`)
	errorHandler := func(pos token.Position, msg string) { fmt.Printf("ERROR %v %v\n", pos, msg)}
	sc.Init(token.NewFileSet().AddFile("", -1, len(src)), src, errorHandler, 0)
	fmt.Printf("%6v %6v %6v\n", "pos", "tok", "lit")
	for {
		pos, tok, lit := sc.Scan()
		if tok == token.EOF {
			break
		}
		fmt.Printf("%6v %6v %6v\n", pos, tok, lit)
	}
}

pos    tok    lit
  1      (       
  2 STRING    "A"
  6      +       
  8 STRING    "B"
 11      )       
 13      +       
 15 STRING    "C"
 18      ;

実装を見ていく。

まずskipWhitespace()でスペースやタブなどを無視して読み進める(next())。その後、見ている文字(s.ch)によってどう読み進めるかを判断する。

func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) {
scanAgain:
	s.skipWhitespace()

	// current token start
	pos = s.file.Pos(s.offset)

	// determine token value
	insertSemi := false
	switch ch := s.ch; {
	case isLetter(ch):
		...
	default:
		s.next() // always make progress
		switch ch {
		case -1:
			if s.insertSemi {
				s.insertSemi = false // EOF consumed
				return pos, token.SEMICOLON, "\n"
			}
			tok = token.EOF
		case '"':
			...
		}
	}
	if s.mode&dontInsertSemis == 0 {
		s.insertSemi = insertSemi
	}

	return
}

文字列だったら(isLetter()=true)、 scanIdentifier()で文字列の最後まで読み進めて、 Lookup()で trueやbreakといったキーワードなのか、そうでないのか(token.IDENT)を判定する。

case isLetter(ch):
    lit = s.scanIdentifier()
    if len(lit) > 1 {
        // keywords are longer than one letter - avoid lookup otherwise
        tok = token.Lookup(lit)
        switch tok {
        case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
            insertSemi = true
        }
    } else {
        insertSemi = true
        tok = token.IDENT
    }

"はscanString()で次の"が来るまで中身をstringとして読み進める。

case '"':
    insertSemi = true
    tok = token.STRING
    lit = s.scanString()

+や-は++や+=かもしれないので次の文字を見て判断したり、

case '+':
    tok = s.switch3(token.ADD, token.ADD_ASSIGN, '+', token.INC)
    if tok == token.INC {
        insertSemi = true
    }

.は...かもしれないのでさらにその次の文字まで見ていたりする。

case '.':
    // fractions starting with a '.' are handled by outer switch
    tok = token.PERIOD
    if s.ch == '.' && s.peek() == '.' {
        s.next()
        s.next() // consume last '.'
        tok = token.ELLIPSIS

go/parser

go/astを生成する。

package main
    
import (
    "fmt"
    "go/ast"
    "go/parser"
)

func f(a string) string {
    return "X"
}

func main() {
    exprs := []string{
        "1 + 1",
        "true || !false",
        `(1 + 1) * f("A")`,
		"X ((Y))))",
    }
    for _, e := range exprs {
        expr, err := parser.ParseExpr(e)
        if err != nil {
            fmt.Printf("%s => %s", e, err)
            continue
        } 
        if be, ok := expr.(*ast.BinaryExpr); ok {
            fmt.Printf("%s => %T(%+v) %T(%+v) %T(%+v)\n", e, be.X, be.X, be.Op, be.Op, be.Y, be.Y)
        }
    }
}

1 + 1 => *ast.BasicLit(&{ValuePos:1 Kind:INT Value:1}) token.Token(+) *ast.BasicLit(&{ValuePos:5 Kind:INT Value:1})
true || !false => *ast.Ident(true) token.Token(||) *ast.UnaryExpr(&{OpPos:9 Op:! X:false})
(1 + 1) * f("A") => *ast.ParenExpr(&{Lparen:1 X:0xc00006a1b0 Rparen:7}) token.Token(*) *ast.CallExpr(&{Fun:f Lparen:12 Args:[0xc0000720c0] Ellipsis:0 Rparen:16})
X ((Y)))) => 1:8: expected 'EOF', found ')'

実装を見てみたが再帰の連続でかなり骨が折れた。調べてみるとgolang.org/x/tools/cmdにあるgoyaccを使うと文法からparserを生成できるようなのでこれを使うことにした。

goyacc

goyaccはparser generatorであるyacc(yet another compiler compiler)のGo版。

$ go get golang.org/x/tools/cmd/goyacc

yacc文法ファイルexpr.yに対して実行すると y.goができる。実行すると入力を受け付け、式を評価して表示するが、これはgoyaccの機能ではなく文法ファイルに書いてある挙動。

$ wget https://raw.githubusercontent.com/golang/tools/gopls/v0.1.7/cmd/goyacc/testdata/expr/expr.y
$ goyacc -p "expr" expr.y
$ go run y.go
> 2 * ((2 + 2) - 1) / 2
3

yacc文法ファイル

%%で区切られた3つの部分からなる。

定義部

%{と%}で囲まれた部分にコードを書けるのでpackage名やimportを書く。 %unionは取り得る型の共用体で、%token <type>で規則によってreduceされる非終端記号を、%type <type>で終端記号の種類と型を定義する。大文字と小文字は区別され、非終端記号は小文字で、終端記号は大文字にすることが多いようだ。 ''で囲まれた一文字記号はここで定義しなくても規則で使える。

%{

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"logging"
	"math/big"
	"os"
	"unicode/utf8"
)

%}

%union {
	num *big.Rat
}

%type	<num>	expr expr1 expr2 expr3

%token '+' '-' '*' '/' '(' ')'

%token	<num>	NUM

規則部

BNF(Backus-Naur Form)のような記法で、左辺: 右辺で右辺が左辺にreduceされる規則を表す。 {}の中にはコードが書けて、$$が左辺で$nが右辺のn番目のtokenになる。

top:
	expr
	{
		if $1.IsInt() {
			fmt.Println($1.Num().String())
		} else {
			fmt.Println($1.String())
		}
	}

expr:
	expr1
|	'+' expr
	{
		$$ = $2
	}
|	'-' expr
	{
		$$ = $2.Neg($2)
	}

expr1:
	expr2
|	expr1 '+' expr2
	{
		$$ = $1.Add($1, $3)
	}
|	expr1 '-' expr2
	{
		$$ = $1.Sub($1, $3)
	}

expr2:
	expr3
|	expr2 '*' expr3
	{
		$$ = $1.Mul($1, $3)
	}
|	expr2 '/' expr3
	{
		$$ = $1.Quo($1, $3)
	}

expr3:
	NUM
|	'(' expr ')'
	{
		$$ = $2
	}

ユーザ定義部

コードを書けてそのまま出力されるが、別のgoファイルに分けた方がエディタのシンタックスハイライトやエラーチェックが効くので書きやすいと思う。

...
func main() {
	in := bufio.NewReader(os.Stdin)
	for {
		if _, err := os.Stdout.WriteString("> "); err != nil {
			log.Fatalf("WriteString: %s", err)
		}
		line, err := in.ReadBytes('\n')
		if err == io.EOF {
			return
		}
		if err != nil {
			log.Fatalf("ReadBytes: %s", err)
		}

		exprParse(&exprLex{line: line})
	}
}

<prefix>Parseはgoyaccによって作られる関数で、Lex(*<prefix>SymType) intとError(string)を実装したLexerを引数に取る。

// The parser uses the type <prefix>Lex as a lexer. It must provide
// the methods Lex(*<prefix>SymType) int and Error(string).
type exprSymType struct {
    yys int
    num *big.Rat
}
type exprLexer interface {
    Lex(lval *exprSymType) int
    Error(s string)
}
func exprParse(exprlex exprLexer) int {
    return exprNewParser().Parse(exprlex)
}

Lex()は値を*<prefix>SymTypeに入れて、一文字記号はそのruneをintにキャストしたものを、それ以外のtoken(NUM)はgoyaccによって数値が割り当てられているのでそれを返す。最後まで読んだら0を返す。

const eof = 0

func (x *exprLex) Lex(yylval *exprSymType) int {
	for {
		c := x.next()
		switch c {
		case eof:
			return eof
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return x.num(c, yylval)
		case '+', '-', '*', '/', '(', ')':
			return int(c)

		// Recognize Unicode multiplication and division
		// symbols, returning what the parser expects.
		case '×':
			return '*'
		case '÷':
			return '/'

		case ' ', '\t', '\n', '\r':
		default:
			log.Printf("unrecognized character %q", c)
		}
	}
}

const NUM = 57346

func (x *exprLex) num(c rune, yylval *exprSymType) int {
        add := func(b *bytes.Buffer, c rune) {
                if _, err := b.WriteRune(c); err != nil {
                        log.Fatalf("WriteRune: %s", err)
                }
        }
        var b bytes.Buffer
        add(&b, c)
L:
        for {
                c = x.next()
                switch c {
                case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.', 'e', 'E':
                        add(&b, c)
                default:
                        break L
                }
        }
        if c != eof {
                x.peek = c
        }
        yylval.num = &big.Rat{}
        _, ok := yylval.num.SetString(b.String())
        if !ok {
                log.Printf("bad number %q", b.String())
                return eof
        }
        return NUM
}

cons,car,cdr評価器を作る

ということでcons,car,cdr評価器を作る。全体のコードはGitHubにある。

sambaiz/goyacc-carcdr-evaluator

yacc文法ファイル

文法ファイルのコードは最低限にして同じpackageのgoファイルに書いているのでユーザ定義部は空。

%{

package parser

import (
	"bytes"
	"fmt"
	"logging"
	"strconv"
)

%}

%union {
	value *Value
	num float64
}

%type <value> expr list nil atom 

%token CAR CDR CONS NIL

%token <num> NUM

%%

expr:
	list
|	atom

list:
	'(' CAR list ')'
	{
		$$ = $3.Left
	}
|	'(' CDR list ')'
	{
		$$ = $3.Right
	}
|	'(' CONS expr expr ')'
	{
		$$ = &Value{Left: $3, Right: $4}
	}
|	nil

nil:
	NIL
	{
		$$ = &Value{IsNil: true}
	}
|	'(' ')'
	{
		$$ = &Value{IsNil: true}
	}

atom: 
	NUM
	{
		$$ = &Value{Num: $1}
	}

%%

Lexer

サンプルコードをベースにcons,car,cdr,nilに対応した。

package parser

import (
	"bytes"
	"errors"
	"logging"
	"strconv"
	"unicode"
	"unicode/utf8"
)

type lexer struct {
	line []byte
	peek *rune
	err error
}

func newLexer(line []byte) *lexer {
	return &lexer{
		line: line,
	}
}

const eof = 0

func (x *lexer) Lex(yylval *exprSymType) int {
	for {
		c := x.next()
		if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z'  {
			return x.token(c, yylval)
		}
		switch c {
		case eof:
			return eof
		case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
			return x.num(c, yylval)
		case '(', ')':
			return int(c)

		case ' ', '\t', '\n', '\r':
		default:
			log.Printf("unrecognized character %q", c)
		}
	}
}

func (x *lexer) next() rune {
	...
}

func (x *lexer) num(c rune, yylval *exprSymType) int {
	...
}

var tokenMap = map[string]int{
	"car": CAR,
	"cdr": CDR,
	"cons": CONS,
	"nil": NIL,
}

func (x *lexer) token(c rune, yylval *exprSymType) int {
	add := func(b *bytes.Buffer, c rune) {
		if _, err := b.WriteRune(c); err != nil {
			log.Fatalf("WriteRune: %s", err)
		}
	}
	var b bytes.Buffer
	add(&b, unicode.ToLower(c))
	for {
		c = x.next()
		if 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' {
			add(&b, unicode.ToLower(c))
		} else {
			x.peek = &c
			break
		}
	}
	token, ok := tokenMap[b.String()]
	if !ok {
		log.Printf("unknown token %q", b.String())
		return eof
	}
	return token
}


func (x *lexer) Error(s string) {
	x.err = errors.New(s)
}

テストを書く。

package parser

import (
	"fmt"
	"github.com/stretchr/testify/assert"
	"testing"
)

func TestLexerLex(t *testing.T) {
	tests := []struct {
		expr []byte
		outs []int
		symTypes []*exprSymType
	} {
		{
			expr: []byte("123.456"),
			outs: []int{NUM},
			symTypes: []*exprSymType{
				{
					num: 123.456,
				},
			},
		},
		{
			expr: []byte("(cons 1 2)"),
			outs: []int{'(', CONS, NUM, NUM, ')'},
			symTypes: []*exprSymType{
				{},
				{},
				{
					num: 1,
				},
				{
					num: 2,
				},
				{},
			},
		},
		{
			expr: []byte("(cdr (CONS (car (cons () NIL)) 1e5))"),
			outs: []int{'(', CDR, '(', CONS, '(', CAR, '(', CONS, '(', ')', NIL, ')', ')', NUM, ')', ')'},
			symTypes: []*exprSymType{
				{},
				{}, // CDR
				{},
				{}, // CONS
				{},
				{}, // CAR
				{},
				{}, // CONS
				{},
				{},
				{}, // NIL
				{},
				{},
				{
					num: 1e5,
				},
				{},
				{},
			},
		},
	}
	for _, test := range tests {
		t.Run(fmt.Sprintf("%s -> %v", string(test.expr), test.outs), func(t *testing.T) {
			i := 0
			lexer := newLexer([]byte(test.expr))
			for {
				symType := &exprSymType{}
				char := lexer.Lex(symType)
				if char == eof {
					break
				}
				assert.Equal(t, test.outs[i], char)
				assert.Equal(t, test.symTypes[i], symType)
				i++
			}
			assert.Equal(t, i, len(test.outs))
		})
	}
}

Parser

サンプルでは直接<prefix>Parse()を呼んでいたが、評価した値を扱えるように<prefix>ParserImplからParseする。

package parser

func Parse(line string) (*Value, error) {
	exprErrorVerbose = true
	parser := &exprParserImpl{}
	lexer := newLexer([]byte(line))
	parser.Parse(lexer)
	if lexer.err != nil {
		return nil, lexer.err
	}
	if len(parser.stack) < 2 {
		return nil, nil
	}
	return parser.stack[1].value, nil
}

package parser

import (
	"github.com/stretchr/testify/assert"
	"testing"
)

func TestParse(t *testing.T) {
	tests := []struct {
		in string
		expected string
	} {
		{
			in: "123.456",
			expected: "123.456",
		},
		{
			in: "(cdr (CONS (car (cons () NIL)) 1e5))",
			expected: "100000",
		},
		{
			in: "(cons (cons 1 2) 3)",
			expected: "((1 . 2) . 3)",
		},
	}
	for _, test := range tests {
		t.Run(test.in, func(t *testing.T) {
			out, err := Parse(test.in)
			assert.Equal(t, test.expected, out.String())
			assert.Nil(t, err)
		})
	}
}

実行結果

動いた。

$ go run main.go
> (car (cdr (cons 1 (cons (cons 20 300.4) (cons 50 60)))))
(20 . 300.4)

参考

プログラミング言語 8 字句解析器(lexer)と構文解析器(parser)

第9章速習yacc