CMSC 330 Homework #4– context–free grammars Fall 2005To make your answers easier to compare with the solutions, use consecutive nonterminals beginning withS when writing your grammars (S, T, U, etc.).1. In Pascal both of the following syntax forms can be used for an array typearray[lower–bound1..upper–bound1, ..., lower–boundn..upper–boundn] of element–type;array[lower–bound1..upper–bound1]...[lower–boundn..upper–boundn] of element–type;What an array’s bounds and an array’s element type can be are described below.Note that an array’s lower subscript is not necessarily 0 as in C, C++, and Java. For example, here area few array types in Pascal (all of which have integer bounds):array[1..10] of integer;array[5..50] of char;array[1..10,10..20] of integer;array[1..10][10..20] of integer;The second one has subscripts ranging between 5 and 50 (inclusive), while the last two are two–dimensional arrays.Write an unambiguous grammar generating array types similar to Pascal’s as specifically describedbelow. (Array types in this problem are based upon, but not completely the same as, Pascal’s arrays.)• For purposes of this problem, an array type begins with the word array, which is followed bythe array’s dimensions, then the word of, then an identifier and a semicolon. Don’t worry aboutindicating where whitespace may appear.• An array’s dimensions are either a sequence of one or more ranges each inside its own set of squarebraces, or a single comma–separated list of one or more ranges all together inside one set of squarebraces.• For purposes of this problem a range consists of two constant values of the same type separated by.. (two adjacent period characters). A range can contain two boolean constants, two identifiers,two character constants, or two integer constants.• The only two boolean constants are true and false. Assume that identifers consist of sequencesof one or more occurrences of of the letters a, b, and c, and the characters which can appear ascharacter constants are x, y, and z. A character constant is surrounded by single quotes (’’).An integer constant consists of a sequence or one or more decimal digits (0 through 9), optionallypreceded by a single plus (+) or minus (-) sign.Note that your grammar must generate all the tokens (integer constants, character constants, etc.) inarray types; the only thing you don’t have to worry about is where whitespace may appear.2. Write unambiguous grammars for the following languages:a. { anbn| n ≥ 0 and n is even }b. { aibjc2i+1dk| i, j, k ≥ 0 }c. { γ1γ2. . . γnγn. . . γ2γ1| γi∈ {a, b}, 1 ≤ i ≤ n }Note this language is describing all strings which are palindromes, that is, they read the sameforward as backwards, over the alphabet Σ = {a, b}.d. { ambnam+n| m ≥ 0 and n ≥ 1 }e. { anbman−m| n ≥ m ≥ 0 }1f. All possible sequences of balanced parentheses. Each string in the language is composed of zero ormore of the symbols ( and ). Each valid string must have same number of left parentheses as rightparentheses, and they must be properly balanced, with every opening left parenthesis paired witha later closing right parentheses. Valid strings may contain nested parentheses. For example, thestrings (()) and (()(()())) contain matching balanced parentheses, while (()(()()) and (()))( do not.g. { w | w ∈ {a, b}∗and w has an equal number of a’s and b’s }h. { ambn| m 6= n and m, n ≥ 0 }i. { ambncpdq| m + n = p + q }3. Write a grammar for the language { anbnambm| m, n ≥ 1 } ∪ { anbmambn| m, n ≥ 1 }. If yourgrammar is ambiguous, prove that it
View Full Document
Unlocking...