JOMO KENYATTA UNIVERSITY OF AGRICULTURE AND TECHNOLOGY
CS153
Class notes
Class Notes for Compiler Construction(CS153, CS132)
0 view 0 purchase
Course
CS153
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
All documents for this subject (5)
Seller
Follow
roykibet
Content preview
Syntax Analysis (Parsing)
This is the process of analysing a sequence of tokens to determine their grammatical structure with respect
to a given formal grammar.
It is the most important phase of a compiler. A syntax analyser (parser) checks for the correct syntax and
builds a data structure (parse tree) implicit in the input tokens i.e. it considers the sequence of tokens for
possible valid constructs of the programming language.
Role of a Parser
1. To identify language constructs present in a given input program. If the parser determines input to be
valid, it outputs the presentation of the input in form of a parse tree.
2. If the input is grammatically incorrect, the parser declares the detection of syntax error in the input.
In this case, a parse tree is not produced.
Illustration
Token
Lexical Parser Parse tree
Analyser
Request for token Syntax error
Symbol
table
Error Handling
Error handling is one of the most important features of any modern compiler. The challenge in error
handling is to have a good guess of possible mistakes a programmer can do and come up with strategies to
point these errors to the user in a very clear and unambiguous manner.
Common errors occurring in a program can be classified into the following:
a. Lexical errors – these are mainly spelling mistakes and accidental insertion of foreign characters.
They are detected by the lexical analyser.
b. Syntax errors – these are grammatical mistakes such as unbalanced parenthesis in an expression, ill-
formed constructs. They are the most common types of errors in a program and are detected by the
parser.
c. Semantic errors – are errors due to undefined variables, incompatible operands to an operator etc.
they are detected by introducing some extra checks during parsing.
d. Logical errors – are errors such as infinite loops. There is no automatic way of detecting them;
however, use of debugging tools may help the programmer identify them.
Generally, a good error handler should:
Report errors accurately and clearly
Recover from an error quickly
Not slow down compilation of valid code
Good error handling is not easy to achieve
Error Recovery
There are four common error-recovery strategies that can be implemented in the parser to deal with errors in
the code, namely:
i). Panic mode
ii). Statement mode
iii). Error Productions
iv). Global Correction
Compiler Construction ~ Wainaina Page 1 of 8
, Not all are supported by all parser generators
i). Panic Mode: - When a parser encounters an error anywhere in the statement, it ignores the rest of the
statement by not processing input from erroneous input. This is the easiest way of error-recovery and
also, it prevents the parser from developing infinite loops.
ii). Statement Mode: - When a parser encounters an error, it tries to take corrective measures so that the
rest of the inputs of the statement allow the parser to parse ahead. E.g. inserting a missing semicolon,
replacing comma with a semicolon, etc. Parser designers have to be careful here because one wrong
correction may lead to an infinite loop.
iii). Error Productions: - Some common errors that may occur in the code are known to the compiler
designers. This requires the designers to create augmented grammar to be used, as productions that
generate erroneous constructs when these errors are encountered. The idea is to specify in the grammar
known common mistakes, which essentially promotes common errors to alternative
Example:
Write 5 x instead of 5 * x
Add the production E → … | E E
iv). Global Correction: - The parser considers the program in hand as a whole and tries to figure out what
the program is intended to do and tries to find out a closest match for it, which is error-free.
When an erroneous input (statement) X is fed, it creates a parse tree for some closest error-free statement
Y. This may allow the parser to make minimal changes in the source code, but due to the complexity
(time and space) of this strategy, it has not been implemented in practice yet.
Grammar
A grammar 𝐺 is defined as a four-tuple with < 𝑉𝑁 , 𝑉𝑇 , 𝑃, 𝑆 > where:
VN:-this is the set of non-terminal symbols used to write the grammar.
VT: - this is the set of terminals (set of words of the language, lexicon or dictionary of words).
P: - this is the set of production rules. It defines how a sequence of terminal and non-terminal
symbols can be replaced by some other sequence.
S: - 𝑆 ∈ 𝑉𝑁 Is a special non-terminal called the start symbol of the grammar.
The language of the grammar 𝐺 =< 𝑉𝑁 , 𝑉𝑇 , 𝑃, 𝑆 > denoted by 𝐿(𝐺) is defined as all those strings over 𝑉𝑇
that can be generated by starting with the start symbol S then applying the production rules in P until no
more non-terminal symbols are present.
Example
Consider the grammar to generate arithmetic expressions consisting of numbers and operator symbols i.e.
+,-,*, /. Rules of the grammar can be written as follows:
𝐸 → 𝐸𝐴𝐸
𝐸 → (𝐸)
𝐸 → 𝑛𝑢𝑚𝑏𝑒𝑟
𝐴→+
𝐴→−
𝐴 →∗
𝐴 →/
We can apply these rules to derive the expression 2 ∗ (3 + 5 ∗ 4) as follows
𝐸 → 𝐸𝐴𝐸 → 𝐸𝐴(𝐸) → 𝐸𝐴(𝐸𝐴𝐸) → 𝐸𝐴(𝐸𝐴𝐸𝐴𝐸) → 𝐸𝐴(𝐸𝐴𝐸𝐴4) → 𝐸𝐴(𝐸𝐴𝐸 ∗ 4) → 𝐸𝐴(𝐸𝐴5 ∗ 4) →
𝐸𝐴(𝐸 + 5 ∗ 4) → 𝐸𝐴(3 + 5 ∗ 4) → 𝐸 ∗ (3 + 5 ∗ 4) → 2 ∗ (3 + 5 ∗ 4)
In the grammar, 𝐸 and 𝐴 are non-terminals while the rest are terminals.
Compiler Construction ~ Wainaina Page 2 of 8
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.
