In this project-centered course you will build a modern software hierarchy, designed to enable the translation and execution of object-based, high-level languages on a bare-bone computer hardware platform. In particular, you will implement a virtual machine and a compiler for a simple, Java-like programming language, and you will develop a basic operating system that closes gaps between the high-level language and the underlying hardware platform. In the process, you will gain a deep, hands-on understanding of numerous topics in applied computer science, e.g. stack processing, parsing, code generation, and classical algorithms and data structures for memory management, vector graphics, input-output handling, and various other topics that lie at the very core of every modern computer system. This is a self-contained course: all the knowledge necessary to succeed in the course and build the various systems will be given as part of the learning experience. The only prerequisite is knowledge of programming at the level acquired in introduction to computer science courses. All the software tools and materials that are necessary to complete the course will be supplied freely after you enrol in the course. This course is accompanied by the textbook "The Elements of Computing Systems" (Nisan and Schocken, MIT Press). While not required for taking the course, the book provides a convenient coverage of all the course topics. The book is available in either hardcopy or ebook form, and MIT Press is offering a 30% discount off the cover price by using the discount code MNTT30 at https://mitpress.mit.edu/books/elements-computing-systems. The course consists of six modules, each comprising a series of video lectures, and a project. You will need about 2-3 hours to watch each module's lectures, and about 15 hours to complete each one of the six projects. The course can be completed in six weeks, but you are welcome to take it at your own pace. You can watch a TED talk about this course by Googling "nand2tetris TED talk". *About Project-Centered Courses: Project-centered courses are designed to help you complete a personally meaningful real-world project, with your instructor and a community of learners with similar goals providing guidance and suggestions along the way. By actively applying new concepts as you learn, you’ll master the course content more efficiently; you’ll also get a head start on using the skills you gain to make positive changes in your life and career. When you complete the course, you’ll have a finished project that you’ll be proud to use and share.
Unit 4.6: The Jack Grammar
Loading...
Из курса от партнера Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
167 оценки
Hebrew University of Jerusalem
167 оценки
Из урока
Compiler I: Syntax Analysis
Познакомьтесь с преподавателями
Shimon SchockenProfessor
Computer Science
So, up until now in this module in the previous units,
we discussed the notions of parsing and grammars and
tokenizing in a rather general context.
And from this unit onward, we are going to talk specifically about the Jack grammar,
and about developing the parser and the syntax analyzer for Jack programs.
All right, now as you noticed,
we use a certain notation when we describe grammars.
And what you see here is the subset of the Jack grammar that we used all along.
And I'd like to say a few words about the notation that we used all
the time without paying much attention to it.
So basically, here is a formal definition of the notation.
If I write something in black font, and I put it within two quotes,
well this is a description of a token that must appear verbatim, as is in the input.
And everything else is sort of meta language that describes the grammar.
All the green stuff is the scriptors that I invented or
more precisely Norman and I invented in order to describe the Jack grammar.
And we're using a certain formalism here that we thought is appropriate for
our purposes.
And so we use parenthesis to describe groupings of tokens,
we use a vertical bar to decide a choice between
different options and so on and so forth.
We also use, as I explained before, question mark to describe something
that should appear zero or one time, and
we use an asterisk to describe something that should appear zero or more times.
So these are the rules of the game.
Very simple, very straightforward and
that's all we need in order to describe the structure of programming languages.
All right, so with that in mind, I'd like to now unveil
the entire Jack grammar in all it's glory and
before I do so I want to warn you that it may look a little bit forbidding.
But the good news is that, the only reason it looks forbidding is because I
condensed it to a size that will fit on one slide.
So, here we see it and actually I think Norma and
I are quite proud that the whole language fits on one slide and
if you were to zoom out from this image here which is lifted out of the book.
You would see that it consist of four sections and
we already discussed most of what we see here.
So what I would like to do next is go through everyone one of these four
sections and spend a few minutes talking bout it.
All right, so first of all the language has a lexicon or
lexical elements and in particular as we said in unit I think
the second unit in this module when we talked about tokenizing we have keywords.
We have symbols, integer constants, strong constants, and identifiers.
And these four terminal rules
describe all the lexical elements that can go into Jack programs.
These are the atoms or the tokens from which Jack programs consist.
All right, moving along what about the structure of a Jack program.
Well a Jack program is a collection of one or more classes.
Each of these classes is stored, handled and compiled separately.
Just like we do with the Java and other object oriented languages.
And the structure of each of these classes is as follows.
And what you see here is a non-terminal rule that describes
what it takes to be a class.
So, a class begins with a keyword class then we have a class name,
which as you will see later on is an identifier.
Then we have curly left paren which begins the definition of the class.
Then we may have zero or
more declarations of either fields or static variables.
So all together we call this class classVarDec.
And then we may have zero or
more subroutine declarations followed a right curly bracket.
So that's what it takes to be a class in Jack.
Now drilling into this definition, what is a classVarDec?
Well it's easier the keyword static or the keyword field followed by a type,
followed by a variable which as you will see later on is an identifier also and
then I might have zero or more comma separated additional viable names.
So it can have something like staticintx, y, z.
This definition here will conform to this grammatical rule.
Then we have a type, what is a type?
Well, in Jack the only three primitive types.
Int, char, boolean or in Java there are eight types or
it just a matter of simple few more keywords.
And because Jack is an object oriented language and
other possibility for a type is the name of a class.
So a class type Is also permissible.
Subroutine declaration always begins with either constructor function or method.
The subroutine can be either void or a typed subroutine.
In other word it returns either a void or a typed value and so on and so forth.
Okay, it might have a parameter list and as you see in the rule,
a parameter list is a name of yet another non terminal rule.
It's the next rule and indeed we see that the entire parameter list is optional.
We have a question mark at the end.
So we either have some parameters or we just have the parenthesis only.
So you see a few more rules here and a few more terminals that describe what
it takes to be a class name, subroutine name and variable name and that's it.
That's the definition of the program structure in Jack.
Okay, what else do we have?
Well, in Jack we have statements, right?
And this is something that we actually dealt with that before in our examples but
basically, we have statement which are zero or
more occurrences of statement in singular.
And statement is either a let, an if, a while, a do, or a return.
And for every one of these statements we have a rule that describes it.
Once again, all this stuff is lifted straight out of the book, and
I simply laid out in front of you in separate slides.
By now, after we went through all the previous examples,
I think that this stuff should be relatively straightforward.
All right, finally we have expressions.
That's the last thing that the grammar describes.
And the expressions are similar to what we discussed in our previous examples and
expression is a term followed by an optional opt term class.
And the thing that makes these expressions somewhat complex in Jack
is the term rule and as you see, the term rule is a little bit involved
match more than the simple grammar that we saw previously.
In fact, the handling of expressions is somewhat tricky and
therefore I would like to defferate to the end of unit.
So, please bear with me we put expression on the side.
And I'd like to sort of summarize what we did so far.
And then I'll back to the handling of expressions.
So to recap, we gave the entire Jack grammar.
And we need this grammar because this is the recipe according to which
we're going to write our parser.
And the parser is going to be a set of compile routines,
one for almost every non-terminal rule that you see in the grammar.
We're going to skip some of these rules because they are very shallow, and
I'll have more to say about it in the subsequent units.
But essentially, we're going to have a rule for every non-terminal, I'm sorry,
we're going to have a parsing routine for every non-terminal rule.
The parsing routine will be written according to
the right-hand side of the corresponding rule.
It will write the required XML, and may call in the process yet
another routine to do the same, and so on, and so forth.
So here you see the sort of tight relationship, the close relationship
between a grammar and a parser that operates according to this grammar.
All right, now I promised that I will handle expression separately and
that's what I'd like to do next before we wrap up this unit.
So let's zoom into the handling of expressions and
we see here the grammatical definition of expressions inject.
And the thing that makes the handling of expressions somewhat challenging
is the handling of the term rule.
The rule that handles the term nonterminal rule.
Now think about it, if the expression, or
I'm sorry, if the current token is an integer constant, simple.
If it's a string constant, also simple.
Likewise, if it's a keyword constant, we can easily handle it.
However, if the current expression, I'm sorry, if the current token
Is a variable name then it turns out that according to the rule here
we have several options and each one of them should be handled separately.
And here are some examples of what may sort of transpire when you
have a token which is a variable name.
It may be just the variable name foo, right?
Which is easy to handle.
But it may also be the name of an array, right?
Foo followed by left square bracket followed by
an expression that evaluates to some index of this array.
It may also be foo.
and then comes a call to either a method or a function,
and we have to decide what we have here, so the bottom line
is that we have to resolve whether we have any one of these options here.
And in order to make this resolution,
we have to look ahead to the next token down the token stream.
So as a rule, when you have an identifier you cannot know immediately what you have.
You have to look ahead at the next one.
And then if the next one is a left square record, you do one thing.
If it's dot you do another and so on and so forth.
This is the only case in the Jack language where the language
becomes LL(2) and you have to work a little bit more delicately
to write code that takes care of these various possibilities.
In all other cases, the language is completely LL(1),
and the writing of the parser is relatively straightforward.
So with that in mind, this is the end of Unit 4.6, and in the next unit,
we're going to talk about finally how to write the Jack Analyzer itself.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
