Send
Close Add comments:
(status displays here)
Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.
E2: Exam#2: Written
1. E2
39: Exam#2: Written , Name: ___________________________
CS 340, Fall 2019, York College of Pennsylvania
42, 150 points, 2019-11-21 (at start of class)
Each of the following questions is based on content from the course in general and quizzes and assignments in particular. Even if not explicitly stated, the answers are to follow the same form as covered previously in the course (in class presentations, class notes, class requirements, etc.).
2. Exam help
{ 2:before: p where e replaces x }
x = e;
{ 1:after: p }
{ pre : ... }
{ ... }
{ inv:p }
while b do
{ p and b }
S
{ p }
end while
{ p and (not b) }
{ ... }
{ post: ... }
3. Question 1 (25 points). String rewriting and regular expressions
Pick a language: (except JavaScript) ________________
Write the code in that language to use a regular expression to pick out the prefix, name, and suffix of a string of text called
text1and assign that text to the variables
prefix1,
middle1, and
suffix1. The
middle1 name will be all uppercase letters in square brackets but the other text can be any valid text.
Example text for
text1: "
The [FUND] fund and [SHARE] are here"
Variable prefix1 would be "The ".
Variable middle1 would be "FUND".
Variable suffix1 would be " fund and [SHARE] are here".
Here are some related content for this problem. Check all the notes for more information.
String rewriting systems
String rewriting in JavaScript
String rewriting examples (for JavaScript, Lua, PHP, Python)
4. Question 2 (25 points). Truth table, tree, Prolog program
For the provided logical expression do the following.
Rewrite the expression.
Draw the corresponding expression tree above the expression, lining up leaves and nodes with the expression operands and operators.
Below the expression, write the extended truth table as done during the semester.
Write a complete Prolog program to output the logical expression and extended truth table as done during the semester. As has been done throughout the semester, label and order interior nodes left to right starting at "
A". You do not need to include the definition for the
prints predicate nor the
solve predicate.
Expression:
(omitted)
5. Question 3 (25 points). Postfix code
Use the provided postfix code and values for the variables in the postfix code.
The first line should be "init the stack".
Write the variable or operator, left justified on a separate line.
On the following line(s) for each variable or operator, write the actions(s), for that variable or operator.
pushes should have the form "push expression as value".
pops should have the form "pop value as variable".
Use reg1 and reg2 as temporary registers.
The last line should indicate the result.
The variable values to be used will be provided. (Note: This was done in class when the exam was given and this text added after the exam).
Postfix code list:
omitted
Variable values:
(omitted)
6. Question 4 (25 points). Syntax diagrams
Given a small EBNF grammar specification, do the following.
Draw the syntax charts for the equivalent EBNF grammar (as done in class and in the nodes).
Convert the EBNF grammar to an equivalent BNF grammar (as done in class and in the nodes)
In both parts, do not change the production or terminal or variable names. For the BNF, add production and variable names as needed. Production:
(omitted)
7. Question 5 (25 points). Operational semantics: goto transformations
You will be given a small C program code fragment consisting of a one or more while loops and one or more if conditionals. Write an equivalent C program that uses labels and goto statements to remove the while and conditional statements. All other statements should retain their same relative position and same form.
All labels should have the form "Lx" where "L" is the upper case letter "L" and "x" is the next label in the sequence - as in the examples covered in class (that is, in the order used in the transformed program).
(omitted)
8. Question 6 (25 points). Axiomatic semantics: program verification
Given the following C-like assignment statements and loop, prove the (partial) correctness of the code in a manner similar to that done in class and in the class notes by filling in the assertions, doing substitutions, making simplifications, etc. Note that depending on how you simplify you may not need all comment lines or you may need more comment lines.
(omitted)
9. Scoring rubric
CS 340 - E2 : Exam#2: Written
Your grade: _ / 150
[LATE] Late or redo penalty: _ / -150
1. [] String rewriting and regular expressions: _ / 25
Language: _ / 1
Code: _ / 8
Prefix - lazy: _ / 8
Middle - uppercase letters: _ / 4
Suffix: _ / 4
2. [Q6] Truth table, tree, Prolog program: _ / 25
Tree: _ / 4
Expression: _ / 2
Table: _ / 4
facts with names and values: _ / 3
go and fail predicate: _ / 3
print predicates - before and after: _ / 3
provided variables names and letters A, B, etc.: _ / 3
predicate calls and proper row order: _ / 3
3. [Q5] Postfix code: _ / 25
Init: _ / 2
var pushes: _ / 7
op1 pushes: _ / 7
op2 pushes: _ / 7
result: _ / 2
4. [Q9] Syntax diagrams: _ / 25
syntax diagrams: _ / 12
BNF grammar: _ / 13
5. [Q7] Operational semantics: goto transformations: _ / 25
unchanged code in order: _ / 5
labels placed and in order: _ / 5
goto and placed: _ / 5
if goto and placed: _ / 5
negate expression , no improvement: _ / 5
6. [Q8] Axiomatic semantics: program verification: _ / 25
loop invariant copy: _ / 5
loop condition copy , negate if needed: _ / 5
precondition derive and simplify: _ / 5
loop body statements derive and simplify: _ / 5
postcondition derive and simplify: _ / 5
Comments:
