程序代写 Computer and Information Science Engineering

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):
, : Non-terminals;
0, 1, 2, …: Terminals
::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
::= |
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
::= |
| + | *
::= X | Y | Z
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