Go言語 - 式の構文解析 - 演算子順位法

再起下降法と比較してのメリットは、演算子の優先度に応じてparse関数を作成する必要がなく、演算子の優先順位・結合方向をデータとして与えるだけで良いということ。

ident1 op1 ident2 op2 ident3 op3 ……

上記のような並びの式の場合、演算子op1とop2の優先順位と結合方向を比較して、ident2がident1とペアのノードとなるか、ident3以降とペアのノードとなるかを判断する。

構文

  expr    = primary { op primary }      # { }は0回以上の繰り返し
  primary = ident | '(' expr ')'
  op      = '=' | '+' | '-' | '*' | '/' | '^'
  ident   = 'A' … 'Z' 'a' … 'z'

primaryの中のカッコの処理は、通常の再起下降法で処理。並びの演算子の比較とノードの作成は、makeNode()関数で実施している。

ソース

package main

import (
	"fmt"
	"os"
)

type Lexer struct{
	buf   string
	size  int
	pos   int
}
func NewLexer(s string) *Lexer {
	l := new(Lexer)
	l.buf = s
	l.size = len(l.buf)
	l.pos = 0
	return l
}
func (self *Lexer) Get() (byte, int) {
	if self.pos >= self.size {
		return 0, self.pos
	} else {
		idx  := self.pos
		char := self.buf[idx]
		self.pos += 1
		return char, idx
	}
}
func (self *Lexer) Peek(offset int) (byte, int) {
	if self.pos + offset >= self.size {
		return 0, self.pos + offset
	} else {
		c := self.buf[self.pos + offset]
		return c, self.pos + offset
	}
}


type NodeType uint32
const (
	NodeIdent    NodeType = iota + 128 // 識別子
	NodeOp                             // 演算子
)


type Node struct {
	Type    NodeType
	Value   byte
	Left    *Node
	Right   *Node
}
func NewNode(t NodeType, char byte) *Node {
	n := new(Node)
	n.Type = t
	n.Value = char
	return n
}


// 引数のNodeを演算子の前置記法で表示
func (self *Node)String() string {
	switch self.Type {
	case NodeIdent:  return string(self.Value)
	case NodeOp:
		s := "(" + string(self.Value)+ " "
		s += self.Left.String() + " "
		s += self.Right.String() + ") "
		return s
	default: return "表示できない要素があります。"
	}
}

// 演算子情報
type OpInfo struct {
	Rank int    // 順位
	Dir  bool   // 結合方向 左結合ならば true
}

//
//  構文
//
//    expr    = primary { op primary }
//
//    primary = ident | '(' expr ')'
//
//    op      = '=' | '+' | '-' | '*' | '/' | '^'
//
//    ident   = 'A' … 'Z' 'a' … 'z'
//
//
type Parser struct{
	lx   *Lexer
	tbl  map[byte] OpInfo
}
func NewParser(s string) *Parser {
	p := new(Parser)
	p.lx = NewLexer(s)
	p.tbl = map[byte]OpInfo{
			'=': {0, false}, // 順位低 右結合
			'+': {1, true }, //        左結合
			'-': {1, true },
			'*': {2, true },
			'/': {2, true },
			'^': {3, false}, // 順位高
			}
	return p
}
func (self *Parser) Parse() *Node {
	leftNode := self.primary()
	c, _ := self.lx.Peek(0)
	b, _ := self.isOp(c)
	for (c != 0) && b {
		leftNode = self.makeNode(leftNode)
		c, _ = self.lx.Peek(0)
		b, _ = self.isOp(c)
	}
	return leftNode
}
func (self *Parser) makeNode(leftIdentNode *Node) *Node {
	curOpNode, curOpInfo := self.readOp()
	rightIdentNode := self.primary()
	c, _ := self.lx.Peek(0)
	b, _ := self.isOp(c)
	for (c != 0) && b {
		nextOpInfo := self.peekOp(0)
		if self.compareOp(curOpInfo, nextOpInfo) {
			rightIdentNode = self.makeNode(rightIdentNode)

		} else {
			break
		}
		c, _ = self.lx.Peek(0)
		b, _ = self.isOp(c)
	}
	curOpNode.Left  = leftIdentNode
	curOpNode.Right = rightIdentNode
	return curOpNode
}
// 次の演算子が優先の場合 true
//   現演算子:左結合  &  現 <  次
//   現演算子:右結合  &  現 <= 次
func (self *Parser) compareOp(cur OpInfo, next OpInfo) bool {
	if (cur.Dir == true) && (cur.Rank < next.Rank ){
		return true
	} else if (cur.Dir == false) && (cur.Rank <= next.Rank) {
		return true
	}
	return false
}

//
// primary = ident | '(' expr ')'
//
func (self *Parser) primary() *Node {
	var node *Node
	char, idx := self.lx.Get()
	switch {
	case char == '(':
		node = self.Parse()
		if char, idx = self.lx.Get(); char != ')' {
			ErrorP("文法エラー0（ ')'ではありません）", char, idx)
		}
	case self.isIdent(char):
		node = NewNode(NodeIdent, char)
	default:
		ErrorP("文法エラー1（変数名ではありません）", char, idx)
	}
	return node
}
func (self *Parser) peekOp(i int) OpInfo {
	char, idx := self.lx.Peek(i)
	b, info := self.isOp(char)
	if b == false {
		ErrorP("文法エラー2（演算子ではありません）", char, idx)
	}
	return info
}
func (self *Parser) readOp() (*Node, OpInfo) {
	char, idx := self.lx.Get()
	b, info := self.isOp(char)
	if b == false {
		ErrorP("文法エラー3（演算子ではありません）", char, idx)
	}
	return NewNode(NodeOp, char), info
}
func (self *Parser) readIdent() *Node {
	char, idx := self.lx.Get()
	if self.isIdent(char) == false {
		ErrorP("文法エラー4（識別子ではありません）", char, idx)
	}
	return NewNode(NodeIdent, char)
}

// 演算子であるかチェック
func (self *Parser) isOp(char byte) (bool, OpInfo) {
	if info, b := self.tbl[char]; b {
		return true, info
	}
	return false, OpInfo{0, false}
}
// 変数（識別子）であるかチェック
func  (self *Parser)isIdent(char byte) bool {
	if ( char >= 'A' && char <= 'Z')||( char >= 'a' && char <= 'z') {
		return true
	}
	return false
}



func ErrorP(msg string, char byte, idx int) {
	var s string
	if char == 0 {
		s = "EOL"
	} else {
		s = string(char)
	}
	fmt.Println(msg, "char:", s, ", pos:", idx)
	os.Exit(1)
}


func main() {
	p := NewParser("a=b=c+(d=e*(f+g))")
	n := p.Parse()
	fmt.Print(n)
}

実行結果

(= a (= b (+ c (= d (* e (+ f g) ) ) ) ) )