Algonquin College - CST8152 - Compilers

Midterm #1 - February 17, 1998

Test Duration - 50 Minutes

Professor - Ian D. Allen

Identification

      Your name: Ian D. Allen Please Print Clearly  
      Your student ID:      

Instructions

Marking Scheme

      This Midterm #1 is marked out of 50. That works out to one mark per minute. Use the number of marks to get a rough idea of how many minutes you should spend on a question, e.g. 10 marks means no more than 10 minutes:

      Q-1 13 marks

      Q-2 10 marks

      Q-3 6 marks

      Q-4 15 marks

      Q-5 6 marks

       

      Marks for each question are listed beside each question.

      Midterms and class quizzes count together for 30% of your final grade.

      The final exam is worth 30% of your final grade.

       

13 marks

Print T in the box if the statement is True; print F if it is False. Correct answers are worth ½ mark each. No answer is worth zero marks. Warning! Incorrect answers are worth minus ½ mark (-0.5) each.
(0|1)*01(0|1)* is a regular expression that matches any string made up of zeroes and ones where a zero precedes a one.

T
(00)+ is a regular expression that matches only non-empty strings made up of an even number of zeroes.

T
(000)+ is a regular expression that matches only non-empty strings made up of an odd number of zeroes.

F
(111)* is a regular expression that matches only strings made up of an odd number of ones, including the empty string.

F
A DFA must have exactly one final (accepting) state.

F
A regular expression is a type of pattern used to classify lexemes.

T
To change between two states in a DFA, you must read exactly one character.

T
Any Regular Expression using the ‘+’ can be rewritten to use the ‘?’ instead.

F
DFA Transition Tables are indexed with current state and next state.

F
Finite State Machines can have an unlimited number of states.

F
Finite State Machines can have two edges leaving the same state labelled with the same label (character).

T
Lexical analysis organizes tokens into unambiguous trees.

F
Lexical analysis is recursive to be able to handle nested parentheses.

F
Non-terminal symbols appear on the left-hand-side of grammar productions.

T
Non-terminal symbols in a grammar correspond to tokens, not lexemes.

F
Regular expression (p|q)? matches the same strings as q?|p?

T
Regular expression (ab)?(ab)* matches the same strings as (ab)*

T
Regular expression (rt)*|(uv)* matches the same strings as (uv|rt)*

F
Regular expression x*y* matches the same strings as (xy)*

F
Regular expressions can not be used to match strings of balanced parentheses.

T
Right-hand-sides of grammar productions contain only terminal symbols.

F
Scanners don’t know anything about the grammar of a language.

T
Syntax analysis handles type checking and type conversions, e.g. int to float.

F
Terminal symbols in a grammar correspond to tokens, not lexemes.

T
The leaves of a parse tree contain both terminals and non-terminals.

F
You can change state in a DFA without reading any input character.

F

 

10 marks

        Given the following regular expression describing a set of strings:

        a(a|c)*bcb(b+c)?a

        Draw a DFA transition diagram that matches exactly this expression (and nothing else):

6 marks

        Put a check mark beside whichever of the following are valid strings as defined by the expression and transition diagram from the preceding question:.

        abcba T bbcba F abbcba F
        abcbaa F aabcbbca T abcbbcca F
        abcbba F accbcbbbbca T aabcbca F

         

         

15 marks

        The state-diagram of the FSM shown below was designed to recognize both unsigned integer and float numeric constants. It has three accepting states. Fill in the next-state table from the given diagram:

        '.'

        '+' | '-'

        'E'

        {digit}

        {OTHER}

        START

        		 1 ERR ERR 5 ERR

        1

        		 FLOAT FLOAT 2 1 FLOAT

        2

        		 JUNK 3 JUNK 4 JUNK

        3

        		 JUNK JUNK JUNK 4 JUNK

        4

        		 FLOAT FLOAT FLOAT 4 FLOAT

        5

        		 1 INT INT 5 INT

         

6 marks

Write underneath the diagram the regular expression corresponding to the following state diagram:

01*2(1|33(2|1)*1) or 01*2(33(2|1)*)?1

_____________________________________

 

This state diagram is deterministic (DFA): ____ True ____ False FALSE (two 1 labels)