Compiler Construction Notes
Welcome to the Compiler Construction Notes! This comprehensive guide is designed to help you understand the fundamental concepts and techniques involved in building a compiler. Whether you are a student, educator, or professional, these notes will provide valuable ins...
Top-down parsing:
The top down construction of a parse tree is done by starting with the
root ,labeled with the starting non-terminal ,and repeatedly performing the
following two steps-
1. at node n, labeled with non-terminal A,select one of the productions for A
and construct
children at n for the symbols on the right side of the production
2. Find the next node at which the subtree is constructed.
For some grammars, the above steps can be implemented during a single left
to right scan of the input string. The current token being scanned on the input
is often called as the lookahead symbol . Initially the lookahead symbol is the
first i.e the leftmost token of the input string.
Let us consider the following grammar.
A -> BA
|a
| aa
B -> BB
|b
and now consider the input string “ bbaa”
The top-down parsing would look like this in different steps-
1. A
input : bbaa , the highlighted character indicates the lookahead.
2. A
, B A
3. A
B A
B B
4. A
B A
B B
b
5. input: bbaa
A
B A
B B
b b
6. input: bbaa A
B A
B B a a
b b
Here we have assumed that , at the first attempt the parser would know
which production to use to get the right output, but in general, the selection of a
production of a non-terminal may involve trial and error, that is we may have to
try a production and backtrack to try another production if the first is found to
be unsuitable. A production is unsuitable ,if after using the production, we
cannot complete the tree to match the input string .we will discuss this parsing
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller v-tekcoding. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $28.49. You're not tied to anything after your purchase.
