CS 434 Exam 1Solution

Spring 2004

  1. Show this grammar is ambiguous by drawing 3 distinct parse trees for the string abc.

S → TU | VW | X

T → aTb | 

U → cU | 

V → aV | 

W → bWc | 

X → aXc | Y

Y → bY | 

  1. List every string with length exactly 6 that is generated by the grammar of problem 1.

aaaaaa / bbbbbb / cccccc / aaabbb / aaaccc
aaaabc / abbbbc / abcccc / bbbccc / aabbcc
  1. Construct a context-free grammar that generates arithmetic expressions using operators +, –, *, /withthe precedence levels and associativities as specified below. Assume that arbitrary operands are denoted by id, so this string could be generated:id+(id–id*id)/id

Operator / Precedence / Associativity
+ / 1st (highest) / right
– / 2nd / left
* / 3rd / right
/ / 4th (lowest) / left

S → S/T | T

T → U*T | U

U → U–V | V

V → W+V | W

W → (S) | id

  1. List every string with length at most 5 that is accepted by this finite-state machine:
xy / xxxy / xxyx / xyxx / yxxx
yx / yyyx / yyxy / yxyy / xyyy
  1. Draw a deterministic finite-state machine that accepts strings over alphabet {0,1,2}such that the difference (number of 0’s minus number of 1’s) is not a multiple of 3. Example: 020120120 should be accepted because (4 –2) is not a multiple of 3. Hint: this DFSM can be drawn with as few as 3 states.
  1. List every string with length at most 4 that is generated by this regular expression: (87*9 | 97*8)+

89 / 879 / 8779 / 8989 / 8998
98 / 978 / 9778 / 9898 / 9889
  1. Construct a regular expression that generates the strings over alphabet {8, 9} that do not contain substring 88 and also do not contain substring 99.

(89)* | (89)*8 | (98)* | (98)*9

  1. Suppose you have downloaded from the Internet a de-compiler that converts SPARC machine code into C++, and this de-compiler is written in SPARC machine code. Suppose you also have access to aSPARC machine. Draw a tombstone diagram that shows how to construct a de-compiler from SPARC to C++ that is written in C++.

  1. Identify a syntax error, a scope error, and a type error in this C++ code. Briefly but precisely describe each error.

class C {

int x;

public:

C (int b) { x=b; }

C * f ( ) { return x; }// Type error: ‘x’ is int, not C*

int g ( ) { return b; }// Scope error: ‘b’ is undefined

void h ( )// Syntax error: missing ‘;’ or ‘{}’

};

  1. First explain a restriction in the C++ language that seems to indicate that a single-pass compiler will be used. Next explain a feature of the C++ language that appears to indicate that a multi-pass compiler must be used. Briefly justify your answers.

Single-pass: Most names must be declared before they can be used.

–C++ ordinary functions must be declared before they can be called.

–C++ classes must be declared before they can be used as type names.

Multi-pass: Some names can be used before they are declared (forward references).

–C++ instance variables can be accessed before they are declared.

– C++ member functions can be invoked before they are declared.