ITEC 380 2008fall ibarland

home—info—lectures—exams—archive

lect06c
mutual recursion example; intro BNF

- Sexpr: data-def'n.  Example: html.
   (see ~/Library/Preferences/.GlobalPreferences.plist.orig)


Data def'n, "S Expression":
An sexpr is:
 - an atom, or
 - a list-of-sexpr

A list-of-sexpr is:
 - empty, or
 - (cons sexpr list-of-sexpr)

An atom is:
 - a number
 - a symbol
 - a String
 - a boolean
 - a structure
 - an image
 - empty (!)

Same data def'n, written in BNF  [Reading: §3.1-§3.3 ]


sexpr ::= atom | sexprList
sexprList ::= empty
            | (cons sexpr sexprList)

atom ::= ...


We have already discussed how code which processes this data
will follow the shape of the data definitions.

Today, we'll start talking about BNF as a grammar specification,
and parsing:
reading in a stream of tokens, and figuring out if it meets the grammar
(building up a parse tree).


See:
Java syntax for 120 (which is incomplete and technically wrong in
some places), and
  BNF for java

Definition:
  terminal, nonterminal.
  Book also uses the terms:
     token (a nonterminal for a 'word' of the grammar), lexeme (a concrete 'word').
     Example: "Identifier" is a token; "173.4" is a lexeme.

That Java page didn't define 'Identifier'.
What is a legal Java identifier?
Write a BNF for it!


Example:
  Suppose we want to define "expressions":
    3+5
    (3+5)*4
    3+5*4
    3+(4*5)+((((7))))

What is a BNF?
- Derive these strings from the start terminal.
- Ambiguity.
- Precedence: hmmm.
  left-associative and right-associative rules.

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Oct.16 (Thu)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu