Dévai Gergely @ ELTE

1. What is the input and output of the lexical analyser (lexer)?
2. Which of the above inputs match the [ab]*(ab)+ regular expression?
   • a, b, ab, ba, aab, bab, baba, ababaab
3. Given the following token definitions, how will the lexer tokenize the if else ifelse apple text?

   if      cout << "IF";
   else    cout << "ELSE";
   [a-z]+  cout << "IDENTIFIER";
   " "+    cout << "SPACES"

4. Write down the steps of the derivation of aaabbb (S ⇒ … ⇒ aaabbb) using the grammar below!
   • S → ab | aSb
5. What is the difference between top-down and bottom-up parsing?
6. Write down the function of a recursive descent parser corresponding to the A → aB | c rules!
7. What are the two operations that an LR parser can perform?
8. What is a symbol table used for?
9. Write a 32-bit NASM assembly program that swaps the contents of the dword [a] and dword [b] memory locations!
10. Write a code generation rule for an assignment operation of the form assignment → variable := expression!

Extend the While language with a new type, called time. An example:

program exam
  time t;
  integer i;
begin
  t := 09:52;
  i := hour(t) + minute(10:02);
  write(i);
end

• Literals of type time should be of the form HH:MM, where the two digits of the hour and minute are arbitrary decimal digits. (It is OK to accept impossible time literals like 99:99, but you are free to create smart regular expressions that allow literals only from the 00:00 - 23:59 range.)
• It should be possible to declare variables of type time.
• Assignement operations should also work for time-typed variables.
• hour and minute should get a time parameter and return integers, the hour and minute respectively.
• It is not possible to input or output time values!

Tasks:

• Download and see the test files.
• Grade 2: Extend the lexer with the necessary regular expressions!
• Grade 3: Extend the parser with the new rules needed!
• Grade 4: Extend the type checking with time-related functionality!
• Grade 5: Extend the code generation to support the new type!
  • Hint: Store type values as integers, using the encoding 100*HH + MM, or store the hours and minutes in two different bytes.