インタプリタを最初から書く方法

「すべてが1と0に要約される」と言う人もいますが、プログラムがどのようにそれらのビットに変換されるかを本当に理解していますか？

コンパイラーとインタープリターはどちらも、プログラムを表す生の文字列を受け取り、それを解析して、それを理解します。 インタプリタは2つのうちで単純ですが、非常に単純なインタプリタ（加算と乗算のみを行う）を作成することも有益です。 コンパイラとインタプリタに共通するもの、つまり入力の字句解析と解析に焦点を当てます。

独自の通訳を書くことのすべきこととすべきでないこと

読者は、正規表現の何が問題になっているのか疑問に思うかもしれません。 正規表現は強力ですが、ソースコードの文法はそれらによって解析されるほど単純ではありません。 どちらもドメイン固有言語（DSL）ではなく、クライアントは、たとえば、承認式のためにカスタムDSLを必要とする場合があります。 しかし、このスキルを直接適用しなくても、インタープリターを作成すると、多くのプログラミング言語、ファイル形式、およびDSLの背後にある取り組みをより簡単に理解できるようになります。

手作業でパーサーを正しく作成することは、すべてのエッジケースが関係する場合に困難になる可能性があります。 そのため、多くの一般的なプログラミング言語のパーサーを生成できるANTLRなどの一般的なツールがあります。 パーサーコンビネーターと呼ばれるライブラリもあり、開発者は好みのプログラミング言語でパーサーを直接記述できます。 例としては、Scalaの場合はFastParse、Pythonの場合はParsecがあります。

専門的な文脈では、読者は車輪の再発明を避けるためにそのようなツールとライブラリを使用することをお勧めします。 それでも、インタプリタを最初から作成することの課題と可能性を理解することは、開発者がそのようなソリューションをより効果的に活用するのに役立ちます。

インタプリタコンポーネントの概要

インタプリタは複雑なプログラムであるため、複数の段階があります。

1. レクサーは、一連の文字（プレーンテキスト）を一連のトークンに変換するインタープリターの一部です。
2. 次に、パーサーは一連のトークンを受け取り、言語の抽象構文木（AST）を生成します。 パーサーが動作するルールは、通常、形式文法によって指定されます。
3. インタプリタは、プログラムのソースのASTをオンザフライで（最初にコンパイルせずに）解釈するプログラムです。

ここでは、特定の統合されたインタプリタを構築しません。 代わりに、これらの各部分とそれらの一般的な問題を別々の例で調べます。 最終的に、ユーザーコードは次のようになります。

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

3つの段階に続いて、このコードが最終値を計算し、 Result is: 19 。 このチュートリアルでは、次の理由からScalaを使用しています。

• 非常に簡潔で、1つの画面に多くのコードを収めることができます。
• 式指向で、初期化されていない/null変数は必要ありません。
• 強力なコレクションライブラリ、列挙型、およびケースクラスを使用して、安全に入力します。

具体的には、ここでのコードは、Scala3のオプションの中括弧構文（Pythonのようなインデントベースの構文）で記述されています。 しかし、どのアプローチもScala固有のものではなく、Scalaは他の多くの言語と似ています。読者は、これらのコードサンプルを他の言語に変換するのが簡単であることに気付くでしょう。 それを除けば、例はScastieを使用してオンラインで実行できます。

最後に、レクサー、パーサー、インタープリターの各セクションには、異なる文法例があります。 対応するGitHubリポジトリが示すように、後の例の依存関係は、これらの文法を実装するためにわずかに変更されますが、全体的な概念は同じままです。

インタプリタコンポーネント1：レクサーの記述

次の文字列をlexしたいとします： "123 + 45 true * false1" 。 さまざまな種類のトークンが含まれています。

• 整数リテラル
• +演算子
• *演算子
• true文字
• 識別子false1

この例では、トークン間の空白はスキップされます。

この段階では、表現は意味をなす必要はありません。 レクサーは、入力文字列をトークンのリストに変換するだけです。 （「トークンの意味を理解する」作業はパーサーに任されています。）

このコードを使用してトークンを表します。

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

すべてのトークンには、元の入力でのタイプ、テキスト表現、および位置があります。 この位置は、レクサーのエンドユーザーがデバッグするのに役立ちます。

EOFトークンは、入力の終わりを示す特別なトークンです。 ソーステキストには存在しません。 パーサーステージを単純化するためにのみ使用します。

これは、レクサーの出力になります。

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

実装を調べてみましょう：

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

トークンの空のリストから始め、次に文字列を調べて、トークンが来たら追加します。

先読み文字を使用して、次のトークンのタイプを決定します。 先読み文字は、常に調査対象の最も遠い文字であるとは限らないことに注意してください。 先読みに基づいて、トークンがどのように見えるかを把握し、 currentPosを使用して現在のトークンで予想されるすべての文字をスキャンし、トークンをリストに追加します。

先読みが空白の場合はスキップします。 一文字のトークンは簡単です。 それらを追加し、インデックスをインクリメントします。 整数の場合は、インデックスのみを処理する必要があります。

ここで、少し複雑なことになります。識別子とリテラルです。 ルールは、可能な限り長い一致を取得し、それがリテラルであるかどうかを確認することです。 そうでない場合は、識別子です。

<や<=などの演算子を処理するときは注意してください。 そこで、もう1文字先を見越して、それが=であるかどうかを確認してから、それが<=演算子であると結論付ける必要があります。 それ以外の場合は、単なる<です。

これにより、レクサーはトークンのリストを作成しました。

インタプリタコンポーネント2：パーサーの作成

トークンに何らかの構造を与える必要があります。リストだけでは多くのことを行うことはできません。 たとえば、次のことを知る必要があります。

どの式がネストされていますか？ どの演算子がどの順序で適用されますか？ もしあれば、どのスコープルールが適用されますか？

ツリー構造は、ネストと順序付けをサポートします。 ただし、最初に、ツリーを構築するためのいくつかのルールを定義する必要があります。 パーサーが明確であり、特定の入力に対して常に同じ構造を返すようにします。

次のパーサーは、前のレクサーの例を使用していないことに注意してください。 これは数字を追加するためのものであるため、その文法には'+'とNUMの2つのトークンしかありません。

 expr -> expr '+' expr expr -> NUM

正規表現のようにパイプ文字（ | ）を「または」記号として使用する同等の機能は次のとおりです。

 expr -> expr '+' expr | NUM

いずれにせよ、2つのルールがあります。1つは2つのexprを合計できることを示し、もう1つはexprをNUMトークンにすることができることを示します。これは、ここでは非負の整数を意味します。

ルールは通常、正式な文法で指定されます。 正式な文法は次の要素で構成されます。上記のルール自体開始ルール（規則に従って指定された最初のルール）ルールを定義する2種類の記号：終端記号：言語の「文字」（およびその他の文字）—トークンを構成する還元不可能な記号非終端記号：構文解析に使用される中間構造（つまり、置換可能な記号）

ルールの左側に配置できるのは非終端記号のみです。 右側には、終端記号と非終端記号の両方を含めることができます。 上記の例では、終端記号は'+'とNUMであり、非終端記号はexprのみです。 より広い例として、Java言語では、 'true' 、 '+' 、「 Identifier 」、 '['などの終端記号と、 BlockStatements 、 ClassBody 、MethodOrFieldDeclなどの非終端記号がありMethodOrFieldDecl 。

このパーサーを実装する方法はたくさんあります。 ここでは、「再帰下降」解析手法を使用します。 理解と実装が最も簡単なため、最も一般的なタイプです。

再帰下降パーサーは、文法の非終端記号ごとに1つの関数を使用します。 それは開始ルールから始まり、そこから下がって（したがって「降下」）、各関数にどのルールを適用するかを判断します。 非終端記号を再帰的にネストできるため、「再帰的」部分は非常に重要です。 正規表現はそれを行うことができません：バランスの取れた括弧を処理することさえできません。 したがって、より強力なツールが必要です。

最初のルールのパーサーは次のようになります（完全なコード）：

 def expr() = expr() eat('+') expr()

eat()関数は、先読みが期待されるトークンと一致するかどうかを確認してから、先読みインデックスを移動します。 残念ながら、文法の問題を修正する必要があるため、これはまだ機能しません。

文法のあいまいさ

最初の問題は文法の曖昧さであり、一見しただけでは明らかではないかもしれません。

 expr -> expr '+' expr | NUM

入力1 + 2 + 3が与えられると、パーサーは、結果のASTで最初に左exprまたは右exprのいずれかを計算することを選択できます。

そのため、非対称性を導入する必要があります。

 expr -> expr '+' NUM | NUM

この文法で表現できる式のセットは、最初のバージョンから変更されていません。 今だけそれは明白です：パーサーは常に左に行きます。 必要なものだけ！

これにより、 +演算は結合性のままになりますが、これはインタプリタセクションに到達したときに明らかになります。

左再帰ルール

残念ながら、上記の修正では、他の問題である左再帰は解決されません。

 def expr() = expr() eat('+') eat(NUM)

ここには無限の再帰があります。 この関数にステップインすると、最終的にスタックオーバーフローエラーが発生します。 しかし、構文解析理論は役に立ちます！

次のような文法があるとします。ここで、 alphaは、終端記号と非終端記号の任意のシーケンスである可能性があります。

 A -> A alpha | B

この文法を次のように書き直すことができます。

 A -> BA' A' -> alpha A' | epsilon

そこでは、 epsilonは空の文字列であり、何もトークンもありません。

文法の現在のリビジョンを見てみましょう。

 expr -> expr '+' NUM | NUM

上記の解析ルールを書き換える方法に従い、 alphaを'+' NUMトークンとして、文法は次のようになります。

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

これで文法はOKになり、再帰下降パーサーで解析できます。 そのようなパーサーが文法のこの最新の反復をどのように検索するかを見てみましょう。

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

ここでは、 EOFトークンを使用してパーサーを単純化します。 リストに少なくとも1つのトークンがあることを常に確認しているため、空のリストの特殊なケースを処理する必要はありません。

また、ストリーミングレクサーに切り替えると、メモリ内のリストではなくイテレーターが作成されるため、入力の最後に到達したことを知るためのマーカーが必要になります。 最後に、 EOFトークンが最後に残っているトークンである必要があります。

コードを見ていくと、式は単なる数値である可能性があることがわかります。 何も残っていない場合、次のトークンはPlusではないため、解析を停止します。 最後のトークンはEOFであり、これで完了です。

入力文字列にさらにトークンがある場合、これらは+ 123のように見える必要があります。 ここで、 exprOpt()の再帰が始まります。

ASTの生成

式の解析に成功したので、そのままでは何もできません。 パーサーにいくつかのコールバックを入れることもできますが、それは非常に面倒で読みにくくなります。 代わりに、入力式を表すツリーであるASTを返します。

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

これは、単純なデータクラスを使用したルールに似ています。

パーサーは、有用なデータ構造を返すようになりました。

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

eat() 、 error() 、およびその他の実装の詳細については、付属のGitHubリポジトリを参照してください。

ルールの簡素化

ExprOpt非終端記号は引き続き改善できます。

 '+' NUM exprOpt | epsilon

見ただけでは文法のパターンがわかりにくいです。 この再帰をより単純な構成に置き換えることができることがわかりました。

 ('+' NUM)*

この構成は、単に'+' NUMが0回以上発生することを意味します。

これで、完全な文法は次のようになります。

 expr -> NUM exprOpt* exprOpt -> '+' NUM

そして、私たちのASTはより良く見えます：

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

結果として得られるパーサーは同じ長さですが、理解と使用が簡単です。 Epsilonを削除しました。これは、空の構造から開始することで暗示されます。

ここではExprOptクラスも必要ありませんでした。 case class Expr(num: Int, exprOpts: Seq[Int]) 、または文法形式でNUM ('+' NUM)*を配置することもできます。 では、なぜ私たちはしなかったのですか？

-や*のような複数の可能な演算子がある場合、次のような文法があることを考慮してください。

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

この場合、ASTはオペレータータイプに対応するためにExprOptを必要とします。

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

文法の[+-*]構文は、正規表現の場合と同じ意味であることに注意してください。「これらの3文字の1つ」です。 これが実際に動作するのをすぐに確認します。

インタプリタコンポーネント3：インタプリタの作成

インタープリターは、レクサーとパーサーを使用して入力式のASTを取得し、そのASTを任意の方法で評価します。 この場合、数値を扱っているので、それらの合計を評価します。

インタプリタの例の実装では、次の単純な文法を使用します。

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

そしてこのAST：

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

（同様の文法のレクサーとパーサーを実装する方法について説明しましたが、行き詰まった読者は、リポジトリ内のこの正確な文法のレクサーとパーサーの実装を熟読できます。）

次に、上記の文法のインタプリタを作成する方法を説明します。

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

エラーが発生せずに入力をASTに解析した場合、常に少なくとも1つのNUMがあると確信しています。 次に、オプションの数値を取得して、結果に加算（または減算）します。

+の左結合性に関する最初からのメモが明確になりました。左端の数字から始めて、左から右に他の数字を追加します。 これは足し算には重要ではないように思われるかもしれませんが、引き算を検討してください。式5 - 2 - 1 --2 --1は(5 - 2) - 1 = 3 - 1 = 2として評価され、 5 - (2 - 1) = 5 - 1 = 4として評価されません。 ！！

しかし、プラス演算子とマイナス演算子の解釈を超えたい場合は、定義する別のルールがあります。

優先順位

1 + 2 + 3のような単純な式を解析する方法は知っていますが、 2 + 3 * 4 + 5に関しては、少し問題があります。

ほとんどの人は、乗算は加算よりも優先されるという慣習に同意します。 しかし、パーサーはそれを知りません。 ((2 + 3) * 4) + 5とだけ評価することはできません。 代わりに、 (2 + (3 * 4)) + 5が必要です。

これは、最初に乗算を評価する必要があることを意味します。 加算の前にASTを強制的に評価するには、乗算をASTのルートからさらに遠ざける必要があります。 このために、間接参照のさらに別のレイヤーを導入する必要があります。

最初から最後まで素朴な文法を修正する

これは元の左再帰文法であり、優先順位の規則はありません。

 expr -> expr '+' expr | expr '*' expr | NUM

まず、優先順位のルールを与え、そのあいまいさを取り除きます。

 expr -> expr '+' term | term term -> term '*' NUM | NUM

次に、非左再帰ルールを取得します。

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

その結果、美しく表現力豊かなASTが実現します。

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

これにより、簡潔なインタプリタの実装が残ります。

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

以前と同様に、必要なレクサーと文法のアイデアについては前に説明しましたが、読者は必要に応じてリポジトリでそれらを見つけることができます。

通訳者を書くための次のステップ

これについては説明しませんでしたが、エラー処理とレポートはパーサーの重要な機能です。 開発者として、コンパイラーが紛らわしいエラーや誤解を招くエラーを生成するときに、それがどれほど苛立たしいものになるかを知っています。 これは、正確で正確なエラーメッセージを表示する、必要以上のメッセージでユーザーを思いとどまらせない、エラーから適切に回復するなど、解決すべき多くの興味深い問題がある領域です。 将来のユーザーがより良い体験をすることができるように、インタープリターまたはコンパイラーを作成するのは開発者次第です。

レクサー、パーサー、インタープリターの例を見ていく中で、コンパイラーとインタープリターの背後にある理論の表面をかじっただけで、次のようなトピックをカバーしています。

• スコープとシンボルテーブル
• 静的タイプ
• コンパイル時の最適化
• 静的プログラムアナライザーとリンター
• コードのフォーマットときれいな印刷
• ドメイン固有言語

さらに読むために、私はこれらのリソースをお勧めします：

• テレンス・パーによる言語実装パターン
• ボブ・ナイストロームによる無料のオンライン本、 Crafting Interpreters
• ポール・クリントによる文法と構文解析の紹介
• CalebMeredithによる優れたコンパイラエラーメッセージの作成
• イーストカロライナ大学のコース「プログラムの翻訳とコンパイル」からのメモ