Hi and welcome to the first session of the  "Building a Parser from scratch class"! My  

name is Dmitry Soshnikov and I'll be teaching this  class and just to set the agenda - this is purely  

practical class, right we will have just few  amount of theory in this class related to parsing,  

but most of the videos will be actually practical  exercises, building a parser from scratch, and  

we'll be building a parser for a full programming  language similar in syntax to Java or JavaScript.  

And for those of you who are interested  in deeper theory for parsing and parsing  

algorithms you may consider also the "Essentials  of Parsing" class where we discuss in detail all  

the parsing algorithms such as LL(1), LR(1)  parsing, etc, and we also built a parser in  

that class using a parser generator tool. And in  the current class - in the Building a Parser from  

scratch" - we will be building a manual parsing,  Recursive-descent, and we will see the whole  

implementation, building a Tokenizer, Parsing  modules construction, AST nodes, etc. Right,  

since sometimes you don't need to go deeper to the  theory and just need to build an actual parser, an  

actual practical thing, so in this case this class  is exactly for you. And for those who have taken  

the "Essentials of Interpretation" class where  we built an interpreter for programming language,  

this parser will be a frontend, since in that  class we used S-expression format for actual  

interpretation, for actual runtime semantics. And  at the S-expression being actually the abstract  

syntax tree format fits the best for interpreters,  however when it comes to ergonomics, users of your  

language usually prefer writing something like  this which looks on the right hand side. So in the  

"Building a Parser from scratch" we will take the  syntax which is on the right hand side and we'll  

parse it into AST, into Abstract Syntax Tree. And  with this being said let's start from the parsing  

pipeline, we will slightly talk about theory and  already today we'll jump into implementation.  

So let's say we have the abstract program  which prints "hello", and the first module  

which meets our program is known as Tokenizer.  Sometimes it's called Lexer or Scanner, and it  

defines the Lexical analysis. And the purpose of  the tokenizer is to group individual characters  

into recognizable stream of tokens, right  as you can see here we scan two tokens:  

identifier with the value "print" and the string  with the value "hello". Again the purpose is just  

to group the characters into higher abstracted  entities since it's more convenient to work with  

these tokens versus the individual characters.  And as you can see token has type and the value.  

And we also should say that the tokenizer  doesn't make any commitment whether our program  

is syntactically valid, right in this case as we  can see we have two tokens: the keyword "if" and  

the open parenthesis "(" and for us, the readers  of this code, this program is definitely invalid,  

but the tokenizer will normally scan this  program and will extract two tokens. Now  

the module which actually validates whether  our program is syntactically valid is known  

as Parser or Syntactic analysis. And in theory the  purpose of the parser is exactly the validation,  

but on practice the parser produces the next  intermediate representation known as Abstract  

Syntax Tree or the AST for short. And in this  case as you can see we have the Call expression  

with the function name "print" and arguments,  with the single argument, the word "hello".  

So let's see one more example of the AST. So we  have the expression "x = 10 * 5 + y". And the  

abstract syntax trees usually have the operators  or the function names as the interior or the root  

nodes - in this case we have the assignment  operator "=" which has left hand side and the  

right hand side, and as you can see the right hand  side here is a complex expression itself - it's  

the "+" operator which also has the left hand side  and the right hand side, again the left hand side  

is the complex expression "*", and the right hand  side is the identifier "y". Okay so the purpose of  

the parser again is to translate this string into  this tree, and this tree is the form which can  

be further passed either to the code generator  or to interpreter to obtain the actual result.  

And if we look again at the syntax, sometimes  people who are not familiar with parsing process  

start thinking: "...how do you actually parse the  string into the tree?.." And the first approach  

people try is just using Regular Expressions. But  in fact regular expressions don't work for parsing  

programming languages. And in the parsing process  we do use regular expressions but those are used  

only for the tokenizer module, right if we take  these two modules - tokenizer and the parser - the  

tokenizer, that is the scanner, uses exactly the  regular expressions, and we'll be using them a lot  

in the tokenizer module. As you can see here we  define the regular expression for numbers \d+  

which means "a digit repeated one or more times",  and we give a name for this regular expression,  

right we name this token as "number". And the  parser itself is defined using something what  

is called Backus-Naur form or the BNF for short.  In this case we have the production "E" that is  

"expression" which derives only one number, right  this is very simple grammar, very simple program,  

which accepts only numbers. And this program can  accept any number since the regular expression  

which is used in tokenizer accepts any digits. And  the Backus-Naur form is exactly the notation to  

describe syntaxes or grammars of languages. Let's  take a look at one more example. So here we have  

the main entry point which is called "Program"  and we say the Program consists of StatementList.  

The StatementList is the list of statements,  and each statement might be anything, for  

example here we have BlockStatement, IfStatement,  FunctionDeclaration, etc. And we're recursively  

defining each production and describe what it  means. For example if the FunctionDeclaration here  

is defined as the "def" keyword, as you can see  here with the cursive we define the actual tokens,  

right not the production rules but actual  tokens which can appear in our programs "as is".  

So the function declaration is defined as "def",  followed by the function name which is Identifier,  

followed by the Arguments which are in the  parenthesis, and followed by the function  

body which is nothing but the BlockStatement. Okay  so that's the BNF grammar which we'll be following  

when we'll be building our manual recursive  descent parser. And when we think about  

tree format, the simple format which is also the  most practical today, is just the JSON notation,  

right each AST node is represented as the object  which has the "type" property, for example for the  

expression "7 + 3 * 4" we see the BinaryExpression  with the operator "+", okay which has left hand  

side, which is number 7, NumericLiteral, and the  right hand side which is a complex expression  

itself, also the BinaryExpression, but it  has different operator, the "*" operator.  

And as you can see here we have the correct  precedence of operations: here the "*" operator  

has the higher precedence than the "+" operator,  and this is also something parser should enforce.  

And when we talk about parsers in general  we differentiate the hand-written parsers  

and automatically generated. And this class is  devoted specifically to the hand-written parsers  

where the main implementation and the most  practical today (and the most powerful)  

is known as Recursive-descent parser. So we'll  be building exactly this parser in this class,  

but also the parsing process can be automated.  And here we have all these cryptic names:  

LL, LR, GLR, PEG, etc, and you can take  a look at the parser generator tool  

called Syntax which is  language-agnostic parser generator.  

Basically what it does is, you can take a  grammar and just create an automated parser.  

But when we have a complex language and want to  understand the parsing process in full details,  

the manual recursive descent parser is pretty much  the standard today for the most production-level  

languages, right since you have the full  control of the parser and you may define  

better error handling, better error messages, and  build more sophisticated parsers which are not  

possible with automated parsers. Again for those  of you who are interested in automated parsers  

and in parsing algorithms, you can address the  class called "Essentials of Parsing" where we  

discuss in detail all these parsing algorithms  and build a parser using a parser generator.  

So let's jump right away into practice, and  with this being said, please meet Letter!  

The Letter is a syntax for a programming  language with a functional heart and  

object-oriented support. And this syntax will be  parsed into AST, right we already agreed to use  

JSON structure for AST with the "type" property,  but you may also parse into S-expression format  

which is also nothing but the AST, and we  will show how to transform different types  

of ASTs between each other. So once again the  Letter syntax on the left and on the right we  

see the parsed AST for the syntax. Okay with this  being said, let me switch to the implementation.  

Okay, so I'm going to create the directory for our  project called "letter-rdp", and RDP here means  

the Recursive-descent parser. And let's make the  source Parser.js - we'll be using Node.js and  

JavaScript to build this parser, please address  how to install Node.js, and the JavaScript being  

the most practical language today should  be accessible for many engineers. And let's  

start building our parser. Now the main API  of the parser is exactly the "parse" method  

which should accept a string and return an AST.  Okay so let's do this - we accept the string,  

means - it starts from the main entry point,  the starting symbol, and goes recursively down  

until it parses the full tree. So let's  name the main entry point as the Program,  

okay. And for each production in the  grammar we're going to have the handler  

function with the same name, so for the Program  production we have the Program function name.  

And today we're going to support only numbers,  let's name the numbers as NumericLiteral. In  

the documentation for each handler of the  production we will write the actual grammar,  

right what this function or what this grammar  rule derives. In this case we say Program  

derives NumericLiteral. In other words we say, our  program may consist only of one number. And that  

exactly what we return - the Program is just  one number, that is just one NumericLiteral.  

And since we introduced the new function,  NumericLiteral, we need to define it. And what  

is NumericLiteral? Well, it's just a number.  This NUMBER, used in the upper-case letters,  

is coming from the tokenizer. We will define the  tokenizer in the next lecture and today we will  

consider the whole string as just containing one  number. So what should return the NumericLiteral?  

As we said, any production should return an  AST node, and we agreed that our AST nodes will  

have the "type" which is the "NumericLiteral",  and some properties associated with this type.  

In this case the NumericLiteral has only one  property, let's call it "value", and the value  

should contain the numeric representation  of the number from the parsing string,  

since the string contains of characters, that  is the string characters, we need to convert the  

string into a number, so we use the whole string  as the program and just convert it to a number.  

At this point we don't use any tokenizer and just  support only a single number. And this should be  

it. Okay, let's write the small test runner  - I'm creating the __tests__ directory and  

the main test runner, and for now let's just  use directly program evaluation - I'm creating  

the parser instance from our Parser class. As  we said the first program will be very simple,  

it will support only one number, let's say  42. And as just in any parser API we call  

the "parse" method passing the string  program, and we should obtain the AST.  

Okay, let's execute, and yes - we have the first  AST node from the parser, and it's NumericLiteral.  

As you can see the 42 number is correctly  presented here as the number but not as a string  

because we use the Number(...) conversion.  And this parser should support any number,  

let's try something else, and yes - as you can  see it's supported. Okay so that's it for today,  

this is the introduction lecture and the agenda  what we'll be building. So in the next lecture  

we'll continue working with our parser and we'll  introduce the tokenizer and we'll be extending  

the language, adding more support for other  constructs. Okay, thanks and see you in the class.