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.3: Grammars
Loading...
Do curso por Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
143 ratings
Hebrew University of Jerusalem
143 ratings
Na lição
Compiler I: Syntax Analysis
Conheça os instrutores
Shimon SchockenProfessor
Computer Science
Welcome to the unit about grammars.
In the previous unit, we talked about tokenizing and we developed the conceptual
ability to think about the program as a set of tokens.
Now I think that you will agree with me that the effect that we have
a set of valid tokens does not necessarily imply
that we also have a valid text or a valid program.
For example, if we deal with the English language,
consider the following set of tokens.
Red drives a he.
Maybe you want me to repeat that.
Red drives a he.
It mean nothing, right?
Well, it means nothing even though each one of the tokens is perfectly legitimate.
Red, drives, a, and he, four legitimate English words.
However they don't come in the right order.
Had I said something, like he drives a red car, everything will become crystal clear.
So it's not only the tokens that are important.
The order of the tokens is critically important as well.
And the artifact that defines in what order
we can put tokens together legibly is call the grammar.
So the grammar, technically speaking, is a set of rules.
Each rule define a certain pattern that indicates how
tokens can be strung together in order to make
meaningful sentences or statements in the underlying language.
So for example, what we see here is a subset of the English language.
In English, we have sentences and
each sentence is a noun phrase followed by a verb phrase.
What is a noun phrase?
Well, a noun phrase is possible determiner,
which is optional followed by a mandatory noun.
So notice that I use question mark to refer to something that may or
may not appear in this pattern, in the pattern known as noun phrase.
What about verb phrase?
Well, a verb phrase is a verb followed by a noun phrase.
So we see that this grammar is quite recursive.
And then we have a set of allowable nouns, which are constants,
like lexical constants, like dog, school, dina, and so on.
We have a set of allowable verbs and we have a set of allowable determiners.
And we can add more rules and more constants to this grammar and
make it as fancy as we please.
So once again, this is just a subset of English language.
But the subset is sufficiently rich to support or
accept such inputs as, for example, Dina went to school.
She said, the dog ate my homework.
Every one of these sentences will be accepted by this grammar.
For example, consider the dog ate my homework.
Well, let's take a look at it.
The is a determiner and dog is a noun.
So we have the determiner followed by a noun,
which taken together are a noun phrase.
So we have something that begins with a noun phrase.
So it looks like we may have a sentence here because a sentence is something that
begins with a noun phrase.
Then we have ate my homework.
Well, ate is a verb and my homework is a noun phrase.
So we have a verb followed
by a noun phrase, which together constitute a verb phrase.
So taken together, we have a noun phrase followed by a verb phrase and, therefore,
we have a legitimate sentence, according to this grammar.
The sentence may not be legitimate in a French grammar,
but it is suddenly acceptable by the English grammar.
And we can do the same exercise and
convince ourselves that the previous two sentences are acceptable as well.
Now looking at this grammar, I can view or
observe that it is made of, as I said, a set of rules,
and these rules fall into two broad categories.
First of all, I have terminal rules and
terminal rules are rules whose right-hand side consists of constants only.
And then I have non-terminal rules and these are the rules whose right-hand side
consists of names of other rules as well as possibly constants.
So taken together, grammar is a set of terminal and non-terminal rules.
This is an observation that will be useful later on in our work.
All right, now let us shift our attention to the Jack grammar.
Because after all,
this course is not about computational linguistics in general.
It is about compilation, or at least this module is about compilation.
So a Jack program is a set of statements.
And I want to focus on a subset of the Jack language in which
we have three possible statements, if, while, and let.
So I use this bar, the vertical bar, to denote choice.
So either, and if, or while,
or let is a acceptable statement in this subset of the language.
And then statements in plural are zero or
more occurrences of statement in singular and
I use the asterisk to indicate zero or more.
So once again, what is statements?
It is zero or more or Karen says,
of the statement pattern.
And the statement pattern is either an ifStatement, while, or let.
Okay, then I have an ifStatement.
An ifStatement is something that begins with a constant if,
the token if, if you will.
It must be followed by a left param symbol, then comes an expression.
Then comes a right param,
a left curly bracket, statements, and a right curly bracket.
If you have an input which corresponds to this definition,
you have a legitimate ifStatement.
Likewise, we define a whileStatement and a letStatement, and
then we go on to define the things which are still missing here.
For example, what is an expression?
Well, an expression is a term followed by
the optional pair up, followed by term.
Why optional?
Because I use question mark to denote zero or one.
So an expression is either a term standing alone or
it's a term followed by up, and another term.
What is a term?
A term is either a variable name or a constant.
A variable name is a string
not beginning with a digit in this subset of the language.
A constant is any decimal number and
op is one of these symbols here, okay?
So taken together, what we have here is the complete grammar
of a subset of the Jack language.
And now we can begin to consider possible inputs and
ask ourselves do they cut mustards so to speak?
Are they accepted by this grammar?
For example, let x = 100.
Well, let's see.
It looks like it should correspond to this pattern.
And indeed, it's start with the token let, and then we have x.
Now what is x?
Well, I look at the grammar and I realize that x qualifies as a varName.
Because a varName is a string not beginning with a digit and
an x is a string not beginning with a digit.
So we have varName.
Now a vowel name is also a term and I'm sorry, all we need is a varName, right?
Because after let, we need the varName, we have it.
Then according to the rule,
we have to have an equal symbol and we do have an equal symbol.
Moving along, we have the token 100.
What is 100? Well, according to the grammar,
100 must be a constant because it's a decimal number
and a constant is also a term.
So what we have here, is a term, [COUGH] I'm sorry.
And a term is also an expression.
So we have an expression and that's what the rule requires, right?
The rule expected to see an expression.
And then the rule says, I also expect to see a semicolon.
And indeed, we have a semicolon.
So taken as a whole, this input is acceptable by the grammar.
What about this input?
Well, once again, we have a let pattern and
let x = x is acceptable, according to the analysis that you did before.
And then we have + 1, now what about this x + 1, what does it mean?
Well, x is a term and +1 is an op followed by another term.
And if you look at the rule that defines expression,
you will see that x + 1 qualifies as an expression in this grammar.
So once again, we have something that will be accepted by this grammar.
What about this input here?
Well, let's see, it looks like we have a whileStatement.
Indeed, we have a while at the beginning, then we have let friend,
very nice indeed,.
Then we have n < lim.
And if you will analyze it, if you will see that n < lim
is a legitimate expression so, so far we are okay.
Then we have a right parenthesis, very nice indeed.
And then we have to have a left curly bracket, which we don't have in the input.
And that's where your compiler is going to throw an error message and
tell you that you have a syntax error in your source code.
All right, so here's an example of an input,
which is not acceptable where this grammar.
What about this input?
Well, here we have an ifStatement.
And we see that the ifStatement allows to have statements
within the curly brackets and statements is zero or
more occurrences of statement.
And indeed, we have here two such occurrences, so once again,
we have a legitimate input.
Finally, what about this input example?
Well, you're welcome to stop the tape and
convince yourself that this input will also be accepted by the grammar.
But it's a good exercise to follow, at least informally,
what we did before and realize that this is actually the case.
So parsing is the art and
science of determining if a given input conforms to a certain grammar.
And notice that in the process of doing this confirmation,
I also uncover the entire grammatical structure of the given input.
Because I analyze how the input
corresponds to the various components of the rule.
And by doing so, I once again construct
the underline grammar, grammatical structure of the input.
And by the way, that's exactly what our brain does in some mysterious way,
which is increasingly becomes more and more understandable.
But basically, when we hear a sentence, we try to match it
on certain patterns, which are sort of wired into our brain,
have been wired from our learning of language throughout our life.
And our brain has this remarkable capacity of understanding sentences,
even if they don't match the grammar perfectly.
If we didn't have this ability,
all the poets in the world would be out of business.
But computer programs and compilers don't have this remarkable ability.
When you deal with a compiler, the input must match the grammar perfectly.
And if there's any discrepancy, the compiler will raise its hands and
say, we have a syntax error, you have to fix your program.
So that's basically what I wanted to say about that parsing.
And with that, the next unit,
we'll discuss the notion of parse trees, which is a data structure that
we use in order to describe the grammatical structure of our input.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
