Given a context-free grammar as follows: S > ( S ) S S > [ S ] S S > (Note: mean

Question

Given a context-free grammar as follows:

S > ( S ) S

S > [ S ] S

S >

(Note: means the empty string or the string containing no character)

     a. Describe, in English, the language generated by this grammar

b. Give a parse tree for string ( [ ] ( [ ] ) ) [ ] ( ( ) )

c. Give a canonical derivation (also called right-most derivation, where the right-most remaining non-terminal is picked for replacement at each step) of this same string. Underscore the non-terminal to be replaced at each step of the derivation.

Explanation / Answer

The canonical example of a context free grammar is parenthesis matching, which is representative of the general case. There are two terminal symbols "(" and ")" and one nonterminal symbol S. The production rules are S SS S (S) S () The first rule allows the S symbol to multiply; the second rule allows the S symbol to become enclosed by matching parentheses; and the third rule terminates the recursion. A second canonical example is two different kinds of matching nested parentheses, described by the productions: S SS S () S (S) S [] S [S] with terminal symbols [ ] ( ) and nonterminal S. The following sequence can be derived in that grammar: ([ [ [ ()() [ ][ ] ] ]([ ]) ]) However, there is no context-free grammar for generating all sequences of two different types of parentheses, each separately balanced disregarding the other, but where the two types need not nest inside one another, for example: [ ( ] ) or [ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ]) A derivation of a string for a grammar is a sequence of grammar rule applications that transforms the start symbol into the string. A derivation proves that the string belongs to the grammar's language. A derivation is fully determined by giving, for each step: • the rule applied in that step • the occurrence of its left hand side to which it is applied For clarity, the intermediate string is usually given as well. For instance, with the grammar: (1) S S + S (2) S 1 (3) S a the string 1 + 1 + a can be derived with the derivation: S (rule 1 on first S) S+S (rule 1 on second S) S+S+S (rule 2 on second S) S+1+S (rule 3 on third S) S+1+a (rule 2 on first S) 1+1+a Often, a strategy is followed that deterministically determines the next nonterminal to rewrite: • in a leftmost derivation, it is always the leftmost nonterminal; • in a rightmost derivation, it is always the rightmost nonterminal. Given such a strategy, a derivation is completely determined by the sequence of rules applied. For instance, the leftmost derivation S (rule 1 on first S) S+S (rule 2 on first S) 1+S (rule 1 on first S) 1+S+S (rule 2 on first S) 1+1+S (rule 3 on first S) 1+1+a can be summarized as rule 1, rule 2, rule 1, rule 2, rule 3 The distinction between leftmost derivation and rightmost derivation is important because in most parsers the transformation of the input is defined by giving a piece of code for every grammar rule that is executed whenever the rule is applied. Therefore it is important to know whether the parser determines a leftmost or a rightmost derivation because this determines the order in which the pieces of code will be executed. See for an example LL parsers and LR parsers. A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example, if the string "1 + 1 + a" is derived according to the leftmost derivation: S S + S (1) 1 + S (2) 1 + S + S (1) 1 + 1 + S (2) 1 + 1 + a (3) the structure of the string would be: { { 1 }S + { { 1 }S + { a }S }S }S where { ... }S indicates a substring recognized as belonging to S. This hierarchy can also be seen as a tree: S /| / | / | S '+' S | /| | / | '1' S '+' S | | '1' 'a' This tree is called a parse tree or "concrete syntax tree" of the string, by contrast with the abstract syntax tree. In this case the presented leftmost and the rightmost derivations define the same parse tree; however, there is another (rightmost) derivation of the same string S S + S (1) S + a (3) S + S + a (1) S + 1 + a (2) 1 + 1 + a (2) and this defines the following parse tree: S /| / | / | S '+' S /| | / | | S '+' S 'a' | | '1' '1' If, for certain strings in the language of the grammar, there is more than one parsing tree, then the grammar is said to be an ambiguous grammar. Such grammars are usually hard to parse because the parser cannot always decide which grammar rule it has to apply. Usually, ambiguity is a feature of the grammar, not the language, and an unambiguous grammar can be found that generates the same context-free language. However, there are certain languages that can only be generated by ambiguous grammars; such languages are called inherently ambiguous languages.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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