Studio 4 25 February 2008

CSE 431S (Spring 2008)

Studio 4: Give me Ambiguity or Give Me Something Else

Studio Sessions Overview:

We gather as a community in studio session to learn from each other. Our community includes:
- Instructor
- TAs
- Students
Our community is egalitarian in terms of learning: all of us will have questions and all of us should try to provide answers.
The idea is to challenge each other and to share what we discover.
You are free (downright encouraged) to collaborate in this session:
- Primarily within your small group of 2-3 people
- Secondarily with any group in the class
- As much as you like with the instructor and TAs
In studio, the instructor's mission is to observe, interact, and work with groups.
- How you think, work, and arrive at a solution is more important than getting the right answer. Thus, the instructor and TAs will observe you throughout the exercise and offer constructive feedback.
- The help you receive may be incomplete at any given time, so that you can work through more of the solution on your own. Do not hesitate to ask for more help.
In studio, the student's mission is to acquire new knowledge and skills by the collaborative solving of problems.
- You are not graded on whether you get wrong or right answers on this exercise.
- You are graded on your level of participation in studio.
Participation is defined as
- Asking questions, at any level, of any person in the studio
- Discussing possible solutions with people in the studio
- Helping somebody in the studio solve a problem
- Presenting or demonstrating your solution to people in the studio
- Documenting your group's experiences in studio
Please eliminate external stimuli (cell phones, IM, Facebook) during studio. Please devote yourself to learning, mastering, and extending the material for the session.

The results of your studio session are to be reported and documented in a file that you save in your workspace. You are to print and turn in one copy of that report for your group. In the descriptions of the studio exercises, verbs like report and document are indications of activities you should summarize and discuss in your report.
In your groups, take turns documenting results, looking over shoulders, and staffing the keyboard.
It is unacceptable to copy anything without understanding it. At any point, the TA or instructor can point to something you've done and ask you why it works, or change it and ask what would happen with the modification.

In each of the following sections, go as far as you can in the time allotted, but move on to the next section so you'll have a chance to work on each section while in studio.

Warm Up: (10 minutes)

Read/review the following
- If CUP can successfully generate a parser for your grammar, without issuing any shift/reduce or reduce/reduce conflicts, then your grammar is unambiguous and is suitable for deterministic, bottom-up parsing with one symbol of lookahead.
- If not then one of the following must be true:
  - Your grammar is ambiguous. Then there must be some string for which (at least) two distinct parses can be generated. Look at a conflict state and try the actions that are under conflict. If you can work your way to a valid sentential form -- a sequence of symbols that can be generated from the goal symbol -- using the conflicting actions, then the grammar is ambiguous. Line up the dots in the conflicting state, and try one action above and one action below. Keep extending left and right until you arrive at the same sequence of symbols that can be derived from the goal symbol both above and below.
    
    As a group, come up with a simple example of an ambiguous grammar. Please keep your terminals in the alphabet {a,b,c,d,e}. Share this with the group next to you and with the TA or professor to make sure you're in the right track.
    Enter your grammar into cup0 and run the build.xml file. Look at the states in cup0.states and verify the ambiguity using the lined-up dots method.
  - The grammar is not ambiguous, but
    - No predeterminable amount of lookahead can resolve the conflict, or
    - A certain amount of lookahead can resolve the conflict.
      - More than one symbol is needed (CUP tries just one), and/or
      - States need to be split to keep track of item-specific lookahead.
Open the CUP User Manual for quick reference.
Open eclipse and carefully follow the following steps. If these steps do not work for you, switch to a new workspace and try again.
Import (File..Import) this zip file using the Existing projects into workspace method (Do not choose the archive file method). After clicking on "Existing projects into workspace" select, as the archive file, the file you downloaded earlier.
Open Main.java as you will have to uncomment some things to test. Don't uncomment anything yet, though.
Right-click on the build.xml file and run it as an Ant Build...
- In the dialog for this, be sure that the JRE tab has the build running in the same JRE as the workspace. You should also arrange for the workspace to be refreshed after the build.
The build should work and you should see the output from running all of the parsers in the console window.

Hereafter, you can run this build by clicking on the arrow with the red toolbox.
This should produce some output in the console window. Not much will be working at this point, and most runs will die in CUP showing Java Error: 100

Main Problems

cup0: This is a short grammar you'll type in yourself by now, having followed the warm-up instructions above.
cup1: Follow the instructions in the grammar file -- be sure to check your work with another group and the TA or prof.
cup2: Follow the instructions, ask questions as needed, check your answers with other groups and the TA or prof.
cup3: Some lines of this file are NOT to be modified -- check this out before you start changing things. Follow the instructions, but ask questions and check your work as you go with others.
cup4: Same deal -- ambiguous, not? Figure it out and fix it up
cup5: I don't expect anybody to get this far, but if you do, this is part of Lab 3. Take a look and talk about it if you have time. We'll work more on it next studio.

Finally

Be sure to submit the following before leaving studio:

A printed copy of your cup files
A printed copy of the console run on all the grammars and test files.

Last modified 16:07:23 CST 25 February 2008 by Ron K. Cytron

CSE 431S (Spring 2008) Studio 4: Give me Ambiguity or Give Me Something Else

CSE 431S (Spring 2008)

Studio Sessions Overview:

Warm Up: (10 minutes)

Main Problems

Finally

CSE 431S (Spring 2008)

Studio 4: Give me Ambiguity or Give Me Something Else