Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees and Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Unit 4.5: Parser Logic

Loading...

Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)

Hebrew University of Jerusalem

5 (219 ratings) | 17K Students Enrolled

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.

Skills You'll Learn

Computer Architecture, Compiler Construction, Compiler, Operating System

Reviews

5 (219 ratings)

5 stars
209 ratings
4 stars
10 ratings

RR

Jul 16, 2017

This is an excellent course giving good view of operating system, compiler and fitting the pieces together. Highly recommended

AD

Sep 02, 2018

One of the best computer science courses I ever had. You start understand how actually things like heap, stack, etc. works.

From the lesson

Compiler I: Syntax Analysis

Unit 4.1: Syntax Analysis7:04

Unit 4.2: Lexical Analysis9:14

Unit 4.3: Grammars14:52

Unit 4.4: Parse Trees6:52

Unit 4.5: Parser Logic20:07

Unit 4.6: The Jack Grammar13:36

Unit 4.7: The Jack Analyzer10:31

Unit 4.8: The Jack Analyzer: Proposed Implementation20:25

Unit 4.9: Project 10: Building a Syntax Analyzer15:40

Unit 4.10: Perspective12:50

Taught By

Shimon Schocken
Professor

Welcome to unit five, in which we're going to talk about the parsing logic.

In the previous unit, we talked about parse trees, and we saw

some example of English parsing and Geck parsing.

And I pointed out that, I can draw a parse tree using either a diagram like this,

or I can also use a XML format, some agreed upon

way to describe the structure of a given input.

The syntactic or the grammatic structure of the input.

And the question of course, as I pointed out is, how do we do it?

How do we actually start with some obscure input,

and end up with such a nice and well structured description,

of what is going on in this input, of course from a linguistic standpoint.

Well, I'd like to kind of fast forward, and

show you the actual code that we're going to use in order to carry out the parsing.

We're going to develop, at a later point in this module, a program for the Parser.

Actually the name of this module is going to be CompilationEngine.

And this CompilationEngine is going to consist

of a set of methods, one method for

almost for every non-terminal rule, in the corresponding grammar.

So, for example, if you look at the grammar,

you will see that we have a rule called statements, plural.

And indeed, we also have a method called compileStatements.

Then we have a rule called ifStatement.

And indeed we have a method called compileifStatement, and so

on and so forth.

For most of the non-terminal rules in the grammar,

we have corresponding methods that are responsible for

parsing the part of the input that corresponds to this particular rule.

There are some rules for which we don't have specific methods, but

we also take care of them implicitly in other rules.

We'll discuss this little detail, later on in the module.

So to illustrate, let's focus on one of these methods,

compileWhileStatement, which corresponds to the whileStatement rule.

And let us see how,

you know this sub-routine actually works in practice.

Now, in general, the method or, I call it sub-routine,

is going to be written according to a set in logic.

And the logic is taken directly from the rule.

So, here is how we do it, we follow the right-hand side of the rule,

and we do exactly what the pattern

that is documented in the right-hand side dictates.

So, for example, if we look at the whileStatement,

it says you should expect to see the word while, or token while.

And if we find it in the input,

we record the fact that indeed we found the token while.

And then the rule will say,

the next thing that you should expect to see, is the token left parenthesis.

So, we look at the input and we check, do we really have a left parenthesis?

And if we do, we can record it in the output file, and so on and so forth.

At some point, we will get something like expression.

So if the right-hand side specifies a non-terminal rule rather

than a token, then we call the corresponding method which is

designed specifically to deal with this particular non-terminal rule.

So as you see, this whole thing is highly recursive.

So we continue to recurse, until we exhaust the input, and run out of tokens,

and then we know that we have completed the passing of the given input.

So how do we get started?

Well, we have to advance the tokenizer, and remember,

I should have told you that before, I wish to remind you that the input is tokenized.

So, I have a tokenizer to my disposal that I can exploit.

I can tell the tokenizer, advance,

I can ask questions about what is the current token, and so on and so forth.

So I advance the tokenizer, and since the first token is while,

I know that I can call the compilewhileStatement,

and let the parsing begin.

So, what we'll do from now on is, I will

walk you through an elaborate simulation of how we parse this particular input.

So let's see.

We call the compilewhileStatement and sub-routine.

So this sub-routine starts running, and

it records the fact that it starts running by writing the tag whileStatement.

And then we look at the rule,

when the rule says that the next thing we should expect is the token while.

Well, let's see, what is the current token?

It is while.

So happily, we record the fact that we have a while.

We look at the rule again.

The next thing we should expect to see,

and I'm sorry, after we record the token, we advance the input.

I should have said this before.

So, then we look at the next part of the rule.

And the rule says you should expect to see a left parentheses.

Well, we look at the current token, it is a left parenthesis, so

we record it, and advance the input.

Back to the rule, the rule says now you should expect to see an expression.

Well with that in mind, we call the compile expression sub-routine,

which starts running.

And let's look at the right-hand side of expression.

The right-hand side says you should now expect to see a term.

Well, a term is a non-terminal rule, so we call compile term, which starts running.

And the right-hand side of term says

you should expect to see either varname, or a constant.

And we look at the current token, indeed, we have a varname.

So we record the fact that we have a varname or an identifier called count.

And we are done with, and we advance the input.

And then we are done dealing with this term.

And then we go back to the rule, and we see that we are done with the term, so

we are back to the expression.

And the expression says, the right-hand side,

you should now expect to see optionally, an op followed by a term.

Well, we look at the input or be kind token, and

see that indeed we have an operator, or an operation there, right?

So let's record it.

We record the fact that we have an operator, or a symbol.

And we advance the input.

Going back to the expression definition,

we see that we should now expect to see a term.

And let's see, so we call the compile term sub-routine

which starts running and the logic of the term says we should

now expect to see either a var name or a constant.

We'll look at the kind of token and indeed we have a constant.

So, we call this constant,

we advanced the input, we're done with the term, we go back to the expression.

We are done with the expression and we go back to the while.

So now, we look at the right hand side of the while and

it says you should expect to see a right parenthesis.

We look at the current token and, indeed, we have a right parenthesis.

So we record it, advance the input, go back to the rule,

and the rule says you should now expect to see a left curly bracket.

We look at the current token, indeed, it is a left curly bracket, so

we record it, back to the rule.

And the rule says you should now expect to see statements,

which is, zero or more occurrences of statement.

So, we call the compileStatements method and

the compileStatements method starts running and

the right hand side says you should look for a statement.

And we look at the current token, the current token is a let right so

we know right away that we have a let statement.

So we call, compile let statement and

the right side of the rules says, you should expect to see

a let token, indeed we have a let token, so we recalled it.

Then you should expect to see a varName, I'm sorry we recalled it in advance.

You should expect to see a varName, we look at the current token indeed, we have

varName here so we call the fact that we have the identifier count.

Then we should expect to see and

we advance then we should expect to see an equal sign.

Indeed we have an equal sign so we code it in advance and so on and so forth.

Now we have an expression that we are processing in a similar way and

at some point we'll be done with the let statement.

And let's see will be decked to the statements.

There will be no more statements to process, so we will go

back to the while and we see that once we finish parsing the statements.

The next thing which we should expect to see is a right curly bracket,

indeed we have a right curly bracket, this is the kind tokens.

So we record it, we advance the input, and we're done with the tokens.

There are no more tokens to process and

therefore, we've finished parsing the input, and we got this lovely

XML file here which describes the parsing of this input.

So, that's the end of the story, or that's the end of the simulation.

And I want to kind of recap and take another look at

the structure of this compilation engine module which implements our parsing logic.

Once again it consists of a set of sub-routines.

One for each almost for every non-terminal rule

in the grammar, and once again I said that the handling of some rules.

Which are the shallow or less interesting rules are handled in

the context of other rules as we'll see later on.

Now let's take a closer look at the compileWhileStatement and

I would like to actually show you the code of

this particular parsing sub routine, so here it is.

I'm going to use a private method that I would describe later on called It, so.

I look at the grammar, well, let me retract a little bit.

What I'm doing now is I'm putting myself in the shoes of the software

developer who has to develop this syntax analyzer.

And this software developer is going to use the grammar

of the language as the kind of dominating

recipe for writing the code of the parser.

So the parser or the parser's code is going to be informed by the grammar.

And in particular if I look at the grammar,

I see that the grammar said you should expect to see a while.

So I'm going to call a method called eat('while') which

means you should expect now to eat the while token.

And then I'm going to write some code to handle the while.

In particular if it's an XML code, I will simply write the while

out with the proper tags and then according to the logic of the rule,

I should expect to eat left parenthesis and I will handle it.

And then I'm going to compile expression, right,

because that's what the rule specifies, or mandates, to do.

And then I should eat the right parentheses and

then I should

eat the left curly bracket, and so on and so forth.

Okay, so that's how I'm going to write the compile while statement subroutine.

Now what about this eat method?

Now, this is a private method,

which I'm not going to expose to users of this syntax analyzer, and in particular,

the method says you should expect to see the given strength.

If you don't see it, you should throw an error and

otherwise, simply advance the input.

So, by using this logic here,

I encapsulate the advancing of input, and I don't have to worry about it.

This eat method is going to do it forming.

So as you see, the code of each compilexxx method follows

the right-hand side of the corresponding xxx-rule.

And each of these methods is responsible for advancing and

handling all the tokens which correspond to this particular rule.

And by having all these methods call it each other recursively

I'm going to accomplish the parsing of the given input.

Now I'd like to end this unit with some theoretical remarks about

the character of these grammars that we are using all the time.

And first of all, I'd like to introduce the notion of an LL grammar.

Now quite frankly, I'm not sure what LL stands for

but I'm quite sure that one of these Ls stands for leftmost.

And an LL grammar is a grammar that can be parsed by a recursive

descent algorithm parsing algorithm without backtracking.

Now what I mean by this is that this grammar is quite friendly.

It's friendly in the sense, that once you start to parse something,

you never have to go back.

When you make a decision that what you have is a while statement or

an if statement, you don't have to kind of retract your progress and

find out that you made a mistake and you had to pass it In a different way.

So this is a very nice property of parses that make

the implementation of the parser rather simple.

The next terminology that I would like to present is LLK.

Now an LLK parser is an LL parser In which we have to look ahead at most

k tokens before you know which rule you are dealing with.

And luckily, the grammar that we saw so far was LL1.

And it's LL1 in the sense of once I have a particular token in my hand,

like Y or let or do I immediately know which rule I have to invoke.

And I don't have to back track later on.

So if a grammar is LL1 then once again it lends it's

self to a parcer which are relatively easy to write.

Now, when you deal with a language like English, the situation is much

more challenging because English is not LL1.

For example, suppose I tell you something like lift,

well we have a token right lift and

yet we still have no idea what we have to do with this token

because the next word may well be something like me.

Well once we have lift me well then I know I have a verb followed by a noun.

And therefore I have a statement which means lift me, verb, noun,

everything is now clear.

However, instead of lift me, I could also say something like lift operator

and if I say lift operator then it's not It's not a sentence.

It's just the beginning of a sentence because what I have is an adjective,

lift is now serving as an adjective and now operator is a noun and it's not

a sentence you know I need to do something with this information further on.

So once again you see that in this particular example I had to look ahead two

tokens before I knew which rule in the English language I have to invoke.

And in general I may have to look more tokens downstream

before I know which rule I have and you know maybe I have to backtrack and

reconsider some of the rules that I thought,

I had to use and so on and so forth.

Our brain is trained to do this parsing in a blinding speed and

it would have been extremely difficult to write a computer program to do the same.

Because English is probably something like LL5 or 6 or 7,

you have to look ahead several tokens before you know

which rule of the English language you have to use.

Whereas, programming languages are mostly LL1 which makes the passing

of these languages a far easier task than parsing in natural language like English.

All right, so with that, we discussed the logic of the parsing process.

And the next thing which we are going to look at is the Jack grammar.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates