JOMO KENYATTA UNIVERSITY OF AGRICULTURE AND TECHNOLOGY
CS153 (CS132)
Class notes
Class Notes for Compiler Construction(CS153, CS132)
4 views 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
BOTTOM-UP PARSING
This is a parsing strategy based on the reverse process to top-down parsing. Instead of expanding successful
non-terminals according to production rules, a current string or right sentential form is collapsed each time until
the start non-terminal is reached to predict the legal next symbol; i.e. it can be regarded as a series of reductions.
This approach is also known as shift-reduce parsing and is the primary parsing method for many compilers,
mainly due to its speed and the tools which automatically generate a parser based on the grammar.
Example
Consider the grammar below:
1 𝑆 → 𝑎𝐴𝐵𝑒
2 𝐴 → 𝐴𝑏𝑐|𝑏
3 𝐵→𝑑
To parse the sentence 𝑎𝑏𝑏𝑐𝑑𝑒 using the bottom up approach gives the following reductions:
𝑎𝒃𝑏𝑐𝑑𝑒
𝑎𝑨𝒃𝒄𝑑𝑒 by 2
Reverse gives in right most derivation:
𝑎𝐴𝒅𝑒 by 2
𝒂𝑨𝑩𝒆 by 3 𝑆 → 𝑎𝐴𝐵𝑒 → 𝑎𝐴𝑑𝑒 → 𝑎𝐴𝑏𝑐𝑑𝑒 → 𝑎𝑏𝑏𝑐𝑑𝑒
𝑆 by 1
Generally, bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches
the root node. Here, we start from a sentence and then apply production rules in reverse manner in order to
reach the start symbol. The figure below depicts the bottom-up parsers available.
Compiler Construction ~ Wainaina Page 1 of 12
, LR Parsing
The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar
which makes it the most efficient syntax analysis technique. It is one of the best methods of syntactic
recognition of programming languages. The L stands for left to right scan, and R stands for right most
derivation in reverse. In general, we can have 𝐿𝑅(𝑘) parsing with 𝑘 symbols of LOOKAHEAD. However, LR
parsing refers to 𝐿𝑅(1) parsing.
Advantages of LR Parsing
i) LR parsers can recognize virtually all programming language constructs written with CFG grammars.
ii) It is the most general, non-backtracking technique known.
iii) It can be implemented in a very efficient manner.
iv) The language it can recognize is a proper super set of that of predictive parsers.
v) It can recognize syntax errors quickly.
Disadvantages
The primary drawback of LR parsers is that they require too much work to manually create LR parsing tables.
However, tools exist to generate LR parsers from a given grammar i.e. parser generators such as YACC,
BISON etc.
LR Parsing Methods
There are three widely used algorithms available for constructing an LR parser:
i) SLR: this stands for Simple LR. It is easy to implement but less powerful than other parsing methods. It
generally works on smallest class of grammar and have few number of states, hence very small table
ii) Canonical LR: this is the most general and powerful. However, it is tedious and costly to implement,
i.e. for the same grammar, it has got much number of states as compared to SLR parsers. Generally, it
works on complete set of LR(1) Grammar and generates large table and large number of states
iii) LALR: this stands for LOOKAHEAD LR. It is a mixture of SLR and canonical LR, but it can be
implemented efficiently i.e. it contains the same number of states as Simple LR parser for the same
grammar.
Notice that most parser generators generate LALR parsers since they are a trade-off between power and
efficiency.
Implementing Shift Reduction
A shift-reduce parser is implemented using the following notation:
An input stream, containing
a phrase to be parsed and
a stack holding a symbols
The input stream holds terminals, the stack can hold a mixture of terminals and non-terminals, the latter
generated by earlier reductions.
The operation shift moves a symbol from the input to the stack while the operation reduce combines the
sequence ending with the last terminal shifted to form a non-terminal on the stack.
When the input is exhausted, the single start symbol should be presented assuming all reductions have been
performed.
Example
Consider the following grammar:
𝑒𝑥𝑝 → 𝑒𝑥𝑝 + 𝑒𝑥𝑝
𝑒𝑥𝑝 → 𝑒𝑥𝑝 ∗ 𝑒𝑥𝑝
Compiler Construction ~ Wainaina Page 2 of 12
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.
