CSE 3341 Simple problems

Problem 1

Consider the following grammar discussed in class, derived from Section 6.4 of the C specification. 

identifier -> nondigit | identifier nondigit | identifier digit

nondigit ->  _ | a | ... | Z

digit ->  0 | ... | 9

Part 1. Does the string _ _ constitute a valid identifier, according to this grammar? If so, show one possible derivation of this string. If not, explain why not.

Part 2. Write a regular expression that describes the language defined by this grammar.

Problem 2

Consider the following grammar discussed in class (shown using BNF):

<integer> ::= <digit> | <digit> <integer> 

<digit> ::= 0 | ... | 9

 The grammar describes integer literals (i.e., integer constants in the code). However, in some languages, such literals should not start with 0. For example, in C, a decimal literal cannot start with 0 because only octal literals start with 0 (so, in C literal 53 has the value 10*5+3 = 53, but literal 053 is octal and has the value 8*5+3 = 43). 

Define a modified grammar that disallows integer literals that start with 0. Feel free to add new nonterminals and productions, or to modify existing productions. 

Problem 3

Consider the following ambiguous context-free grammar: 

<expr> ::= <expr> + <expr> | <expr> * <expr> |  ident

Show all possible parse trees for string x * y + z * w