F1: Final: Written

39: Final: Written , Name: ___________________________

CS 340, Fall 2019, York College of Pennsylvania
42, 200 points

Each of the following questions is based on content from the course in general and exams, quizzes and assignments, etc., 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: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: ... }

On the left half of the page, write the numbers from 0 to 15, one per line. Do this in binary (left most column), hexadecimal (middle column), and decimal (rightmost column). Include the appropriate suffix for each number.

You will be given a decimal number in the range of 0 to 255. On the right part of the page, convert that number to base 2 and base 16 representation, including the appropriate suffix for each number. Clearly indicate each answer by drawing a box around just the answer for each part.

Number: (omitted)

Pick a language: ________________

Write the code in that language to use a regular expression to pick out the digits, work, and caption, from a string of text called text1 and assign that text to the variables digits1 (integer), work1 (text string), and caption1 (text string). The work1 name will be one uppercase letter followed by one or more digits. All three variables should then be printed with explanatory text but only if a match.

Example text for text1: "3. [Q5] Postfix code 4. [E2] more text"

Variable digits would be integer value 3.
Variable middle1 would be text string "Q5".
Variable suffix1 would be " Postfix code [E2] more text".

The following text would be recognized. You should account for and ignore any leading white space.

3. [Q5] Postfix code 4. [A2] Caption for A2

The following text would not be recognized.

1. Question 1 2. [] Question 2 Other text

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)

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.

(omitted)

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).

omitted

(omitted)

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)

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)

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)

Write a small example that has a main code part and a module part that contains a class. Draw a box around the module and the main code and label each as main or module.

The module part should define a class Multiplier. Use your initials for the prefix of the module name. The module name suffix should be Multiplier. The constructor should set the integer class variable product to 1.0. The class should contain a method timesMultiply which takes one integer and multiplies that value to the multiplication. The class should contain a method timesGet1 which should return the current product.

The main code should access the module, create an instance of the Multiplier class and then call that instance to multiply the integer values from 0 to 8 using the timesMultiply method of the Multiplier class. The main code should then use the timesGet1 method to get and display the product using a print statement.

Note: This example can be worked out and tested before the quiz/exam, but you need to remember how to do the various parts from memory for the quiz.

Module code complete filename: _________________________ (not C, C++, Java)

CS 340 - F1 : Final: Written Your grade: _ / 200 [LATE] Late or redo penalty: _ / -200 1. [Q1] Base conversion: _ / 25 suffixes on each number: _ / 2 0 to 15 in each base: _ / 8 binary conversion correct with suffix: _ / 8 hex conversion correct with suffix: _ / 7 2. [] String rewriting and regular expressions: _ / 25 Language: _ / 1 Ignore leading white space: _ / 3 Lazy match: _ / 3 Groups - integer digits, text work and caption: _ / 10 Print output - only if match: _ / 8 3. [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 4. [Q5] Postfix code: _ / 25 Init: _ / 2 var pushes: _ / 7 op1 pushes: _ / 7 op2 pushes: _ / 7 result: _ / 2 5. [Q9] Syntax diagrams: _ / 25 syntax diagrams: _ / 12 BNF grammar: _ / 13 6. [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 7. [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 8. [Q10] Module and class: _ / 25 main and module names: _ / 2 module definition: _ / 2 class definiton: _ / 9 module access: _ / 2 class creation: _ / 2 main code loop and output: _ / 8 Comments: