プログラミング言語の日記01：関数適用の構文解析

日記をつけてみようと思います。今日は一回目。続くかな？続かない気がする。 一発書きです。技術的な正確性は大目に見てください。間違いを見つけたらコメントで補足などしてもらえると助かります。

再帰下降構文解析で、以下のような関数適用をうまくパースしたい。

List(1, 2, 3).map(x => add(1)(x))

こんな文法を考えると、うまくいきそうに思う。

term = variable | literal ;
expr = term
     | expr "(" expr ("," expr)* ")"
     | expr "." ident
     ;

再帰下降構文解析を実装するときは、まず左再帰除去を行う。 さっきの文法を左再帰除去するとこんな感じ。

expr = term exprTail ;

exprTail = ε
         | "(" expr ("," expr)* ")" exprTail
         | "." ident exprTail
         ;

この文法を実装すると、だいたいこんな感じ。 簡単だけど、↑の文法と↓の文法が一対一で対応している！って感じはしない。

func (p *Parser) expr() Node {
    term := p.term()
    return p.exprTail(term)
}

func (p *Parser) exprTail(expr Node) Node {
    if p.peek() == "(" {
        arguments := p.arguments()
        return p.exprTail(Apply { expr, arguments })
    } else if p.peek() == "." {
        name := p.ident()
        return p.exprTail(Project { expr, name })
    }
    return expr
}

改めてお題に戻る。 ↓のコードをグッと睨むと、関数適用(1, 2, 3)やフィールドアクセス.mapが、後置演算子に見えてこないだろうか。 後置演算子は、i++みたいなやつ。見えてこない？

List(1, 2, 3).map(x => add(1)(x))

見えたとします。関数適用は後置演算子だ！って考えで文法を書くとこうなる。

expr = term exprTail+ ;

exprTail = "(" expr ("," expr)* ")"
         | "." ident
         ;

さっきの文法と比べると、意味は同じだけどスッキリしている。

-expr = term exprTail ;
+expr = term exprTail+ ;

-exprTail = ε
-      | "(" expr ("," expr)* ")" exprTail
-      | "." ident exprTail
-      ;
+exprTail = "(" expr ("," expr)* ")"
+         | "." ident
+         ;

実装もしやすい。

func (p *Parser) expr() Node {
    term := p.term()
    for p.peek() == "(" || p.peek() == "." {
        term = p.exprTail(term)
    }

    return term
}

func (p *Parser) exprTail(expr Node) Node {
    if p.peek() == "(" {
        arguments := p.arguments()
        return Apply { expr, arguments }
    } else if p.peek() == "." {
        name := p.ident()
        return Project { expr, name }
    }
}

以前のコードではexprTailは再帰関数だった。 一方、今回のコードではexpr内でループ呼び出ししている。 しかも「関数適用は後置演算子」と思いながら直感的に書いた文法と一対一で対応している！

最近は「関数適用は後置演算子」戦略でパーサーを書くことが多い。 多分、これを発展させるとPrattパーサーみたいな話が出てくるのかな。