[SOLVED] 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 Assignmentchef assignmentchef

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 righttree?
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 notbetween + 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: assignmentchef QQ: 1823890830 Email: [email protected]