Here is an informal description of a simple language. Statements in the language
ID: 3748932 • Letter: H
Question
Here is an informal description of a simple language. Statements in the language are as follows: read a; | read an integer from standard input device into the variable a. a can be any lower case letter. wite a; | Write the value of a on standard output device (whatever it is). a can be any lower case letter. a := b; | Assign to the variable a the value of the variable b. a and b can be any letter between a and z. a := 58; | Assign the value of 58 to the variable a. a can be any letter between a and z. 58 can be any single digit or multiple digit integer. a := a + 1; | Add 1 to a. a can be any lower case letter. a := a - 1; | Subtract 1 from a. a can be any lower case letter. if a < 0 goto L;| If a < 0, transfer control to statement labeled with L. L can be any letter between A and Z. a can be any lower case letter. if a = 0 goto L;| If a = 0, transfer control to statement labeled with L. L can be any letter between A and Z. a can be any lower case letter. if a > 0 goto L;| If a > 0, transfer control to statement labeled with L. L can be any letter between A and Z. a can be any lower case letter. goto L; | Transfer control to statement labeled with L. L can be any letter between A and Z. halt; | Stop execution, program should always end with halt Lower case letters a-z represent names of integer variables, upper case letters A-Z represent names of labels. Each statement may have a label as a prefix, separated from the statement by a colon (:). A program must have at least one statement and ends with halt. All statements end with ;. For example, the following program computes the sum of two positive integers a + b. Preconditions: Variables a and b contain positive integers Postconditions: Variable a contains the sum of the integers, the contents of variable b is destroyed. read a; read b; L: a := a+1; b := b-1; if b > 0 goto L; write a; halt; Task 1 (10 points): Using the statements of the simple language described above, write a program that computes the sum of two integers a and b, with the following specifications: Preconditions: Variables a and b contain any integers (might be positive, negative, or zero). Postconditions: Variable x contains the sum a + b, the contents of a and b are preserved. Note: You may use additional variables in your program if necessary. For simplicity, you may use single letter for variables and labels. Use lower case letter for variables and upper case letters for labels. Task 2 (30 points): Develop a formal definition of the language syntax using BNF notation. Make sure your grammar covers all the valid statements in this language.
Explanation / Answer
Task 1
Idea behind the program is to make copy the values of a and b to temporary variables, and if they are negative, bring them close to zero (by adding 1) and decrement x and if they are positive, bring them close to zero (by subtracting 1) and increment x.
Lables L and M work for two different variables. Both of them stops when their respective variables (y and z) become 0.
x=0;
read a;
read b;
y:=a;
z:=b;
L: if y>0 goto N;
if y<0 goto O;
M: if z>0 goto P;
if z<0 goto Q;
wite x;
halt;
N: y := y - 1;
x := x + 1;
goto L;
O: y := y + 1;
x := x - 1;
goto L;
P: z := z - 1;
x := x + 1;
goto M;
Q: z := z + 1;
x := x - 1;
goto M;
Task 2
BackusNaur form / Backus normal form (BNF) is used to define the syntax of the statements of a programming language. It is a notation technique for context-free grammars.
<KEYWORD> ::= "read","wite"
<LOWER> ::= 'a' .. 'z'
<UPPER> ::= 'A' .. 'Z'
<NUM> ::= 0 .. 9 | <NUM><NUM> (for multi digit numbers)
<OPERATOR> ::= '+' , '-'
<CONDITION> ::= '<' , '>' , '='
<VAR> ::= <LOWER>+
<LABEL> ::= <UPPER>+
<EXIT> ::= "halt"
<CONDITION-STATEMENT> ::= <VAR> <CONDITION> <VAR> | <VAR> <CONDITION> <NUM>
<OPERATION> ::= <VAR> <:=> <VAR> <OPERATOR> <NUM>
<RULE> ::= <KEYWORD> <VAR> (Satisfies statements 1 & 2)
| <VAR> ":=" <NUM> (Satisfies statement 3)
| <VAR> ":=" <VAR> (Satisfies statement 4)
| <VAR> ":=" <VAR> <OPERATOR> <NUM> (Satisfies statements 5 & 6)
| "if" <CONDITION-STATEMENT> "goto" <LABEL> (Satisfies statements 7,8 & 9)
| "goto" <LABEL> (Satisfies statement 10)
| <LABEL> ':' <RULE> (Satisfies the Label declaration, as seen in program)
| "halt" (Satisfies statement 11)