Page 208 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes Likewise, the following grammar does not emerge to have any left-recursion:
S  Tu | wx
T  Sq | vvS
Yet after replacement of S into T, the left-recursion comes to light:
S  Tu | wx
T  Tuq | wxq | vvS
If we then eliminate left-recursion, we obtain:
S  Tu | wx
T  wxqT' | vvST'

Self Assessment

Fill in the blanks:
1. In ..................................., productions are of the appearance u -> v where both u and v are
random strings of symbols in V, with u non-null.
2. In ..................................., productions are of the appearance uXw  uvw where u, v and w
are random strings of symbols in V, with v non-null, and X a single nonterminal.
3. In ................................... productions are of the appearance X  v where v is an random
string of symbols in V, and X is a single nonterminal.
4. In Type 3 (regular grammars), productions are of the appearance X a, X aY, or X
where X and Y are ...................................and a is a terminal.

5. Even though Type 1 and Type 0 grammars are more influential than Type 2 and 3, they are
far less functional as we cannot generate competent ................................... for them.
6. If a grammar allows more than one parse tree for a number of sentences, it is said to be
...................................
7. If the recursive nonterminal is at the left of the right-side of the production, e.g. A -> u |
Av, we call the production ...................................

8. Each type 3 grammar is a type 2 grammar, and each type 2 is a ................................... and so on.

13.2 Backus Naur Form – Backus Normal Form (BNF)

BNF, formerly was named as "Backus Normal Form". It is a formal meta syntax used to articulate
context-free grammars. Backus Normal Form was renamed Backus Naur Form at the suggestion
of Donald Knuth.
The syntax of a programming language states the structure and organization of the elements in
the text of programs written in that language.

Did u know? The designers and implementers of FORTRAN, the first high-level
programming language, depicted its syntax in English prose, supplemented by instances.
Early FORTRAN programs were specified on punched cards, and the syntax of the language
reflects this. A FORTRAN program comprises more or less self-governing statements, usually in
one-to-one correspondence with cards. Every type of statement has an idiosyncratic syntax, which
is either fully fixed or has only a finite number of variants. FORTRAN statements are not nested.

202 LOVELY PROFESSIONAL UNIVERSITY