Foto
17Jun

Computer Software Assignment Help

Computer Software Assignment Help

email Us : support@locusrags.com
Call Us : +44-7497786317, +61-280147200

Computer Software Assignment HelpHow to use   it:

Download the file hw2.zip to your own directory and unzip it, producing a subdirectory named hw2. Go into that directory (cd hw2) and type

make

then type

./see

then type the lines

x = 5
y = 2*x – 3
(x+y)/3
[Ctrl-D]

and observe the output. (There is also an executable file see-solution, which is a complete solution to the assignment. You may run that program as well.) To see more examples, you can also run

./see < sample-input. txt

Running bison with the options given in the Make file produces a file y.output, which describes the parser created from the grammar in detail. You should browse through it, but I don’t expect you to understand the stuff regarding states. We’ll cover it later.

  1. Edit main.c, changing the guideline = 0;to readdebugger = 1;Then repeat all the steps in the last item. Now you get messages describing what the parser is doing at each step (i.e., shifting what token or reducing by what production). You may then return this line in main.c to its original content.

My task is to do the following:

  1. Currently, yylex() is written by hand in the utilities section of parse.y. Write a flex program named scan.l that handles the lexical analysis in the same way. Running flex on scan.l will then produce the needed yylex() function, so you remove the hand-written one. Note that variable names in SEE are single letters and case insensitive. (All attributes are integers, which is the default.) Edit the Makefile to accommodate scan.l (which includes adding lex.yy.o to the list of OBJECTS). To let bison and flex work together, you need to do two things:
    1. Use the “-d” option when running bison. This (along with the “-y” option) generates the header file y.tab.h for use by scan.l. (Edit the Makefile.)
    2. Insert the line#include “y.tab.h”inside the %{ and %} delimiters in the preamble of scan.l. (Note: if you include other files in your scan.l preamble, you should place them above the include directive for y.tab.h, so they are included first; otherwise, you may get gcc compiler errors.)
  2. Alter the grammar in parse.y to allow for unary prefix + and – (the first operator does nothing, the second negates its argument). The syntax rules are as follows: The first term in an expression may optionally be preceded with a single ‘+’ or ‘-‘, and that is the only place it can appear. The operator applies to the whole first term. This gives unary + and – the same precedence and associations as their binary counterparts. Thus for example,
  1. – 2*x+ 5 is evaluated as (-(2x))+5,
  2. – – 3 is a syntax error, but -(-3) is ok,
  3. 3*-xis a syntax error, but 3*(-x) is ok.

In particular, you cannot apply two of these operators in a row without anything in between. NOTE: This is how Pascal parses these operators, but not how C/C++/Java handles them. In C/C++/Java, all unary operators have precedence higher than all binary operators.

  • Note: If you decide to implement the last task, then you will need to rewrite some of the code you use for this task. If you implement the last two tasks fully, you will also get credit for this task as well.

We now want to remember each expression entered (the expression itself, not its value) and be able to refer to it by number. The first expr entered has number 1, the second has number 2, etc. The idea is to be able to re-evalate expressions with variables after the variables change. Here is a sample session using my renamed executable “see2”. Each number followed by a colon is a computer-generated prompt giving the number of the expression to be entered.

1: x = 5
5
2: y = 2*x – 3
7
3: x = 13
13
4: y = #2
23
5: y
23
6: Ctrl-D

The string ‘#2’ is an expression referring to the expression entered on input line 2, i.e., 2*x – 3. Note that the value assigned to y on input line 4 is now 23, reflecting the new value of x used in the expression ‘#2’.

NOTE: The following paragraphs may not make much sense right now, because I have not yet had a chance to explain the details in lecture, particularly, passing attributes around of different types (besides the default int). I have therefore added some sample snippets of code below. Skim the next few paragraphs, then look at the sample code, then reread the paragraphs to see if they make more sense.

Edit parse.y so that syntax trees are created as attributes, rather than integer values. (For this you will need a %union declaration in parse.y; see the example below.) Keep the completed syntax trees for the exprs on a list. Please do not put all your code in parse.y this time. Make your actions reasonably short (no more than about five or six lines, say, and fewer is better), calling high-level tree-building functions. Implement these functions in a separate file, tree.c, with an accompanying tree.h to export the definitions there. Include tree.h in the preamble of parse.y and also in the preamble of scan.l before the inclusion of y.tab.h. (This is because y.tab.h includes the attribute union you declared in parse.y, but does not include any of the typedef’s that support it. Also note that the type of yylval is now the union you declared in parse.y.)

Add a new production for factor so that a factor can expand into ‘#’ followed by a CONST (there could be whitespace in between). The corresponding action should assign to the parent nonterminal (a pointer to) the nth syntax tree on the list, where n is the value of the CONST. If n is out of range, give an error message and quit the program. Don’t create a duplicate tree, just a reference to the existing tree. Thus, expressions may be shared.

The actions for the productions

assign
: VAR ´=´ expr
| expr
;

must now each evaluate the tree given as the expr attribute by post-order traversal and pass its (integer) value to $$ to be printed as before.

You must also store the expression tree ($3 in the first production above; $1 in the second) in a global list of expressions. Note that, in the case of the first production, you don’t store the whole assignment as an expression, just the right-hand side. The actual update of the variable only occurs once, i.e., you don’t “reassign” as a result of evaluating a #-reference. For example:

1: x = 5
5
2: x = 17
17
3: #1
5
4: x
17

Put your definition(s) of the tree-evaluating function(s) in a separate file eval.c, with an accompanying eval.h. (It’s alright by me if you include “tree.h” inside eval.h.) Don’t forget to update the Make file to accommodate your new source files.

  • To evaluate these expressions efficiently, one must be sure not to evaluate a shared node more than once in a traversal. This precaution can prevent an exponential slow-down, so it really should be done. For example, consider: 2
    2
    2: (#1 + #1) % 11
    4
    3: (#2 + #2) % 11
    8
    4: (#3 + #3) % 11
    5
    5: (#4 + #4) % 11
    10
    6: (#5 + #5) % 11
    9
    (etc.)Suppose we continue this pattern. Then a naive evaluation of the expression on line ntakes Θ(2n) time, but if we “memoize” (or “cache”) our intermediate results we can evaluate it in time Θ(n).

You only need to memoir values of expressions of the form `#n‘, that is, values of top-level expressions, one per input line. You do not need to detect or memoir common sub expressions within the same expression. Every time any variable is reassigned, you should “erase” all your currently memorised values, because the reassignment may render these values obsolete. The next evaluation would then start from scratch.

Add Your Review

fifteen − thirteen =

Rating*