Replacing parser technology
===========================

Your project is to replace Pleasant's recursive descent parser (found
in the accompanying tarfile in language-COP4020/compiler/parser.c)
with a parser generated by the Lemon parser generator.

While the canonical reference is the recursive descent parser in the
tar file distributed with this assignment (it's in
language-COP4020/compiler/parser.c), a rough BNF-like grammar for
Pleasant is also given below:



   "BNF-like" grammar for Pleasant
   ===============================

   <program> ::= "main" <declarations_section> <program_section> <functions_section>

   <module> ::=  <exports> | <imports_section> <declarations_section> <functions_section>


   <exports_section> ::= "exports" "{" <function_declaration_list> "}"

   <imports_section> ::= "imports" "{" <module_list> "}"

   <declarations_section> ::= "declarations" "{" <function_declaration_list> "}"

   <program_section> ::= "program" <statement_block>

   <functions_section> ::= "functions "{" <function_list> "}"


   <statement_block> ::= "{" <statement_list> "}"

   <statement_list> ::= ( <> | <variable_declaration> ";" 
                             | <statement_block> 
                             | <if_else_statement> 
                             | <while_statement> 
                             | <function_call> ";" 
                             | <assignment> ) <statement_list>

   <variable_declaration> ::= "var" <assignment_statement>

   <assignment_statement> ::= (IDENTIFIER | identifier_list) "=" <expression> ";" 

   <if_else_statement> ::= "if" "(" <expression> ")" <statement_block> "else" <statement_block>

   <while_statement> ::= "while" "(" <expression> ")" <statement_block>

   <function_call> ::= IDENTIFIER <argument_list> 


   <expression> ::= NUMBER | STRING | IDENTIFIER | <function_call>

   <argument_list> ::= <> | "(" ( <expression> , )* ")" <expression>

   <identifier_list> ::= <> | ( IDENTIFIER , )* IDENTIFIER



   <module_list> ::= ( IDENTIFIER ";" )*


   <function_declaration_list> ::= ( <function_declaration> )*

   <function_declaration> ::= "(" <identifier_list> ")" "=" IDENTIFIER "(" <identifier_list> ")" ";"

   <function_list>  ::= ( <function> )*

   <function> ::= "(" <identifier_list> ")" "=" IDENTIFIER "(" <identifier_list> ")" <statement_block>



Remember, the above grammar is only a rough one in convenient format,
and that the reference version is the recursive descent parser.c, not
the above approximate BNF.

Your parser will need to call the existing lexer, which provides two
external variables, current_token and next_token.

It also provides three functions of interest here:

   must_match(char *regex) --> attempts to match the current token
   against the regular expression; if it succeeds, it consumes the
   token advance()s current_token and next_token

   try_match(char *regex) --> attempts to match the current token 
   against the regular expresssion

   advance() --> consumes the current token and advances the
   current_token and the next_token variables

You should not need to use the first two (matching is something that your generated
parser will do, instead of the explicit matching needed by a recursive descent
parser), but you will need to use the advance() function to get the next token.

Your semantic rules should resemble those in the recursive parser; the most important
thing to note is that your attributes are all synthetic (i.e., this is an S-attributed
grammar), and that you do not have to build a syntax tree --- this language
is simple enough for a simple emit protocol. The items understood by the
emitter are:

    assign(n) --> copy the variable at the top of the expression stack 
                  to the nth item on the activation stack

    allocate_a(n) --> allocate n new variables on the activation stack
    allocate_e(n) --> allocate n new anonymous variables on the evaluation stack
    allocate_e_in(n) --> allocate n new "in" items on the evaluation stack
    allocate_e_out(n) --> allocate n new "out" variables on the evaluation stack
    allocate_e_constant(x) --> allocate a new anonymous constant on the stack

    deallocate_a(n) --> remove the top n variables from the activation stack
    deallocate_e(n) --> remove the top n variables from the evaluation stack

    copy_e_a(n) --> copy the nth variable in the activation to the evaluation stack
    copy_e_e(n,m) --> copy the mth variable (source variable) to the nth variable (target) on the evaluation stack
    dup_e(n) --> push a new copy of the nth variable on the evaluation stack

    function_invocation(name) --> set up a call to the function 'name'
    function_prologue(name) --> set up a new function (does nothing for now)
    function_epilogue(name) --> closes out the definition of a function

    boolean_assert(fail) --> checks the value of the variable at the top of the
                             evaluation stack; if evaluates to false, then go to
                             the label "fail"
    boolean_assert_failed(fail) --> sets up the failure branch for a boolean_assert
    goto_(name) --> unconditional branch to label 'name' 
    label(name) --> output the label 'name'


You do not have to use the Judy trees that are used in the source
code; they are there only to provide a convenient method for keeping
state about all of the functions found and their status, but with the
current runtime environment, this isn't so useful.

You know that you have completed this correctly when you have written
a parser.y file that lemon can turn into a parser.c that replaces
the current parser.c, and that all of the test programs in the
test suite successfully compile and run.

Your submission: you should turn in only the required file, and it should have the 
filename "parser.lemon" (please do not turn in the entire tar file.)


-------- OPTION B ---------

NEW on 2017-12-04:

OPTION B:

You can submit just the grammar rules without any semantic rules in
your "parser.lemon" file; if the grammar does parse the test files,
then you will get a B on this assignment.

Please put "OPTION B" in a comment near the top of the
"parser.lemon" file if you want to be graded on this basis, and make
sure that there are no semantics or attributes in the grammar file
that you turn in.