体系ガイド · 基礎から応用へ

字句解析から構文木まで、式の変換を追う

同じ式を文字列・トークン列・構文木で表し、優先順位、エラー位置、評価との役割の違いを具体的に確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. まず一つの式を最後まで追う
  2. 文字を位置付きのトークンへ分ける
  3. 優先順位を文法の段階として表す
  4. 同じ優先順位でも結合の向きを決める
  5. 必要な構造だけを木に残す
  6. 失敗した段階と位置を残す
  7. 段階ごとの試験を組み合わせる
  8. 負号を追加するときの責任を分ける
  9. 条件を変えて説明する
  10. デモの一歩を字句と構文で分ける
  11. 式言語の規則をHTMLへ持ち込まない
  12. この記事をロゲイアに質問する理解を確かめる

まず一つの式を最後まで追う

電卓へ12 + 3 * (4 - 1)と入力したとき、処理系は文字を左から計算するだけではありません。どこまでが一つの数かを認識し、掛け算と足し算のまとまりを作り、その構造に従って計算します。この教材では、この三つの仕事を分けて追います。字句解析は文字からトークンを取り出す仕事、構文解析はトークン同士の関係を木にする仕事、評価は木から値を求める仕事です。最初に期待する値を21と確認しておくと、途中で作った表現が同じ意味を保っているかを調べやすくなります。ここでは整数、変数名、四則演算、括弧だけを持つ小さな式言語を考えます。実用言語の全文法を再現するのではなく、入力から結果までの見通しを得ることが目的です。変数や関数を使った経験があれば、前提となる知識は十分です。

文字を位置付きのトークンへ分ける

最初の12は二文字ですが、一つの整数を表します。字句解析器は数字が続く間だけ進み、NUMという種類、12という綴り、開始位置0を持つトークンを作ります。続く空白はこの言語では区切りとして扱い、足し算の記号は位置3の別トークンになります。位置は元の文字列で数えるため、空白を除いた後で番号を振り直してはいけません。a12という変数名も、識別子の規則を先に決めれば一つのNAMEとして扱えます。一方、12aを許すかは別の仕様です。この実装ではNUMとNAMEへ分かれ、後の構文解析が余分な入力として拒否します。数字に見える文字をどこまで認めるかも言語の選択です。実験ではASCIIの数字と英字を使い、Unicodeの識別子やコメントは追加していません。扱う文字の範囲を小さく明示する方が、認識できない入力を黙って捨てるより原因を説明できます。

段階この例での関係
入力12 + 3 * (4 - 1)
構造加算の右側に乗算、その右側に減算
内側の計算4 - 1 = 3
全体の結果12 + 3 * 3 = 21

優先順位を文法の段階として表す

トークン列だけでは1 + 2 * 3をどの順に計算するかは決まりません。この教材では、式を「項を一つ読み、続く加減算を読むもの」、項を「原子を一つ読み、続く乗除算を読むもの」と定めます。原子は整数、変数、括弧で囲まれた式です。掛け算を読む処理が足し算より内側で完結するので、木では掛け算が足し算の右の子になります。1 + 2 * 3の木と(1 + 2) * 3の木を紙に描くと、括弧が構造をどう変えるかが分かります。文法は計算速度の都合で後付けするものではありません。利用者が書いた式をどう読むかという契約です。演算子を増やす際には、認識する記号だけでなく、どの段階で読むかも決めます。ここでは単項のマイナスをまだ扱わないため、-2は構文エラーです。負の値を計算したい場合と、負号を含むリテラルを文法へ追加する場合も区別します。

同じ優先順位でも結合の向きを決める

8 - 3 - 1を左からまとめると4ですが、右からまとめると6です。加算と違い、減算では木の形を変えるだけで結果が変わります。再帰下降の実験では、最初の項をleftへ置き、減算が現れるたびに「今までのleftから次の項を引く木」を作り直します。この繰り返しによって左結合を表します。単に減算の右側でも同じ式全体を再帰的に読むと、意図せず右結合になることがあります。また、式の規則の先頭から同じ式の関数を呼ぶ左再帰は、素朴な再帰下降では入力を消費しない再帰になります。ここでは規則を書き換え、繰り返しで同じ段階を読む形を採ります。再帰を使っているから優先順位や結合規則が自動で正しくなるわけではありません。どの呼出しが入力位置を進めるか、どの木を返すかの二点を、短い入力で確認する必要があります。

必要な構造だけを木に残す

構文木の節点は、例えば加算、乗算、整数、変数を表します。括弧は入力のまとまりを決める役割を果たした後、抽象構文木では独立した節点として残さなくてもかまいません。12 + 3 * (4 - 1)なら、根は加算で、左の子は12、右の子は乗算です。乗算の右の子には4から1を引く部分木が入ります。この木を作った時点では、変数名が実際に値を持つかまでは判定しません。x + 1は正しい構文ですが、評価するときにxが環境に存在しなければ失敗します。構文として読めたことと実行できることを分けると、エラーの説明も明確になります。木の表現にはクラスやタプルなどを使えますが、必要な種類と子の数をそろえることが先です。整形器やエディタを作る場合は、元の括弧やコメントを保つ別の表現が必要になることもあります。

失敗した段階と位置を残す

12 + @という入力なら、@をトークンにできないので字句解析の段階で止まります。12 +という入力では、最後の加算の右に原子が必要なのに入力が終わるため、構文解析の段階で止まります。12 / 0は木を作れますが、ゼロ除算を禁じる評価規則によって実行時に失敗します。この違いを単に「入力エラー」とまとめると、何を直せばよいか分からなくなります。実験では入力の末尾にEOFというトークンを一つ置き、終わりも位置付きで扱います。また、最初の木を一つ作れた時点で成功とせず、EOFまで読んだことを確認します。そうしないと1 2の前半だけを受理して、後半を無視する不具合が生まれます。高度な処理系は複数のエラーから回復できますが、ここでは最初の失敗を明確に報告して止まる方針です。回復処理を省くことと、余分な入力を許すことは同じではありません。

段階ごとの試験を組み合わせる

字句解析の試験では、種類だけでなく綴りと開始位置を照合します。構文解析では期待する木を比較し、評価の試験では値と例外を調べます。この三種類の試験を分けると、21が出なかった原因を探しやすくなります。例えばトークン列が正しいのに木が違うなら、数字の認識より文法の呼出し順を見直します。木も正しければ、演算の実装や変数環境を調べます。正常な例に加え、空入力、空の括弧、不正な文字、閉じ括弧の不足、余ったトークンも試してください。入力の長さや括弧の深さには実行環境の制約があるため、この小さな実装を外部公開のサービスへそのまま載せることは想定しません。説明用の短い入力で各段階の契約を確かめ、実験記事にあるassertと自分の予想を照合するのが学習の中心です。使ったPythonの版とコードを記録しておくと、後で規則を変えた際にも比較できます。

負号を追加するときの責任を分ける

たとえば-12を扱う仕様へ広げるなら、負号を数値トークンへ含めるか、単項演算として構文規則へ置くかを先に決めます。1-2の二項減算と、-2の単項演算を同じ見た目から区別する必要があるためです。既存の字句解析器がMINUSを返すなら、構文解析器へ単項の規則を加える設計もあります。今回の小言語は単項演算を持たないため、負数を書ける処理系だと説明してはいけません。仕様の追加、トークン列、構文木、評価結果の四つを一緒に更新します。

条件を変えて説明する

自分で確かめる課題として、12 + 3 * (4 - 1)から括弧だけを外し、トークン列、木、値がそれぞれどう変わるかを予想してください。解答では、括弧のトークンがなくなり、乗算3 * 4が先にまとまる一方、加算と減算が左結合になるため、値は23になります。元の式の値21とは違います。空白だけを増やした場合は、トークンの開始位置は変わりますが、木と値は変わりません。この二つを対にすると、字句上の違いと意味上の違いを区別できます。次に8 - 3 - 1を試し、木の左の子がさらに減算になっていることを確認します。解答の4だけを覚えるのではなく、どの規則がその結果を決めたかを説明できれば、この教材の到達点を満たしています。実装を読みたい場合は字句解析器の実験から順に進み、木を手で描く段階へ戻りたい場合は構文解析の実験を使ってください。

デモの一歩を字句と構文で分ける

ブラウザの字句解析デモへ進むと、同じ「一段階進める」でも何を一段と数えるかが重要になります。文字を一文字読んだ段階、トークンを一つ確定した段階、木へノードを追加した段階は同じではありません。たとえば<p>A</p>の開始タグを読む途中には、タグ名pが分かっていても開始タグがまだ確定していない状態があります。入力位置、作りかけのトークン、出力済みトークンを別に残し、構文側は出力済みのものだけを使います。停止・再開・巻き戻しでは、この組を同じ時点へそろえると、なぜその木になったかを再現できます。

式言語の規則をHTMLへ持ち込まない

式のパーサで空白を飛ばせたからといって、HTMLの空白を全て捨ててよいわけではありません。Hello worldの間の空白も文書の文字内容です。また、この式言語は余分なトークンをエラーにしますが、実際のHTMLには不正な入れ子や省略された要素を処理する回復規則があります。共通するのは、入力、状態、出力を決めて試験する設計の方法です。個別の文法と意味の規則まで共通とは限りません。新しい言語を作るときは、再利用できる枠組みと書き直す規則を表へ分け、対応外の入力を黙って受理しないようにしてください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 20

学習コースから次を選ぶ