 
This homework is due on Wednesday March 6 before midnight. We will use the lex command and Makefile we show and check your program with test inputs that include the example given as well as other cases. (1) Axiomatic semantics I (15 points)Compute the weakest precondition for the following sequence of statements, given the stated post condition. Hint: Start by deciding what variable or variables should be mentioned in the precondition. Recall the rule for sequences: the precondition for a statement in a sequence is equal to the postcondition for the statement that preceeds it. Note: Your answer will involve a relationship between a and b. (2) Axiomatic semantics II (15 points)Compute the weakest precondition for the following statements and the given post condition. . Hint: Analyze the two cases that the ifthenelse creates: one where x is greater than y and one where it is not. Figure out what are the weakest preconditions for each. Find the strongest single precondition that is logically implied by both. On Regular expressionsThe lexical level of a programming language is usually specified with regular expressions or finite state automata. Consider the definition of strings for simple integers. We specify that an unsigned integer must be either a single zero, or be a string that begins with a nonzero digit and continues with any number of additional digits (e.g., '1', '451', and '0' are all ok, but '001', 'foo' and '3.14' are not ok). This can be described by the deterministic finite automaton (DFA) to the right. Note that we identify the start state, and mark each accepting state with an asterisk. The transitions (arrows) are labeled with the input that will cause the transition and we use the common notation [c1c2] to mean any single character in the ascii range between c1 and c2. We can also write this language specification as a regular expression:
(3) Anaconda numbers in lex (70 points)You are developing a new programming language Anaconda and need to decide how integers should be represented. The following is a specification for an Anaconda integer that one of your teammates comes up with.
Notice how long and confusing this description has to be to ensure that it is unambiguous. You can see that we do not allow "leading zeros" in any of the representations, e.g., 0x007 is a bad hex number, and 007 is both a bad octal number and a bad decimal number. (3a) Lexical Scanner in Java/Python/C (20 points)Write a program in Java, Python, or C/C++ that reads in a singlecharacter at a time, and when it reaches endoffile, reports whetherit has read in a decimal, octal, or hexadecimal number, and whatthat number is (as a string), or "NONSENSE" if it isn't a wellformednumber. Name your program file lexical.{pycjava}(suffix obviously depending on what language you choose).(3b) Deterministic Finite Automata (DFA) (15 points)Draw deterministic finite automata that correxpond to the three patterns for Anaconda integers. You can either do this by hand, scan it in and add it to a pdf file or use a drawing program to produce the diagrams. Google Docs do allow you to create drawings and save them as pdf. (15 points) (3c) Lexical Scanner in Lex (35 points)Develop a lexical scanner for Anaconda integers using the Unix utility Lex or Flex. Start by reading the compact guide to lex and yacc. The look at and experiment with the the simplescanner example which uses lex to create a simple lexical scanner for a Pascallike language. The file scanner.l is the input to lex. Running make with the Makefile will use lex to create scanner.c and compile this to produce an executable named scanner. Invoking this with a simple file input will produce this session. Now look at the directory anacondaScanner that we have provided with a stub scanner.l and a sample input file and a session that should be produced using that sample input. For your convenience, both of the directories simplescanner and anacondaScanner are available as the tar files: anacondaScanner.tar and simplescanner.tar. Extra Credit (10 points)(A slight variation on what we talked about in class:) Design a DFA that will recognize acceptthe regular expression:(Note that ε (epsilon) means the empty string.) What to submitSubmit three files to the hw3 project via the submit system on gl:

CMSC 331 — Spring 2013
CMSC 331  CSEE  UMBC