Syntax Analysis

Dr. Nguyen Hua Phung

nhphung@hcmut.edu.vn

HCMC University of Technology, Viet Nam

07, 2019

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 1 / 37

Outline

1 Introduction to Syntax Analysis

2 Context-free grammar

3 Write a grammar

4 Some issues

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 2 / 37

Introdution

Roles
read the sequence of tokens
produce as output a parse tree or abstract syntax tree
(AST)
give error messages when detecting syntax errors

token parse
source lexical syntax
tree /
program analyzer analyzer
get next AST
token
symbol
table

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 4 / 37

Example

Source program: a = b * 4
Lexer output (parser input): ID ASSIGN ID MULOP INTLIT
Parser output:
<assign-stmt>

ID ASSIGN <expr>

<term>

<term> MULOP <fact>

ID INTLIT

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 5 / 37

Regular Expression

Can we use regular expression to express the following

language?

L = {an bn | n > 0}
Example
In programming languages, there are some symmetric
structure
(((...))) the number of ( must be equal to that of )
repeat ... repeat ... until ... until

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 7 / 37

Recursive Structure

More generally, programming languages have many recursive

structures
Example
<expr> ::= <expr> + <expr>
<stmt> ::= if <expr> then <stmt> else <stmt>

Regular expressions cannot describe this kind of structure

We need
A mean to describe this kind of language
A method to detect if a sequence of tokens is valid or
invalid regarding to this kind of language

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 8 / 37

Context-free grammar

A context-free grammar (CFG) consists of

A set of terminals T
A set of non-terminals N
A start symbol S ∈ N
A set of productions P
A production p ∈ P is in the form: X → α
where X ∈ N and α is a sequence of symbols in T and/or N

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 9 / 37

Example

CFG for simple integer expressions consists of:

Set of terminals (tokens):{ADDOP, MULOP, INTLIT, LB,
RB}
Set of non-terminals:{<exp>}
Start symbol: <exp>
Set of productions:
<exp> → <exp> ADDOP <exp>
<exp> → <exp> MULOP <exp>
<exp> → INTLIT
<exp> → LB <exp> RB

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 10 / 37

Example

CFG for simple integer expressions consists of:

Set of terminals (tokens):{ADDOP, MULOP, INTLIT, LB,
RB}
Set of non-terminals:{<exp>}
Start symbol: <exp>
Set of productions:
<exp> → <exp> ADDOP <exp>
| <exp> MULOP <exp>
| INTLIT
| LB <exp> RB

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 11 / 37

Derivation

How to know the language which a CFG describe?

Language Generation
1 Start with the string containing only the start symbol
2 Replace any non-terminal symbol X in the string with the
right-hand side of some production X → α
3 Repeat (2) until there are no non-terminals in the string

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 12 / 37

Example

Grammar
<exp> → <exp> ADDOP <exp> (1)
| <exp> MULOP <exp> (2)
| LB <exp> RB (3)
| INTLIT (4)

Derivation
(2)
<exp> ⇒ <exp> MULOP <exp>
(4)
⇒ INTLIT MULOP <exp>
(1)
⇒ INTLIT MULOP <exp> ADDOP <exp>
(4)
⇒ INTLIT MULOP INTLIT ADDOP <exp>
(4)
⇒ INTLIT MULOP INTLIT ADDOP INTLIT

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 13 / 37

Context-free language

Let G be a context-free grammar with start symbol S. The

language L(G) generated from G is:

+
{ a1 a2 ...an | ai ∈ T and S ⇒ a1 a2 ...an }

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 14 / 37

Language Recognization

CFG is a good mean to describe PL, but:

Not only check if a string is valid but also its parse tree
how to handle gracefully error

Parse Tree
Start symbol as the parse tree’s root
For a production X → Y1 Y2 ...Yn , add children Y1 Y2 ...Yn to
node X

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 15 / 37

Example

Source: 12 * (4 + 5)
Parser input: INTLIT MULOP LB INTLIT ADDOP INTLIT
RB
Parser output:
<exp>

<exp> MULOP <exp>

INTLIT LB <exp> RB

<exp> ADDOP <exp>

INTLIT INTLIT

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 16 / 37

Some tricks

Based on the language specification

Try to find out the hierarchy structure of a language
Focus on the order of syntax units instead of their
meaning or other constraints
Use recursion to describe something occurring many
times
Use recursion to describe nested structures

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 18 / 37

Based on language specification

Each language has its own specification which sometimes

differs from common sense
Smalltalk has the same precedence for all binary
operators
a + b * c ≡ ((a + b) * c)
C specifies > , < , >= , <= higher priority than ==, != while
Pascal lets these operators same priority

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 19 / 37

Hierarchy Structure

program

declaration function

variable constant parameter

statement
declaration declaration declaration

type idlist expression

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 20 / 37

Example

program → ...
program
declaration → ...
variable_decl → ...
declaration function const_decl → ...
type_decl → ...
variable constant parameter idlist → ...
statement
declaration declaration declaration
function → ...
para_decl → ...
type idlist expression stmt → ...
exp → ...

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 21 / 37

Just the order, not other constraints

CFG just helps to describe the order of tokens

CFG cannot be used to describe type constraints
Some other kinds of constraints such as scope, name
resolution,... cannot be solved by CFG

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 22 / 37

Example

2.1 Constant Declaration:

Each constant declaration has the form:

<identifier> = <expression> ;
The <expression> will be discussed later in the Expression
section. Note that the expression in a constant declaration must
be evaluated statically, so it cannot include a variable or a
method invocation.
For example:
My1stCons = 1 + 5;
MyndCons = 2 * My1stCons;

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 23 / 37

One vs Many

Some language structures may contain unlimited list of

elements:
A variable declaration may have a list of identifiers
a, c10, b: integer;
A function declaration may have a list of parameter
function foo(a:integer; b:real)
A block may have many statements inside
begin
c := 1;
m := 10;
end

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 24 / 37

Write grammar rule for <many>

Use recursion to describe <many> based on <one>

<many> → <one> <many’>
| <non recursive case>
<many’> → [<separator>] <one> <many’>
| 
<separation>: symbol is used to separate elements in a list
a, c10, d: integer
function foo(a:integer;b:real)
<non recursive case>: the minimum number of elements in
the list
<one> if there is at least one element
 if the list may be empty
For example,
listid → ID tailid | ID
tailid → COMMA ID tailid | 

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 25 / 37

Nested structures

In programming languages, there are many nested structures:

There may be a function declaration in a function
declaration
A statement may appear inside another statement.
A block may appear inside another block
An expression may be an operand of another expression
...
Use recursion to describe a nested structures, for example
<stmt> → IF <exp> THEN <stmt> ELSE <stmt>
| WHILE <exp> DO <stmt>
| ...

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 26 / 37

Extended Backus-Naur Form(EBNF)

EBNF
allow to use operators in regular expression in RHS
higher expressiveness
often supported by top-down parsing generators
BNF EBNF (RHS) ANTLR
<exp> → <exp> ’+’ <term>
exp:
| <exp> ’-’ <term> <term> ((’+’|’-’) <term>)*
term ((’+’|’-’) term)*;
| <term>
<else> → ELSE <stmt> else:
(ELSE <stmt>)?
|  ("else" stmt)?;
<idlist> → ID ’,’ idlist idlist:
ID (’,’ ID)*
| ID ID ("," ID)* ;

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 27 / 37

Ambiguous grammar

When more than one parse tree can be found for a string of
tokens, the grammar is ambiguous
Ambiguity makes the meaning of some programs ill-defined

Example: INTLIT ADDOP INTLIT MULOP INTLIT

<exp> <exp>

<exp> MULOP <exp> <exp> ADDOP <exp>

<exp> ADDOP <exp> INTLIT INTLIT <exp> MULOP <exp>

INTLIT INTLIT INTLIT INTLIT

ADDOP calculated first MULOP calculated first

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 29 / 37

Disambiguous ambiguous grammar

Rewrite the grammar unambiguously

In some grammar tools, there are disambiguating
declarations
<exp> → <exp> ADDOP <exp> | <exp> MULOP <exp>
| INTLIT
| LB <exp> RB
The recursive term <exp> appeared in both sides of
ADDOP and MULOP is the source of ambiguity.
Removing one recursive term in right hand side of
productions can disambiguous the grammar.
<exp> → <exp> ADDOP <term> | <exp> MULOP <term>
| <term>
<term> → INTLIT
| LB <exp> RB

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 30 / 37

Operator Association

A binary operator o is left-associated (or right-associated)

when the left (or right) operator o in expression x o x o x is
calculated first.
For example,
9-5-2⇒6⇒2
The operator side where the recursive term appears will
determine the association of the operator

For example,
if ADDOP is left-associated, the grammar should be
<exp> → <exp> ADDOP <term>
if ADDOP is right-associated, the grammar should be
<exp> → <term> ADDOP <exp>

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 31 / 37

Operator Precedence

To priorize opterators, the left hand sides (lhs) of the rules

where these operators appear should be different
if operator o1 has higher priority than operator o2 , o1 ’s lhs
is generated by o2 ’s lhs
For example,
<exp> → <exp> ADDOP <term>
| <term>
<term> → <term> MULOP <factor>
| <factor>
<factor> → INTLIT
| LB <exp> RB

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 32 / 37

If Statement

<stmt> → IF <exp> THEN <stmt> ELSE <stmt>

| IF <exp> THEN <stmt>
| <other>
Draw parse tree for input
IF <exp> THEN IF <exp> THEN <other> ELSE <other>
<stmt>

IF <exp> THEN <stmt> ELSE <other>

IF <exp> THEN <other>

or
<stmt>

IF <exp> THEN <stmt>

IF <exp> THEN <other> ELSE <other>

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 33 / 37

Disambiguous grammar of if statement

Natural if-statement grammar

<stmt> → IF <exp> THEN <stmt> ELSE <stmt>
| IF <exp> THEN <stmt>
| <other>

Unambiguous if-statement grammar

<stmt> → <matchStmt>
| <unmatchStmt>
<matchStmt> → IF <exp> THEN <matchStmt>
ELSE <matchStmt>
| <other>
<unmatchStmt> → IF <exp> THEN <stmt>
| IF <exp> THEN <matchStmt>
ELSE <unmatchStmt>

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 34 / 37

Declarations in grammar tools

Some grammar tools has declarations to disambiguous

grammar
Write grammar in natural format and use declarations to
disambiguous it
For example, ANTLR has
use option <assoc=left>, <assoc=right> for left- and right-
associativity, respectively.
the order of these declarations makes the order of operator
precedence

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 35 / 37

Example in ANTLR

main : expr EOL

;
expr :
LB expr RB
| ADDOP expr // highest
| expr MULOP expr //default: left-assoc
| expr ADDOP expr
| <assoc=right> expr ’=’ expr // lowest, right-assoc
| INT
| ID
;

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 36 / 37

Summary

Context-free grammar: only one non-terminal symbol on

the LHS
Some issues when writing a CFG
ambiguous - dis-ambiguous
operator association
operator precedence

Dr. Nguyen Hua Phung nhphung@hcmut.edu.vn Syntax Analysis 37 / 37