Go言語 - PEGで構文解析 - 構文木の作成

PEGで構文木を作成するプログラムを書いてみました。
簡易化の為に、識別子（ident）と代入演算子（=）と加算演算（+）のみ解析して、ポーランド表記で出力します。

構文

root <- expression EOT /
        expression <.+> EOT /    エラー用
        <.+> EOT                 エラー用

EOT <- !.

expression <- assign / 
              additive

assign     <- ident <'='> expression

additive   <- factor ( <'+'> factor )*

factor     <- '(' expression ')' /
              ident

ident      <- <[0-9a-zA-Z]+>

goyaccでは、演算子に結合方向や優先順位を指定できましたが、PEGではできないようなので構文のなかで記述します。
代入演算子は右結合であるためassignの構文にて'='の右側にassign自身（とadditive）が来るようにして、"="の右側を先に評価するようにしています。加算演算子は左結合の為、additiveの構文においてadditiveより優先順位の高いfactorを加算演算子で接続して左から順に評価するようにしています。

構文木の作成

構文木の枝葉を構成する構造体としてNode型を定義しています。フィールド変数Kindにノードの種類、構文木の葉の場合はValueにident名を保存し、枝の場合は子となるNodeへのポインタをLeft/Rightに保存します。関数String() string はNode型構造体をPrintしたときにポーランド表記で表示させるための処理です。
各構文のアクションとして、parserがidentを検出した場合には葉となるノードを作成してAST型構造体（p.a）内部のstackに積みます。

ident      <- <[0-9a-zA-Z]+>  { n := p.a.NewValue(text)
                                p.a.Push(n)
                              } /

構文assign, additiveの場合は演算子で右側の要素が評価された時点でstackのトップと2段目に積まれているNodeを取り立し、新たに作成したNodeの子にし、その新しいNodeを改めてstackに積みます。
また演算子の文字列を読み取るためにAST構造体に演算子用stack(opstack)を用意して、演算子の評価の直後に取得した演算子文字列を積んでいます。読み取った演算子文字列はノード作成時にとりだしてNode構造体のフィールド変数Valueに保存します。

assign     <- ident <'='>       { p.a.PushOp(text)}
                    expression  { n2 := p.a.Pop()
                                  n1 := p.a.Pop()
                                  n := p.a.NewNode(NodeAssign, n1, n2)
                                  p.a.Push(n)
                                }

ast.peg

package main

type Parser Peg {
    a AST
}

root <- expression EOT  { p.a.root = p.a.Pop() } /
        expression <.+> { p.a.Err(begin) } EOT /
        <.+>            { p.a.Err(begin) } EOT

EOT <- !.

expression <- assign / 
              additive

assign     <- ident <'='>       { p.a.PushOp(text)}
                    expression  { n2 := p.a.Pop()
                                  n1 := p.a.Pop()
                                  n := p.a.NewNode(NodeAssign, n1, n2)
                                  p.a.Push(n)
                                }

additive   <- factor (
                      <'+'>     { p.a.PushOp(text)}
                      factor    { n2 := p.a.Pop()
                                  n1 := p.a.Pop()
                                  n := p.a.NewNode(NodeAdd, n1, n2)
                                  p.a.Push(n)
                                } 
                     )*

factor     <- '(' expression ')' /
              ident                {// identを先にすると上手くいかない?
                                   }

ident      <- <[0-9a-zA-Z]+>  { n := p.a.NewValue(text)
                                p.a.Push(n)
                              }

ast.go

package main

import (
    "fmt"
)

type NodeType uint8
const (
    NodeIdent    NodeType = iota + 1
    NodeAssign
    NodeAdd
)

type Node struct {
    Kind   NodeType
    Value  string
    Left   *Node
    Right  *Node
}

// 解析した式をPN表記で表示
func (self *Node) String() string {
    if self.Kind == NodeIdent {
        s := " " + self.Value
        return s
    }
    s := fmt.Sprint(" (",self.Value)
    s += self.Left.String()
    s += self.Right.String()
    s += fmt.Sprint(" )")
    return s
}

type AST struct {
    root   *Node
    stack  []*Node
    
    opstack  []string
}

func (self *AST) Push(n *Node) {
    self.stack = append(self.stack, n)
}

func (self *AST) Pop() *Node {
    var l int   = len(self.stack)
    var n *Node = self.stack[l-1]
    self.stack = self.stack[:l-1]
    return n
}

func (self *AST) PushOp(s string) {
    self.opstack = append(self.opstack, s)
}

func (self *AST) PopOp() string {
    var l int   = len(self.opstack)
    var s string = self.opstack[l-1]
    self.opstack = self.opstack[:l-1]
    return s
}


func (self *AST) NewValue(s string) *Node {
    n := new(Node)
    n.Kind = NodeIdent
    n.Value = s
    return n
}

func (self *AST) NewNode(t NodeType, l *Node, r *Node) *Node {
    n := new(Node)
    n.Kind  = t

    n.Value = self.PopOp()
    n.Left  = l
    n.Right = r
    return n
}

func (self *AST) Root() *Node {
    return self.root
}

//func (self *AST) Init() {   // Debug用にstack bottomにダミーを積む
//    n := new(Node)
//    n.Kind = NodeIdent
//    n.Value = "Stack Bottom"
//    self.Push(n)
//}

func (self *AST) Err(i int) {
    fmt.Printf("\n!!文法エラー!! (%d 文字目)\n", i)
}


func main() {
//    const s string = "a+b+c"
//    const s string = "a+(b+c)"
//    const s string = "a=b=c"
//    const s string = "a=b+c"
//    const s string = "(a=b)=c" // Error
    const s string = "a=b+(c=1+2)"

    parser := &Parser{Buffer: s}
    parser.Init()
//    parser.a.Init()
    err := parser.Parse()
    if err != nil {
        fmt.Println(err)
    } else {
        parser.Execute()
        root := parser.a.Root()
        fmt.Println("入力:", s)
        fmt.Println("出力:", root)
    }
}

実行結果

入力: a+b+c
出力:  (+ (+ a b ) c )


入力: a+(b+c)
出力:  (+ a (+ b c ) )


入力: a=b=c
出力:  (= a (= b c ) )


入力: a=b+c
出力:  (= a (+ b c ) )


!!文法エラー!! (5 文字目)
入力: (a=b)=c
出力: <nil>


入力: a=b+(c=1+2)
出力:  (= a (+ b (= c (+ 1 2 ) ) ) )