2.0 Introduction

2.1 Grammars

2.2 Ambiguity

2.3 Summary

Web References

Exercises

Extended BNF

Reecursive procedures in programming can be rewritten using iteration (and a stack). Similarly, we can rewrite recursive procedures using iteration. Braces, { } are often used to represent 0 or more occurrence of their contents, while brackets, [], enclose optional items. Thus, using extended BNF, we can write the Expression grammar:

    E -- > T {+ T}

    T -- > F {* F}

    F -- > (E) | a

The first rule derives the sentential forms T, T + T, T + T + T, etc.

Of course, since F can derive an E in F -- > (E), this grammar is still (indirectly) recursive.