Computer and Information Science Engineering
BNF (“ Form”): The BNF grammar of a prog. lang. L is a precise description of the context-free requirements that programs of L must satisfy
Reserved symbols of BNF: <, >, ::=, |
Copyright By PowCoder代写 加微信 powcoder
Simple Example (Not Realistic):
0, 1, 2, …: Terminals
To define a BNF grammar:
Specify terminal and non-terminal symbols
Specify starting non-terminal
Define the production for each non-terminal
Knowledge check:
Why is the above example not realistic?
BNF (aka Context-free Grammars)
Derivation trees/Parse trees
How do you derive “655” from this grammar?
Knowledge check: What is the bug in this tree?
The string derived (or parsed) by the tree:
Append together the labels at the leaves in left-to-
right order.
Example: Grammar of expressions
|
Parse tree for X + Y :
Grammar of expressions (contd.)
Parse tree for X + Y * Z:
Grammar of expressions (contd.)
Another tree for X + Y * Z:
Knowledge check: Which is the right tree?
The grammar is ambiguous.
Knowledge check:
Show that this grammar is not ambiguous
Another grammar for expressions
Knowledge check:
Reintroduce ambiguity among +’s and *’s
(but not between + and *)
Knowledge check (more difficult):
Allow parenthesized expressions so we can have expressions such as: (X + Y) * Z
Knowledge check (contd.)
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com