Implement an autoincrement operator for variables

Assignment Help Programming Languages
Reference no: EM131485079

Principles of Programming Languages Assignment

Part A - Haskell

Complete the following Haskell function definitions. Unless stated otherwise do not use library functions that are not in the Haskell standard prelude. This constraint is so that you gain practice in simple Haskell recursive programming.

The testing process may use many more test cases than the ones shown in the specification. So, please test your functions extensively to ensure that you maximise your marks.

1. Write the function insertAt :: Int -> a -> [a] -> [a].

insertAt n x xs will insert the element x into the list xs at position n items from the beginning of xs. In other words, skip n items in xs, then insert the new element.

You can assume that n will be a non-negative number. If n is greater than the length of the list xs then add it to the end of the list.

2. Write a function uniq :: Eq a => [a] -> [a] that removes duplicate entries from a sorted (in ascending order) list. The resulting list should be sorted, and no value in it can appear elsewhere in the list.

3. Write a function

join :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b,c)].

join takes two lists of pairs, and returns a single list of triples. A triple is generated only when there exists a member of both argument lists that have the same first element. The list elements are not sorted. This is the same semantics as the relational algebra natural join operation.

4. This question extends the join function from question 3. Write the function ljoin :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b,Maybe c)].

This is the left outer join from relational algebra. If a tuple (database row) from the first (left) argument does not have a matching tuple from the second argument, include that tuple in the resulting tuple, but place a "null" value in place of the un-matched value. For this implementation we use a Maybe data type, and use the Nothing value to denote Null.

5. Consider the following definition for a binary tree.

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

A binary tree is balanced if, at every node, the difference between the height of the left and right subtree is at most one. Tree height is defined as follows:

  • height of an Empty node is 0
  • height of a Leaf node is 1
  • height of a Node node is 1 greater than the height of its tallest sub-tree.

(a) Write the function height::Tree a -> Int that calculates tree height

(b) Write the function isBalanced :: Tree a -> Bool that decides if the tree is balanced.

6. Write a function isNumber :: String -> Bool that tests if a string contains a valid number. A valid number is defined in EBNF as:

number → .digit+ | digit+ [ .digit]

7. Write a function getElems :: [Int] -> [a] -> [Maybe a] which takes a list of integers signifying the position of an element in a list, and a list. It returns those elements that correspond to the positions specified. Because a position may be greater than the list size the returned element is a Maybe data type. If the position specified is greater the maximum list position then Nothing is returned, else Just value.

Part B - SPL

Information about SPL, and using the Bison compiler generator

Laboratory exercises to guide your learning of SPL

Information on obtaining the SPL source code and using Git repositories to manage and submit your assignment.

You are required to make a number of modifications to the SPL compiler to implement new features of the SPL language. Each of the following questions is independent in that they do not rely on any of the other modifications. In marking the assignment, they will be tested independently.

I will be compiling and running your SPL system so your code must compile (make) without errors. If you are unable to get some parts working and GCC or Bison compile errors exist, then comment out the error-producing code so that I can compile and execute what you do have working.

1. Implement an autoincrement operator for variables. The syntax for these new operations is described by the extended factor grammar rule

factor → ++id | id++ | id | num | ( expression ) | - expression

These have the same semantics as the C operators of the same kind. The value of pre-increment expression ++x is the current value of x, plus one, while the value of post-increment expression x++ is the current value of x. Evaluation of both operators would increase the stored value of x by one.

You should implement auto-increment for all kinds of variables (globals, locals, and parameters).

The simplest kind is global variables because CPU instructions can access them with DIRECT addressing. I suggest that you start by implementing globals; locals and parameters will attract less marks than globals.

Consider the following program.

var a, b; {a := 1; b:=1; display a, b;

b := ++a; display a, b;

b := a++; display a, b;

}

On execution it should produce as output the sequence 1, 1, 2, 2, 3, 2.

You will need to modify the lexer lexer.c and the parser spl.y as follows:

  • Create new token name (say) INC in spl.y, and modify lexer.c to recognise the corresponding ++ symbol. Look at the way two-character symbols like '>=' are handled. Make sure that you update dispToken().
  • Add grammar rules for the two new f actor alternatives in spl.y.
  • Generate the increment code for the two increment operators. Use the current rule for factor : IDENT as a basis. You will need to generate add and move operations.

You'll probably need a new temporary register, whose number will be stored in a variable like reg, to store the operand '1'.

2. Implement a do ... until post-tested loop. The statement has syntax:

do statement+ until condition ;

Note that the body is a list of statements. This is different from the 'while' loop whose body is a compound statement. Also note the trailing semicolon.

You will need to modify the lexer lexer.c and the parser spl.y as follows:

  • Create new token name (say) UNTIL in spl.y, and modify lexer.c to recognise the corresponding until reserved word. Make sure that you update dispToken().
  • Add the 'until' loop grammar rule to spl.y.
  • Add actions to the loop rule to generate corresponding code. Use the existing 'while' code for guidance, but beware the semantics are different. Most importantly, the condition test follows the body of the loop, so the conditional jump address does not need to be backpatched into the jump instruction. Also, unlike the 'while' loop, this loop terminates when the condition is true.

3. Implement simple global constant identifiers. (Do not implement procedurelocal constants.) The declaration has the EBNF form

const id = num {, id = num};

There may be zero or one constant declaration statement(s) (i.e. it is optional).

For example you could declare const max = 100;.

You will need to do the following:

  • Create new token name (say) CONST in spl.y, and modify lexer.c to recognise the corresponding const reserved word. Make sure that you update dispToken().
  • Add grammar rules to spl.y for (1) a constant declaration and (2) a list of constant declarations; modify the program rule to include the constant declarations.
  • Modify the symbol table to record the constant identifier's value. Modify st.h to add a new identifier class and add a 'value' attribute to the attr structure. Modify list st in st.c so that the value and not the address of constant identifiers is displayed.
  • Add actions to spl.y. You should - Add a symbol table entry when a constant declaration is recognised. And Generate the correct machine code instruction to load a constant value into a register when a constant IDENT in the f actor rule is recognised.

Attachment:- Assignment File.rar

Reference no: EM131485079

Questions Cloud

Level of chromosome compaction. : Based on DNA length, what level of chromosome compaction would you predict for a plasmid of 1 kb, a YAC of 50 kb and a YAC of 1 Mb?
Personality company applies to its products : Company refers to the organization that markets or produces products or services, brand refers to the image and Personality Company applies to its products.
How to develop a successful project team : How to develop a successful project team. The core of the case is a description of an actual team development situation - characteristic stages of team development
Data communication system from circuit maker tellabs : When a company purchased a voice and data communication system from circuit maker Tellabs, Attendance is voluntary.
Implement an autoincrement operator for variables : CSC8503 Principles of Programming Languages Assignment. Implement an autoincrement operator for variables. Implement a do ... until post-tested loop
Examples of reasonable accommodation for disability : List five examples of reasonable accommodation for disability.
Basic function of the hind brain : 1. Which part of the brain is the largest part and what is its function? 2. What is the basic function of the hind brain (brain stem)?
Tracking gantt chart help communicate project progress : how does a Tracking Gantt chart help communicate project progress?
Write a paper on contract of labour in saudi arabia : Write a paper on Contract of labour in Saudi Arabia. Explain what are the contract of labour in saudi arabia? What we need to do to improve the labour contacts?

Reviews

len1485079

5/5/2017 4:48:40 AM

Australian student, need it as pr the guidelines. Submit these Haskell questions using the USQ Study Desk assignment submission facility. Submit a single file containing all definitions. Use the specified function name as your code will be tested by a Haskell function expecting that function name. This assignment is submitted by pushing your local SPL repository to your remote USQ repository. I will pull from your USQ remote repository and mark the code in the branch ass2 or, if you wish to use separate branches for each question. I will pull your code and mark this assignment following the due date unless you have received an official extension. There is no “submit” action on your part except to make sure you have pushed your assignment branch(es) by the due date.

Write a Review

Programming Languages Questions & Answers

  Write a haskell program to calculates a balanced partition

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition,

  Create an application to run in the amazon ec2 service

In this project you will create an application to run in the Amazon EC2 service and you will also create a client that can run on local machine and access your application.

  Explain the process to develop a web page locally

Explain the process to develop a Web page locally

  Write functions

These 14 questions covers java class, Array, link list , generic class.

  Programming assignment

If the user wants to read the input from a file, then the output will also go into a different file . If the user wants to read the input interactively, then the output will go to the screen .

  Write a prolog program using swi proglog

Write a Prolog program using swi proglog

  Create a custom application using eclipse

Create a custom Application Using Eclipse Android Development

  Create a application using the mvc architecture

create a application using the MVC architecture. No scripting elements are allowed in JSP pages.

  Develops bespoke solutions for the rubber industry

Develops bespoke solutions for the rubber industry

  Design a program that models the worms behavior

Design a program that models the worm's behavior.

  Writing a class

Build a class for a type called Fraction

  Design a program that assigns seats on an airplane

Write a program that allows an instructor to keep a grade book and also design and implement a program that assigns seats on an airplane.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd