PegjsでAltjsを作る 第3回 計算の式と項

今回はpegjsで 3 + 4 * (5 + 6) みたいな式をパースすることを目標にします。

注意！

今回は pegjs-coffee-plugin https://npmjs.org/package/pegjs-coffee-plugin を使って、PEG.jsのブロックの中はcoffeescriptで記述しています。僕が楽だからです。

Lispの木は構文木

まずLispの話をします。Lispは構文木そのものだからです。
まず、計算式を表す前提として、慣れ親しんだ掛け算と括弧による優先順位を付けねばなりません。

3 + 4 * (5 + 6) をLispで表現すると、次の様になります

(+ 3 (* 4 (+ 5 6)))

Lispでは計算順は自明です。

ここでルールを明文化しましょう。

• 式は複数の項で表現される
• 項は * か / 、または(...)で結合される値のグループである

これをPEG.jsで表してみましょう

全文

start = Program
Symbol = $([a-zA-Z] [a-zA-Z0-9]*)
Number = $(("+" / "-")? _ [1-9] [0-9]* ("." [0-9]+)? )
Whitespace = [\t\v\f \u00A0\uFEFF]
LineTerminator = [\n\r\u2028\u2029]
_  = (Whitespace / LineTerminator)*
__ = Whitespace+

Program = AdditiveStatement
AdditiveOperator = "+" / "-"
AdditiveStatement = head:Term tail:(_ op:AdditiveOperator _ term:Term { op:op, term:term })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.term
    root
  }

MulticativeOperator = "*" / "/"
Term
  = head:Primary tail:(_ op:MulticativeOperator _ primary:Primary { op:op, primary:primary })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.primary
    root
  }
  / Primary

Primary
  = "(" _ statement:AdditiveStatement _ ")" { statement }
  / Value

Value
  = symbol:Symbol { identifier:symbol }
  / number:Number { {number} }

結果

入力

3 + 4 * (5 + 6)

出力

left:
  number: 3
op:    +
right:
  left:
    number: 4
  op:    *
  right:
    left:
      number: 5
    op:    +
    right:
      number: 6

解説

最初のはおまじないというか頻出パターンのスニペット

Symbol = $([a-zA-Z] [a-zA-Z0-9]*)
Number = $(("+" / "-")? _ [1-9] [0-9]* ("." [0-9]+)? )
Whitespace = [\t\v\f \u00A0\uFEFF]
LineTerminator = [\n\r\u2028\u2029]
_  = (Whitespace / LineTerminator)*
__ = Whitespace+

_ で間に挟まるスペースを表現します。あと識別子と数値型。
小さな単位から見て行きましょう。

括弧

Primary
  = "(" _ statement:AdditiveStatement _ ")" { statement }
  / Value

Value
  = symbol:Symbol { identifier:symbol }
  / number:Number { {number} }

AddtiveStatementはこの式全体を再帰した表現です。()で囲われた式、ということで優先順位をつけます。
あるいは単体のValue。そしてValueはシンボルか数値で表される、というわけです。

項

MulticativeOperator = "*" / "/"
Term
  = head:Primary tail:(_ op:MulticativeOperator _ primary:Primary { op:op, primary:primary })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.primary
    root
  }
  / Primary

Primary句を * か / で結合したもの。あるいはPrimaryそのもの。

式

AdditiveOperator = "+" / "-"
AdditiveStatement = head:Term tail:(_ op:AdditiveOperator _ term:Term { op:op, term:term })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.term
    root
  }

Additiveは T [, T]* という形になります
headをrootにして、構文木を「上に」向けて作っていきます。こうしないと + と - が入り混じった式で、意味が反転したりしてしまいます。

実行したスクリプト全文

escodegen = require 'escodegen'
esprima = require 'esprima'
pj = require 'prettyjson'
PEG = require 'pegjs'
PEGjsCoffeePlugin = require 'pegjs-coffee-plugin'
PEGjsCoffeePlugin.addTo PEG
fs = require 'fs'

p = console.log.bind console

# show ast tree
get_js_ast = (code) -> pj.render esprima.parse code
json_dump = (code)-> p pj.render code

# pegjs parser
gen_parser = (src) -> PEG.buildParser src
parse_with_gen = (parser_code, code) ->
  parser = gen_parser parser_code
  parser.parse code

# pegjs parser and ast
parse_with_gen_and_escodegen = (parser_code, code) ->
  parser = gen_parser parser_code
  escodegen.generate parser.parse code

parse_with_gen_and_escodegen_exec = (parser_code, code) ->
  eval parse_with_gen_and_escodegen parser_code, code

# peg_parser = fs.readFileSync('blace.pegjs').toString()
peg_parser = """
start = Program
Symbol = $([a-zA-Z] [a-zA-Z0-9]*)
Number = $(("+" / "-")? _ [1-9] [0-9]* ("." [0-9]+)? )
Whitespace = [\\t\\v\\f \\u00A0\\uFEFF]
LineTerminator = [\\n\\r\\u2028\\u2029]
_  = (Whitespace / LineTerminator)*
__ = Whitespace+

Program = AdditiveStatement
AdditiveOperator = "+" / "-"
AdditiveStatement = head:Term tail:(_ op:AdditiveOperator _ term:Term { op:op, term:term })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.term
    root
  }

MulticativeOperator = "*" / "/"
Term
  = head:Primary tail:(_ op:MulticativeOperator _ primary:Primary { op:op, primary:primary })*
  {
    root = head
    while node = tail.shift()
      root =
        left : root
        op   : node.op
        right: node.primary
    root
  }
  / Primary

Primary
  = "(" _ statement:AdditiveStatement _ ")" { statement }
  / Value

Value
  = symbol:Symbol { identifier:symbol }
  / number:Number { {number} }
"""

code = """
3 + 4 * (5 + 6) / 2
"""

p '-----------' + new Date
data = parse_with_gen peg_parser, code
p code
p pj.render data