Homework 5

This is the archived website of SI 413 from the Fall 2012 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Use a separate sheet of paper for your answers! Everything should be submitted in one packet, all printed out for me to see.

1 Homographs and Synonyms

Pick a pair of two programming languages that you know, and come up with an example of each of the following:

  1. A homograph is a code fragment that is the same syntactically between the two languages, but has different semantics in each..
  2. A synonym is a code fragment that is the same semantically between the two languages, but has different syntax.

2 Scanner DFA

Draw the DFA for the scanner that accepts the following tokens (as specified by regular expressions). Label accepting states with the name of the token.

FLOAT: [0-9]*"."[0-9]+
  INT: [0-9]+
RANGE: [0-9]+":"[0-9]+
  HEX: 0x[0-9a-f]+

(Remember, a + means "one or more of the previous thing", and a * means "zero or more of the previous thing". Square brackets [] indicate a range of characters (or multiple ranges), and anything in quotes "" means that literal character.)

3 Modified Scanner

Now suppose we want to add a new token OCT to the language above, matching the regular expression 0[0-7]+ (that is, a zero followed by one or more digits between 0 and 7).

  1. Draw the modified DFA that includes this new token. (Don't just modify your picture from the previous problem, draw a new one.)
  2. Compare the work you had to do for (a) to the changes you would have to make to the specification for an automatic scanner generator like flex.

4 Modifying a Grammar

The following grammar is ambiguous (in terms of parsing), but it still defines a language:

S → exp
exp → exp OPA exp
exp → NUM

Write a new grammar for the same language which is unambiguous and would work well for top-down parsing. (In particular, your new grammar should be LL(1).)

5 Top-Down Parsing

Using your modified grammar from the previous problem, draw the parse tree that would be generated by a top-down parser for the following string:

53 + 89 - 103

6 PREDICT and FOLLOW

  1. Give the PREDICT and FOLLOW sets for your modified grammar from two problems ago.
  2. State how these would be used to create a recursive-descent parser.
  3. State how these would be used to create a table-driven top-down parser.