NUIMCrest SE307 - Computational Complexity Theory
Department of Computer Science
National University of Ireland, Maynooth

T Naughton, NUIM
Back to SE307 home

Lab 4 - Mechanical reasoning about machines

In this lab you will begin work on the concept of using a machine to analyse another machine.

Problem 4.A Construct a machine that takes a C++ function as input and checks if all variables that appear in the code are declared at the variable initialisation section of the function. The machine outputs a `T' if all variables have been declared, and an `F' otherwise. All input programs will have a restricted structure: each one is a word in the language defined by the following context-free grammar.


  • The Input to each machine has the form
          void inputfn(void) { DeclarationList StatementList }
  • A DeclarationList is either a single Declaration, or a Declaration followed by another DeclarationList.
  • Each Declaration is
          int Var = 0;
  • A StatementList is either a single Statement, or a Statement followed by another StatementList.
  • Each Statement is one of
          Var = 0;
          Var++;
          while (Var < Var) { StatementList }
          cout << Var;
  • Each Var is a word over the alphabet {a, b}.


    For the purists among you, here is the grammar in Backus normal form (the green symbols denote nonterminals and black symbols denote terminals).


    F -> voidinputfn(void){NL}
    N -> D | DN
    D -> intV=0;
    L -> S | SL
    S -> V=0; | V++; | while(V<V){L} | cout<<V;
    V -> C | CV
    C -> a | b


    As can be seen from the grammar, variables will only be declared at the beginning of the function and are always initialised to zero. Blank spaces and control characters (tab, newline) should be ignored by your machine. You may assume that (other than possibly containing undeclared variables) all inputs will be syntactically correct programs -- your machine will not need to deal with incorrectly structured programs. The following is an example of a word from the language defined above.


    void inputfn(void) {
      int a = 0;
      int b = 0;
      int aa = 0;

      a++;
      a++;
      b = 0;
      while (aa < a) {
        b++;
        aa++;
      }
      
      cout << a;
    }


    When this word is passed as input to your machine, your machine should respond with a `T'. Here is another word from the language.


    void inputfn(void) {
      int aa = 0;
      aa++;
      cout << a;
    }


    Your machine should output an `F' when passed this word as input. You may use any programming language (TM, RAM, C, Java, Perl, ...) to build your machine. As a guide, I have included the following files:

  • MachineBase is a virtual C++ class for a machine that takes care of all of the technical details of reading the code of an input machine, but doesn't actually do anything with it,
  • MachineFourA is an example machine derived from MachineBase that "pretty prints" the input machine's code,
  • lab4a.cpp is a driver program that creates a MachineFourA object,
  • a few sample inputs.

    If you wish to use this code to solve the problem then you could simply modify the MachineFourA class. This will involve (possibly) adding data mambers to MachineFourA and appropriately modifying its ProcessDeclaration() and ProcessStatement() member functions.

    End of sheet