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,
store it as our property, and since this parser is known as recursive descent parser - what it
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.