Homework 2 – CMSC 331 – Summer 2023Due Date June 16, 2023 – 11:59 PM
Submission instructions:
● Please prepare your answers electronically as a single pdf file and submit it as
“your_name.pdf” on Blackboard.
● The file name is your complete name with no space character. For example, the
file name would be john_smith.pdf, if your name is John Smith.
● Do not include the questions in your answer sheet. Only write the answers.
● When uploading your answer sheet to Blackboard, wait for the feedback
message from Blackboard to make sure the upload operation is complete.
● After upload, check that your file in Blackboard contains all pages.
1 – Semantics – Attributes Grammar (25 points)
Using the following grammar write an attributes grammar that can calculate the decimal
value of an octal number.
Grammar:
number = list
list = list octal | octal
octal = ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’
Notes:
An octal number consists of octal digits, i.e. 0 to 7.
The following example shows how to convert the octal 67 to its equivalent
decimal. The symbol star represents multiplication.
67 = 6 * 81 + 7 * 80 = 6 * 8 + 7 = 55
Questions:
1a – introduce an attribute (4 points)
1b – specify the type of your attribute, i.e. intrinsic, inherited, or synthesized. (5
points)
1c – write the attributes grammar (Syntax rule, Semantic rule, Semantic
condition) for every grammar rule. (16 points)
2 – Axiomatic Semantics (25 points)
2a – Determine the precondition for the following sequence of expressions. Please provide all
your work including calculations, and final answer. (10 points)
{ ? } a = 4 * (3 * b – a); b = 4 * a – 6; { b > 10 }
2b – Determine the strongest precondition for the following if-else statement. Please provide all
your work including calculations, logic implications if any applies, and final answer. (15 points)
{?}
if (x > y)
y=x–5
else if (x < y)
y=x+8
else
y = 3x
{ y > 15}
3 – Lexical Analysis – Regular Expressions (25 points)
3a – Write a regular expression that finds all strings starting with a number between 0
and 299 inclusively, followed by an x, followed by any combination of zero or more x
and y, and ends with y.
Examples of accepted strings: 299xxy, 4xyy, 156xy, 23xxxyyy, 23xxyxyy, 0xxyy
Examples of rejected strings: 300xy, 400yx, 305yyyx, 444yxyxy, 002xy
3b – One way of implementing a specific regular expression as a computer program is
to convert the regular expression to its equivalent Finite Automaton. Draw an NFA or
DFA for your regular expression in part 3a.
4 – Lexical Analysis – NFA and DFA (25 points)
Convert the following NFA to its equivalent DFA. Please provide all your work including
state-transition table and the resulting DFA. The DFA must be a complete machine
including the accepting state(s).
