/*
      These predicates define a parser for the grammar with 
    start symbol <program> and productions 
        <program> ::= <block>
        <block> ::= { <block-name> <declaration>* <block>* 
                    <call-statement>* <print-statement>* }
        <call-statement> ::= call <variable-name> ;
        <print-statement> ::= print <variable-name> ;
        <declaration> ::= 
           declare <variable-name> <type-name> <literal>;
        <variable-name> ::= <letter-initial-token>
        <block-name> ::= <letter-initial-token>
        <type-name> ::= <letter-initial-token>
        <literal> ::= <digit-initial-token>

    The top-level predicate is program/2.  It associates
  a list of tokens (each represented as a Prolog string)
  with a nested structure similar to a parse tree
  that represents the syntactic organization of the program  

    Recursive descent parsing is used, with a difference
  list representation for the input string.  No lookahead
  is used.

    A predicate test/0 is provided that exercises the 
  program/2 predicate on all lists of strings that appear
  as arguments of the predicate p/1.

*/


% A list of token strings X parses as a program with 
%   representation Rep if the difference list X/[]
%   that corresponds to X represents a block in the
%   grammar.  

program(X,Rep) :- 
  block(X/[],Rep).


% This predicate finds a block at the beginning of
%   unconsumed input X, leaving unconsumed input Y.
% The representation of the block is given as Struct.
 
block(X/Y, Struct) :- 
  left_brace(X/X1),
  block_name(X1/X2, NameString),
  declarations(X2/X3, Decls),
  blocks(X3/X4, Blocks),
  calls(X4/X5, Calls),
  prints(X5/X6, Prints),
  right_brace(X6/Y),
  Decl_struct =.. [declare | Decls],
  Call_struct =.. [call | Calls],
  Print_struct =.. [print | Prints],
  Block_struct =.. [subblocks | Blocks],
  string_to_atom(NameString, Name),
  Struct =.. 
    [Name, Block_struct, Decl_struct, Call_struct, Print_struct].


% This predicate finds a sequence of declarations
%   at the beginning of unconsumed input X, 
%   leaving unconsumed input Y.
% The second argument is a list of the representations
%   (as variable names) of the declarations.
 
declarations(X/X, []).

declarations(X/Y, [Var | VarList]) :-
  declaration(X/X1, Var),
  declarations(X1/Y, VarList).


% This predicate finds a declaration at the beginning of
%   unconsumed input X, leaving unconsumed input Y.
% The representation of the declaration is given as Var,
%   which is simply the name of the variable being
%   declared.
   
declaration(X/Y, Var) :-
  declare_literal(X/X1),
  variable(X1/X2, Var),
  type(X2/X3),
  initial_value(X3/X4),
  semicolon(X4/Y).


% This predicate finds a sequence of blocks
%   at the beginning of unconsumed input X, 
%   leaving unconsumed input Y.
% The second argument is a list of the representations
%   (as structures) of the declarations.
 
blocks(X/X,[]).

blocks(X/Y, [Rep|Reps]) :-
  block(X/X1, Rep),
  blocks(X1/Y, Reps).


% This predicate finds a sequence of calls
%   at the beginning of unconsumed input X, 
%   leaving unconsumed input Y.
% The second argument is a list of the representations
%   (as names of the functions being called)
%   of the statements.

calls(X/X, []).

calls(X/Y, [Var | VarList]) :-
  call_statement(X/X1, Var),
  calls(X1/Y, VarList).


% This predicate finds a call statement at the beginning of
%   unconsumed input X, leaving unconsumed input Y.
% The representation of the statement is given as Var,
%   which is simply the name of the function being
%   called.
   
call_statement(X/Y, V) :-
  call_literal(X/X1),
  variable(X1/X2, V),
  semicolon(X2/Y).


% This predicate finds a sequence of print statements
%   at the beginning of unconsumed input X, 
%   leaving unconsumed input Y.
% The second argument is a list of the representations
%   (as names of the variables being printed) of the 
%   statements.
 
prints(X/X, []).

prints(X/Y, [Var | VarList]) :-
  print_statement(X/X1, Var),
  prints(X1/Y, VarList).


% This predicate finds a print statement at the beginning of
%   unconsumed input X, leaving unconsumed input Y.
% The representation of the statement is given as Var,
%   which is simply the name of the variable being
%   called.
   
print_statement(X/Y, Var) :-
  print_literal(X/X1),
  variable(X1/X2, Var),
  semicolon(X2/Y).



% Block names, variable names, type names, 
%   and initial values are recognized by
%   their initial characters.
% Type names have no representation;
%   the other three are represented simply
%   by the names or values.

block_name([Name|X]/X, Name) :-
  letter_initial(Name).

variable([Name|X]/X, Name) :-
  letter_initial(Name).

type([Name|X]/X) :-
  letter_initial(Name).

initial_value([Value|X]/X) :-
  digit_initial(Value).


% Predicates to recognize strings
%   that begin with letters or digits

letter_initial(String) :-
  string_to_list(String,[Char|_]),
  letter(Char).

digit_initial(String) :-
  string_to_list(String,[Char|_]),
  digit(Char).


% These predicates check for keyword tokens
%   at the beginning of the unconsumed input.
% There is no representation associated with 
%   any of the keywords.

left_brace(['{'|X]/X).
right_brace(['}'|X]/X).
semicolon([';'|X]/X).
declare_literal(['declare'|X]/X).
call_literal(['call'|X]/X).
print_literal(['print'|X]/X).


% predicates to recognize particular
%   types of characters.

letter(Char) :-
  char_type(Char, alpha).

digit(Char) :-
  char_type(Char, digit).


% A pretty_print predicate that takes a structure
%    to be pretty printed, and a string
%    (preferably consisting of a small number of spaces)
%    to be used for indenting.
% If a structure or substructure has any arguments
%   that are structures, then these arguments are printed
%   on separate lines.  
% Otherwise the entire structure or substructure is printed
%   on a single line

% Initially there is no indenting 
%   (as represented by the 2nd argument to pretty_print/3
%   The 3rd argument is the indent string given by
%   the 2nd argument to pretty_print/2, but represented
%   as a list of characters.

pretty_print(Struct, IncrementString) :-
  string_to_list(IncrementString, IncrementList),
  pretty_print(Struct, [], IncrementList).


% This clause handles structures with substructures as
%   arguments

pretty_print(Struct, Indent, Increment) :-
  Struct =.. [Functor | Args ],
  has_compound_member(Args),!,  
  string_to_list(IndentString, Indent),
  print(IndentString), print(Functor), print('('), nl,
  append(Indent, Increment, NewIndent),
  pretty_print_args(Args,NewIndent,Increment),
  print(IndentString), print(')'), nl.


% This clause handles other structures

pretty_print(Struct, Indent, _) :-
  string_to_list(IndentString, Indent),
  print(IndentString), print(Struct), nl.


% Determines whether a list has a member that's a structure
% It succeeds just once.

has_compound_member([A|_]) :-
  compound(A),!.

has_compound_member([_|T]) :-
  has_compound_member(T).


% Pretty prints a given list of arguments, given also
%   the current level of indenting (represented as a 
%   list of characters)
%   and the additional indenting for each level
%     (also represented as a list of characters)

pretty_print_args([],_,_).

pretty_print_args([Arg|Tail],Indent,Increment) :-
  pretty_print(Arg, Indent, Increment),
  pretty_print_args(Tail, Indent, Increment).





% The test predicate.
% This version assumes a pretty_print/2 predicate.

test :-
  p(X), program(X,Y), pretty_print(Y,'  '),
  nl,fail.




% Lists of tokens to test as programs.

p(['{', 'f1', 'declare', 'x', 'int', '1', ';',
             'declare', 'y', 'real', '6', ';',
             '{', 'h',  
               'declare', 'x', 'real', '25', ';',
               'declare', 'w', 'real', '26', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               'print', 'w', ';',
             '}',
             '{', 'g',
               'declare', 'y', 'real', '15', ';',
               'declare', 'v', 'real', '16', ';',
               'call', 'h', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               'print', 'v', ';',
              '}',
              'call', 'g', ';',
              'call', 'h', ';',
              'print', 'x', ';',
              'print', 'y', ';',
              '}']).

  % syntactically correct program 
  
p([ '{', 'f2', 'declare', 'x', 'int', '2', ';',
              'declare', 'y', 'real', '6', ';',
               '{', 'h',
                  'declare', 'x', 'real', '25', ';',
                  'declare', 'w', 'real', '26', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               '{', 'g',
                  'declare', 'y', 'real', '15', ';',
                  'declare', 'v', 'real', '16', ';',
                  'call', 'h', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'v', ';',
               '}',
               'call', 'g', ';',
               'call', 'h', ';',
               'print', 'x', ';',
               'print', 'y', ';',
      '}']).








  % syntactically correct program 
  
      p(['{', 'f3',                 
                'declare', 'x', 'int', '3', ';',
                'declare', 'y', 'real', '4', ';',
               '{', 'g',
                  'declare', 'x', 'real', '5', ';',
                  'declare', 'z', 'real', '6', ';',
                  'call', 'f', ';',
                  'call', 'g', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'z', ';',
                '}',
                'print', 'x', ';',
                'print', 'y', ';',
         '}']).                                     




  % syntactically, correct program

           p(['{', 'f4',                 
                'declare', 'x', 'int', '4', ';',
                'declare', 'y', 'real', '8', ';',
                'declare', 'w', 'int', '9', ';',
               '{', 'g',
                  'declare', 'x', 'real', '17', ';', 
                  'declare', 'z', 'real', '18', ';',
                  '{', 'h',
                     'declare', 'y', 'int', '27', ';',
                     'declare', 'z', 'real', '28', ';',
                     'print', 'w', ';',
                     'print', 'x', ';',
                     'print', 'y', ';',
                     'print', 'z', ';',
                  '}',
                  'call', 'h', ';',
                  'print', 'w', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'z', ';',
                '}',
                'call', 'g', ';',
                'print', 'x', ';',
                'print', 'y', ';',
                'print', 'w', ';',
             '}']).                                     


  % inaccessible variable in g

           p(['{', 'f5',                 
                'declare', 'x', 'int', '5', ';',
                'declare', 'y', 'real', '6', ';',
               '{', 'h',
                  'declare', 'x', 'real', '25', ';',
                  'declare', 'w', 'real', '26', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               '{', 'g',
                  'declare', 'y', 'real', '15', ';',
                  'declare', 'v', 'real', '16', ';',
                  'call', 'h', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               'call', 'g', ';',
               'call', 'h', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               '}']).


  % inaccessible function in f

           p(['{', 'f6',                 
                'declare', 'x', 'int', '6', ';',
                'declare', 'y', 'real', '8', ';',
                'declare', 'w', 'int', '9', ';',
               '{', 'g',
                  'declare', 'x', 'real', '17', ';',
                  'declare', 'z', 'real', '18', ';',
                  '{', 'h',
                     'declare', 'y', 'int', '27', ';',
                     'declare', 'z', 'real', '28', ';',
                     'print', 'w', ';',
                     'print', 'x', ';',
                     'print', 'y', ';',
                     'print', 'z', ';',
                  '}',
                  'call', 'h', ';',
                  'print', 'w', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'z', ';',
                '}',
                'call', 'h', ';',
                'print', 'x', ';',
                'print', 'y', ';',
                'print', 'w', ';',
             '}']).                                    

  
  % no initial value for variable in 'g',
  
           p(['{', 'f7',                 
                'declare', 'x', 'int', '7', ';',
                'declare', 'y', 'real', '6', ';',
               '{', 'h',
                  'declare', 'x', 'real', '25', ';',
                  'declare', 'w', 'real', '26',';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               '{', 'g',
                  'declare', 'y', 'real', ';',
                  'declare', 'v', 'real', '16', ';',
                  'call', 'h', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'v', ';',
               '}',
               'call', 'g', ';',
               'call', 'h', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               '}']).







  % attempt to 'call', a non'f',unction 
           p(['{', 'f8',                 
                'declare', 'x', 'int', '8', ';',
                'declare', 'y', 'real', '81', ';',
               '{', 'h',
                  'declare', 'x', 'real', '18', ';',
                  'declare', 'w', 'real', '181', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               '{', 'g',
                  'declare', 'y', 'real', '28', ';',
                  'declare', 'v', 'real', '281', ';',
                  'call', 'h', ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'v', ';',
               '}',
               'call', 'g', ';',
               'call', 'x', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               '}']).




  % attempt to 'print', a 'f',unction 
  
          p([ '{', 'f9',                 
                'declare', 'x', 'int', '9', ';',
                'declare', 'y', 'real', '8', ';',
               '{', 'h',
                  'declare', 'x', 'real', '9',  ';',
                  'declare', 'w', 'real', '9',  ';',
                  'print', 'x', ';',
                  'print', 'y', ';',
                  'print', 'w', ';',
               '}',
               '{', 'g',
                  'declare', 'y', 'real', '9',  ';',
                  'declare', 'v', 'real', '9',  ';',
                  'call', 'h', ';',
                  'print', 'x', ';',
                  'print', 'h', ';',
                  'print', 'v', ';',
               '}',
               'call', 'g', ';',
               'call', 'h', ';',
               'print', 'x', ';',
               'print', 'y', ';',
               '}']).








%  analogs to test cases with syntatic errors from Assignment 1
   

  % bad variable 
           p(['{', 'f10',                 
                'declare', 'x', 'int', '10', ';',
                'declare', 'y', 'real', '11', ';',
               '{', 'g',
                  'declare', 'x', 'real', '21', ';',
                  'declare', '#', 'real', '22', ';',
                  'call', 'f', ';',
                  'call', 'g', ';',
                '}',
                'print', 'x', ';',
             '}']).                                     



  % bad declaration
           p(['{', 'f11',                 
                'declare', 'x', 'int', '11',  ';',
                'declare', 'y', 'real', '12',  ';',
               '{', 'g',
                  'declare', 'x', 'real', '21',  ';',
                  'declare', 'z', '22',  ';',
                  'call', 'f', ';',
                  'call', 'g', ';',
                '}',
                'print', 'x', ';',
             '}']).                                     



  % duplicate identifier  
           p(['{', 'f12',                 
                'declare', 'x', 'int', '12', ';',
                'declare', 'y', 'real', '13', ';',
               '{', 'g',
                  'declare', 'x', 'real', '21', ';',
                  'declare', 'z', 'real', '22', ';',
                  'declare', 'x', 'real', '23', ';',
                  'call', 'f', ';',
                  'call', 'g', ';',
                '}',
                'print', 'x', ';',
             '}']).                                     



  % duplicate identifier  
          p([ '{', 'f13',                 
                'declare', 'x', 'int', '13',  ';',
                'declare', 'y', 'real', '14',  ';',
               '{', 'y',
                  'declare', 'x', 'real', '21',  ';',
                  'declare', 'z', 'real', '23',  ';',
                  'call', 'f', ';',
                  'call', 'g', ';',
                '}',
                'print', 'x', ';',
             '}']).                                     
  



  
  % pro'g',ram must be'g',in 'w',it'h', le'f',t brace
              p(['f14',                 
	              'declare', 'x', 'int', '14',  ';',
	              'declare', 'y', 'real', '15',  ';',
	             '{', 'g',
	                'declare', 'x', 'real', '21',  ';',
	                'declare', 'z', 'real', '24',  ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              '}',
	              'print', 'x', ';',
	           '}']).                                   
  




  % g should not be recognized as a block 

             p(['{', 'f15',                 
	              'declare', 'x', 'int', '15', ';',
	              'declare', 'y', 'real', '16', ';',
	              'g',
	                'declare', 'x', 'real', '21', ';',
	                'declare', 'z', 'real', '25', ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              '}',
	              'print', 'x', ';',
	           '}']).                                   
  



  % bad statement
             p(['{', 'f16',                 
	              'declare', 'x', 'int', '16', ';',
	              'declare', 'y', 'real', '17', ';',
	             '{', 'g',
	                'declare', 'x', 'real', '21', ';',
	                'declare', 'z', 'real', '26', ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              '}',
	              '<<', 'x', ';',
	           '}']).                                   
  



  % missing right brace
            p(['{', 'f17',                 
	              'declare', 'x', 'int', '17', ';',
	              'declare', 'y', 'real', '18', ';',
	             '{', 'g',
	                'declare', 'x', 'real', '21', ';',
	                'declare', 'z', 'real', '27', ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              'print', 'x', ';',
	           '}']).                                   
  



  % program must end with right brace

            p(['{', 'f18',                 
	              'declare', 'x', 'int', '18', ';', 
	              'declare', 'y', 'real', '19', ';',
	             '{', 'g',
	                'declare', 'x', 'real', '21', ';',
	                'declare', 'z', 'real', '28', ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              '}',
	              'print', 'x', ';']).                        
    



  
  % missing semicolon in declaration
            p([ '{', 'f19',                 
	              'declare', 'x', 'int', '19', ';',
	              'declare', 'y', 'real', '20',
	             '{', 'g',
	                'declare', 'x', 'real', '21', ';',
	                'declare', 'z', 'real', '29', ';',
	                'call', 'f', ';',
	                'call', 'g', ';',
	              '}',
	              'print', 'x', ';',
	           '}']).                                   
  



  
  % missing semicolon in statement

           p([ '{', 'f20',                 
	              'declare', 'x', 'int', '20', ';',
	              'declare', 'y', 'real', '21', ';',
	             '{', 'g',
	                'declare', 'x', 'real', '22', ';',
	                'declare', 'z', 'real', '23', ';',
	                'call', 'f', ';',
	                'call', 'g', 
	              '}',
	              'print', 'x', ';',
	           '}']).