CS 320 : Formal Grammars
Marco Gaboardi MSC 116 gaboardi@bu.edu
Announcements
• Thethirdprogrammingassignmentisposted.
• Due Sunday October 25th 11:59pm.
Plan for today
• IntrotoPart2
• Formalgrammars
PART II
What is the area of P Programming Languages?
ØLanguage Design L
• Programming Constructs, Abstractions ØFormal mechanisms to reason about and specify
What we
have
focused What we
on so far. will do for
the rest of the class.
programs / languages
• Type Systems, Verification
ØCompiler Design
• Optimizations, Program Analysis, JIT
ØLanguage Runtime Design
• Virtual Machines, Garbage Collection, JIT, Interpreters
Commonalities and differences
I n t e r p r e t a t i o n
C o m p i
l a t i o n
© 2015 Elsevier, Inc. All rights reserved.
TopHat Q1-Q3
Formal Grammars
BNF – Backus Normal/Naur Form
• A grammar is defined by a set of terminals (tokens), a set of nonterminals, a designated nonterminal start symbol, and a finite nonempty set of rules
::=
::= a | an | the
::= man | apple | worm | penguin ::=
Generator vs Recognizer
::= a | b | c | d
Recognize a sentence Generate a sentence
a = b + const
= b + const = + const =
=
a =
a =
a = +
a = b +
a = b + const
TopHat Q4-Q8
Some examples
::=
::= a | an | the
::= man | apple | worm | penguin ::=
How do we generate the following sentence?
the penguin sees.
Some examples
::=
::= a | an | the
::= man | apple | worm | penguin ::=
How do we generate the following sentence?
a worm eats an apple.
Some examples
::=
::= a | an | the
::= man | apple | worm | penguin ::=
How do we recognize the following sentence?
a man throws a penguin.
TopHat Q9-Q14