Write a parser as described below, in Prolog. Your parser is to use the grammar of Assignment 2. Some Prolog predicates, including a 0-argument test predicate, are given in the Assignment 5 test file that is available on the class web site. You should add your own definitions directly to a copy of this file.

Please make sure that the test predicate doesn't crash. This may involve giving some of your other predicates dummy definitions so that they will succeed.

You may hard-code the grammar into your parser. You needn't worry about symbol tables, scoping issues, calling nonfunctions, printing functions, or error handling. Note that this means that some of the test cases that did not have parses in earlier assignments will have parses in this one. It is permissible to have the parser simply fail if it is given illegal input.

As with the Prolog grammars shown in class, you should use recursive descent parsing, but you needn't use lookahead.

You may define any auxiliary predicates that you find useful. You may use my solutions to any of the earlier assignments if you want (with appropriate credit, of course).

For full credit, you should define a top-level parsing predicate program/2 whose first argument is a list of tokens (each represented as strings), and whose second argument is a Prolog structure that describes the syntactic structure of the program. The structure needn't be a parse tree. You may represent declarations, print statements and call statements by single variables as long you use substructures to make it clear what's being declared, printed, or called. You needn't represent type names or initial values. So for example, the first test input of Assignment 2 may be represented by the following nested structure:

For a penalty of 15 points, you may represent the second argument of program/2 as a list with the same information as specified above.

For a penalty of 40 points, you may have the parser simply succeed or fail. In this case you should change the test predicate to remove the second argument to program, and substitute its remaining argument for the argument to print.

For 15 points of extra credit, you may replace the print/1 predicate in the test program with a pretty_print/2 predicate, whose first argument is the value to be printed and whose second argument is a string (preferably of spaces) that determines how far to indent substructures. Structures and substructures that have structures as arguments should print all their arguments on separate lines. Other structures and substructures should be printed on single lines. So for example, with a second argument that's a string of two spaces, the structure above would be pretty printed as

f1(
  subblocks(
    h(
      subblocks
      declare(x, w)
      call
      print(x, y, w)
    )
    g(
      subblocks
      declare(y, v)
      call(h)
      print(x, y, v)
    )
  )
  declare(x, y)
  call(g, h)
  print(x, y)
)