hakeの日記

Windows環境でプログラミングの勉強をしています。

Go言語 - goyaccで構文解析

program golang

Go言語にはgoyaccという構文解析ツールがあるので一番単純な整数の四則演算を行うプログラムを作成してみました。
以下は作成のポイントとなるメモです。

参考サイト

lex.Lexer（lex/lexer.go）

先日作成した字句解析プログラムを少し修正してpackage lexとする。修正点は以下のとおり。

  • Scan()メソッドはトークン種別（int）を返す様に変更した。またEOFの場合はゼロを返す。
  • トークンの位置と文字列を取得するメソッドを追加した。
func (self *Lexer)Scan() int
func (self *Lexer)Text() string
func (self *Lexer)Line() int
func (self *Lexer)Column() int

Lexer（paeser.go.y）

goyaccから呼ばれるLexerを定義し、そこにlex.Lexerを埋め込みます。フィールド変数resultは構文解析の結果を格納しmain関数に渡す変数（今回は整数演算なのでint型）で、cLineとcColはエラー時に表示する位置を格納しています。
LexerはParserのyyParseで使用する為に、interface型として、LexメソッドとErrorメッソドを定義する必要があります。

type Lexer struct {
	lex.Lexer
	result  int
	cLine   int
	cCol    int
}

func (l *Lexer) Lex(lval *yySymType) int
func (l *Lexer) Error(e string)

Lexメソッドの戻り値は各トークンの種別(int)になります。ただし、ここで使用されるトークン種別は、後述の%tokenで定義された独自の値（int）が割り振られる為にlex.Lexer.Scan()が返す値を、この値に変更する必要があります。

func (l *Lexer) Lex(lval *yySymType) int {
	token := l.Scan()
	if token == lex.NUMBER {
		token = NUMBER
	}
          ……
	return token

Lexメソッドの引数yySymTypeは、%union{…}で定義したフィールド変数をメンバに持つ構造体となります。Lexメソッドが呼ばれるごとに必要に応じて取得したトークンの情報をyySymTypeに渡します。

func (l *Lexer) Lex(lval *yySymType) int {
	token := l.Scan()
          ……
	lval.token = Token{token: token, literal: l.Text()}
          ……
	return token
}

Parser部（paeser.go.y）

トークンおよび構文の中で使用する型を定義しています。

%union{
	token Token
	num   int
}

構文の中の各非終端記号（type）と終端記号（token）の型を定義しています。<…>が%unionで定義したフィールド変数名になります。

%type<num> program
%type<num> expr
%token<token> NUMBER

構文のトップでLexrerのフィールド変数resultに結果を代入して、main()に渡します。

program
	: expr
	{
		$$ = $1
		yylex.(*Lexer).result = $$
	}


その他は基本的にc言語で使用するyacc(bison)と同じ記述になります。

parser.go.y

%{
package main

import (
	"os"
	"strconv"
	"fmt"
	"./lex"
)

type Token struct {
	token   int
	literal string
}
%}

// yySymType型の定義（Lexerの引数として使用する）
%union{
	token Token
	num   int
}

// 非終端記号、終端記号の型の定義
%type<num> program         // <...>はunionのメンバ名
%type<num> expr mnumber
%token<token> NUMBER

// 一文字の終端記号は文字がそのまま使用可能
// 演算子の結合方向の定義
// 下に書いた方が優先順位が高い
%left '+', '-'
%left '*', '/'
%left NEG

%%

program
	: expr                              // EOFは書かない。
	{
		$$ = $1
		yylex.(*Lexer).result = $$  // 演算結果をLexerに戻す。
	}

mnumber
	: '-' NUMBER %prec NEG
	{
		$$, _ = strconv.Atoi($2.literal)
	}

expr
	: NUMBER
	{
		$$, _ = strconv.Atoi($1.literal)  // NUMBERトークン時に数字文字列を数値に変換する
	}
	| mnumber
	{
		$$ = -$1
	}
	| expr '+' expr
	{
		$$ = $1 + $3
	}
	| expr '-' expr
	{
		$$ = $1 - $3
	}
	| expr '*' expr
	{
		$$ = $1 * $3
	}
	| expr '/' expr
	{
		$$ = $1 / $3
	}
	| '(' expr ')'
	{
		$$ = $2
	}

%%

type Lexer struct {
	lex.Lexer
	result  int    // 構文のTOPでここに評価結果が代入される。
	cLine   int    // 現在の行（エラー表示に使用）
	cCol    int    // 現在のカラム（同上）
}

func (l *Lexer) Lex(lval *yySymType) int {
	token := l.Scan()
	if token == lex.NUMBER {   // Lexerのトークン種別（int値）を
		token = NUMBER     // %tokenで定義した値に変換する。
	}
	lval.token = Token{token: token, literal: l.Text()}
	l.cLine = l.Line()
	l.cCol  = l.Column()
	return token
}

func (l *Lexer) Error(e string) {
	fmt.Fprintf(os.Stderr, "line %d(%d) : %s\n", l.cLine, l.cCol, e)
	os.Exit(1)
}

func main() {
	fp, err := os.Open("test.txt")
	if err != nil{
		fmt.Fprintln(os.Stderr, "File cannot open")
		os.Exit(1)
	}
	defer fp.Close()

	l := new(Lexer)
	l.Init(fp)

	yyParse(l)

	fmt.Printf("result: %d\n", l.result)
}

lex/lexser.go

package lex

import (
	"bufio"
	"io"
)

const (
	IDENT = -(iota + 2)
	NUMBER
	STRING
	OTHER
	VAR
	INT
)

var TokenTable = map[string]int{
	"var": VAR,
	"int": INT,
}

type Lexer struct{
	r         *bufio.Reader
	buffer    string  // トークンのリテラル格納
	line      int     // トークンのある行
	col       int     // トークン開始カラム
	pos       int     // 現在カラム位置
	ch        rune    // 現在の文字
	kind      int     // トークン種類
	table     map[string]int
}

func NewLexer() *Lexer {
	lx := &Lexer{}
	return lx
}

func (self *Lexer)Init(fp io.Reader) {
	self.r = bufio.NewReader(fp)
	self.buffer  = ""
	self.line    = 1
	self.pos     = -1
	self.table   = TokenTable

	self.nextChar()
}

func (self *Lexer)nextChar() {
	ch, _, err := self.r.ReadRune()
	self.pos++
	if err != nil {
		self.ch = 0
		return
	}
	self.ch = ch
}

func (self *Lexer)isNumber() bool {
	if (self.ch >= '0')&&(self.ch <= '9'){
		return true
	}
	return false
}

func (self *Lexer)isLetter() bool {
	if ((self.ch >= 'a')&&(self.ch <= 'z')) || ((self.ch >= 'A')&&(self.ch <= 'Z')) || self.ch == '_' {
		return true
	}
	return false
}

func (self *Lexer)isIDENT() bool {
	if self.isNumber() || self.isLetter() {
		return true
	}
	return false
}

func (self *Lexer)isWhiteSpace() bool {
	if self.ch == ' ' || self.ch == '\t' || self.ch == '\r' || self.ch == '\n' {
		return true
	}
	return false
}

func (self *Lexer)scanNumber() {
	var s []rune
	self.kind = NUMBER
	self.col = self.pos
	s = append(s, self.ch)
	self.nextChar()
	for self.isNumber() {
		s   = append(s, self.ch)
		self.nextChar()
	}
	self.buffer = string(s)
}

func (self *Lexer)scanIDENT() {
	var s []rune
	self.kind = IDENT
	self.col = self.pos
	s = append(s, self.ch)
	self.nextChar()
	for self.isIDENT() {
		s   = append(s, self.ch)
		self.nextChar()
	}
	ss := string(s)
	if v, b := self.table[ss]; b {
		self.kind = v
	}
	self.buffer = string(ss)
}

func (self *Lexer)scanString() {
	var s []rune
	self.kind = STRING
	self.col = self.pos
	self.nextChar()
	for self.ch != '"' {
		s   = append(s, self.ch)
		self.nextChar()
	}
	self.nextChar()
	self.buffer = string(s)
}

func (self *Lexer)skipWhiteSpace() {
	for self.isWhiteSpace() {
		if self.ch == '\n' {
			self.line++
			self.pos = -1
		}
		self.nextChar()
	}
}


func (self *Lexer)Scan() int {
	self.buffer = ""
	self.skipWhiteSpace()

	switch{
	case self.isNumber():
		self.scanNumber()
	case self.isLetter():
		self.scanIDENT()
	case self.ch =='"':
		self.scanString()
	default:
		switch {
		case self.ch < 0x80: // 1文字演算子, EOF( = 0)
			self.kind = int(self.ch)
			self.buffer = string(self.ch)
		default:
			self.kind = OTHER
			self.buffer = string(self.ch)
		}
		self.col = self.pos
		self.nextChar()
	}
	return self.kind
}

func (self *Lexer)Text() string {
	return self.buffer
}

func (self *Lexer)Line() int {
	return self.line
}

func (self *Lexer)Column() int {
	return self.col
}

コンパイル、実行

go tool yacc -o parser.go parser.go.y
go run parser.go

結果

  • test.txt
(1+2)
*-3
  • 結果
result: -9
  • test.txt(文法エラー時）
(1+2)
**-3
  • 結果
line 2(1) : syntax error
exit status 1