Suppose a grammar has the extended productions: A 0[B1]C2 | 0B[1C]2 Convert this
ID: 3758468 • Letter: S
Question
Suppose a grammar has the extended productions:
A 0[B1]C2 | 0B[1C]2
Convert this pair of extended productions to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended productions above.
(a) A 0A1C2 | 0BA22
A1 B1
A2 1C
(b) A 0B1C2 | 0C2 | 0B2
(c) A 0A12
A1 B1 | 1C
(d) A 0B1C2 | 0C2 | 0B2 | 02
Programming languages are often described using an extended form of context-free grammar, where square brackets are used to denote an optional construct. For example, A B[C]D says that an A can be replaced by a B and a D, with an optional C between them. This notation does not allow us to describe anything but context-free languages, since an extended production can always be replaced by several conventional productions.Suppose a grammar has the extended productions:
A 0[B1]C2 | 0B[1C]2
Convert this pair of extended productions to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended productions above.
(a) A 0A1C2 | 0BA22
A1 B1
A2 1C
(b) A 0B1C2 | 0C2 | 0B2
(c) A 0A12
A1 B1 | 1C
(d) A 0B1C2 | 0C2 | 0B2 | 02
Explanation / Answer
A context-free grammar is a description mechanism for formal languages that is easy to comprehend. This accounts for its popularity as a descriptive tool (v.s. BNF).
However, a number of apparently simple languages are not context-free, although close.
Such languages are often best described by giving a context-free grammar and noting the exceptions and restrictions.
e.g.,
Syntax of the Ada block statement (simplified)
<block> ::= <block identifier> :
begin <statement> {<statement>}
end <block identifier> ;
The Ada reference manual adds the restriction that the second block identifier must be equal to the first block identifier. Since this description is not difficult to express, it would be convenient if it were easily formalizable without resorting to context-sensitive grammars.
One approach is to augment the context-free production above with an attribute OK that will be set to true if the production is used correctly.
For example, A B[C]D says that an A can be replaced by a B and a D, with an optional C between them. This notation does not allow us to describe anything but context-free languages, since an extended production can always be replaced by several conventional productions.
A 0[B1]C2 | 0B[1C]2
A is replaced by 0 and C2 or 0B and 2 as an otional of B1 and 1C
Ans is D:
A 0B1C2 | 0C2 | 0B2 | 02
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.