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.7: The Jack Analyzer
Loading...
来自 Hebrew University of Jerusalem 的课程
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
143 个评分
Hebrew University of Jerusalem
143 个评分
从本节课中
Compiler I: Syntax Analysis
与讲师见面
Shimon SchockenProfessor
Computer Science
In previous units we talked in general terms about parse trees and
the process logic.
And in this unit I would like to specify exactly
what our Jack Analyzer is expected to output.
So once again, let's look at the general roadmap and
remember that we are developing a compiler.
But in this module we are focusing only on the syntax analyzer.
So there's an interesting question here which is,
how can we unit-test the syntax analyzer in isolation?
How can we convince ourselves that the syntax analyzer
understands the source code before we actually
develop the capability to generate code from the source?
Well, the answer is we can defer
the development of the code generator to a later stage, as indeed we do.
And for now we can ask the analyzer to output
the structured code of the source in some pre-determined way.
And in particular, here is what we do.
We shortcut the code analyzer.
I'm sorry, we shortcut the code generator and
instead of generating VM code, we generate XML code.
And XML code is something that we discuss in the past and
now I will show you exactly What kind of output we expect the analyzer to emit.
So here's an example of some source code that we saw before.
And here is the XML output that our analyzer will
output when it processes this particular source code.
And by the way, I use the terms parser and syntax and analyzer interchangeably.
And in the context of this unit and the subsequent units
when I say parser I mean the parser which already has the tokenizer embedded in it.
So we see that the parser generates marked-up output and
it is marked-up according to the XML format.
And the marked-up actually creates a textual parse tree.
And this parse tree is generated according to the Jack grammar.
So why do we do this?
We do this once again because we want to create some evidence
that the parser understands the source code.
So that whenever the parser sees some construct in the source code
it will be able to say that what we have here is either an expression or
a variable name or a let statement or whatnot.
And the parser should possess this syntactic understanding
in a complete recursive way.
And the XML code which is also, not exactly recursive but hierarchical,
is designed to demonstrate that the parser is well-behaving.
So what I'd like to do next is go through the Jack grammar.
And I'm not going to do it in detail, I will actually do it in broad terms, and
show you how the parser should handle inputs
that are structured according to this grammar.
So first of all, how should we handle
inputs that correspond to the grammar's terminal rules.
Well, if we have to process an input which is either a keyword,
a symbol, an integer constant, a string constant or an identifier, which is
according to our grammar considered a terminal element of the input,
then we generate output that looks like this.
In particular let's look at an example because is it much more
instructive than the general definition here.
So if we have something like the word method or the token method well it's
a keyword so we just mark it up as keyword begin, keyword end and that's it.
Likewise if we have a symbol or an integer constant we simply
wrap them up in the right XML tags and emit them to the output.
So this is very simple,
that's what we do with inputs that correspond to terminal rules.
But how about non-terminal rules?
well we have two subsets of a nonTerminal rules and
I would like to discuss this two sub sets in isolation.
So first of all, we have this sub sets of terminal rules which
constitutes the vast majority of the rules in the grammar.
When we have inputs that correspond to any one of these rules, here's what we do.
Once again, we write the name of the non-terminal,
and at the beginning and at the end, we write slash the same name again.
And in between We are going to recursively output everything,
which relates to the body of this non-terminal rule.
And once again, an example is worth a thousand words.
So suppose that the input is the simple statement, return x.
That's it.
How do I handle it?
Well, the parser should say what we have here is a returnStatement.
It should write it out, returnStatement.
And according to the rule,
a returnStatement should begin with the keyword return.
And indeed, we have a keyword return and then we should have an expression.
Once again the analyzer is following the grammar.
We should have an expression and the expression consists of a term and
indeed we have here an identifier x which constitutes a term and so on and so forth.
So the analyzer must once again emit
all the output that constitutes the body of the rule.
And this output may will be nested because the rule is made up of other rules and
so on and so forth.
And that is why the parser must be a recursive program.
Now we have another subset of non-terminals,
which I sometimes refer to as shallow rules.
Or rules that are not terribly interesting from a syntactic standpoint.
Well, inputs that correspond to such shallow rules are handled, but
the analyzer does not generate any XML associated with them.
Let me give you an example.
Let us focus on this subset of the Jack grammar
that describes a let statement and the varName.
Now suppose that and I decide to focus on
the varName because the varName is one of these non-terminal rules
they decided not to include in my XML.
So for example, if I have to handle let x equals 17, I look at the let statement.
I recall the fact that I have a let statement,
I recall the fact that I have a let token.
And then according to the rule, I should have a var name, right?
However, look at the output, I don't say begin varName.
I skip the varName rule because I was told that I'm supposed to skip it.
And I delve right into the identifier,
which is the right-hand side of the varName rule.
So once again, just notice that varName,
the varName rule generates no mark-up.
And we decided to do it because, some of these rules,
the rules that are mentioned here are very simple, for instance varName is
just a name of a rule whose body is the name of yet another rule.
So we allow ourselves to skip the parsing of these simple rules
because we want to try to eliminate some of the clutter that would result
if we didn't take these shortcuts here.
So that's what I wanted to say about the outputs
that the Jack Analyzer is expected to emit.
And notice that in this unit I didn't say about how the analyzer
is supposed to emit these outputs.
And I didn't say for two reasons.
First of all in unit 4.5 we
discuss in broad terms how the analyzer is suppose to generate the output.
And all that we said that it's going to have a set of methods one for
each rule that handles the corresponding rule.
And also in the mixed unit,
we are going to give you the proposed implementation of the Jack Analyzer.
And taken together, these two units, 4.5 and 4.8, will give you
all the information that you need in order to write such a Jack Analyzer yourself.
