X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2Ftutorial%2FLangImpl2.html;h=018d0be76032fcac56a4e1cfd7a84d0d13f6faa2;hb=04eeefb32a3ae7de4cde1908d30bff61e0d6b86e;hp=2339d96a91292e380746dc6915e6f5d291e74052;hpb=128eb863dfb242aac982b505a9aab06dc35be8d1;p=oota-llvm.git diff --git a/docs/tutorial/LangImpl2.html b/docs/tutorial/LangImpl2.html index 2339d96a912..018d0be7603 100644 --- a/docs/tutorial/LangImpl2.html +++ b/docs/tutorial/LangImpl2.html @@ -14,6 +14,7 @@
This routine follows the same style as the other routines (it expects to be +
This routine follows the same style as the other routines. (It expects to be called if the current token is a tok_identifier token). It also has recursion and error handling. One interesting aspect of this is that it uses look-ahead to determine if the current identifier is a stand alone variable reference or if it is a function call expression. It handles this by -checking to see if the token after the identifier is a '(' token, and constructs +checking to see if the token after the identifier is a '(' token, constructing either a VariableExprAST or CallExprAST node as appropriate.
-Now that we have all of our simple expression parsing logic in place, we can -define a helper function to wrap them up in a class. We call this class of -expressions "primary" expressions, for reasons that will become more clear -later. In order to parse a primary expression, we need to determine what sort -of expression it is:
+Now that we have all of our simple expression-parsing logic in place, we can +define a helper function to wrap it together into one entry point. We call this +class of expressions "primary" expressions, for reasons that will become more +clear later in the tutorial. In order to +parse an arbitrary primary expression, we need to determine what sort of +expression it is:
@@ -375,13 +383,13 @@ static ExprAST *ParsePrimary() {
Now that you see the definition of this function, it makes it more obvious -why we can assume the state of CurTok in the various functions. This uses -look-ahead to determine which sort of expression is being inspected, and parses -it with a function call.
+Now that you see the definition of this function, it is more obvious why we +can assume the state of CurTok in the various functions. This uses look-ahead +to determine which sort of expression is being inspected, and then parses it +with a function call.
-Now that basic expressions are handled, we need to handle binary expressions, -which are a bit more complex.
+Now that basic expressions are handled, we need to handle binary expressions. +They are a bit more complex.
@@ -434,16 +442,17 @@ int main() {For the basic form of Kaleidoscope, we will only support 4 binary operators -(this can obviously be extended by you, the reader). The +(this can obviously be extended by you, our brave and intrepid reader). The GetTokPrecedence function returns the precedence for the current token, or -1 if the token is not a binary operator. Having a map makes it easy to add new operators and makes it clear that the algorithm doesn't depend on the specific operators involved, but it would be easy enough to eliminate the map -and do the comparisons in the GetTokPrecedence function.
+and do the comparisons in the GetTokPrecedence function. (Or just use +a fixed-size array).With the helper above defined, we can now start parsing binary expressions. The basic idea of operator precedence parsing is to break down an expression -with potentially ambiguous binary operators into pieces. Consider for example +with potentially ambiguous binary operators into pieces. Consider ,for example, the expression "a+b+(c+d)*e*f+g". Operator precedence parsing considers this as a stream of primary expressions separated by binary operators. As such, it will first parse the leading primary expression "a", then it will see the @@ -471,8 +480,8 @@ static ExprAST *ParseExpression() {
ParseBinOpRHS is the function that parses the sequence of pairs for -us. It takes a precedence and a pointer to an expression for the part parsed -so far. Note that "x" is a perfectly valid expression: As such, "binoprhs" is +us. It takes a precedence and a pointer to an expression for the part that has been +parsed so far. Note that "x" is a perfectly valid expression: As such, "binoprhs" is allowed to be empty, in which case it returns the expression that is passed into it. In our example above, the code passes the expression for "a" into ParseBinOpRHS and the current token is "+".
@@ -519,7 +528,7 @@ operator and that it will be included in this expression:As such, this code eats (and remembers) the binary operator and then parses -the following primary expression. This builds up the whole pair, the first of +the primary expression that follows. This builds up the whole pair, the first of which is [+, b] for the running example.
Now that we parsed the left-hand side of an expression and one pair of the @@ -539,8 +548,8 @@ compare it to BinOp's precedence (which is '+' in this case):
If the precedence of the binop to the right of "RHS" is lower or equal to the precedence of our current operator, then we know that the parentheses associate -as "(a+b) binop ...". In our example, since the next operator is "+" and so is -our current one, we know that they have the same precedence. In this case we'll +as "(a+b) binop ...". In our example, the current operator is "+" and the next +operator is "+", we know that they have the same precedence. In this case we'll create the AST node for "a+b", and then continue parsing:
In our example above, this will turn "a+b+" into "(a+b)" and execute the next -iteration of the loop, with "+" as the current token. The code above will eat -and remember it and parse "(c+d)" as the primary expression, which makes the -current pair be [+, (c+d)]. It will then enter the 'if' above with "*" as the -binop to the right of the primary. In this case, the precedence of "*" is +iteration of the loop, with "+" as the current token. The code above will eat, +remember, and parse "(c+d)" as the primary expression, which makes the +current pair equal to [+, (c+d)]. It will then evaluate the 'if' conditional above with +"*" as the binop to the right of the primary. In this case, the precedence of "*" is higher than the precedence of "+" so the if condition will be entered.
The critical question left here is "how can the if condition parse the right @@ -574,8 +583,8 @@ context):
// the pending operator take RHS as its LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { - RHS = ParseBinOpRHS(TokPrec+1, RHS); - if (RHS == 0) return 0; + RHS = ParseBinOpRHS(TokPrec+1, RHS); + if (RHS == 0) return 0; } // Merge LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); @@ -593,15 +602,17 @@ precedence required for it to continue. In our example above, this will cause it to return the AST node for "(c+d)*e*f" as RHS, which is then set as the RHS of the '+' expression. -Finally, on the next iteration of the while loop, the "+g" piece is parsed. +
Finally, on the next iteration of the while loop, the "+g" piece is parsed and added to the AST. With this little bit of code (14 non-trivial lines), we correctly handle fully general binary expression parsing in a very elegant way. +This was a whirlwind tour of this code, and it is somewhat subtle. I recommend +running through it with a few tough examples to see how it works.
This wraps up handling of expressions. At this point, we can point the -parser at an arbitrary token stream and build an expression from them, stopping +parser at an arbitrary token stream and build an expression from it, stopping at the first token that is not part of the expression. Next up we need to -handle function definitions etc.
+handle function definitions, etc. @@ -612,7 +623,7 @@ handle function definitions etc.-The first basic thing missing is that of function prototypes. In Kaleidoscope, +The next thing missing is handling of function prototypes. In Kaleidoscope, these are used both for 'extern' function declarations as well as function body definitions. The code to do this is straight-forward and not very interesting (once you've survived expressions): @@ -632,6 +643,7 @@ static PrototypeAST *ParsePrototype() { if (CurTok != '(') return ErrorP("Expected '(' in prototype"); + // Read the list of argument names. std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); @@ -665,7 +677,7 @@ static FunctionAST *ParseDefinition() {
In addition, we support 'extern' to declare functions like 'sin' and 'cos' as -well as to support forward declaration of user functions. 'externs' are just +well as to support forward declaration of user functions. These 'extern's are just prototypes with no body:
Now that we have all the pieces, lets build a little driver that will let us +
Now that we have all the pieces, let's build a little driver that will let us actually execute this code we've built!
@@ -720,7 +732,7 @@ static void MainLoop() { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; - case ';': getNextToken(); break; // ignore top level semicolons. + case ';': getNextToken(); break; // ignore top-level semicolons. case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; @@ -730,13 +742,13 @@ static void MainLoop() { -The most interesting part of this is that we ignore top-level semi colons. +
The most interesting part of this is that we ignore top-level semicolons. Why is this, you ask? The basic reason is that if you type "4 + 5" at the -command line, the parser doesn't know that that is the end of what you will -type. For example, on the next line you could type "def foo..." in which case +command line, the parser doesn't know whether that is the end of what you will type +or not. For example, on the next line you could type "def foo..." in which case 4+5 is the end of a top-level expression. Alternatively you could type "* 6", which would continue the expression. Having top-level semicolons allows you to -type "4+5;" and the parser will know you are done.
+type "4+5;", and the parser will know you are done. @@ -746,32 +758,34 @@ type "4+5;" and the parser will know you are done.With just under 400 lines of commented code, we fully defined our minimal -language, including a lexer, parser and AST builder. With this done, the -executable will validate code and tell us if it is gramatically invalid. For +
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, +parser, and AST builder. With this done, the executable will validate +Kaleidoscope code and tell us if it is grammatically invalid. For example, here is a sample interaction:
-$ ./a.out -ready> def foo(x y) x+foo(y, 4.0); -ready> Parsed a function definition. -ready> def foo(x y) x+y y; -ready> Parsed a function definition. -ready> Parsed a top-level expr -ready> def foo(x y) x+y ); -ready> Parsed a function definition. -ready> Error: unknown token when expecting an expression -ready> extern sin(a); +$ ./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 +ready> ^D $
There is a lot of room for extension here. You can define new AST nodes, extend the language in many ways, etc. In the next -installment, we will describe how to generate LLVM IR from the AST.
+installment, we will describe how to generate LLVM Intermediate +Representation (IR) from the AST.Here is the complete code listing for this and the previous chapter. Note that it is fully self-contained: you don't need LLVM or any external -libraries at all for this (other than the C and C++ standard libraries of -course). To build this, just compile with:
+libraries at all for this. (Besides the C and C++ standard libraries, of +course.) To build this, just compile with:# Compile - g++ -g toy.cpp + g++ -g -O3 toy.cpp # Run ./a.out@@ -856,7 +870,7 @@ static int gettok() { if (LastChar == '#') { // Comment until end of line. do LastChar = getchar(); - while (LastChar != EOF && LastChar != '\n' & LastChar != '\r'); + while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); @@ -915,10 +929,11 @@ public: }; /// PrototypeAST - This class represents the "prototype" for a function, -/// which captures its argument names as well as if it is an operator. +/// which captures its name, and its argument names (thus implicitly the number +/// of arguments the function takes). class PrototypeAST { std::string Name; - std::vector< Args; + std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} @@ -940,7 +955,7 @@ public: //===----------------------------------------------------------------------===// /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current -/// token the parser it looking at. getNextToken reads another token from the +/// 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() { @@ -983,16 +998,18 @@ static ExprAST *ParseIdentifierExpr() { // Call. getNextToken(); // eat ( std::vector<ExprAST*> Args; - while (1) { - ExprAST *Arg = ParseExpression(); - if (!Arg) return 0; - Args.push_back(Arg); + if (CurTok != ')') { + while (1) { + ExprAST *Arg = ParseExpression(); + if (!Arg) return 0; + Args.push_back(Arg); - if (CurTok == ')') break; + if (CurTok == ')') break; - if (CurTok != ',') - return Error("Expected ')'"); - getNextToken(); + if (CurTok != ',') + return Error("Expected ')' or ',' in argument list"); + getNextToken(); + } } // Eat the ')'. @@ -1115,7 +1132,7 @@ static FunctionAST *ParseDefinition() { static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { // Make an anonymous proto. - PrototypeAST *Proto = new PrototypeAST("", std::vector<()); + PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; @@ -1150,7 +1167,7 @@ static void HandleExtern() { } static void HandleTopLevelExpression() { - // Evaluate a top level expression into an anonymous function. + // Evaluate a top-level expression into an anonymous function. if (FunctionAST *F = ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top-level expr\n"); } else { @@ -1165,7 +1182,7 @@ static void MainLoop() { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; - case ';': getNextToken(); break; // ignore top level semicolons. + case ';': getNextToken(); break; // ignore top-level semicolons. case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; @@ -1194,6 +1211,7 @@ int main() { }