CS 581, Winter 2022 Homework 2 (Abstract Syntax)
Important Reminders!
1. Upload your solution as a Haskell file (ending in .hs) to Canvas.
2. Only submit files that compile without errors! (Put all non-working parts in comments.)
Copyright By PowCoder代写 加微信 powcoder
3. You must do all homework assignments by yourself, without the help of others. Also, you must not use
services such as Chegg or Course Hero. If you need help, simply ask on Canvas, and we will help!
4. Thehomeworkisgradedleniently,andwerewardseriousefforts,evenwhenyoucan’tgetacorrectsolution.
Exercise 1. Mini Logo
Mini Logo is a simplified version of the Logo language for programming 2D graphics. The idea behind Logo and Mini Logo is to describe simple line graphics through commands to move a pen from one position to another. The pen can either be “up” or “down.” Positions are given by pairs of integers. Functions can be defined (using def)) and called (using call) to reuse groups of commands. The syntax of Mini Logo is as follows (nonterminals are typeset in italics, and terminals are typeset in typewriter font).
| moveto (pos,pos)
| def name ( pars ) cmd
| call name ( vals )
| cmd; cmd
num | name name, pars | name
num, vals |
Note: Remember that unspecified nonterminals, such as num and name, should be represented by corresponding
predefined Haskell types, such as Int and String.
(a) Define the abstract syntax for Mini Logo as a Haskell data type Cmd.
(b) Write a Mini Logo function vector that draws a line from a given position (x1,y1) to a given position (x2,y2) and represent the function in abstract syntax, that is, as a Haskell value of type Cmd in (a).
Note. What you should do is write a Mini Logo program that defines a function vector. Using concrete syntax, the answer would have the following form.
def vector (…) …
It might be a good idea to actually write the solution in concrete syntax first. But then you should translate that Mini Logo program into abstract syntax, that is, you should give a Haskell value that starts as follows (assuming Def is the constructor name representing the def production of the Haskell data type).
vector = Def “vector” … …
You only need to submit this Haskell definition of the value vector as part of your Haskell program. (If you like, you can include the concrete syntax as a comment, but it is not required.)
(c) Define a Haskell function steps :: Int -> Cmd that constructs a Mini Logo program which draws a stair of n steps. (The function steps is a program generator.) Your solution should not use the macro vector.
mode ::= pos ::= pars ::= vals ::=
CS 581, Winter 2022, Homework 2 (Abstract Syntax) 2
Results of the Mini Logo programs produced by steps 1 and steps 3.
Note for parts (b) and (c): The Haskell program you submit doesn’t have to draw anything. It only needs to contain the abstract syntax of the macro vector (part (b)) and the Haskell function steps that produces Mini Logo abstract syntax (part (c)). Only if executed by a Mini Logo interpreter, vector called with arguments should result in a line being drawn. And the program that results from the application of steps to a number would draw steps only if interpreted by a Mini Logo interpreter.
Exercise 2. Grammar Grammar
Consider the following grammar that describes the syntax of the language for grammar definitions.
grammar ::= prod ::= rhs ::= symbol ::=
prod; … ;prod nt::=rhs| …|rhs symbol∗
A grammar is given by a list of (grouped) productions (prod), each of which consists of a nonterminal nt and a list of alternative right-hand sides (rhs). A definition lists all the productions for a particular nonterminal. A right-hand side of a production is given by a sequence of terminal (term) and nonterminal (nt) symbols.
Note carefully the difference between the object language symbols ::= and | (typeset in blue typewriter font) and the similar-looking symbols ::= and | that belong to the grammar metalanguage.
(a) GiveHaskell(data)typedefinitionsfortypesGrammar,Prod,RHS,andSymboltorepresenttheabstractsyntaxfor the above language. As part of your definition, use the types NT and Term, defined as follows.
type NT = String
type Term = String
(b) Consider the following grammar for a small imperative language Imp.
cond ::= T | notcond | (cond)
stmt ::= skip | while cond do { stmt } | stmt; stmt
Represent this grammar by a value of the type Grammar defined in part (a). imp :: Grammar
It might be useful to break this definition down into smaller parts and create a few auxiliary definitions (for example, a separate value for each production group, maybe even a separate value for each right-hand side).
(c) Definethefollowingtwofunctionsforextractingalldefinednonterminalsandallusedterminalsformagrammar.
nonterminals :: Grammar -> [NT]
terminals :: Grammar -> [Term]
For the value imp defined in part (b), the functions would produce the following results. > nonterminals imp
[“cond”,”stmt”]
> terminals imp [“T”,”not”,”(“,”)”,”skip”,”while”,”do”,”{“,”}”,”;”]