程序代写代做代考 interpreter C compiler CS 320 : Formal Grammars

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 ::= | ::= eats | throws | sees | is

Generator vs Recognizer ::=
::= | ;
::= =
::= a | b | c | d
::= + | ::= | const
Recognize a sentence Generate a sentence
a = b + const
= b + const = + const = + const = + =

=:: ::=
=
a =
a = +
a = +
a = b +
a = b + const

TopHat Q4-Q8

Some examples




::= . ::=


::= a | an | the
::= man | apple | worm | penguin ::= | ::= eats | throws | sees | is
How do we generate the following sentence?
the penguin sees.

Some examples




::= . ::=


::= a | an | the
::= man | apple | worm | penguin ::= | ::= eats | throws | sees | is
How do we generate the following sentence?
a worm eats an apple.

Some examples




::= . ::=


::= a | an | the
::= man | apple | worm | penguin ::= | ::= eats | throws | sees | is
How do we recognize the following sentence?
a man throws a penguin.

TopHat Q9-Q14