<title>Kaleidoscope: Implementing a Parser and AST</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="author" content="Chris Lattner">
- <link rel="stylesheet" href="../llvm.css" type="text/css">
+ <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
</head>
<body>
-<div class="doc_title">Kaleidoscope: Implementing a Parser and AST</div>
+<h1>Kaleidoscope: Implementing a Parser and AST</h1>
<ul>
<li><a href="index.html">Up to Tutorial Index</a></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Chapter 2 Introduction</a></div>
+<h2><a name="intro">Chapter 2 Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Welcome to Chapter 2 of the "<a href="index.html">Implementing a language
with LLVM</a>" tutorial. This chapter shows you how to use the lexer, built in
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="ast">The Abstract Syntax Tree (AST)</a></div>
+<h2><a name="ast">The Abstract Syntax Tree (AST)</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>The AST for a program captures its behavior in such a way that it is easy for
later stages of the compiler (e.g. code generation) to interpret. We basically
class NumberExprAST : public ExprAST {
double Val;
public:
- explicit NumberExprAST(double val) : Val(val) {}
+ NumberExprAST(double val) : Val(val) {}
};
</pre>
</div>
class VariableExprAST : public ExprAST {
std::string Name;
public:
- explicit VariableExprAST(const std::string &name) : Name(name) {}
+ VariableExprAST(const std::string &name) : Name(name) {}
};
/// BinaryExprAST - Expression class for a binary operator.
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="parserbasics">Parser Basics</a></div>
+<h2><a name="parserbasics">Parser Basics</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Now that we have an AST to build, we need to define the parser code to build
it. The idea here is that we want to parse something like "x+y" (which is
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="parserprimexprs">Basic Expression
- Parsing</a></div>
+<h2><a name="parserprimexprs">Basic Expression Parsing</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>We start with numeric literals, because they are the simplest to process.
For each production in our grammar, we'll define a function which parses that
ExprAST *Arg = ParseExpression();
if (!Arg) return 0;
Args.push_back(Arg);
-
+
if (CurTok == ')') break;
-
+
if (CurTok != ',')
return Error("Expected ')' or ',' in argument list");
getNextToken();
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="parserbinops">Binary Expression
- Parsing</a></div>
+<h2><a name="parserbinops">Binary Expression Parsing</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Binary expressions are significantly harder to parse because they are often
ambiguous. For example, when given the string "x+y*z", the parser can choose
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="parsertop">Parsing the Rest</a></div>
+<h2><a name="parsertop">Parsing the Rest</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
The next thing missing is handling of function prototypes. In Kaleidoscope,
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="driver">The Driver</a></div>
+<h2><a name="driver">The Driver</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>The driver for this simply invokes all of the parsing pieces with a top-level
dispatch loop. There isn't much interesting here, so I'll just include the
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="conclusions">Conclusions</a></div>
+<h2><a name="conclusions">Conclusions</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>With just under 400 lines of commented code (240 lines of non-comment,
non-blank code), we fully defined our minimal language, including a lexer,
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="code">Full Code Listing</a></div>
+<h2><a name="code">Full Code Listing</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
Here is the complete code listing for this and the previous chapter.
<div class="doc_code">
<pre>
- # Compile
- g++ -g -O3 toy.cpp
- # Run
- ./a.out
+# Compile
+clang++ -g -O3 toy.cpp
+# Run
+./a.out
</pre>
</div>
tok_def = -2, tok_extern = -3,
// primary
- tok_identifier = -4, tok_number = -5,
+ tok_identifier = -4, tok_number = -5
};
static std::string IdentifierStr; // Filled in if tok_identifier
class NumberExprAST : public ExprAST {
double Val;
public:
- explicit NumberExprAST(double val) : Val(val) {}
+ NumberExprAST(double val) : Val(val) {}
};
/// VariableExprAST - Expression class for referencing a variable, like "a".
class VariableExprAST : public ExprAST {
std::string Name;
public:
- explicit VariableExprAST(const std::string &name) : Name(name) {}
+ VariableExprAST(const std::string &name) : Name(name) {}
};
/// BinaryExprAST - Expression class for a binary operator.
ExprAST *Arg = ParseExpression();
if (!Arg) return 0;
Args.push_back(Arg);
-
+
if (CurTok == ')') break;
-
+
if (CurTok != ',')
return Error("Expected ')' or ',' in argument list");
getNextToken();
//===----------------------------------------------------------------------===//
static void HandleDefinition() {
- if (FunctionAST *F = ParseDefinition()) {
+ if (ParseDefinition()) {
fprintf(stderr, "Parsed a function definition.\n");
} else {
// Skip token for error recovery.
}
static void HandleExtern() {
- if (PrototypeAST *P = ParseExtern()) {
+ if (ParseExtern()) {
fprintf(stderr, "Parsed an extern\n");
} else {
// Skip token for error recovery.
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
- if (FunctionAST *F = ParseTopLevelExpr()) {
+ if (ParseTopLevelExpr()) {
fprintf(stderr, "Parsed a top-level expr\n");
} else {
// Skip token for error recovery.
fprintf(stderr, "ready> ");
getNextToken();
+ // Run the main "interpreter loop" now.
MainLoop();
+
return 0;
}
</pre>
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
- Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
+ <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
+ Last modified: $Date$
</address>
</body>
</html>