Hello! Can someone help me to answer Task4 and Task7: Complete \"TODO\" in this
ID: 3775046 • Letter: H
Question
Hello!
Can someone help me to answer Task4 and Task7:
Complete "TODO" in this files:
AssignCompiler.scala
AssignInstrs.scala
AssignRuntime.scala
Task4: It is about handling conditional statements. The statement can be assign. For example, a=5;
This is already done. Now, we need to handle if statement. For example, if(false) { x := x + 1 } { x := 0 }
which is if Expr stmt* stmt*. (stmt*) many statements.
This is all the definition:
Prog ::= Stmt*
Stmt ::= Identifier = Expr | if Expr Stmt* Stmt*
Expr ::= Identifier | Literal | Expr {+,-,/,*,&&,||,=} Expr | {-,!} Expr
Literal ::= Number | true | false
Identifier ::= String
Task7 same idea but with while loop.
# Conditionals
In the first part of this exercise, we extend the Assign language with
conditional statements.
Syntax of the Assign language with conditionals
Prog ::= Stmt*
Stmt ::= Identifier = Expr | if Expr Stmt* Stmt*
Expr ::= Identifier | Literal | Expr {+,-,/,*,&&,||,=} Expr | {-,!} Expr
Literal ::= Number | true | false
Identifier ::= String
Task 1: Define the SOS relations for expressions and programs that add
conditionals to the assign language. Provide traces for 3 different
programs.
Done
# Compile conditionals
We compile conditionals to a machine that features only two
instructions: one for assignment as before and one for conditional
jumps.
Instr ::= Idx = Expr | jumpif Number Expr
For `jumpif`, the first component describes the target program
counter, which must be a constant number. The second component
describes the condition under which the jump takes place. That is, a
jump only takes place if the condition evaluates to `true` and is
skipped otherwise.
We reuse machine states unchanged:
State ::= (Prog, PC, Heap)
PC ::= Number
Heap ::= empty | Literal; Heap
Task 2: Define the semantics of the Assign language with conditionals
as a state transition relation. Provide traces for 3 different
programs.
Done
# Implementation of conditionals
To gain a detailed understanding of the Assign language with
conditionals and to facilitate experimentation, we will implement the
compiler and the abstract machine of the language in Scala. We use
[SBT](http://www.scala-sbt.org/) for building the project and
[ScalaTest](http://www.scalatest.org/) for testing. To compile the
project, run `sbt compile` on the command-line. With `sbt test` you
can execute the tests.
Task 3: Study the code of the Assign language and add two tests for
programs with assignments to `AssignTest.scala`.
Done
Task 4: Implement conditionals for the Assign language. We already
extended the expression type with conditionals. Please do not change
any of the signatures of expressions, because this makes it impossible
for us to test your code! To solve this task, add conditionals jumps
to the instructions, extend the compiler to handle conditionals and
extend the runtime of the abstract machine to handle conditional
jumps. Add at least 3 tests to `AssignTest.scala`, that test programs
containing conditionals.
# The While language
Next we want to add while loops to the language:
Syntax of the While language
Prog ::= Stmt*
Stmt ::= Identifier = Expr | if Expr Stmt* Stmt* | while Expr Stmt*
Expr ::= Identifier | Literal | Expr {+,-,/,*,&&,||,=} Expr | {-,!} Expr
Literal ::= Number | true | false
Identifier ::= String
Task 5: Define the SOS relations for expressions and programs of the
While language. Provide traces for 3 different programs.
# Compiled While language
While loops are also compiled to conditional jumps. The set of
instructions and the abstract machine stay unchanged:
State ::= (Prog, PC, Heap)
PC ::= Number
Heap ::= empty | Literal; Heap
Task 6: Define the semantics of the compiled While language as a state
transition relation. Provide traces for 3 different programs.
# Implementation of while loops
Task 7: Implement while loops for the Assign language with
conditionals. Use the same code base that you created for task 3. Add
at least 3 tests to `WhileTest.scala`, that test programs containing
while loops.
# Security vulnerabilities?
Task 8: Can you spot weaknesses in our model of While that may yield
security vulnerabilities later on? Describe any weakness you can find and
discuss whether it is exploitable or how it would become exploitable.
Explanation / Answer
Task-4 :A shift-reduce conflict that frequently occurs involves the if-else construct. Assume we have the following rules:
and the following state:
We need to decide if we should shift the ELSE or reduce the IF expr stmt at the top of the stack. If we shift then we have
where the second ELSE is paired with the second IF. If we reduce we have
where the second ELSE is paired with the first IF. Modern programming languages pair an ELSE with the most recent unpaired IF. Consequently the former behavior is expected. This works well with yacc because the default behavior, when a shift-reduce conflict is encountered, is to shift.
Although yacc does the right thing it also issues a shift-reduce warning message. To remove the message give IF-ELSE a higher precedence than the simple IF statement.
task-7
The while statement is used for repeated execution as long as an expression is true:
This repeatedly tests the expression and, if it is true, executes the first suite; if the expression is false (which may be the first time it is tested) the suite of the else clause, if present, is executed and the loop terminates.
A break statement executed in the first suite terminates the loop without executing the else clause’s suite. A continue statement executed in the first suite skips the rest of the suite and goes back to testing the expression.
task-1 :-
In case the result of
s
S
,
is not available we say that
is a
stuck
configuration and there
is no subsequent transitions.
Although SOS emphasizes to the intermediate execution, the
meaning
of a program
P
on
an input state
s
is the set of
final
states (also stuck configuration) that can be executed in
arbitrary finite steps.
Example Semantic
Going back to the “While” programming language example, the first two axioms
]
[
sos
ass
and
]
[
sos
skip
have not changed at all because the assignment and
skip
statements are
fully executed in one step.
[
]
[
]
s
s
skip
a
x
s
s
a
x
ass
sos
sos
=
,
]
[
,
:
]
[
skip
6
The two rules
]
[
1
sos
comp
and
]
[
2
sos
comp
for a statement
2
1
S
;
S
express that the execution
starts with the first step of
1
Sfrom
s
. Then there are two possible outcomes derived from
the two possibilities for transition relation:
1.
]
[
1
sos
comp
- The execution of
1
S
has not been completed we have to complete it
before embarking on the execution of
2
S . In this case the first step of
s
S
,
is an
intermediate configuration
'
,
'
1
s
S
then the next configuration is
'
,
;
'
2
1
s
S
S
.
'
,
;
'
,
;
'
,
'
,
]
[
2
1
2
1
1
1
1
s
S
S
s
S
S
s
S
s
S
comp
sos
2.
]
[
2
sos
comp
- The execution of
1
S has been completed we can start on the execution
of
2
S . In this case the result of execution
1
S from is a final state
s’
then the next
configuration is
'
,
2
s
S
Operational Semantics
Page 13
'
,
,
;
'
,
]
[
2
2
1
1
2
s
S
s
S
S
s
s
S
comp
sos
The first step of the condition statement starts with testing
b
, then branching according to
the outcome:
[
]
[]
ff
s
b
s
S
s
S
S
b
if
tt
s
b
s
S
s
S
S
b
if
ff
sos
tt
sos
=
=
if
else
then
if
if
else
then
if
,
,
]
[
,
,
]
[
2
2
1
1
2
1
The first step of the while statement is to “unf
old” it one level, that is to rewrite it as a
condition. In the next execution step a test is performed and the execution resumes. Note
that the
]
[
sos
while
rule breaks the compositional structur
e of the semantic (the reason is
that the rule defines the semantic in terms of
itself), hence structural induction doesn’t
work here fine.
skip,s
S
b
S;
b
s
S
b
while
sos
else
)
do
while
(
then
if
do
while
,
]
[
Derivation Sequence
A derivation sequence of a statement
S
starting in state
s
is either:
1. a finite sequence:
k
,..,
,.
,
2
1
0
of configurations satisfying:
•
s
S
,
0
=
•
0
,
0
1
<
+
k
k
i
i
i
for
•
ion
configurat
stuck
or
ion
configurat
terminal
a
either
is
k
2. an infinite sequence
,...
,
,
2
1
0
of configurations satisfying:
•
s
S
,
0
=
•
i
i
i
+
0
1
for
More notations:
1. For a terminal or a stuck configuration
i
we write:
i
i
0
- indicates that there are
i
steps in the execution from
i
to
0
i
*
0
- indicates that there is a finite number of steps from
i
to
0
2. we construct a derivation tree for each step in the sequence (see example below)
Examples
:
1.
()
z
y
y
x
x
z
=
=
=
:
;
:
;
:
assuming
5
0
=
x
s
and
7
0
=
y
s
The derivation sequence can be constructed as follows:
()
[]
[][]
[][][]
5
)
7
)
5
((
7
)
5
(
,
:
5
,
:
;
:
,
:
;
:
;
:
0
0
0
0
6
6
6
6
6
6
y
x
z
s
x
z
s
z
y
z
s
z
y
y
x
s
z
y
y
x
x
z
Thats all i know to give ans !!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.