Pratt パーサーとエラー回復を作る

目標

トークンの一覧をAST(/root/mini/ast_nodes.pyのノード)に組み立てるパーサーを作ります。式はPratt方式で、優先順位と結合の方向を表1つで扱い、文は再帰下降で読み、エラーが起きたら控えて、次の文から読み直します。

なぜ重要なのか

優先順位や結合の方向が1つでもずれると、プログラムはエラーなしに別の値を計算します。10 - 4 - 3を右から結ぶと、3ではなく9になり、だれも警告しません。そして、最初のエラーで止まるパーサーは、ユーザーに、直して再実行することをエラーの数だけさせます。

文法と木

program     := declaration* EOF
declaration := "let" IDENT "=" expr ";"  |  "fn" IDENT "(" [IDENT ("," IDENT)*] ")" block  |  statement
statement   := "print" expr ";" | "if" "(" expr ")" block ["else" (if문 | block)]
             | "while" "(" expr ")" block | "return" [expr] ";" | block | expr ";"
block       := "{" declaration* "}"
결합력      = 1(오른쪽) · || 2 · && 3 · == != 4 · < <= > >= 5 · + - 6 · * / % 7
             앞 - ! 는 피연산자를 8 로 · ^ 9(오른쪽) · 호출 ( 10
노드 위치   ast_nodes.py 맨 위 표 — 연산자 토큰, 호출은 여는 괄호, Let·Fn 은 이름 토큰, 문장은 키워드,
             Block 은 여는 중괄호, ExprStmt 는 식의 위치. && 와 || 는 Logical, 나머지 두 항은 Binary
오류 글자   ParseError(토큰, 메시지), str() 은 "줄:칸: 메시지". 위치는 기대한 것을 찾지 못한 그 토큰
             expected expression · expected ';' · expected ')' · expected '(' · expected '{' ·
             expected '}' · expected identifier · expected '=' · invalid assignment target(그 = 의 위치)
복구        declaration 이 ParseError 를 잡아 self.errors 에 글자를 적고 synchronize() 한 뒤 None.
             synchronize: 지금 토큰이 '}' 가 아닌 STARTERS(fn let if while print return { }) 면 그대로
             멈춘다. 아니면 한 토큰을 소비하고, 끝이 아닌 동안 ';' 바로 뒤이거나 STARTERS 앞이면 멈춘다.

ステップ

/root/mini/parser.pyのParseError、Parser(tokens)(属性はtokens・pos・errors)と、peek・previous・at_end・advance(EOFでは動かない)・check・match(*kinds)・expect(kind, message)を埋めます。
prefix()を埋めます。INT・true/false・IDENT・括弧で囲んだ式を扱います。-・!はprefix_operator()に渡し(ステップ4)、それ以外のトークンなら、その位置でexpected expressionを出します。
POWERの表とexpression(rbp=0)、infix(left)を埋めます。二項演算の優先順位と左結合です。(・^・=は、finish_call・right_assocに渡します。
UNARY、prefix_operator()、right_assoc(left)を埋めます。前置演算子、^・=の右結合、代入の対象が名前でなければinvalid assignment targetを出します。
finish_call(callee)を埋めます。引数なしから複数まで、f(x)(y)のような続けての呼び出しも扱います。
declaration・let_declaration・fn_declaration・statement・if_statement・block・programと、モジュールのparse_program(src)を埋めます。戻り値は(Program, 오류 목록)で、プレースホルダーはエラー一覧です。レキサーのエラーはその1つだけを入れ、木はNoneにします。
STARTERSとsynchronize()を埋めます。採点ツールが、エラープログラムのエラー一覧と、救い出した木を基準と突き合わせます。
採点ツールが、ランダムなプログラム120個の木と、トークンを1つ壊した240個のエラー一覧を、基準と突き合わせます。

参考

python3 /root/mini/mini.py parse 파일.miniが、自分のパーサーでS式やエラーを出力します(プレースホルダーはファイル名です)。式だけを見たいときは、print 식;だけの1行のファイルを使ってください(プレースホルダーは式です)。
レキサー(lexer.py)とノード(ast_nodes.py)は、ラボを開始するときに置かれています。前のモジュールで作った自分のlexer.pyを貼り付けて使ってもかまいません。
よくある間違いは、すべての演算子を右結合で読む、-a^bを(-a)^bと結ぶ、呼び出しを単項より緩くする、回復で1トークンも消費せずにその場で回り続ける、の4つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

トークンを見て、消費し、期待する

pos1つでトークンの一覧を指します。advanceは今のトークンを返し、それがEOFでないときだけposを上げます。expectは、種類が合えばadvance、そうでなければ今のトークン(peek)の位置でParseErrorを出します。今通り過ぎたトークンではありません。

式の最初の部品

トークンの種類で振り分けます。INTはint(text)、true/falseはBool、IDENTはVarで、ノードの位置はそのトークンの行・桁です。括弧は、内側をexpression()で読んで')'を期待しますが、括弧のノードは別に作らず、内側の式をそのまま返します。

結合力の表で優先順位を解く

while POWER.get(peek().kind, 0) > rbp: left = infix(left)。infixは演算子を消費して、右をexpression(その演算子の結合力)で読みます。同じ層の演算子は結合力が同じで>を超えられないので、外側のループに戻って左結合になります。

前置演算子と右結合

前置演算子は、オペランドをexpression(UNARY)で読みます。UNARYがより大きく、^より小さくて初めて、-abは(-a)*b、-a^bは-(a^b)になります。^と=は、右を結合力 - 1で読み、同じ層を右が飲み込むようにします。=の左がVarでなければ、その=の位置でエラーです。

呼び出し: いちばん強く結びつく

(も、結合力10の、後ろに付く演算子として扱います。finish_callは、開き括弧を消費し、')'でなければexpression()を読み、','があるあいだ繰り返してから、')'を期待します。Callノードの位置は開き括弧です。

文とブロック: 再帰下降

declarationはlet・fnを、statementはprint・if・while・return・ブロック・式文を振り分けます。elseのあとにifが来たら、if_statementをもう一度呼んで連鎖を作ります。declarationはParseErrorを捕まえて控え、synchronizeしてからNoneを返し、block・programはNoneを捨てます。

エラーのあとで立ち直る

エラーのトークンが'}'ではないSTARTERSなら、消費せずに止まります。そのキーワードで始まる文はキーワードから消費するので、その場で回り続けることはありません。そうでなければ少なくとも1トークンを消費し、previous()が';'であるか、peek()がSTARTERSなら止まります。

ランダムなプログラムと壊したプログラム

新しいコードはありません。壊したプログラムでエラーが基準より多いなら、回復のあとに見当違いの場所から読み直している(連鎖エラー)のであり、少ないなら、1つのエラーのあとで遠くまで読み飛ばしています。