Welcome back, guys! In the previous lectures we have talked about ambiguous grammars
and mentioned some reasons why the grammar can be ambiguous. In particular this may happen when we
don't enforce correct precedence, when for example plus operator suddenly got higher precedent than
the multiplication operator. And also when we have the same precedence this may happen when we don't
enforce correct associativity of operators, for example the minus operator is left associative.
Today's video will be mainly practical: we will test all the theory we have
learned so far on practice and we'll be using the Syntax tool which is a parser generator
which will allow writing us grammar of our language and producing a parser.
And once again in the previous lecture we showed how we can enforce these two principles:
we used the layers of non-terminals and also enforced needed associativity.
And once again today's lecture will be devoted to the introduction of the Syntax tool and also
we will actually start building a parser for our language and we will see how syntax helps us here.
Now in the first lecture we said that parsers can be either hand-written or automatically generated.
There are multiple algorithms which have been studied for a long time, don't worry for now about
all these LL, LR, etc - we will cover all this in detail but for now we just need to say that one
of the practical algorithms is LALR which allows parsing in one pass that is scanning a string only
once from left to right and without using any recursion, it will be fast table-driven parser.
Once again we'll be using the Syntax tool which you can find in this URL
and it is a language-agnostic parser generator. What is "language-agnostic"? This means we can
define a grammar once and then generate parsers for multiple target architectures, for multiple
target languages, it might be for JavaScript, for Python, for Rust and many other plugins exist
Now with this being said, please meet Letter! For those of you who have followed the "Essentials
of Interpretation" class know that we've been implementing the language which is called Eva.
And the Letter will be basically another language which might be a frontend for the Eva virtual
machine, for the Eva interpreter. So Letter specifically is a syntax for a very similar
programming language which both supports functional programming and object-oriented
programming. And here's the example how the Letter syntax will look like. On the left hand
side you can see the S-expression format which we've been using in Eva interpreter, and on the
right hand side you can see the Letter syntax. And in the previous lectures we said that the
parsing process is divided into two stages. And these are Tokenizer that is the lexical analysis
and the actual Parser or syntactic analysis. And we also said that for tokenizer we're
going to use the regular expression notation. It is possible to extract all stream of tokens
from a string using just regular expressions. However the regular expressions are not enough
for the actual parser and as we've been discussing we'll be using Backus-Naur form or BNF to define
the actual language. And with this being said I'm going to switch to the implementation.
So i'm going to create a directory for our project, letter, and as we said we start with the
grammar for our language. So i'm going to create a directory grammar and specifically "letter.bnf"
in the grammar directory. Okay let me switch to the editor
and let's just start writing the same grammar we have discussed in the previous lecture for
mathematical expressions. And we need to say that in Syntax all the grammars start with the double
percent sign %% and I'm taking the same grammar we've been discussing in the previous lecture
that is our starting symbol is E which can be E + T and as you can see we can use the raw tokens
directly in the BNF, and in this case they should be put in quotes like in this case this plus
sign '+', the plus operator. So the E might be E +T, exactly from our previous lecture or T.
Right, as we agreed, we're going to separate each BNF rule with a semicolon
so and put semicolon and define the next rule for T. T stands for "term" here for multiplication and
T might be the same T * F or F, where F stands for "factor" and defines the simple number the primary
expression. So this is our grammar. If this looks unfamiliar please take a look at the previous
lecture where we discussed in detail how we obtain this grammar. And as we said this is exactly
unambiguous grammar for mathematical expressions which accepts expressions such as 3 + 2 * 5. And
now let's take a look at this "NUMBER" token. In contrast with the '+' and '*' operators which are
raw tokens and can be defined directly using just quotes, the NUMBER is something a group of tokens,
it defines all the numbers as we said not just a specific number. So in this case we're going
to use a tokenizer. As we've been discussing in the previous lecture, the Syntax tool allows us
defining both syntactic grammar and lexical grammar in the same file but there is also
ability to extract the lexical grammar into a separate file. For now let's just define them all
here so it's easier to see where the tokens come from. Okay so I'm separating the syntactic grammar
from the lexical grammar and the lexical block is defined in these delimiters %lex and /lex.
And once again each grammar starts with a double percent sign %% after which we can
define our rules. So for numbers it's very simple, it's a simple regular expression /d+
which stands for digit and the + here means repeated one or more times. And for now we'll
be using just simple numbers but as an assignment you can add support for the floating point numbers
just extending this regular expression. So we have the grammar but the grammar itself doesn't mean
anything if we don't have a special tool which can process this grammar and produce us working parser
and such tools are called parser generators. As we already said we'll be using the Syntax tool so i'm
going to switch to the terminal and just install it from npm, and npm is the package manager for
Node.js, please address the documentation how to install npm if it's not installed on your machine.
The specific module is called syntax-cli that is the command line utility for this Syntax package.
So let's take a look at the help of the Syntax. And yes, as we can see here,
it accepts the grammar as the file so let's do this right away let's pass the grammar and
point to our letter.bnf which we just created. For now like I said let's use the LALR mode
which is the most practical in this case and let's just go ahead and parse the first expression for
example the simple number, let's say 2. And voila, that accepted which means our grammar
completely able to accept such numbers and again this comes from the tokenizer
which recognized all the simple numbers and propagated through the grammar rules to the
simple number. Okay let's try something else 2 + 2 and here we get some first problem. The parser
tells us unexpected token - space " " - and that exactly correct, in fact spaces or whitespaces are
not even handled in our tokenizer yet so let's go ahead and add support. Most of the languages just
skip white spaces all together let's follow the same approach, if we met a white space in the
tokenizer and the rule for the white spaces /s+ we're just going to omit token type altogether
which means Syntax will not be handling these tokens at all, so we're going to skip white spaces
and this is how easy to add support for white spaces and so let's go back and try again,
and yes now it's accepted. So congratulations, we already started to have
more-less working parser which can accept mathematical expressions. At this point we
don't build any intermediate presentations such as abstract syntax trees or anything
for now we're just testing the grammar and the parser and see whether it accepts our strings.
Okay so our grammar works, we have restructured it to be unambiguous and
our parser can perfectly accept the strings, but now let's actually see how Syntax can be helpful
in determining whether our grammar is ambiguous or we need to do something else with it.
So let's actually take the first grammar we had in the initial lecture which was very simple but
as we said it was completely ambiguous and actually didn't work. So it was E + E, E * E
or just NUMBER - super easy grammar but let's see that it's actually not working grammar and
if we try to parse the same string 2 + 2, we get something which is called shift-reduce conflict.
Now what does shift-reduce conflict we will learn in the next lectures in the greater detail
for now we can skip this terminology and just see that Syntax was able to determine that this
grammar is not working and in fact there is also some options in the syntax-cli such as --table
or --validate which can help seeing us that yes there are some problems with our grammar.
So let's take a look and as you can see in the states number 5 and 6 we see something in red
that is reduce and shift, reduce and shift - that is exactly the shift-reduce conflict
which tells that this grammar actually is not working. Now the two reasons why this grammar
is ambiguous is that we don't enforce correct precedence of operators and don't enforce correct
associativity of operators. The way we fix it by explicitly defining + to be left associative and
by explicitly defining the * operator has higher precedence than the + operator. Well in fact
Syntax has the full support of defining it as just a meta information. We can indicate Syntax that
the + operator should be %left associative and this is how we write it, the * operator is also
%left associative so we write it the same going after the + operator, and this is also interesting
feature - the fact that we wrote the * operator going after the + makes the * operator to have
the higher precedence than the + operator and this is actually all we need to fix this
ambiguous grammar and to turn it into unambiguous. Under the hood it's exactly the same what we did
manually here but this grammar might be even easier to read it has smaller parts and table and
let's just take a look execute again and yes as you can see all the shift-reduced
conflicts are gone and now this grammar is actually unambiguous, which again shows
that parser generator might be smart enough to figure out how it needs to structure underline
implementation if we provide some information for the associativity or precedence. Okay
and again if we remove the meta information about the correct precedence and correct associativity
we again see the same exact issue, this grammar has actually the following conflicts and this
is exactly the shift-reduced conflict. Again don't worry about this magic word "shift-reduce"
we will cover it in greater detail for now just pure practice showing the capabilities of the
Syntax tool and of parser generators in general. So once again we can actually continue using this
grammar E + E, E * E, but in this class I want to make it more explicit so we're going to use
this explicit grammar instead, and at this point let's start switching to more mature
grammar names, let's use it the same as it used in other programming languages
and to replace this E with AdditiveExpression, given more descriptive name
and by the way this is exactly how it's called for example in JavaScript programming language,
if you open specification for JavaScript you will find this AdditiveExpression
defined exactly like this. The factor becomes with a descriptive name MultiplicativeExpression and
the number will be held by the PrimaryExpression, something very basic which has the highest
precedence. Now to reiterate the closer non-terminal is to the starting symbol
the lower precedence it has, the starting symbol here is AdditiveExpression
which means the multiplication has higher precedence and primary has even higher precedence.
Okay once again let's see that this grammar doesn't have any conflicts,
as you can see Syntax was able to pick our new names and we'll be continuing with that grammar,
okay so what else can we get, for example the grouping expression, in fact if we put a
grouping parenthesis, this expression will have completely different semantics, in this case
(2 + 2) * 2 would become 8 instead of 6 and as you can see it's currently not supported because
we don't handle the parenthesis and so this will be your first assignment for today please go ahead
and implement the grouping parenthesis and inside those parentheses might be any expression, it
might be simple number or as 2 + 2 in this case or 2 * 2, just a small hint this grouping parenthesis
should have the same precedence as the primary expression and we will cover the solution in the
next lecture. Okay so that's it for today please go ahead and take a look at this grammar again
in the next lecture we'll continue extending this language and we'll come back to the theory
and we'll be gradually adding support for other operations. Okay thanks and see you in the class.