Page 204 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes
!
Caution There are no limitations on what occurs on the left or right-hand side except the
left hand side must be non-empty.

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. Alternatively, X may be substituted by v but
only when it is bounded by u and w. (i.e., in a specific context).
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. Wherever you locate X, you can substitute with v (in spite of context).

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. Specifically, the left-hand side must be a single nonterminal and the right-hand
side can be either unfilled, a single terminal by itself or with a single nonterminal. These
grammars are the most limited in terms of important power.

Did u know? Each type 3 grammar is a type 2 grammar, and each type 2 is a type 1 and so on.
Type 3 grammars are chiefly simple to parse due to the lack of recursive builds. Competent
parsers survive for many classes of Type 2 grammars. 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 parsers for them. In scheming programming languages by means of formal grammars,
we will utilize Type 2 or context-free grammars, frequently just shortened as CFG.

Task Make distinction between unobstructed grammars and regular grammars.
13.1.1 Issues in parsing Context-free Grammars

There are numerous competent approaches to parsing most Type 2 grammars. Though, there are
concerns that can interfere with parsing that we must take into consideration when scheming
the grammar. Let's discuss three of them: ambiguity, recursive rules, and left-factoring.

Ambiguity

If a grammar allows more than one parse tree for a number of sentences, it is said to be ambiguous.

Example: Consider the following typical arithmetic expression grammar:
E  E op E | ( E ) | int op  + | - | * | /
This grammar indicates expressions that contain integers connected by binary operators and
perhaps counting parentheses. As defined above, this grammar is uncertain since for certain
sentences we can build more than one parse tree.

198 LOVELY PROFESSIONAL UNIVERSITY