Reference no: EM132375954
TASK 1
1) Write unambiguous grammar in BNF and EBNF forms for logical expressions composed of:
• constants tt and ff,
• variables (the variable name starts with a capital letter. Follows a string of none, one or more upper case and lower case letters) and
• operations and, or, xor, => („follows") un <=> ("equivalent"),
• brackets ( ), which can be used to determine the sequence of execution of other operations within the expression value calculation
EBNF grammar must be formatted so that in any export rule no left-hand symbol appears in the corresponding right-hand expression.
Outside brackets, or within single brackets expressions:
• the arguments are most closely connect by operation and,
• next closely are operations or and xor (the same priority),
• next closely is operation =>,
• next closely is operation <=>.
Make grammar such that and, or, xor, <=> associate to the left, but => associate to the right.
Examples:
X1 and X3 or X2 => X1 <=> tt and X1 correspond (matches)
(((X1 and X3) or X2) => X1) <=> (tt and X1).
X1 xor X2 xor X3 correspond (matches) (X1 xor X2) xor X3 X1 => X2 => X3 correspond (matches) X1 => (X2 => X3)
2) Create a logical expression that does not contain brackets ( ) and contains exactly 6 logical links, including each of the links and, or, xor, => , <=> at least once.
3) Draw for this expression parse tree.
4) Write one output (export) example how from the beginning non-terminal symbol corresponding to your grammar rules to get the expression of your choice.
TASK 2
Given a program:
a := a + 13;
while i > n do
if i-1 >= n then
a := a - i
else
fi;
a := a + (2 * i)
i := i - 1
od
1) Draw a natural semantics export tree that describes the action of this program from the initial state σ = {i
= NN + 3, n = NN, a = 15}. NN=40
2) Create structural operational semantics (small step semantics) output (export) (string of states and their transitions with motivated transition steps) according to the action of given program from the given starting state σ.