ITEC 460 - Chapter 3 Notes

Grammar Review

• CFG Definition
• Derivations and parse trees
• Ambiguous grammars
• Expression Grammar
• EBNF

CFG Grammar Definition

• CFG = Context Free Grammar
• T: Terminals
• N: Non-terminals (aka Variable)
• R: Rewrite rules (aka productions)
• S: Start symbol ∈ N
• Example Figure 3.2:
• T = {id, num, if, then, else, print, =, {, }, ;, {, } }


• S → print(E);
  | while ( B ) do S
  | { L}


• E → id | num


• B → E > E


• L → S | S L


• CF Grammars have single variable on LHS and any string of
  variables and terminals on RHS
• CF grammars called BNF (Backus Nauer Form) grammars

Derivations and Sentential Form

• Derivations:
• Start with start symbol
• Replace one nonterminal at each step
• Use ⇒ at each step


• Sentential Form: String of terminals and variables that can be derived from the start symbol


• Derive: while (ie > num) do print (id);

Right and Left Most Derivations

• Replace Right- (Left-) most variable at each step


• Derive: while (ie > num) do print (id);


• Relevant for different types of parsers
• Top Down - LL - Leftmost scan, leftmost derivation
• Bottom Up - LR - Leftmost scan, rightmost derivation (in reverse)

Parse Trees

• Graphical representation of a derivation
• Children of a node: RHS of a production w/ node as LHS
• Root: Start symbol
• Interior nodes: variables
• Leaves: terminals


• Derive: while (ie > num) do print (id);

Ambiguous Grammar

• ... if there is at least one string derivable from the grammar that has ...
• Ambiguous expression grammar
• Parse trees imply meaning so ambiguous grammars cause problems
• Unambiguous expression grammar
• No variable F

EBNF

• Use RE notation in grammars
• Examples: *, +, ?, |