Harvey Mudd College
Computer Science 131
Programming Languages
Spring Semester 2000

Homework 01

Parsing - Part 1

DUE DATE:

Thursday, March, 23 2000 at 5PM.

PURPOSE:

To familiarize you with some of the technical details of parsing.

DETAILS:

Part I: Regular Languages, Regular Expressions, and Finite Automata:

1. Describe, in English, the language accepted by the following DFA:

2. Give a regular expression that describes the same language.

    

3. Give a regular expression for the language of dollar values, written with an optional leading minus (but not plus) followed by an optional leading dollar sign, with required commas used to group the digits in threes, and an optional final three characters consisting of a decimal point and two digits (for the cents). (I.e., -$12,345.67 and 1,234,567.89 and 12.34 and -12,345 are ok, but 12345.67 and 12,345. and 12,345.6 and 123,45.67 are not.)

   Leading zeroes should not be allowed in the dollar part of the value, unless the entire whole dollar part is just a single zero.

4. Draw a DFA for that language.

5. Draw the DFA that accepts strings of decimal digits that represent numbers divisible by 7. (I.e. it should accept 0, 7, 28, 350, etc., and reject 3, 19, 191, etc.)

6. Extra Credit: Give a regular expression for that language.

Part II: Context-Free Grammars and SLR(1) Parsing:

1. Given the SLR(1) parse table for s-expressions given in the handout, parse the string " ( ( ) id ( id ) ) $ ". Show the parse tree constructed for the string and the complete history of the stack.

   To show the stack history, just cross out the elements on the stack as they are popped, but leave them there so that they can be read. That is, I just want a record of the order things were pushed on the stack.