let式の構文解析
導入
<digit> ::= [0-9]
<alphabet> ::= [a-zA-Z]
<int> ::= <digit> | <digit><int>
<id> ::= <alphabet> | <id>
<expr> ::= <int>
| <id>
| '(' <expr> ')'
| "let" <id> '=' <expr> "in" <expr>
| <expr> '+' <expr>さて、この文法には２つの曖昧性がある。一つは足し算の結合性、もう一つはlet式と足し算の優先順位の曖昧性だ。
1 + 2 + 3 =>
(+ (+ 1 2) 3)
| (+ 1 (+ 2 3))
let x = 1 in 2 + 3 =>
(let (x 1) (+ 2 3))
| (+ (let (x 1) 2) 3)ここでは曖昧性を解決するために足し算は左結合とし、足し算がlet式に優先するとしたい。
そのような文法はPEG*2で以下のように表現できる。
INT <- [0-9]+
ID <- [a-zA-Z]+
P <- INT / ID / '(' E ')' / "let" ID '=' E "in" E
E <- E ('+' P)*今回の記事ではこのような文法を曖昧性のない文脈自由文法で定義してみる。
最初の試み
自然に考えられる文法として以下のようなものがある。
<prim> ::= <int> | <id> | '(' <expr> ')'
<term> ::= <prim> | <term> '+' <prim>
<expr> ::= <term> | "let" <id> '=' <expr> "in" <expr>この文法は上の二つの例を正しくパーズする。
1 + 2 + 3 => (+ (+ 1 2) 3) let x = 1 in 2 + 3 => (let (x 1) (+ 2 3))
しかし、この文法は期待する言語を表現していない。例えば次のような式をパーズできない。
1 + let x = 1 in x => Error!
次の試み
上の例からprimがlet式を含まなければならないということがわかった。
しかしprim '+' exprとなっている場合はprimがlet式を含んでいてはならない。
つまり、足し算の第２オペランドにlet式が出現できるかどうかを区別する必要が有る。
<atom> ::= <int> | <id> | '(' <expr> ')'
<prim> ::= <atom> | "let" <id> '=' <expr> "in" <expr>
<term> ::= <atom> | <term> '+' <atom>
<expr> ::= <prim> | <term> '+' <prim>この文法は期待する言語を表現する。
1 + let x = 1 in x => (+ 1 (let (x 1) x)) 1 + let x = 1 in 1 + 2 => (+ 1 (let (x 1) (+ 1 2))) 1 + (let x = 1 in x) + 3 => (+ (+ 1 (let (x 1) x)) 3)
yaccによる動作確認
この文法に曖昧性がないことを確かめるためにyaccに書き下す。
Parsing
yaccがconflictを出さなかったのでこの文法は曖昧でない。
ちなみに動作例。
$ ocamlbuild main.native $ ./main.native 1 + let x = 1 in x + x Plus(1, Let(x, 1, Plus(x, x))) 1 + 2 + 3 Plus(Plus(1, 2), 3) 1 + (2 + 3) Plus(1, Plus(2, 3)) (let x = 1 in let y = 2 in x + y) + 3 Plus(Let(x, 1, Let(y, 2, Plus(x, y))), 3)
yaccのPrecedenceについて
上のようなパーサはyaccのPrecedenceを適切に設定することによっても得ることができる。
gist114a58bce2ab6af47926
このPrecedenceがどう働くかは
http://dinosaur.compilertools.net/yacc/
に記述がある。
The precedences and associativities are used by Yacc to resolve parsing conflicts; they give rise to disambiguating rules. Formally, the rules work as follows:
1. The precedences and associativities are recorded for those tokens and literals that have them.
2. A precedence and associativity is associated with each grammar rule; it is the precedence and associativity of the last token or literal in the body of the rule. If the %prec construction is used, it overrides this default. Some grammar rules may have no precedence and associativity associated with them.
3. When there is a reduce/reduce conflict, or there is a shift/reduce conflict and either the input symbol or the grammar rule has no precedence and associativity, then the two disambiguating rules given at the beginning of the section are used, and the conflicts are reported.
4. If there is a shift/reduce conflict, and both the grammar rule and the input character have precedence and associativity associated with them, then the conflict is resolved in favor of the action (shift or reduce) associated with the higher precedence. If the precedences are the same, then the associativity is used; left associative implies reduce, right associative implies shift, and nonassociating implies error.
要約すると、各ruleの一番最後に現れるtokenのprecedenceをそのruleのprecedenceとし、パーサを構成する過程でconflictが起こったところでprecedenceの高いruleを選択するという仕組みのようだ。
どうにもad-hocに思えてならないのだが、上手くいく裏付けが何かあるのだろうか。
