CSE411: Introduction to Compilers

Introduction to Parsing

Jooyong Yi (UNIST)

Parsing

        position  =  initial  +  rate   *   60
                           ↓
        |------------------------------------|
        |      Lexical Analyzer (Lexer)      |
        |------------------------------------|
                           ↓
        <id, 1> <=> <id, 2> <+> <id, 3> <*> <int, 60>
                           ↓
        |------------------------------------|
        |      Syntax Analyzer (Parser)      |
        |------------------------------------|
                           ↓
                       =
                      / \
                <id,1>   +
                        / \
                   <id,2>  *
                          / \
                    <id,3>   <int,60>                   

Why a Tree?

Why a Tree?

            IfStmt                                  
        /           \                             
      Cond          Then                      
        |             |                       
      BinExp        Assign                    
      /  | \       /       \                   
     ID OP   Num   Left     Right                
     |   |   |     |         | 
     x   >    0    ID      BinExp
                   |     /    |     \    
                   y   Left  Op  Right
                        |     |      |
                        ID    +      Num
                        |            |
                        x            1

Parse Tree and Abstract Syntax Tree (AST)

          Parse Tree                                  AST

            IfStmt                                  IfStmt
        /           \                             /       \
      Cond          Then                      BinOp(>)     Assign
       |             |                          /  \      /   \
      BinOp        Assign                      x    0    y   BinOp(+)
      /  \       /       \                                   /  \
     ID  Num   Left     Right                               x    1
     |    |     |         | 
     x    0     ID      BinExp
                |    /    |      \    
                y   Left  BinOp  Right
                     |    |       |
                     ID   +       Num
                     |            |
                     x            1

How to write a parser to generate a parse tree?

Recall how a lexer is obtained

RE -> NFA -> DFA

What to give as the specification for a parser?

What to give as the specification for a parser?

Recall that a parser is also known as a syntax analyzer, which detects syntactic errors.

Is a regular expression sufficient to describe the syntax of a programming language?

INT: 0 | [1-9] [0-9]*
VALID: INT

1  : valid
10 : valid
5  : valid
0  : valid
01 : invalid

INT : 0 | [1-9] [0-9]*
PLUSEXP:
VALID: INT | PLUSEXP

1+1   : valid
10+5  : valid
5+0   : valid
0+01  : invalid
01+55 : invalid

INT : 0 | [1-9] [0-9]*
PLUSEXP: INT '+' INT
VALID: INT | PLUSEXP

1+1   : valid
10+5  : valid
5+0   : valid
0+01  : invalid
01+55 : invalid

INT : 0 | [1-9] [0-9]*
PLUSEXP: INT '+' INT
PARENEXP: '(' PLUSEXP ')'
VALID: INT | PLUSEXP | PARENEXP

(1+1)   : valid
(10+5)  : valid
(5+0)   : valid
(0+01)  : invalid
(01+55) : invalid

INT : 0 | [1-9] [0-9]*
PLUSEXP: INT '+' INT
PARENEXP: '(' PLUSEXP ')'
VALID: INT | PLUSEXP | PARENEXP

(1+(10+5)) : valid
(10+5))    : invalid

How to change the regular expression?

INT : 0 | [1-9] [0-9]*
PLUSEXP: EXP '+' EXP
PARENEXP: '(' EXP ')'
EXP: INT | PLUSEXP | PARENEXP
VALID: EXP

(1+(10+5)) : valid
(10+5))    : invalid

INT : 0 | [1-9] [0-9]*
PLUSEXP: EXP '+' EXP
PARENEXP: '(' EXP ')'
EXP: INT | PLUSEXP | PARENEXP
VALID: EXP

(1+(10+5)) : valid
(10+5))    : invalid

Is this a regular expression?

Context-Free Grammar (CFG)

INT → 0 | [1-9] [0-9]*
PLUSEXP → EXP '+' EXP
PARENEXP → '(' EXP ')'
EXP → INT | PLUSEXP | PARENEXP
VALID → EXP

• CFG
  • : a finite set of non-terminals (e.g., VALID, EXP, PARENEXP, PLUSEXP).
  • : a finite set of terminal symbols (e.g., '(', ')', '+', INT)
  • : a start non-terminal (e.g., VALID)
  • : a finite set of productions.
    • Each production has the form
      • where and

What does "context-free" mean?

• CFG
  • : a finite set of non-terminals (e.g., VALID, EXP, PARENEXP, PLUSEXP).
  • : a finite set of terminal symbols (e.g., '(', ')', '+', INT)
  • : a start non-terminal (e.g., VALID)
  • : a finite set of productions.
    • Each production has the form
      • where and

Context-Free Grammar vs. Context-Sensitive Grammar

• CFG , CSG
  • : a finite set of non-terminals (e.g., exp).
  • : a finite set of terminals (e.g., '(', ')', PLUS)
  • : a start non-terminal (e.g., start)
  • : a finite set of productions.
    • CFG
      • Each production has the form
        • where and
    • CSG
      • Each production has the form
        • where , and

Recall

• Regular expression specifies what to recognize as legitimate tokens.
• There exists a NFA that recognizes the tokens specified by .
• Given an NFA , there exists a DFA that recognizes the same language as .

Recall

• What: regular expression
• How: NFA and DFA

• What: CFG specifies what to recognize as syntactically valid programs.
• How:

• What: CFG specifies what to recognize as syntactically valid programs.
• How: Non-deterministic Pushdown Automata (NPDA)

CFG and NPDA

Theorem: For any context-free grammar , there exists an NPDA accepting .

NPDA

Automaton with a stack

NPDA Example

INT → 0 | [1-9] [0-9]*
PLUSEXP → EXP '+' EXP
PARENEXP → '(' EXP ')'
EXP → INT | PLUSEXP | PARENEXP
START → EXP

Non-deterministic PDA (NPDA)

• NPDA
  • : a finite set of states
  • : the input alphabet
  • : the stack alphabet
  • : the transition function
  • : the initial state
  • $ : stack start symbol
  • : set of final states

Acceptance Condition of NPDA

• Suppose
• if and
  1. When all symbols of the input are consumed, the final state is reached.
  2. The state of the stack is irrelevant to the acceptance.

Deterministic PDA (DPDA)

• DPDA
  • : a finite set of states
  • : the input alphabet
  • : the stack alphabet
  • : the transition function
    • Note: If is defined, then should not be defined for every .
  • : the initial state of the control unit
  • $ : stack start symbol
  • : the set of final states

Is it a DPDA?

DPDA Example

'#' indicates the end of the input.

NPDAs are more expressive than DPDAs.

NPDAs are more expressive than DPDAs.

• Multiple states in an NFA ⟼ a single state in a DFA (possible)
• Multiple stack configurations in an NPDA ⟼ a single stack configuration in a DPDA (not always possible)

CFG NPDA DPDA

• This does not work.
• We need a different approach to obtain a deterministic parser.

Science and Engineering

• Tony Hoare (Turing Award Laureate, 1980) once said something along these lines:
  • Engineers seek the 'it works!' moment, while scientists seek the 'Aha!' moment.

• Which department are you in?