JOMO KENYATTA UNIVERSITY OF AGRICULTURE AND TECHNOLOGY
CS153 (CS132)
Class notes
Class Notes for Compiler Construction(CS153, CS132)
0 view 0 purchase
Course
CS153 (CS132)
Institution
JOMO KENYATTA UNIVERSITY OF AGRICULTURE AND TECHNOLOGY
The document contains class notes for compiler construction. The notes include topics touching on Lexical Analysis, syntax analysis, top-down parsing and bottom-up parsing which are key concepts when learning about compiler construction.
JOMO KENYATTA UNIVERSITY OF AGRICULTURE AND TECHNOLOGY
CS153 (CS132)
All documents for this subject (5)
Seller
Follow
roykibet
Content preview
TYPES OF PARSING
There are two types of parsing:
i). Top-down parsing
ii). Bottom-up parsing
I). TOP-DOWN PARSING
Top-down parsing is a parsing strategy that finds the derivation of the input string from the start symbol of
the grammar.
There are two main approaches for top-down parsing:
a) Recursive descent parsing
b) Predictive parsing
a) Recursive Descent Parsing
It is a common form of top-down parsing that uses a parsing technique, which recursively parses the input to
make a parse tree from the top and the input is read from left to right. It is called recursive, as it uses
recursive procedures to process the input. The central idea is that each nonterminal in the grammar is
implemented by a procedure in the program.
Generally, these parsers consist of a set of mutually recursive routines that may require back-tracking to
create the parse tree.
Backtracking: It means, if one derivation of a production fails, the syntax analyser restarts the process using
different rules of same production. This technique may process the input string more than once to determine
the right production.
Example
Consider the following grammar
𝑆 → 𝑎𝑏𝐴
𝐴 → 𝑐𝑑|𝑐|𝑒
For the input stream 𝑎𝑏, the recursive descent parser starts by constructing a parse tree representing
𝑆 → 𝑎𝑏𝐴 as shown below:
S
a b A
The stream is then expanded with the production 𝐴 → 𝑐𝑑 as shown below
S
a b A
c d
Since it does not match 𝑎𝑏, it backtracks and tries the alternative 𝐴 → 𝑐 as shown below:
Compiler Construction ~ Wainaina Page 1 of 9
, S
a b A
c
However, the parse tree does not match 𝑎𝑏; the parser backtracks and tries the alternative 𝐴 → 𝑒 as shown
below:
S
a b A
e
With this, it finds a match and thus pursing is completely successful.
In general, using recursive descent parsing, one can write a procedure for each non-terminal in the language
definition:
i). Where the right hand side contains alternatives, the next symbol to input provides the selector for a
switch statement, each branch of which represents one alternative.
ii). If 𝑒 is an alternative, it becomes the default of the switch.
iii). Where a repetition occurs, it can be implemented iteratively.
iv). The sequence of actions within each branch, possibly one, consists of an inspection of the lexical
token for each terminal, and a procedure will be assigned to a local or global variable as required by
semantics of the language.
Example
The following is a recursive descent parser for the grammar shown below:
T’ →T$
T→R
T → aTc
R→ɛ
R → bR
parseT’() =
if next = ’a’ or next = ’b’ or next = ’$’ then
parseT() ; match(’$’)
else reportError()
parseT() =
if next = ’b’ or next = ’c’ or next = ’$’ then
parseR()
else if next = ’a’ then
match(’a’) ; parseT() ; match(’c’)
Compiler Construction ~ Wainaina Page 2 of 9
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 roykibet. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.49. You're not tied to anything after your purchase.
