Page 213 - DCAP507_SYSTEM_SOFTWARE

Unit 13: Formal Systems

13. At times syntactic elements are included in quotation marks and the names of syntactic Notes
categories are written without the ................................
14. It frequently occurs that two ................................ for the similar syntactic category vary
only in the presence or absence of some optional constituent.
15. Backus-Naur form is named after John Backus and ................................

13.3 Summary

 There are four types of formal grammars in the Chomsky Hierarchy, they extent from
Type 0, the most common, to Type 3, the most limiting.
 In Type 0 (free or unobstructed grammars) , productions are of the appearance u  v
where both u and v are random strings of symbols in V, with u non-null.
 In Type 1 (context-sensitive grammars), 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.
 In Type 2 (context-free grammars), productions are of the appearance X  v where v is an
random string of symbols in V, and X is a single nonterminal.
 In Type 3: regular grammars, productions are of the appearance X  a, X  aY, or X 
where X and Y are non-terminals and a is a terminal.
 BNF, formerly was named as "Backus Normal Form" which is a formal meta syntax used
to articulate context-free grammars.

 The syntax of a programming language states the structure and organization of the elements
in the text of programs written in that language.

 Plain vanilla BNF is unwieldy. For convenient use, the notation is usually extended in
different manners.

13.4 Keywords

Backus Normal Form: BNF, formerly was named as "Backus Normal Form" which is a formal
meta syntax used to articulate context-free grammars.
Type 0 (free or unobstructed grammars): In Type 0 (free or unobstructed grammars) , productions
are of the appearance u  v where both u and v are random strings of symbols in V, with u
non-null.
Type 1 (context-sensitive grammars): In Type 1 (context-sensitive grammars), 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.
Type 2 (context-free grammars): In Type 2 (context-free grammars), productions are of the
appearance X  v where v is an random string of symbols in V, and X is a single nonterminal.
Type 3 (regular grammers)  In Type 3 (regular grammars), productions are of the appearance X
 a, X  aY, or X  where X and Y are non-terminals and a is a terminal.

13.5 Review Questions

1. Elucidate the concept of languages hierarchy.
2. Make distinction between context-sensitive grammars and context-free grammars.

LOVELY PROFESSIONAL UNIVERSITY 207