..

2023-08-30

Parse Tree vs Syntax Tree

  • ST is a condesed version of PT
  • PT will have everything
  • ST is smaller

Derivations

  • Evaluation is done through Post Order Traversal(Left, Right, Node) of the PT
  • Ambiguous strings are those who have two PT
  • This ambiguity can occur in three ways
    • > 1 Left Most Derivations
    • > 1 Right Most Derivations
    • >= (1 LMD && 1 RMD)

Examples

x - 2 * y
EXPR -> EXPR OP VAL | VAL
VAL -> ID | NUM
NUM -> [0-9]+
ID -> [a-z]+
OP -> + | - | * | /

LMD

EXPR
EXPR OP VAL
EXPR OP VAL OP VAL
VAL OP VAL OP VAL
ID OP NUM OP ID
x - 2 * y

RMD

EXPR
EXPR OP VAL
EXPR OP ID
EXPR OP y
EXPR * y
EXPR OP VAL * y
EXPR OP NUM * y
EXPR OP 2 * y
EXPR - 2 * y
VAL - 2 * y
ID - 2 * y
x - 2 * y

HW

Remove ambiguity from this grammar

STMT -> if EXPR then STMT | if EXPR then STMT else STMT