CMSC 330 HOMEWORK EXERCISES #2

  1. Give unambiguous grammars for the following languages:
  1. {anbn  |  n ³ 0 and n is even}
  2. {aibjc2i+1dk  | i,j,k ³ 0}
  3. {a1a2 ... anan ... a2a1 | ai Î {a,b}, 1 £ i £ n}
  4. {ambnam+n | m ³ 0 and n ³ 1}
  5. {anbman-m | n ³ m ³ 0}
  6. All possible sequences of balanced parentheses
  7. {w | w Î {a,b}* and w has an odd number of a's and an odd number of b's}.
  8. {w | w Î {a,b}* and w has an equal number of a's and b's}
  9. {ambncpdq | m+n = p+q}
  10. {ambn | m ¹ n and m,n ³ 0}
  11. {w | w Î {a,b}* and w contains no substrings of the form ab}
  12. {w | w Î {a,b}* and every pair of a's is followed by at least one b}

 

  1. Write a grammar for the language
        {anbnambm | m,n ³ 1}  È   {anbmambn | m,n ³ 1 }
    If your grammar is ambiguous, prove that it is.

 

  1. Consider a grammar with the following productions:

                    <stmtlist>     ::=  <stmtlist> ; <stmt> | <stmt>
                    <stmt>         ::=  <if stmt> | skip
                    <if stmt>     ::=   if b then <stmtlist> <else part> fi
                    <else part>  ::=  else <stmtlist>  | e

    Do these productions cure the ``dangling'' else problem by eliminating the ambiguity of which <if stmt> the final <else part> is associated with?  Does the following grammar cure the problem?

                    <Stmt>        ::=  <UStmt> | <CStmt>
                    <UStmt>     ::=   skip | begin <StmtList> end
                    <CStmt>     ::=   if b then <UStmt> else <Stmt> | if b then <UStmt>
                    <StmtList>   ::=  <StmtList> ; <Stmt> | <Stmt>

 

  1. Grammars can be used to express concepts like associativity and precedence. For each of the following languages, give unambiguous grammars capturing the appropriate associativity and precedence.
  1. 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.
  2. Propositional calculus formulas having operators unary ~ and binary É , operands p and q, and parentheses.  The operators  should both be right associative and have their usual precedence.
  3. C++ expressions with identifiers a and b and operators ->,  *, and ++.  -> is a left associative binary operator,  * is a right associative unary operator, and  ++ is a right associative postfix operator.  The unary operators have precedence lower than the postfix expressions but higher than all binary operators. For example, the expression *a++ increments a before dereferencing it.

 

  1. Context-free grammars cannot express all the restrictions normally placed on programming languages, e.g., that all procedure statements have the same number of actual parameters as the procedure's definition had formals.  Consider a LISP-like language which permits a single procedure definition and procedure statement (each with an arbitrary number of parameters) defined by the following grammar:

                    <S>               ::=   (defun p ( <Formals> ) <Body} ) (p <Actuals>)
                    <Formals>     ::=  <Formals> <Id>  | e
                    <Actuals>      ::=  <Actuals> <Exp>  | e
                    <Body>         ::=  ...
                    <Id>              ::=  ...
                    <Exp>           ::=  ...

    Develop another grammar for this language that enforces the restriction that a call must have the same number of arguments as the declaration (you can treat <Body>, <Id> and <Exp> as non-terminals for this purpose).
    Is it possible to generalize this to a language in which arbitrarily many calls to a procedure can occur?