JavaScript代写：COMP302 AST

作业比较另类，需要接着上次的AST生成器用JavaScript继续写，这次是写解析器。

Requirement

In this assignment you will develop the code to evaluate the WML language parsed in the previous assignment. You will therefore need an AST generator. You may use your code from assignment 2, or base this assignment on the code provided as a solution to assignment 2, available in mycourses.

Again, a(n optional) framework you can use to test your evaluator code is provided through the files wml.html and wml.js , or you may adapt the evaluator code written by some of your TAs and linked in MyCourses.

Your code must run without error or modification in current versions of Firefox or Chrome: restrict yourself to basic JavaScript idioms defined in the ECMA standard 5.1. Be sure to respect precise naming, input, and output requirements.

All code should be well-commented, in a professional style, with appropriate variables names, indenting (uses spaces and avoid tabs), etc. The onus is on you to ensure your code is clear and readable. Marks will be very generously deducted for bad style or lack of clarity.

Question 1

Develop code to represent environments. Environments are objects, with a (probabilistically) unique name as a floating point number given by Math.random() , a set of bindings, and a parent environment (object, not name).

{ name: ,
  bindings: { ... },
  parent: }

You should have have 2 functions associated with this structure,

• createEnv(parent), which creates a new environment.
• lookup(name,env), which returns the first binding value for binding key name . This function searches through the given environment and then parents, returning null if no binding is found.

Question 2

Develop functionality to evaluate the AST generated from your solution to assignment 2. You should define a set of functions for processing the different AST nodes, each of which received an AST node and an environment, and returns a string.

At the top-level you should define function evalWML(ast,env) . This function should be able to process a (list of) outer AST nodes, evaluating text or delegating to other, appropriate eval* functions as appropriate.

Your code should add appropriate bindings at template definitions. A definition binding is a map between a template name, and a structure which records the parameters as an array, the body AST node, and the defining environment.

{ params: ,
  body: ,
  env: }

Your code from this question should be capable of correctly executing non-trivial WML code, including invocations, nested definitions, and recursive definitions. You should aim to implement static scoping.

Question 3

To be able to easily and efficiently do non-trivial computation, you will need some special functions.

Modify your evaluation code to recognize #if, #ifeq, and #expr when invoked and perform the appropriate behaviour.

Question 4

Add the ability to return and pass around a template declaration as a first-class value. As described in class, this is done by recognizing the single-backquote character as the first character in a template name (but is excluded from the actual name of the template).

In this your code should allow for anonymous templates to be returned, expressed as templates with no name. Note that returned templates with names are still recorded as bindings in the current environment, but anonymous templates are not.

To return a template, convert the template binding value to a string. When a returned template is subsequently encountered in an invocation, it must be converted back to a binding value. Use the stringify and unstringify functions provided (these are for your convenience, you may develop your own).

Note that there is some uncertainty in an invoke as to whether the template being invoked is specified by name or by a binding.

Question 5

Show how to compute prefix-sum with Church numerals in WML. Define suitable helper templates, such as for succ, isZero, plus as well as makeN, which receives an argument n and returns the Church numeral for n.

What to hand in

Submit your assignment to MyCourses. Note that clock accuracy varies, and late assignments will not be accepted without a medical note: do not wait until the last minute.

For each question n, include a file qn.js with the source code of your answer. You can assume your code from question 1 will be included in evaluating questions 2–4. Do not include the provided files ( wml.html and wml.js ), or stringify.js , unless you altered it. If you did not use the provided solution to assignment 2, include am assig2.js file with your code.