CMSC 330 Homework #5Using grammars for programming languagesFall 20051. Grammars can be used to express concepts like associativity and precedence of operators. For eachof the following languages, give unambiguous grammars capturing the appropriate associativity andprecedence.a. Propositional calculus formulas having operators unary ∼ (negation) and binary → (implication),operands p and q, and parentheses. The operators should both be right associative and have theirusual precedence, which is that ∼ has higher precedence than →.b. C expressions with identifiers a and b and operators ->, *, and ++. -> is a left associative binaryoperator, * is a right associative unary prefix operator, and ++ is a left associative unary postfixoperator. The prefix * operator has a lower precedence than the postfix ++ operator, but higherthan the binary -> operator. For example, the expression *a++ increments a before dereferencingit.c. Operators in APL are right associative and have equal precedence, unless altered by parentheses.The operators +, −, *, / can appear as both monadic (unary) and dyadic (binary) operators.Assignment (←) is also treated as a binary operator that returns the value assigned as its result.Write an unambiguous context free grammar for APL expressions containing the operands a, b,and c.Since the operators all have the same precedence, make sure your grammar gives the correctinterpretation to an expression like for example −a + b, which according to the above would be(unlike in conventional arithmetic and languages you have seen) −(a + b).2. In lecture an ambiguous grammar for if statments was shown, in which it was impossible to concludewhich of two nested if statments an else belonged to (the “dangling else” problem). Consider the twogrammars below. Does each grammar cure the dangling else problem by eliminating the ambiguity ofwhich if statement an else part is associated with? Assume in both cases that the only valid booleanexpression consists of the single boolean variable b, and the only valid statement consists of the terminalstring skip (obviously we could extend the grammars with more realistic productions, but it would justmake the problem longer and not really be germane).a. <stmtlist> ::= <stmtlist> ; <stmt> | <stmt><stmt> ::= <ifstmt> | skip<ifstmt> ::= if b then <stmtlist> <elsepart> end<elsepart> ::= else <stmtlist> | ²b. <stmt> ::= <ustmt> | <cstmt><ustmt> ::= skip | begin <stmtlist> end<cstmt> ::= if b then <ustmt> else <stmt> | if b then <ustmt><stmtlist> ::= <stmtlist> ; <stmt> | <stmt>Note that <ustmt> represents an unconditionally–executed statement, while <cstmt> representsa conditionally–executed statement.3. Context-free grammars cannot express all the syntactic restrictions normally placed on programminglanguages; for instance one example is that all function calls must have the same number of actualparameters as the number of formal parameters in the function’s definition. Consider a Scheme–likelanguage which permits a definition of a single function f followed by a single call to it (each with anarbitrary number of parameters) defined by the following grammar:1<program> ::= ( define f ( <formals> ) <body> ) ( f <actuals> )<formals> ::= <formals> <id> | ²<actuals> ::= <actuals> <expr> | ²<body> ::= ...<id> ::= ...<expr> ::= ...The expression (define f ( <formals> ) <body> ) is the definition of a function f with parameterlist <formals> and body <body>, while the following expression ( f <actuals> ) is a following callto f with actual parameters <actuals>. Productions for <body>, <id> and <expr> aren’t given; youshould assume that they derive the body of a function (a list of expressions), an identifier, and anexpression respectively. As above, this grammar generates small programs which consist of only a singledefinition of one function, followed by a single call to it.The problem with this grammar is that it derives programs (consisting of a function definition followedby a call) where the call to the function f has a different number of arguments than the definition ofthe function f has parameters. For example, you can verify that the following can be derived from thestart symbol <program>; this is a case where f is defined to have two formal parameters but is thencalled with only one actual parameter: ( define f ( <id> <d> ) <body> ) ( f <id> ).a. Develop another grammar for this language which enforces the restriction that a call to f musthave the same number of arguments as there are formal parameters in its definition. As above, youcan treat <body>, <id> and <expr> as nonterminals.b. Determine whether it is possible to generalize the approach in part (a) to a language in whicharbitrarily many calls to a procedure or function can occur. In other words, can your grammarfrom part (a) be adjusted to allow multiple calls to f following the definition of f, where each callhas the same number of actual parameters as the number of formal parameters in the definition off?4. Write unambiguous grammars for the following languages:a. { w | w ∈ {a, b}∗and w has an odd number of a’s and an odd number of b’s }b. { w | w ∈ {a, b}∗and w contains no substrings of the form ab }c. { w | w ∈ {a, b}∗and every pair of a’s in w is followed by at least one b
View Full Document
Unlocking...