二つの数で解く優先順位 — Pratt パーシング

一言でいうと

パーサーは、トークンの並びを木に組み立てます。文は、文法規則1つにつき関数を1つ置く再帰下降で、式は、演算子ごとに結合力(数値1つ)を置き、その数値を比べながら木を育てるPrattパーシングで読みます。そうすると、優先順位と結合の方向が表1枚に集まり、エラーが起きても、次の文から読み直せます。

なぜ必要なのか

1 - 2 - 3は(1 - 2) - 3なので-4で、2 ^ 3 ^ 2は2 ^ (3 ^ 2)なので512です。同じ形なのに、結びつける方向が逆です。-2 ^ 2は-4ですが、-2 * 2は(-2) * 2です。この規則がずれると、プログラムは文法エラーなしに別の値を計算します。いちばん見つけにくい種類のバグです。

文法規則ごとに関数を1つ置く再帰下降(덧셈 := 곱셈 (('+'|'-') 곱셈)*のように。プレースホルダーは加算と乗算です)でも式は読めますが、優先順位の層ごとに関数が1つずつ増え、層が10個なら関数も10個になり、層を1つ挟むには関数の連鎖を直さなければなりません。Prattパーシングは、これを表1枚に減らします。層は数値で、結合の方向は、右を読むときにその数値をそのまま使うか、1つ下げるかです。

そして、パーサーは最初のエラーで止まってはいけません。ユーザーは、エラーを1つ直して再実行し、次のエラーを見るという作業を繰り返したくありません。エラーを控えておき、次の文が始まりそうなところまで読み飛ばしてから読み続ければ、1回で複数のエラーを知らせられます。

どう動くのか

Prattパーサーの心臓部は、ループ1つです。

expression(rbp):
    left = prefix()                      # 숫자·이름·괄호·앞에 붙는 - !
    while 다음 연산자의 결합력 > rbp:
        left = infix(left)               # 그 연산자로 left 를 왼쪽 자식 삼아 한 층 위 노드를 만든다
    return left

infixは、右のオペランドをexpression(그 연산자의 결합력)で読みます(プレースホルダーはその演算子の結合力です)。すると、右の式は自分より強い演算子だけを飲み込み、同じ層の演算子の手前で止まって、外側のループに渡します。それが左結合です。右結合(^、=)は、右を결합력 - 1で読み(プレースホルダーは結合力です)、同じ層まで右が飲み込むようにします。1 - 2 * 3 - 4で木が育つ様子は次のとおりです(-は6、*は7)。

읽은 것            left 의 모양               다음 연산자  비교
1                  1                          -  6 > 0     → infix: 오른쪽을 expression(6) 으로
  2 * 3            (* 2 3)                    -  6 > 6 ?   → 아니오, 오른쪽은 여기서 멈춤
1 - (2*3)          (- 1 (* 2 3))              -  6 > 0     → infix 한 번 더, 방금 트리가 왼쪽 자식으로
  4                4                          끝
최종               (- (- 1 (* 2 3)) 4)

この言語の結合力の表です。前に付く-・!はオペランドを8で読むので、*(7)は飲み込めず、^(9)は飲み込みます。そのため、-a*bは(-a)*b、-a^bは-(a^b)です。

結合力	演算子	結合
1	`=`	右
2・3	`\|\|`・`&&`	左
4・5	`== !=`・`< <= > >=`	左
6・7	`+ -`・`* / %`	左
8	前に付く`-` `!`	—
9・10	`^`・呼び出し`f(…)`	右・—

代入は右結合であり、左辺が名前でなければなりません。a = b = cはa = (b = c)で、a + b = cは(a + b) = cと読まれたあと、「代入の対象が名前ではありません」として拒否されます。この検査を抜くと、パーサーは黙っておかしな木を作ります。

文は再帰下降で読みます。ifを見ると、(、式、)、ブロック、[else(if文またはブロック)]の順に期待し、期待したトークンでなければ、そのトークンの位置で「expected ';'」のようなエラーを出します。エラーを捕まえる場所は、宣言1つ(declaration)です。捕まえたらエラーを控えて回復(synchronize)します。;の直後か、let・fn・if・while・print・return・{・}の手前まで、トークンを読み飛ばします。このとき守るべきことが1つあります。少なくとも1トークンは進める必要があります。いちばん外側の}のように、どの文も始められないトークンでエラーが起きたのに、その位置で止まると、次の宣言が同じトークンで同じエラーを出して、永遠に回り続けます。

現場での姿

GCCとClangの手書きのパーサー。どちらのコンパイラーも、パーサージェネレーター(yacc・bison)ではなく、手で書いた再帰下降パーサーを使います。エラーメッセージと回復を、人が細かく磨けるからです。式の部分は、優先順位の表で読む方式(演算子順位構文解析)が、Prattと同じ考え方です。
1回で複数のエラー。コンパイラーがエラーを20個ずつ見せるのに、後ろのものが的外れなら、回復が足りていません。最初のエラーのあと、間違った場所から読み直し始めて、正常なコードをエラーとして読んだ「連鎖エラー」です。そのため、ほとんどのコンパイラーが「最初のエラーから直してください」と言います。
エディターの寛容なパーサー。エディターの言語サーバーは、入力しているあいだ、常に文法の間違ったコードを受け取ります。回復の優れたパーサーだからこそ、書きかけの関数の下のコードでも、自動補完と下線が正しく動きます。

次のラボですること

parser.pyに、パーサーを7つの部品として作ります。トークンを見て・消費して・期待する道具、リテラル・名前・括弧、Prattのループと二項演算、前置演算子と右結合(^・=)と代入対象の検査、呼び出し、文とブロック、そしてエラー回復です。木の形はast_nodes.py(コースが渡します)のノードとS式で決まっていて、採点ツールが、ランダムな式数百個の木とノードの位置を、基準のパーサーと文字単位で突き合わせます。