Programming languages are often described using an extended form of context-free

Question

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 B[CD]EF | BC[DE]F

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 BCDEF | BEF

b) A BA1F

A1 CD | DE |

c) A BA1EF | BCA2F

A1 CD |

A2 DE |

d) A BA1EF | BCA2F

A1 CD

A2 DE

What is the answer? Explain me Plz

Explanation / Answer

Given grammar :-

A B[CD]EF | BC[DE]F

says that an A can be replaced by a B and a EF, with an optional CD between them or A can be replaced by a BC and a F, with an optional DE between them.

Conventional productions that is equivalent to the productions above :-

c) A BA1EF | BCA2F

A1 CD |

A2 DE |

Hint :-

a is not possible because A BCDEF is not always a production

b is not possible because A BA1EF | BCA2F; A1 CD | ; A2 DE | ; does not give B[CD]EF | BC[DE]F

d is also not possible because it does not have

only option c gives A B[CD]EF | BC[DE]F

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.