2. Kaleidoscope: パーサーとASTの実装¶
2.1. 第2章 はじめに¶
「LLVMを使った言語の実装」チュートリアルの第2章へようこそ。この章では、第1章で作成した字句解析器を使用して、Kaleidoscope言語の完全なパーサーを構築する方法を説明します。パーサーが完成したら、抽象構文木 (AST) を定義して構築します。
これから構築するパーサーは、再帰下降構文解析と演算子順位構文解析を組み合わせてKaleidoscope言語を構文解析します（後者は二項演算子、前者はその他すべて）。構文解析に入る前に、パーサーの出力である抽象構文木について説明しましょう。
2.2. 抽象構文木 (AST)¶
プログラムのASTは、コンパイラの後続の段階（例えば、コード生成）が解釈しやすいように、プログラムの動作を捉えます。基本的には、言語の各構成要素に対して1つのオブジェクトが必要であり、ASTは言語を密接にモデル化する必要があります。Kaleidoscopeでは、式、プロトタイプ、関数オブジェクトがあります。まずは式から始めましょう。
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
};
上記のコードは、基底クラスExprASTと、数値リテラルに使用する1つのサブクラスの定義を示しています。このコードで重要なのは、NumberExprASTクラスがリテラルの数値をインスタンス変数として保持していることです。これにより、コンパイラの後続のフェーズで格納されている数値を知ることができます。
今はASTを作成するだけなので、便利なアクセサメソッドはありません。例えば、コードをきれいに印刷するための仮想メソッドを追加するのは非常に簡単です。Kaleidoscope言語の基本的な形式で使用する他の式ASTノード定義を以下に示します。
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;
public:
VariableExprAST(const std::string &Name) : Name(Name) {}
};
/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;
public:
BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;
public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
};
これはすべて（意図的に）非常に分かりやすいものです。変数は変数名を保持し、二項演算子は演算コード（例：'+'）を保持し、呼び出しは関数名と引数式のリストを保持します。ASTの良いところは、言語の構文について言及することなく、言語の機能を捉えていることです。二項演算子の優先順位、字句構造などについては議論されていないことに注意してください。
基本的な言語では、これらが定義するすべての式ノードです。条件付き制御フローがないため、チューリング完全ではありません。これは後の記事で修正します。次に必要なのは、関数のインターフェースについて説明する方法と、関数自体について説明する方法の2つです。
/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
public:
PrototypeAST(const std::string &Name, std::vector<std::string> Args)
: Name(Name), Args(std::move(Args)) {}
const std::string &getName() const { return Name; }
};
/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;
public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
};
Kaleidoscopeでは、関数は引数の数だけで型付けされます。すべての値が倍精度浮動小数点数であるため、各引数の型をどこかに格納する必要はありません。より積極的で現実的な言語では、「ExprAST」クラスはおそらく型フィールドを持つでしょう。
この足場があれば、Kaleidoscopeでの式と関数本体の構文解析について説明できます。
2.3. パーサーの基本¶
構築するASTができたので、それを構築するためのパーサーコードを定義する必要があります。ここでのアイデアは、「x+y」（字句解析器によって3つのトークンとして返される）のようなものを、次のような呼び出しで生成できるASTに構文解析したいということです。
auto LHS = std::make_unique<VariableExprAST>("x");
auto RHS = std::make_unique<VariableExprAST>("y");
auto Result = std::make_unique<BinaryExprAST>('+', std::move(LHS),
std::move(RHS));
これを行うために、まずいくつかの基本的なヘルパールーチンを定義します。
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parser is looking at. getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() {
return CurTok = gettok();
}
これは、字句解析器の周囲に単純なトークンバッファを実装します。これにより、字句解析器が返しているトークンを1つ先読みすることができます。パーサーのすべての関数は、CurTokが構文解析する必要がある現在のトークンであると想定します。
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
LogErrorルーチンは、パーサーがエラー処理に使用する単純なヘルパールーチンです。パーサーのエラー回復は最良ではなく、特にユーザーフレンドリーではありませんが、チュートリアルには十分です。これらのルーチンは、さまざまな戻り値の型を持つルーチンでのエラー処理を容易にします。常にnullを返します。
これらの基本的なヘルパー関数を使用して、文法の最初の部分である数値リテラルを実装できます。
2.4. 基本的な式の構文解析¶
数値リテラルは処理が最も簡単なので、そこから始めます。文法の各生成規則に対して、その生成規則を構文解析する関数を定義します。数値リテラルの場合、次のようになります。
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
このルーチンは非常にシンプルです。現在のトークンがtok_numberトークンであるときに呼び出されることを想定しています。現在の数値を取得し、NumberExprASTノードを作成し、字句解析器を次のトークンに進め、最後に返します。
これにはいくつかの興味深い側面があります。最も重要なのは、このルーチンが生成規則に対応するすべてのトークンを食べ、次のトークン（文法生成規則の一部ではない）を字句解析器バッファに返して準備を整えることです。これは、再帰下降パーサーのかなり標準的な方法です。より良い例として、括弧演算子は次のように定義されています。
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
getNextToken(); // eat (.
auto V = ParseExpression();
if (!V)
return nullptr;
if (CurTok != ')')
return LogError("expected ')'");
getNextToken(); // eat ).
return V;
}
この関数は、パーサーに関するいくつかの興味深い点を示しています。
1) LogErrorルーチンの使用方法を示しています。呼び出されると、この関数は現在のトークンが '(' トークンであることを想定していますが、部分式を構文解析した後、 ')' が待機していない可能性があります。たとえば、ユーザーが「(4)」ではなく「(4 x」と入力した場合、パーサーはエラーを発行する必要があります。エラーが発生する可能性があるため、パーサーはエラーが発生したことを示す方法が必要です。パーサーでは、エラーが発生するとnullを返します。
2) この関数のもう1つの興味深い側面は、ParseExpressionを呼び出すことによって再帰を使用していることです（すぐにParseExpressionがParseParenExprを呼び出すことができることがわかります）。これは、再帰的な文法を処理でき、各生成規則を非常にシンプルに保つことができるため、強力です。括弧はASTノード自体を構築しないことに注意してください。このようにすることもできますが、括弧の最も重要な役割はパーサーをガイドし、グループ化を提供することです。パーサーがASTを構築すると、括弧は必要ありません。
次の単純な生成規則は、変数参照と関数呼び出しを処理するためのものです。
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(IdName);
// Call.
getNextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> Args;
if (CurTok != ')') {
while (true) {
if (auto Arg = ParseExpression())
Args.push_back(std::move(Arg));
else
return nullptr;
if (CurTok == ')')
break;
if (CurTok != ',')
return LogError("Expected ')' or ',' in argument list");
getNextToken();
}
}
// Eat the ')'.
getNextToken();
return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
このルーチンは、他のルーチンと同じスタイルに従います。（現在のトークンがtok_identifierトークンである場合に呼び出されることを想定しています）。また、再帰とエラー処理も備えています。この興味深い側面の1つは、現在の識別子がスタンドアロンの変数参照であるか、関数呼び出し式であるかを判断するために*先読み*を使用していることです。識別子の後のトークンが '(' トークンかどうかをチェックし、必要に応じてVariableExprASTノードまたはCallExprASTノードを構築することで、これを処理します。
単純な式の構文解析ロジックがすべて揃ったので、それを1つのエントリポイントにまとめるヘルパー関数を定義できます。 チュートリアルの後半でより明確になる理由から、このクラスの式を「プライマリ」式と呼びます。任意の一次式を構文解析するには、それがどのような種類の式であるかを判断する必要があります。
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (CurTok) {
default:
return LogError("unknown token when expecting an expression");
case tok_identifier:
return ParseIdentifierExpr();
case tok_number:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
}
}
この関数の定義を見ると、さまざまな関数でCurTokの状態を想定できる理由がより明らかになります。これは先読みを使用して、どの種類の式が検査されているかを判断し、関数呼び出しで構文解析します。
基本的な式が処理されたので、二項式を処理する必要があります。それらはもう少し複雑です。
2.5. 二項演算子の構文解析¶
二項式は、あいまいな場合が多いため、構文解析が znacznie困難です。たとえば、文字列「x+y*z」が与えられた場合、パーサーはそれを「(x+y)*z」または「x+(y*z)」のいずれかとして構文解析することを選択できます。数学の一般的な定義では、 "*"（乗算）は "+"（加算）よりも*優先順位*が高いため、後の構文解析が想定されます。
これを処理する方法はたくさんありますが、洗練されていて効率的な方法は、演算子順位構文解析を使用することです。この構文解析手法では、二項演算子の優先順位を使用して再帰をガイドします。まず、優先順位の表が必要です。
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
if (!isascii(CurTok))
return -1;
// Make sure it's a declared binop.
int TokPrec = BinopPrecedence[CurTok];
if (TokPrec <= 0) return -1;
return TokPrec;
}
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
...
}
Kaleidoscopeの基本的な形式では、4つの二項演算子のみをサポートします（これは、勇敢で大胆な読者であるあなたが明らかに拡張できます）。 GetTokPrecedence関数は、現在のトークンの優先順位を返します。トークンが二項演算子でない場合は-1を返します。マップを使用すると、新しい演算子を簡単に追加でき、アルゴリズムが関係する特定の演算子に依存しないことが明らかになりますが、マップを削除してGetTokPrecedence関数で比較を行うこともできます。（または、固定サイズ配列を使用するだけです）。
上記ヘルパー関数を定義したので、二項式の解析を開始できます。演算子の優先順位解析の基本的な考え方は、潜在的に曖昧な二項演算子を含む式を部分に分解することです。たとえば、式「a+b+(c+d)*e*f+g」を考えてみましょう。演算子の優先順位解析は、これを二項演算子で区切られた主要式のストリームと見なします。そのため、最初に主要式「a」を解析し、次にペア[+, b] [+, (c+d)] [*, e] [*, f]、そして[+, g]を確認します。括弧は主要式であるため、二項式パーサーは(c+d)のような入れ子になった部分式をまったく気にする必要がないことに注意してください。
まず、式は主要式で、その後ろに[二項演算子,主要式]のペアが続く場合があります。
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
ParseBinOpRHSは、ペアのシーケンスを解析する関数です。これは、優先順位と、これまでに解析された部分の式へのポインタを取ります。「x」は完全に有効な式であることに注意してください。そのため、「binoprhs」は空にすることができ、その場合は渡された式を返します。上記の例では、コードは「a」の式をParseBinOpRHSに渡し、現在のトークンは「+」です。
ParseBinOpRHSに渡される優先順位値は、関数が処理できる*最小の演算子の優先順位*を示します。たとえば、現在のペアストリームが[+, x]で、ParseBinOpRHSに40の優先順位が渡された場合、トークンは消費されません（「+」の優先順位は20しかないため）。これを念頭に置いて、ParseBinOpRHSは以下から始まります。
/// binoprhs
/// ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
std::unique_ptr<ExprAST> LHS) {
// If this is a binop, find its precedence.
while (true) {
int TokPrec = GetTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (TokPrec < ExprPrec)
return LHS;
このコードは現在のトークンの優先順位を取得し、それが低すぎるかどうかを確認します。無効なトークンの優先順位を-1と定義したため、このチェックは、トークンストリームに二項演算子がなくなるとペアストリームが終了することを暗黙的に認識します。このチェックが成功した場合、トークンは二項演算子であり、この式に含まれることがわかります。
// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken(); // eat binop
// Parse the primary expression after the binary operator.
auto RHS = ParsePrimary();
if (!RHS)
return nullptr;
そのため、このコードは二項演算子を処理（および記憶）し、次に続く主要式を解析します。これにより、ペア全体が構築され、最初のペアは実行例では[+, b]になります。
式の左辺とRHSシーケンスの1つのペアを解析したので、式をどのように関連付けるかを決定する必要があります。具体的には、「(a+b) 二項演算子 未解析部分」または「a + (b 二項演算子 未解析部分)」を持つことができます。これを決定するために、「二項演算子」を先読みしてその優先順位を決定し、BinOpの優先順位（この場合は「+」）と比較します。
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
「RHS」の右側の二項演算子の優先順位が現在の演算子の優先順位以下の場合、括弧は「(a+b) 二項演算子…」として関連付けられることがわかります。この例では、現在の演算子は「+」で、次の演算子は「+」であるため、同じ優先順位であることがわかります。この場合、「a+b」のASTノードを作成し、解析を続けます。
... if body omitted ...
}
// Merge LHS/RHS.
LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS),
std::move(RHS));
} // loop around to the top of the while loop.
}
上記の例では、これは「a+b+」を「(a+b)」に変換し、現在のトークンとして「+」を使用してループの次の反復を実行します。上記のコードは、主要式として「(c+d)」を処理、記憶、および解析し、現在のペアを[+, (c+d)]にします。次に、主要式の右側の二項演算子として「*」を使用して、上記の「if」条件を評価します。この場合、「*」の優先順位は「+」の優先順位よりも高いため、if条件に入ります。
ここで残されている重要な問題は、「if条件がどのように右辺全体を解析できるか」です。特に、この例でASTを正しく構築するには、RHS式変数として「(c+d)*e*f」のすべてを取得する必要があります。これを行うコードは驚くほどシンプルです（上記の2つのブロックのコードをコンテキストのために複製しました）。
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
RHS = ParseBinOpRHS(TokPrec+1, std::move(RHS));
if (!RHS)
return nullptr;
}
// Merge LHS/RHS.
LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS),
std::move(RHS));
} // loop around to the top of the while loop.
}
この時点で、主要式のRHSの二項演算子は、現在解析している二項演算子よりも優先順位が高いことがわかります。そのため、演算子がすべて「+」よりも優先順位が高いペアのシーケンスは、一緒に解析され、「RHS」として返される必要があることがわかります。これを行うには、ParseBinOpRHS関数を再帰的に呼び出し、続行するために必要な最小優先順位として「TokPrec+1」を指定します。上記の例では、これにより「(c+d)*e*f」のASTノードがRHSとして返され、「+」式のRHSとして設定されます。
最後に、whileループの次の反復で、「+g」部分が解析され、ASTに追加されます。この少量のコード（14行の重要な行）で、非常に洗練された方法で完全に一般的な二項式解析を正しく処理します。これはこのコードの whirlwind tour であり、やや微妙です。それがどのように機能するかを確認するために、いくつかの難しい例で試してみることをお勧めします。
これで式の処理は終わりです。この時点で、パーサーを任意のトークンストリームにポイントし、式の一部ではない最初のトークンで停止して、式を構築できます。次に、関数定義などを処理する必要があります。
2.6. 残りの部分の解析¶
次に欠けているのは、関数プロトタイプの処理です。Kaleidoscopeでは、これらは「extern」関数宣言と関数本体定義の両方に使用されます。これを行うコードは簡単で、あまり面白くはありません（式を理解できれば）。
/// prototype
/// ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
if (CurTok != tok_identifier)
return LogErrorP("Expected function name in prototype");
std::string FnName = IdentifierStr;
getNextToken();
if (CurTok != '(')
return LogErrorP("Expected '(' in prototype");
// Read the list of argument names.
std::vector<std::string> ArgNames;
while (getNextToken() == tok_identifier)
ArgNames.push_back(IdentifierStr);
if (CurTok != ')')
return LogErrorP("Expected ')' in prototype");
// success.
getNextToken(); // eat ')'.
return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}
これを考えると、関数定義は非常にシンプルで、プロトタイプと本体を実装するための式だけです。
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
getNextToken(); // eat def.
auto Proto = ParsePrototype();
if (!Proto) return nullptr;
if (auto E = ParseExpression())
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
return nullptr;
}
さらに、「sin」や「cos」などの関数を宣言したり、ユーザー関数の前方宣言をサポートしたりするために、「extern」をサポートしています。これらの「extern」は、本体のないプロトタイプです。
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
最後に、ユーザーが任意のトップレベル式を入力して、オンザフライで評価できるようにします。これらを処理するために、匿名のnullary（ゼロ引数）関数を定義します。
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto E = ParseExpression()) {
// Make an anonymous proto.
auto Proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
}
return nullptr;
}
すべての要素が揃ったので、構築したこのコードを実際に*実行*できる小さなドライバを構築しましょう！
2.7. ドライバ¶
このドライバは、トップレベルのディスパッチループですべての解析部分を呼び出すだけです。ここにはあまり興味深いものはないので、トップレベルのループのみを含めます。「トップレベルの解析」セクションの完全なコードについては、以下を参照してください。
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof:
return;
case ';': // ignore top-level semicolons.
getNextToken();
break;
case tok_def:
HandleDefinition();
break;
case tok_extern:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}
これの最も興味深い部分は、トップレベルのセミコロンを無視することです。なぜこうなるのか疑問に思うかもしれません。基本的な理由は、コマンドラインで「4 + 5」と入力した場合、パーサーはそれが入力の終わりかどうかをわからないためです。たとえば、次の行に「def foo…」と入力すると、4+5はトップレベル式の終わりになります。または、「* 6」と入力して式を続けることもできます。トップレベルのセミコロンを使用すると、「4+5;」と入力でき、パーサーは入力が完了したことを認識します。
2.8. 結論¶
400行未満のコメント付きコード（コメントなし、空白行なしの240行のコード）で、字句解析器、パーサー、ASTビルダーを含む最小限の言語を完全に定義しました。これで、実行可能ファイルはKaleidoscopeコードを検証し、文法的に無効かどうかを通知します。たとえば、サンプルのインタラクションを以下に示します。
$ ./a.out
ready> def foo(x y) x+foo(y, 4.0);
Parsed a function definition.
ready> def foo(x y) x+y y;
Parsed a function definition.
Parsed a top-level expr
ready> def foo(x y) 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）を生成する方法について説明します。
2.9. 完全なコードリスト¶
実行例のための完全なコードリストを以下に示します。
# Compile
clang++ -g -O3 toy.cpp
# Run
./a.out
コードは次のとおりです。
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>
//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
tok_eof = -1,
// commands
tok_def = -2,
tok_extern = -3,
// primary
tok_identifier = -4,
tok_number = -5
};
static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal; // Filled in if tok_number
/// gettok - Return the next token from standard input.
static int gettok() {
static int LastChar = ' ';
// Skip any whitespace.
while (isspace(LastChar))
LastChar = getchar();
if (isalpha(LastChar)) { // identifier: [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 == '.') { // Number: [0-9.]+
std::string NumStr;
do {
NumStr += LastChar;
LastChar = getchar();
} while (isdigit(LastChar) || LastChar == '.');
NumVal = strtod(NumStr.c_str(), nullptr);
return tok_number;
}
if (LastChar == '#') {
// Comment until end of line.
do
LastChar = getchar();
while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
}
// Check for end of file. Don't eat the EOF.
if (LastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
int ThisChar = LastChar;
LastChar = getchar();
return ThisChar;
}
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//
namespace {
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
};
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
};
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;
public:
VariableExprAST(const std::string &Name) : Name(Name) {}
};
/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;
public:
BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;
public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
};
/// PrototypeAST - This class represents the "prototype" for a function,
/// which captures its name, and its argument names (thus implicitly the number
/// of arguments the function takes).
class PrototypeAST {
std::string Name;
std::vector<std::string> Args;
public:
PrototypeAST(const std::string &Name, std::vector<std::string> Args)
: Name(Name), Args(std::move(Args)) {}
const std::string &getName() const { return Name; }
};
/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;
public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parser is looking at. getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
if (!isascii(CurTok))
return -1;
// Make sure it's a declared binop.
int TokPrec = BinopPrecedence[CurTok];
if (TokPrec <= 0)
return -1;
return TokPrec;
}
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
static std::unique_ptr<ExprAST> ParseExpression();
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
getNextToken(); // eat (.
auto V = ParseExpression();
if (!V)
return nullptr;
if (CurTok != ')')
return LogError("expected ')'");
getNextToken(); // eat ).
return V;
}
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(IdName);
// Call.
getNextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> Args;
if (CurTok != ')') {
while (true) {
if (auto Arg = ParseExpression())
Args.push_back(std::move(Arg));
else
return nullptr;
if (CurTok == ')')
break;
if (CurTok != ',')
return LogError("Expected ')' or ',' in argument list");
getNextToken();
}
}
// Eat the ')'.
getNextToken();
return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (CurTok) {
default:
return LogError("unknown token when expecting an expression");
case tok_identifier:
return ParseIdentifierExpr();
case tok_number:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
}
}
/// binoprhs
/// ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
std::unique_ptr<ExprAST> LHS) {
// If this is a binop, find its precedence.
while (true) {
int TokPrec = GetTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (TokPrec < ExprPrec)
return LHS;
// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken(); // eat binop
// Parse the primary expression after the binary operator.
auto RHS = ParsePrimary();
if (!RHS)
return nullptr;
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
if (!RHS)
return nullptr;
}
// Merge LHS/RHS.
LHS =
std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
}
}
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
/// prototype
/// ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype() {
if (CurTok != tok_identifier)
return LogErrorP("Expected function name in prototype");
std::string FnName = IdentifierStr;
getNextToken();
if (CurTok != '(')
return LogErrorP("Expected '(' in prototype");
std::vector<std::string> ArgNames;
while (getNextToken() == tok_identifier)
ArgNames.push_back(IdentifierStr);
if (CurTok != ')')
return LogErrorP("Expected ')' in prototype");
// success.
getNextToken(); // eat ')'.
return std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
getNextToken(); // eat def.
auto Proto = ParsePrototype();
if (!Proto)
return nullptr;
if (auto E = ParseExpression())
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
return nullptr;
}
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto E = ParseExpression()) {
// Make an anonymous proto.
auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
}
return nullptr;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
//===----------------------------------------------------------------------===//
// Top-Level parsing
//===----------------------------------------------------------------------===//
static void HandleDefinition() {
if (ParseDefinition()) {
fprintf(stderr, "Parsed a function definition.\n");
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleExtern() {
if (ParseExtern()) {
fprintf(stderr, "Parsed an extern\n");
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (ParseTopLevelExpr()) {
fprintf(stderr, "Parsed a top-level expr\n");
} else {
// Skip token for error recovery.
getNextToken();
}
}
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof:
return;
case ';': // ignore top-level semicolons.
getNextToken();
break;
case tok_def:
HandleDefinition();
break;
case tok_extern:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}
//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
// Prime the first token.
fprintf(stderr, "ready> ");
getNextToken();
// Run the main "interpreter loop" now.
MainLoop();
return 0;
}