Week 3 Notes

Grammars Continued | CS 3040

Terminals

Things that aren't substituted

Definitions

Definition 6.1 (Context-free grammar (CFG)).

• A CFG G is a quadruple <N,T,P,S> where

  • N is a finite set of nonterminals
  • T is a finite set of terminals, with N and T = null set
  • P is a finite set of rules (or productions) as a subset of N x (N or T)*
    • These are typically written with ->: N -> (N or T)*
  • S in N is the start symbol

• Example: formal definition of a grammar for positive binary numbers:

  • < N, T, P, S>: < {B}, {0, 1}, {B -> 0B, B -> 1B, B -> epsilon}, B >

Definition 6.2 (Context-free derivation):

• Given a CFG G = <N,T,P,S> and
• a sequence p n q with n in N, p, q in (N U T)*,
• the sequence p r q with r in (N U T)* is called a derivation step,
  • denoted by p n q => p r q,
• if n -> is a production in P.
• Example derivation sequence for expressions:

Expression => Term => Factor * Term => Constant * Term => Digit * Term

Definition 6.3 (Language generated by a CFG):

• Given a CFG G = <N,T,P,S>, the language L(G) generated by G:
  • the set of all terminal sequences that are derivable from S
• More concisely, L(G) = { w in T* | S =>+ w}

The start is always not a terminal.

Definition 6.4 (Well-formed CFG):

Every non-terminal is useful.

• A CFG G = <N,T,P,S> is well-formed if for each n in N,
  • There exists a w in T* such that n =>+ w
  • There exist p,q, in (N U T)* such that S =>* p n q

Grammars Continued | CS 3040

Extended BNF (EBNF)

• Almost alwasys use some extension
• Use | for alternatives:
  • Statement -> IfStatement | ForStatement
• Mark optional portions (following textbook): items?
  • Statement -> if '(' Expr ')' Statement (else Statement)?
• Repeat an element: (...)* (zero or more), (...)+ (1 or more)
  • Bit -> 0 | 1
  • Number -> Bit+ ( '.' Bit+ )?
• Allow specifying terminals using regular expressions:
  • Digit -> [0-9]
  • PhoneNumber -> [0-9]+-[0-9]+

stmt -> Variable '=' expression';'
stmt -> 'return' Expression';'
stmt -> 'ident' '(' ExpressionsList ')' ';'
ExpressionList -> epsilon | Expression (',' Expression)* 
...

Are there non-context sensitive languages?

• Yes, but proof out of scope for CS3040
• Involves lanugages recognized by Turing Machines; covered elsewhere
• These are effectively anything that's computable

Chomsky Hierarchy:

• L(RE) subset L(CFG) subset L(CSG) subset all Formal Lanugages
• "All formal languages": ones for which there exist a Turing Machine; also known as a "Turing Complete" languages

EBNF vs. BNF

• Do we have to have EBNF?
• Theorem: For every EBNF grammar G, there is a BNF grammar G' that recognized the same strings
• Suppose we have a production A -> a y? b
• It can be rewritten as

A -> a A' B
A' -> y | epsilon

• EBNF is easier
• Easier to prove results with BNF

Other ways

• Railroad Diagrams

Grammars | CS 3040

Ambiguous Grammars

• More than one parse tree
  • More than one derivation sequence is not enough!
  • Multiple parse trees = multiple structural interpretations
• Example:
  • Expr -> Expr Op Expr
  • Expr -> [0-9]+
  • Op -> 'x' | '*' | '-' | '/'
• Apply to 3 - 4 / 5
• Fix: Separate different operator types using Expression/Term/Factor grammar from earlier…
  • Allow (+|-) in Expression
  • Allow (* | /) in Term, but then…

Meta-meta-level Languages

• Textbook: Discusses using CFGs to specify CFGs
  • Shows that CFGs are powerful
• A common standard for programming languages through the 80s and 90s: if a language is powerful, one should be able to write the compiler in that language
  • 00s and beyond: there is no real difference in power, just expressiveness
  • The only people who care about the compiler's language are those who are maintaining the compiler
  • Get the job done
• Challenge with using CFGs to specify CFGs: notation like ':' can either be a part of a grammar rule or a meta-symbol

Haskell?

• Can be a "pure functional" programming language - no side-effects
  • Easier to reason about - don't have to worry calling a method changes some data at random
  • Easier to parallelize - each node can compute its own result without other nodes being able to change data the nodes depends on
  • Type system will help us determine which are pure functions
  • Sophisticated type system - one of the most powerful

Haskell | CS 3040

(Haskell Discussion)