Hi and welcome to the first session of the "Essentials of Parsing" class! My name is
Dmitry Soshnikov and I'll be teaching this class, and let's start from the agenda what
we'll be studying in this class. Now this class has two parts. And the first part of this class
will be devoted specifically to parsing theory, different algorithms, such as LL, LR parsing, what
is Left recursion, Context-free grammars, what is Shift-Reduce conflict, etc. And in the second
part which actually will run in parallel we'll be implementing a full parser for programming
language very similar to Python or JavaScript. And for those of you who have taken the "Essentials of
Interpretations" class this will be a frontend for the Eva programming language which we have
built in that interpreters class. We have been using the S-expression format to focus on the
interpretation and runtime semantics itself and skip the parsing stage altogether. And for
runtime semantics S-expression does exactly the job right - it allows starting and implementing
the language itself right away. And why would we need a separate syntax in that case? Well,
first of all it's ergonomics. Pretty often users of your language would like to write
something which looks as similar on the right hand side. So a good syntax of your programming
language is also a reason why people would choose to use specifically your programming
language. And with this being said let's get started and we'll talk about parsing
pipeline. We have already talked about it in the "Essentials of Interpretation" so for those of
you who have taken that class this will be slight repetition but let's get started! So let's say we
have an abstract program which prints the word "hello". And the first module which meets your
program is known as Tokenizer or Lexical analysis. Sometimes this module is called Lexer or Scanner,
and what's the purpose of the Tokenizer? As we can see here we have characters "p", "r", "i",
"n", "t", "(", etc and it's not very convenient to work with individual characters. So the purpose
of the Tokenizer is exactly to group this set of characters and to produce the first intermediate
representation known as stream of tokens. And as you can see token has a type and the value,
and this value is also called a Lexeme. So in this case we have two tokens: the identifier
with the value "print" and the string token with the value "hello". And we should also say
that tokenizer doesn't validate whether our program is syntactically valid. It might be
completely syntactically invalid as in this case we have the program which consists of two tokens:
the keyword "if" and the "(". And for us for readers of this code it's obvious that this
code is invalid but tokenizer will normally be able to obtain two tokens, again the keyword "if"
and "(". Now the module which actually validates whether our program is valid, syntactically valid,
is known as Parser. And this is exactly the purpose of our class: we'll be focusing
specifically on this module and we'll implement and talk about all the different algorithms used
for parsing. And in theory the purpose of the parser is specifically the validation,
that is whether the string is accepted by your grammar or not. But in practice parser produces
the next intermediate representation known as Abstract Syntax Tree or AST for short. This is
a tree representation of our program and this is something what we can already feed to an
interpreter or to virtual machine and to obtain the result. And again in this class we will build
a parser which consumes some programming string representation and produces specifically the AST.
So let's take one more example of the AST: x = 10 * 5 + y. So a possible AST for this program might
be an Assignment operator = which has the left hand side and right hand side. And on the left
hand side we see the identifier "x" and the right hand side here is a complex expression itself.
This is an Addition + which has left-hand side, which is Multiplication * again with the left-hand
side 10, and right-hand side 5, and also the right-hand side for the Addition that is the
identifier "y". So that is the example of the AST. And when we talk about parsers we differentiate
the hand-written parsers and automatically generated parsers. Now for the hand written
parsers we mainly have the implementation which is known as Recursive-descent and there are multiple
implementations with backtrack, predictive -- most of them are recursive, that's why it's
called Recursive-descent. But in general the parsing process can be automated and there are
tools which are called Parser generators which can take a grammar of your language and produce a fast
non-recursive, that is table-driven, parsers which can scan in linear time. As an example
you can take a look at this tool called Syntax which is language-agnostic parser generator.
What is language-agnostic? It means you can write a grammar once and then produce multiple targets
for different languages for example JavaScript, Python, Rust there's a Python integration,
Ruby and many others. And we'll be actively using Syntax tool in this class to build our parser. So
the parsing process relates to text processing. A text consists of sentences, sentences consist
of words or tokens (lexemes), and this is exactly what we start with and we'll talk about symbols,
alphabets and languages. Now first of all let's talk about alphabet. Usually in parsing process
the alphabet is denoted with a Greek letter Sigma. And let's say we have this alphabet
consisting of only two characters: "a" and "b". An English alphabet consists of 26 characters,
Russian alphabet consists of 33 characters, in this case we have only 2. So we say that the
alphabet is a set of characters. And a language is also a set but in this case it's a set of strings
consisting of the characters from the alphabet. For example the language L1 here consists of any
possible strings of any length of any permutations from the symbols from this alphabet. And as you
can see we call such languages as infinite, since we can generate again all possible permutations.
However we can continue adding some restrictions for example the language L2. Specifically that
all the strings in this language should exactly have the length 2. And in this case the set of
strings is actually finite. The main takeaway here: once we start applying restrictions on
the language we form exactly the Grammar. The grammar is a set of restrictions on top of the
alphabet for the specific language so let's take a look what is the Formal grammar. Again all the
languages have grammars: there is English grammar, there is Russian grammar and programming languages
have grammars. Technically a grammar is a tuple of 4 elements: (N, T, P, S). Let's take a look
what it is. On the right hand side here we see an example grammar and let's take a look what
specifically each component means here. So the N which stands for Non-terminals or the Variables
defines a set of symbols in our grammar which can hold some value, which can hold either a
single letter a single character or a subset of other characters. And in this case we have two
variables: the variable S which is the starting symbol in this grammar and the variable X which
as you can see can be rewritten with the value "b". So once again a variable can be replace with
the value it holds. In contrast the terminals are the actual symbols which appear in our strings in
our programs "as is". It's not a special variable but exactly the specific character that's why it's
called terminal that is final symbol. And in this case we have two terminals: again the character
"a" and the character "b". The P component defines the set of Productions or the Rules
in this grammar. These are exactly restrictions or rules which form our language which specifically
tells how the language is structured. And final component in the grammar is the starting symbol.
This is just the first production the symbol we start our analysis from and start our derivation
process that is replacing some variables followed by the values they hold. So once again this is the
grammar and this tuple (NTPS) is enough to describe any complex programming language:
context-free, context-sensitive regular, as we will see shortly, and let's move forward. And
when we talk about grammars there is so-called Chomsky grammar hierarchy, defined by the Noam
Chomsky and who made a great contribution to the formal grammars to programming languages and
natural languages processing. And Chomsky defined this hierarchy consisting of 4 types of grammars:
the Unrestricted grammars, that is Type 0, are used mainly for natural languages processing,
the Context-sensitive and mainly Context-free are used specifically for parsing programming
languages and the Regular grammars are used for parsing regular expressions. To reiterate in
this class we'll be focusing specifically on the Context-free grammars. So what is Context-free
grammar? Why Context-free grammars? Well, it turns out, the Regular expressions which we
studied in the "Automata Theory" class, are not enough to parse a programming languages.
The simplest example, balanced parenthesis, is not possible to parse with classic regular expressions
based on the finite automata. On the other hand the context-free grammar which is abbreviated
as CFG is trivial here, let's take a look. So first of all we replace the inner S by itself,
that is again parentheses, S, parentheses. Again replace S by itself, finally we eliminate the S
by the second rule the symbol called Epsilon and literally it means we can eliminate the
symbol altogether. So again this is the trivial context-free grammar while it's not possible in
regular grammars and now let's give a formal definition of what a context-free grammar is.
First of all context-free grammar may have only one non-terminal on the left-hand side. In this
case we have non-terminal S and non-terminal X on the left-hand side. The second property
of a context-free grammar is that left-hand side cannot have any context. What this means,
the variable when it's appears on the right-hand side unconditionally and with no ambiguity defines
the specific value it holds. There is no X in this context, but when X appears in
that context it means something different - no, when X appears on the right-hand side it can be
rewritten here only with the value "b", and it doesn't matter how and when the X appears. And
the last property of a context-free grammar the right-hand side may contain a mix of terminals
and non-terminals in any order. Okay so that's it for today, this is the introductory lecture that's
exactly what we'll be studying in this class, we'll be talking about formal grammars build
parsers discuss parsing algorithms. And building a parser by itself is a complex engineering task and
implementing it will definitely make you a better engineer. Ok thanks and see you in the class.