1つの式に2つの答え
在庫を数えるスクリプトが、2 + 3 * 4 を計算します。テストした1人は14だと言い、もう1人は20だと言います。
2人とも、同じトークンを同じ順に読んでいます。違うのは、まとめ方です。コンパイラは、いつも同じ1通りでまとめなければなりません。そのまとめ方を書き下したものが文法です。
このレッスンのゴール
メモ
トークンから構文木を組み立てられる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| 文法 | どんなトークンの並びを許すかの規則 | |
| 構文木 | トークンのまとまり方を表す木 | |
| パーサー | 構文木を組み立てる、コンパイラの部分。構文解析器とも言う | |
| 優先順位 | どの演算子が先にまとまるか | * は + より先 |
| 結合性 | 同じ強さの演算子が、どちら側からまとまるか | 左結合 |
| 再帰下降 | 規則1つに関数1つを書くパーサー |
学生が入力するセルは、このプレビューでは空白です。
文法がトークンのまとまり方を決める
文法は短い規則の一覧です。規則は、文のある部分に名前を付け、何からできているかを言います。
下の3つの規則は、* と / に、+ と - より高い優先順位を与えます。和は積からできているので、積が先にまとまります。かっこの中は一番上の規則からやり直すので、かっこで順番を変えられます。
例: 式のための3つの規則
| 規則 | 何からできているか | 例 |
|---|---|---|
| expr | term のあとに、+ か - と term が何回でも続く | 2 + 3 * 4 |
| term | factor のあとに、* か / と factor が何回でも続く | 3 * 4 |
| factor | 数か、かっこで囲んだ expr | 4 や (2 + 3) |
学生が入力するセルは、このプレビューでは空白です。
規則1つに関数1つ
再帰下降のパーサーは、規則ごとに関数を1つ持ちます。parse_expr が parse_term を呼び、parse_term が parse_factor を呼びます。かっこがあると、parse_factor がもう一度 parse_expr を呼びます。これが再帰です。
parse_expr のループは、そこまでの木を左側に置きます。だから - は左に寄ります。デモは、そのループだけを取り出したものです。
- を左に寄せるループ
# 20 - 5 - 3 のような式の木を、左から組み立てます。
tokens = ["20", "-", "5", "-", "3"]
pos = 0
tree = int(tokens[pos])
pos = pos + 1
while pos < len(tokens):
op = tokens[pos]
right = int(tokens[pos + 1])
# ここまでの木が左側になるので、- は左に寄ります。
tree = [op, tree, right]
pos = pos + 2
print(tree)
# tokens を ["60", "/", "4", "/", "3"] に変えて、もう一度実行しましょう。
bison は文法からパーサーを作る
bison のようなパーサーの生成系は、文法を読み、C でパーサーを書きます。calc.y の規則 expr には、演算子ごとに1行あります。それだけでは、2 + 3 * 4 をどちらにもまとめられてしまいます。
それを決めるのが、%left の2行です。どちらも、その演算子が左に寄ると言います。後に書いた行ほど強く結びつくので、* と / が先にまとまります。
コンパイラのフォルダに入る
cd ~/compilerここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
電卓ができているか確かめる
makeここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
優先順位の2行
grep -n "%left" calc.yここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
- は左に寄る
echo "20 - 5 - 3" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
整数の割り算も左に寄る
echo "60 / 4 / 3" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
かっこで木が変わる
echo "2 * (3 + 4)" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
閉じていないかっこ
echo "(1 + 2" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
数が2つ並ぶ
echo "3 4" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
パーサーは左から順に計算する、と思いがちです。それなら 2 + 3 * 4 は20です。実際は、文法が木を決め、木が計算の順番を決めます。優先順位が 3 * 4 を木の下に置くので、先に計算されます。左から、が効くのは、同じ強さの演算子どうしだけです。
優先順位を取り去る
次の Run は、calc.y から %left の2行を消したコピーを作ります。そのコピーを bison に読ませます。
優先順位がないと、bison には動き方が2つあって選べない場所が、いくつもできます。そのような場所をshift/reduce の衝突と呼びます。最後の Run で、最初の衝突の例を bison に出させます。
優先順位のない文法のコピー
sed "/%left/d" calc.y > noprec.yここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
bison に作らせる
bison noprec.yここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
衝突の例を1つ見る
bison -Wcounterexamples noprec.y 2>&1 | head -n 3ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: べき乗は右に寄る
課題のパーサーに、べき乗の ^ を足しましょう。* より強く結びつき、右に寄ります。2 ^ 3 ^ 2 は 2 ^ (3 ^ 2) です。
前に付いた - と factor の間に、新しい規則を1つ足します。-2 ^ 2 の木がどうなるべきかも決めましょう。そして、parse_expr と同じループでは、なぜ正しい木にならないかを説明しましょう。