Welcome back, guys! So in today's lecture I'd like us to talk about more
convenient format for our tests and will be using an actual S-expression format
and as we said the JavaScript arrays match 1:1 already to
S-expressions but we still need to use all this quotation, commas, and the actual
S-expression format in the string presentation allows us writing the same
in cleaner way, so let's go ahead and introduce today the test utility with a
convenient "test" method which would accept our program in the string
presentation, in the S-expression format, and for this we're going to come
back to parsers and will implement a really tiny parser which takes the
S-expression and converts to the equivalent AST format. And as we
mentioned in the previous lectures the actual parsing will be extracted into a
separate class where we'll be studying different parsing algorithms and today
I'll show you how to use the "Syntax" tool which is a parser generator and allows
building us automatic parsers from BNF grammars. So our "test" method will looks
exactly like this: it takes the program in the S-expression and we would expect
the expected result. So the variable "x", variable "y", and let's do this expression
"x * 10 + y" which should be equal to 120. So let's go ahead and execute and
yes we see the test util is not implemented let's go ahead and add it
and the test function in our test utils should accept the Eva
instance that is the interpreter, the code in S-expression, that is in string
format and the expected result. We're going to use the same strict equal
assertion and in this case we have to parse this expression this string of the
expression to obtain the actual AST and then pass to the Eva evaluation
method and again we're testing whether it's equal to the expected
and like I said we'll be using this Syntax tool, okay I'm going to install it
from NPM and the module is called a "syntax-cli" is a command-line utility for
the Syntax package, and the main thing we should do here is to create the actual
grammar file, and recall that "BNF" stands for Backus-Naur Form and this is
the notation we used to define semantics: either the parsing semantics (and mainly
the parsing semantics) or we've been using also the BNF to define runtime semantics
and in contrast with the runtime semantics our parsing semantics will
have only two options: this is the "Atom" that is the simplest expression such as
numbers and strings, and symbols, and the "List", that is the nested sub-expression
and then we have to define what is Atom, and what is List. As we said
the Atom is the simplest expression and will be number string and symbol and
we'll get back to List a bit later after we will define the atoms. Now if we
recall the very first lecture we've been talking that parsing process is divided
into two stages: this is the syntactic grammar that is the actual parser and
the lexical grammar that is the Tokenizer. And in Syntax we define both grammars
here. The lexical block, the block for the lexical grammar is defined
through these delimiters: %lex and /lex and here we're going to define the
tokens. Now first of all we're going to skip all the white spaces okay and then
let's start defining our tokens. First let's define a string. So what is a string?
we said that in Eva will be using a double quotes notation so a string is
something in between of two double quotes -- plain simple. Now the
numbers are even simpler: \d. And for symbols, that is identifiers, will be
using special symbols: actual letters, numbers, characters like "+", "*", "=", etc.
The Syntax tool allows us doing quick tests by passing the expression we want
to parse and we also can obtain the tokens
and really if passed the value 42 we really see we obtained the token number
with the value of 42 and this is the result of our parsed value. Now let's go
ahead and test strings. By the way the quotes have to be escaped here so
we're adding the slashes, and so let's test it: the string "hello", and yes -- token type
"STRING" and the value "hello". Sounds great, let's test the symbols. Okay, so
the symbol foo, and -- yes, we get the symbol. Sounds great, we have the atoms, now let's
go down and implement the List. Again a list will stand for a complex
sub-expression. It might be an empty list or list containing some other expressions
by the way as the result of the number talking we want to return not the string
representation of the number but convert it to the actual number so Syntax
allows doing some post-processing for tokens and special rules and this block
is called semantic action. So in the semantic action of the numbers token we
convert it to the actual number. So finally let's go down to List. So what is List?
Well, it's something starts with the
parenthesis "(" and followed by the list entries. The list entries is optional and
followed by the closing parenthesis ")". As the result of the list in its semantic
action we're going to return the actual list entries and the return value in BNF
grammar is determined by this double dollar $$ sign: in this case we assign it to
the value $2 which corresponds to this the list entries
so open parenthesis "(" is $1, list enters is $2, and the
closing parenthesis ")" is variable $3. Wince we defined a new
non-terminal "ListEntries", we have to define what it is. So the list entries is
optional: it might be empty, so let's put a comment that it's empty and in
case if it's empty our return value for the list entries should be an empty array
and in case if it's not empty it can contain multiple expressions and
the way we define it using the recursive rule in the BNF and it's written like this
list entries followed by expression: "ListEntries Exp". So in this case this list entries might
be substituted by anything contained in the list entries that is by itself and
so this is how we obtain the multiple expressions followed by expressions
so list entries is replaced by list entries followed by expression, again replaced by
itself, etc, and finally we replace the last list entry with empty with
"nothing" (empty), and the handler for this rule should add the actual expression to the
list which was created in the initial stage and the final result of this
rule is the actual list entries, collected each expression. Okay let's go
ahead and test it. Let's use a (+ 5 foo), and as we can see here all the
tokens were parsed correctly and we got the final value that is specifically
the JavaScript array and what exactly we need. Okay now when we have confirmed our
parser works, Syntax allows us generating this parser and extracting it into a
separate module. For this we pass the "--output" option and provide the filename
for the output. Let's call it "evaParser.js" and Syntax tells us
"successfully generated", let's go ahead and test it. As we can see it's a generated parser which
is non-recursive, that is table-driven, and which means very fast parser
And now when we have a parser let's get back to our testing code and try to execute
it. And we forget passing the Eva instance to our test function and also
need to add "assert" module to the test utils
okay let's execute, and yes -- all assertions passed, so now we can pass Eva
expressions in the actual S-expression format and our parser will be able to
convert to exactly the same underlying array structure which we use in
JavaScript which again as we see a 1:1 corresponds to the JS arrays
but it's even more convenient since we don't need all this quotation, commas, and
other things so once again this is our BNF grammar for the parser
and it's pretty trivial only two rules: it's either an Atom or a List and we then
define what is an Atom, that is number, string and symbol, and what is List which
might be an empty list or list with entries. So go ahead and play more with Syntax tool
for example you can extend support for the numbers and handle not only
integer numbers as we do here but also floating-point numbers and for
this you'll need to change only this rule here in the tokenizer
the regular expression for the numbers token will slightly be different
so that's it for today, and in the next lecture we'll start talking about
functions and we'll consider the first type built-in or the native functions
Thanks, and see you in the class!