チュートリアル「LLVMを使用したプログラミング言語の作成」の第2章にようこそ。 この章では、
第1章で作成した字句解析プログラムを使用して、万華鏡言語の完全な
パーサーを構築する方法を説明します。 パーサーの準備ができたら、
抽象構文ツリー（AST） （抽象構文ツリー）を構築します。
再帰的降下による 解析と演算子の優位性の解析 （後者はバイナリ式用で、最初は他のすべて用）の組み合わせを使用して、万華鏡言語用のパーサーを開発します。 解析自体に進む前に、出力で得られるものについて話しましょう：Abstract Syntax Tree。
抽象構文ツリー（AST）
ASTは、コンパイラーの後の段階（コード生成など）で簡単に解釈できるようにプログラムを表示します。 言語構成ごとに1つのオブジェクトが必要です。 カレイドスコープには、式、プロトタイプ、および関数があります。 式から始めましょう：
上記のコードは、数値リテラルに使用するExprAST基本クラスとそのサブクラスの定義を示しています。
ここで、さまざまな便利な操作方法なしでASTのみを作成します。 必要に応じて、たとえば、フォーマットされたコード出力用の仮想メソッドを追加するのは非常に簡単です。 カレイドスコープで使用する他のAST式のノード定義は次のとおりです。
簡単です。変数には変数名が含まれ、バイナリ演算子にはそのオペコード（たとえば「+」）および左右式（ASTノード）が含まれ、関数呼び出しには関数名とすべての引数のリストが含まれます。 ASTの素晴らしい点の1つは、プログラミング言語の構文に関係なく言語機能をカバーできることです。 二項演算子、字句構造などの優先度については、論争のある問題はないことに注意してください。
言語の表現のすべてのノードを特定しました。 チューリング完全ではありません。条件付き制御フローがないため、次の部分で修正します。 次の2つの必要なものは、関数インターフェイスと関数自体です。
Kaleidoscopeでは、関数は引数の数によってのみ入力されます。 すべての値は倍精度の実数であるため、各引数の型をどこにでも格納することは意味がありません。 実際のプログラミング言語では、おそらくExprASTクラスには別の型フィールドが含まれます。
これで、カレイドスコープでの式と関数の解析について最終的に説明できます。
パーサーベース
AST要素ができたので、コードパーサーを定義してビルドする必要があります。 ここでの考え方は、「x + y」（字句解析中に3つのトークンの形式で返される）のようなものを、次のようなものによって生成可能なASTに解析することです。
ExprAST *X = new VariableExprAST("x"); ExprAST *Y = new VariableExprAST("y"); ExprAST *Result = new BinaryExprAST('+', X, Y);
これを行う前に、いくつかの補助手順を定義します。
このコードは、字句アナライザーの上に最も単純なトークンバッファーを実装します。 これにより、字句解析プログラムによって返される1つのトークンを期待できます。 パーサーの各関数は、CurTokが構文解析の現在のトークンであると見なします。
これらは、パーサーがエラーを処理するために使用する補助プロシージャです。 パーサーでのエラーの修正は最高とはほど遠く、ユーザーにとって特に便利ではありませんが、このチュートリアルのフレームワーク内では十分です。
これらのヘルパー関数を使用して、文法の最初の部分である数値リテラルを実装できます。
式の解析
数値リテラルから始めましょう。最も簡単な方法です。 文法規則ごとに、この規則を分析する関数を定義します。 数値リテラルの場合、次のものがあります。
この関数は非常に単純です。呼び出されると、現在のトークンがtok_numberであると想定されます。
NumberExprASTノードを作成し、現在の数値を渡し、字句解析
プログラムを次のトークンに移動して、作成されたノードを返します。
いくつかの興味深い側面があります。 最も重要なことは、この関数は、文法規則に一致するトークンを受け取り、次のトークン（文法規則の一部ではない）が処理可能なレキシカルアナライザーバッファーを返すことです。 これは、再帰降下による解析の標準的な方法です。 これをよりよく理解するために、括弧内の式の解析を検討してください。
この関数は、パーサーに関するいくつかの興味深いことを示しています。
- エラー手順の使用方法を示します。 呼び出されると、関数は現在のトークンが記号 '（'であることを予期しますが、部分式を解析した後、予期される '）'が存在しない可能性があります。 たとえば、ユーザーが「（4）」ではなく「（4 x」と入力した場合、アナライザーはエラーを表示する必要があります。このようなエラーが発生する可能性があるため、パーサーはエラーが発生したことを示す方法を必要とします。
- この関数のもう1つの興味深い側面は、 ParseExpressionを呼び出すときに再帰を使用することです （ ParseExpressionがParseParenExprを呼び出すことができることがすぐにわかります）。 これは強力なメカニズムです。再帰的な文法を処理し、そのような文法のルールに非常に簡単に対処できるためです。 括弧用のASTノードは作成されないことに注意してください。 括弧の重要な役割は、パーサーにグループ化機能を提供することです。 パーサーがASTを構築すると、括弧は不要になります。
次の文法規則は、変数参照と関数呼び出しを処理しています。
この関数は、前のものと同じように機能します。 （呼び出されると、現在のトークンtok_identifierが必要です）。 また、再帰とエラー処理も使用します。 興味深い点の1つは、現在の識別子が変数への参照か関数呼び出しかを判断する
ために先読みしなければならないことです。 これは、識別子に続くトークンが記号 '（'であるかどうかに応じて、チェックです
。VariableExprASTまたは
CallExprASTを呼び出します。
最も単純な式を解析するためのすべてのロジックが揃ったので、1つのエントリポイントにラップする補助関数を定義できます。 この式クラスを「primary」（primary）と呼びます。理由
は、チュートリアルの終わりに向かって明らか
になるでしょう。 任意の一次式を解析するには、どのような式であるかを判断する必要があります。
この関数の定義が確認できたので、さまざまな関数で有効なCurTok状態を想定できる理由がより明確になります。 この場合、先読みを使用して、どの種類の式をチェックする必要があるかを判断し、その後、呼び出された対応する関数で式自体を分析します。
基本的な式を処理できるようになったので、バイナリ式を操作できます。 それらははるかに複雑です。
バイナリ式の解析
バイナリ式はあいまいになることが多いため、解析がはるかに困難です。 たとえば、文字列「x + y * z」の場合、パーサーは「（x + y）* z」または「x +（y * z）」として解析できます。 数学の基本を知っていれば、「*」（乗算）の優先順位が「+」（加算）よりも高いため、2番目のオプションが必要です。
多くの可能な解決策がありますが、最もエレガントで効率的な方法は
、演算子の優位性を
解析することです。 この解析手法では、再帰を使用して操作の優先順位を決定します。 まず、優先度テーブルが必要です。
Kaleidoscopeは4つの二項演算子のみをサポートします（ただし、勇敢で大胆不敵な読者によって明らかに拡張できます）。
GetTokPrecedence関数は、現在のトークンの優先順位を返します。トークンがバイナリ演算子でない場合は-1を返します。 このようなテーブルが存在すると、新しい演算子を簡単に追加できます。もちろん、アルゴリズムは特定の演算子に依存しません。 優先順位テーブルを簡単に削除し、
GetTokPrecedence関数で比較を行うことができます。
これで、バイナリ式の解析を開始できます。 演算子の優位性を解析する主なアイデアは、潜在的に曖昧なバイナリ演算子を含む式を部分に分割することです。 たとえば、「a + b +（c + d）* e * f + g」という式を考えてみましょう。 演算子優先順位パーサーは、それを2項演算子で区切られた一次式のストリームと見なします。 したがって、一次解析中に、先頭の一次式「a」が最初に解析され、[+、b] [+、（c + d）] [*、] [*、f]および[+、g ]。 括弧に注意してください：パーサーは（c + d）のようなネストされた式について心配する必要はありません。
まず、式は一次式であり、[binop、primaryexpr]ペアのシーケンスが後に続く可能性があります。
ParseBinOpRHSは、ペアのシーケンスを分析する関数です。 優先され、分析用の式へのポインタが使用されます。 「x」は絶対に有効な式であることに注意してください。したがって、「binoprhs」は空の場合があり、その場合、関数は渡された式を返します。 上記の例では、コードは式「a」と現在のトークン「+」を
ParseBinOpRHSに渡します。
ParseBinOpRHSに渡される優先度の値は、それを受け入れるために必要な
オペレーターの最小優先度を示します。 たとえば、ストリーム[+、x]およびParseBinOpRHSの現在のペアが優先度40に転送される場合、トークンは受け入れられません（優先度 "+"は20のみであるため）。 したがって、ParseBinOpRHSは次で始まります。
このコードは現在のトークンを優先し、それがどれだけ低いかをチェックします。 -1の優先度を持つトークンは無効であると判断したため、ペアのストリームが終了するタイミングを決定する暗黙のチェックが発生します。 このチェックに成功した場合、トークンは間違いなく二項演算子であり、式に含まれることがわかります。
したがって、このコードは二項演算子を受け取り（そして記憶し）、その後に続く一次式を解析します。 ペアを作成します。この例では、最初のペアは[+、b]です。
式の左側とRHSシーケンスの1つのペアを分析したので、式をバインドする方法を決定する必要があります。 特に、「（a + b）binop unparsed」と「a +（b binop unparsed）」の両方を使用できます（binopはバイナリ演算子、unparsedは未アセンブル部分です）。 決定するには、別の「binop」（二項演算子）を使用してその優先度を決定し、それをBinOpの優先度（この場合は「+」）と比較します。
「RHS」の右側の二項演算子の優先度が現在の演算子の優先度以下である場合、「（a + b）binop ...」というケースがあることがわかります。 この例では、現在の「+」演算子と次の「+」演算子の優先順位は同じです。 したがって、「a + b」のASTノードを作成し、解析を続行します。
... ... }
この例では、「a + b +」は「（a + b）」として返され、ループの次の反復が実行され、「+」が現在のトークンになります。 この部分は受け入れられ、さらに思い出すように、「（c + d）」は一次式として解析される必要があります。つまり、現在のペアは[+、（c + d）]になります。 次に、バイナリ演算子として「*」を含む式が受信されます。 この場合、優先度「*」は優先度「+」よりも高いため、上記の条件付き構築が実行されます。
ここで最も重要な左側の質問は、「この状態で右側を完全に分解する方法」です。 特に、この例でASTを正しく構築するには、RHS式変数として完全な式「（c + d）* e * f」を取得する必要があります。 このコードは驚くほど単純です（上記の2つのブロックのコードはコンテキストのために複製されています）：
RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0;
}
現時点では、一次式の右側の二項演算子は、現在解析されている二項演算子よりも優先度が高いことがわかっています。 したがって、「+」よりも高い優先度を持つ演算子のペアのシーケンスを分解し、「RHS」として返す必要があることがわかります。 これを行うには、続行するために必要な最小優先度としてパラメーター「TokPrec + 1」を指定してParseBinOpRHS関数を再帰的に呼び出します。 長い間苦労している例では、これによりASTノードはRHSとして「（c + d）* e * f」を返し、それが「+」を持つ式の右側になります。
最後に、whileループの次の反復で、+ g部分が解析され、ASTに追加されます。 この小さなコード（14行）の助けを借りて、エレガントな解析方法を使用してバイナリ式を正しく処理します。 これはコードの簡単な概要でしたので、いくつかの例を使用して実行して、どのように機能するかを確認することをお勧めします。
これで、式の処理が完了します。 現時点では、アナライザーにトークンの任意のストリームを既に示し、そこから式を作成し、式の一部ではない最初のトークンで停止できます。 ここで、関数宣言などに対処する必要があります。
残りの解析
次に欠けているのは、プロトタイプ関数の処理です。 カレイドスコープでは、外部関数の宣言と関数の本体の宣言の両方に使用されます。 解析のこの部分のコードは単純で、あまり興味深いものではありません（式の解析を生き延びた後）。
関数を宣言する単純さを考えると、関数の本体にはプロトタイプ+式が含まれます。
さらに、「sin」や「cos」などの関数を宣言し、ユーザー定義関数の早期宣言をサポートするには、「外部」サポートが必要です。 「extern」は、本体のないプロトタイプのみで構成されます。
最後に、ユーザーが任意のトップレベルの式を入力し、その場で評価できるようにする必要があります。 匿名のヌル引数（引数なし）関数を定義して処理します：
すべての部品が揃ったので、作成したすべてのコードを試すことができる小さな制御プログラムを作成しましょう！
管理プログラム
制御プログラムは、単純に周期的に解析を呼び出します。 ここでは何もおもしろいものはありません。以下の完全なコードの「トップレベル解析」セクションをご覧ください。
このコードで最も興味深い部分は、トップレベルのセミコロンを無視することです。 なぜだろう？
主な理由は、コマンドラインで「4 + 5」と入力しても、パーサーはこれが終了であることを認識しないため、テキストを入力し続けることです。たとえば、次の行に「def foo ...」と入力できます。この場合、4 +5がトップレベルの式の最後になります。または、「* 6」と入力して式を続行できます。上位レベルのセミコロンが存在するため、「4 + 5;」と印刷でき、パーサーはその意味を認識します。結論
コメント付きコードがわずか400行（コメントまたは空白行のない240行）で、レキシカルおよびパーサーとAST構築を含む最小限のプログラミング言語を完全に定義しました。これらすべてにより、Kaleidoscopeは実行時にコードを検証し、文法的に間違っているかどうかをお知らせします。インタラクティブセッションの例を次に示します。$ ./a.out
ready> def foo(xy) x+foo(y, 4.0);
Parsed a function definition.
ready> def foo(xy) x+yy;
Parsed a function definition.
Parsed a top-level expr
ready> def foo(xy) x+y );
Parsed a function definition.
Error: unknown token when expecting an expression
ready> extern sin(a);
ready> Parsed an extern
ready> ^D
$
改善する方法はたくさんあります。新しいASTノードを定義したり、さまざまな方法で言語を拡張したりできます。次のパートでは、ASTからLLVM中間表現（IR）を生成する方法を見ていきます。完全なコードリスト
これは、この章と前の章のコードの完全なリストです。コードは完全に独立していることに注意してください。LLVMや外部ライブラリは必要ありません。（もちろん、標準のCおよびC ++ライブラリを除きます）。このコードは次のようにコンパイルできます。#
g++ -g -O3 toy.cpp
#
./a.out
さて、コード自体： #include <cstdio> #include <cstdlib> #include <string> #include <map> #include <vector> //===----------------------------------------------------------------------===// // Lexer ( ) //===----------------------------------------------------------------------===// // [0-255], , // enum Token { tok_eof = -1, // ( ) tok_def = -2, tok_extern = -3, // ( : , ) tok_identifier = -4, tok_number = -5 }; static std::string IdentifierStr; // , tok_identifier static double NumVal; // , tok_number /// gettok - . static int gettok() { static int LastChar = ' '; // . while (isspace(LastChar)) LastChar = getchar(); if (isalpha(LastChar)) { // : [a-zA-Z][a-zA-Z0-9]* IdentifierStr = LastChar; while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; if (IdentifierStr == "def") return tok_def; if (IdentifierStr == "extern") return tok_extern; return tok_identifier; } if (isdigit(LastChar) || LastChar == '.') { // : [0-9.]+ std::string NumStr; do { NumStr += LastChar; LastChar = getchar(); } while (isdigit(LastChar) || LastChar == '.'); NumVal = strtod(NumStr.c_str(), 0); return tok_number; } if (LastChar == '#') { // do LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); } // . if (LastChar == EOF) return tok_eof; // ASCII int ThisChar = LastChar; LastChar = getchar(); return ThisChar; } //===----------------------------------------------------------------------===// // Abstract Syntax Tree ( ) //===----------------------------------------------------------------------===// /// ExprAST - . class ExprAST { public: virtual ~ExprAST() {} }; /// NumberExprAST - (, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} }; /// VariableExprAST - (, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST - . class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} }; /// CallExprAST - . class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} }; /// PrototypeAST - "" , /// (, , /// ). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} }; /// FunctionAST - class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} }; //===----------------------------------------------------------------------===// // Parser ( ) //===----------------------------------------------------------------------===// /// CurTok/getNextToken - . CurTok - /// , . getNextToken /// CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); } /// BinopPrecedence - static std::map<char, int> BinopPrecedence; /// GetTokPrecedence - . static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // , . int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } /// Error* - . ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } static ExprAST *ParseExpression(); /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); // . if (CurTok != '(') // . return new VariableExprAST(IdName); // . getNextToken(); // ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } // ')'. getNextToken(); return new CallExprAST(IdName, Args); } /// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); // return Result; } /// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); // (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); // ). return V; } /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } } /// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { // , while (1) { int TokPrec = GetTokPrecedence(); // , // , if (TokPrec < ExprPrec) return LHS; // , , . int BinOp = CurTok; getNextToken(); // eat binop // ExprAST *RHS = ParsePrimary(); if (!RHS) return 0; // BinOp RHS , RHS, // RHS LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0; } // LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } } /// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); } /// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); // . std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); // . getNextToken(); // ')'. return new PrototypeAST(FnName, ArgNames); } /// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); // def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; } /// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { // . PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; } /// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); // extern. return ParsePrototype(); } //===----------------------------------------------------------------------===// // Top-Level parsing ( ) //===----------------------------------------------------------------------===// static void HandleDefinition() { if (ParseDefinition()) { fprintf(stderr, "Parsed a function definition.\n"); } else { // . getNextToken(); } } static void HandleExtern() { if (ParseExtern()) { fprintf(stderr, "Parsed an extern\n"); } else { // . getNextToken(); } } static void HandleTopLevelExpression() { // . if (ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top-level expr\n"); } else { // . getNextToken(); } } /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; // . case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } } //===----------------------------------------------------------------------===// // Main driver code ( ) //===----------------------------------------------------------------------===// int main() { // . // 1 - . BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; // highest. fprintf(stderr, "ready> "); getNextToken(); // " ". MainLoop(); return 0; }
PS
この章の翻訳は非常に難しかったので、あまり質の悪い翻訳と少しの「非ロシア語のターン」をおaびします。次の章で訂正することをお約束します（簡単です）。いつものように、私は喜んでPMの修正、説明、希望、脅威を受け入れます:)