Remember our \"rewrite game\" in the second lecture. We represent arithmetic val
ID: 3783856 • Letter: R
Question
Remember our "rewrite game" in the second lecture. We represent arithmetic values > 0 as sequences of symbols. For example, | represents value 1, and ||||| represents value 5. The input to your rewrite system is either a single value representation, or two value representations surrounded by a begin ($) and end (#) marker, and separated by a & marker. For example, the single input value 3 is represented by $|||#, and the input pair 2, 5 is represented by $||&|||||#. The normal forms produced by the rewrite systems do not contain any markers. Give rules of rewrite systems that implement different arithmetic operations on our chosen representation. A rewrite system consists of a set of rewrite rules of the form X Y as discussed in class. Successor function: f(x) = x + 1, x > 0 Example: $|||# will be rewritten to |||| Show the rewrite sequence of your rewrite system for the example input. Double function: f(x) = 2 * x, x > 0 Example: $|||# will be rewritten to |||||| Show the rewrite sequence of your rewrite system for the example input. Addition function: f(x, y) = x + y, x > 0 and y > 0 Example: $||&|||# will be rewritten to ||||| Show the rewrite sequence of your rewrite system for the example input.Explanation / Answer
As mentioned, we need to parse the input value 'X' and need to feed it to a system which does some operations over it and produces the output 'Y' of the rewrite system depending on a given rule or funtion and produce the output in terms of symbol '|' .
Objective - 1 :
1) Parse the input and determine the value as x and y .
Now since we get the value in terms of symbol '|' contained within '$' & '#', we need to determine that value first.A simple algorithm for that would be to fetch each character and take a decision. I assume the system always gets the value starting with '$' so we can skip it and start from the second character of the input and go on until we find a '&' or a '#' .Everytime i fetch a character other that '&' and '#' i increment the value of my first input value "val1". After some iteration if we get a '#' then it would represent we don't have a second value otherwise if we encounter a '&' before '#' then we need to fetch the second value too. Everytime i fetch a character other than '#' i increment the value of my second input "val2"
Objective - 2:
Pass the value to the computing function (rewrite engine) and perform arithmetic operations to arrive at a result.
result <-- rewriteEngine(X)
Replace the value that we fetched into the placeholders of the functions. E.g for successor funtions put the "val1" inplace of 'X' and determine the value of f(x) by adding 1 to it. Then we can printf '|' as many times the value of f(x)
I have implemeted such rewrite engine in a "C" program
#########################################
C program to implement this
#########################################
#include<stdio.h>
#include<string.h>
void parse(char* input);
void successor(void);
void twoTimes(void);
void addition(void);
int val1 = 0;
int val2 = 0;
int main(int argc, char* argv[])
{
char input[200] = {''};
printf("Enter the input sequence ");
scanf("%s",input);
parse(input);
if((val1!=0) && (val2 == 0)){
successor();
twoTimes();
}
else{
successor();
twoTimes();
addition();
}
return 0;
}
/**********************************************************
Parse function to fetch the value from the input
***********************************************************/
void parse(char* input)
{
int i = 1, len = 0;
len = strlen(input);
/*** Fetching value of val1 ****/
while( (input[i] !='&' ) && (input[i] != '#')){
val1++;
i++;
}
/***** If the previous loop exited because '&' was found then we need to fetch val2 too *********/
if(input[i] == '&'){
i++;
while( input[i] != '#'){
val2++;
i++;
}
}
else
return;
}
void successor(void){
int i=0;
for(i=1;i <= (val1 + 1);i++)
printf("|");
printf(" ");
}
void twoTimes(void){
int i=0;
for(i=1; i <= (2*val1);i++)
printf("|");
printf(" ");
}
void addition(void){
int i=0;
for(i=1; i <= (val1 + val2);i++)
printf("|");
printf(" ");
}