Lecture#7 - cse344compilerdesign

Lecture # 7
Chapter 4: Syntax Analysis
What is the job of Syntax Analysis?
• Syntax Analysis is also called Parsing or Hierarchical Analysis.
• A Parser implements grammar of the language may it be C,
C++ etc
• The parser obtains a string of tokens from the lexical analyzer
and verifies that the string can be generated by the grammar
for the source language
• The grammar that a parser implements is called a Context
Free Grammar or CFG
Position of a Parser in the Compiler
Get next
Lexical error
and rest of
Syntax error
Semantic error
Symbol Table
The Parser
The role of the parser is twofold:
1. To check syntax (= string recognizer)
And to report syntax errors accurately
2. To invoke semantic actions
For static semantics checking, e.g. type checking of
expressions, functions, etc.
What is the difference between Syntax
and Semantic?
• Syntax is the way in which we construct
sentences by following principles and rules.
• Semantics is the interpretations of and
meanings derived from the sentence
transmission and understanding of the
message or in other words are the logical
sentences making sense or not
Error Handling
• A good compiler should assist in identifying and
locating errors
– Lexical errors: important, compiler can easily recover and
continue such as misspelling an identifier, keyword etc.
– Syntax errors: most important for compiler, can almost
always recover such as arithmetic expression with
unbalanced parenthesis
– Static semantic errors: important, can sometimes recover
such as operator applied to incompatible operands
– Dynamic semantic errors: hard or impossible to detect at
compile time, runtime checks are required
– Logical errors: hard or impossible to detect such as infinite
recursive calls
Viable-Prefix Property
• The viable-prefix property of parsers allows
early detection of syntax errors
– Goal: detection of an error as soon as possible
without further consuming unnecessary input
– How: detect an error as soon as the prefix of the
input does not match a prefix of any string in the
for (;)
Error is
detected here
Error Recovery Strategies
• Panic mode
– Discard input until a token in a set of designated
synchronizing tokens is found
• Phrase-level recovery
– Perform local correction on the input to repair the error
• Error productions
– Augment grammar with productions for erroneous
• Global correction
– Choose a minimal sequence of changes to obtain a global
least-cost correction
Context free Grammar
• Context-free grammar is a 4-tuple
G = (N, T, P, S) where
– T is a finite set of tokens (terminal symbols)
– N is a finite set of nonterminals
– P is a finite set of productions of the form
where   N and   (NT)*
– S  N is a designated start symbol
Example Grammar
Context-free grammar for simple expressions:
G = <{expr,op,digit}, {+,-,*,/,0,1,2,3,4,5,6,7,8,9,),(}, P,expr>
with productions P =
expr expr op expr
expr (expr)
expr  digit
digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
op  + | - | * | /
Notational Conventions Used
• Terminals: Lower case letters, operator symbols,
punctuation symbols, digits, bolface strings are all
• Non Terminals: Upper case letters, lower case
italic names are usually non terminals
• Greek letters such as ,, represent strings of
grammars symbols. Thus a generic production
can be written as A 
Examples of CFG
• Write a CFG that generates Even Palindrome
S  aSa | bSb | є
• Write a CFG that generates Odd Palindrome
S  aSa | bSb | a | b
• Write a CFG that generates Equal number of a’s
and b’s
S  aSbS | bSaS | є
• Write a CFG that generates Equal number of
a’s and b’s
S  aSbScS | aScSbS | bSaScS | bScSaS |
cSaSbS | cSbSaS | є

similar documents