Rules:

• You may discuss concepts and design issues of the questions below with your classmates.
• You may bounce ideas for your solutions off your classmates, and ask for their critical advice.
• Questions of the above sort should be of the form "what do you think of this idea" and not "how do I do this" or "how do I get started"?
• You must give credit to those who have given you critical feedback.
  • Cite them (by name) on the exam paper you turn in, and
  • credit them for the help they have given you.
• By turning in this exam, you acknowledge that you have:
  • abided by the above rules
  • abided by the statement of academic integrity, except as relaxed by the above rules, and
  • not done anything sneaky (seriously, just ask if you're unsure).

OK here goes.

Exam Questions

1. [20 points] The recognition and treatment of comments in programming languages is typically handled by the scanner and not the parser. For example:

   // This is a comment
   int foo;  /* This is another comment */
   

   Why should comments be handled by the scanner and not the parser? Specifically, how would comments for Java be handled in a parser (instead of the scanner) using a context-free grammar?
2. [20 points] When a web browser fetched a page (URL), the contents of that page is parsed and the results are shown on the screen. If the page's contents has a syntax error in its HTML text, no error is reported by your browser when the page is fetched. For example, this page has many HTML syntax errors and problems. Why does your browser not complain? What are good design goals for a browser that must handle bad HTML?
3. [60 points] On the other hand, this site will validate an HTML page.
   1. [5 points] Try it out: What happens when you run the page on
      • www.google.com?
      • itself? (W3C Markup Validator)
      • the WUSTL home page
      • my bad page
   2. [55 points] Suppose you are asked to write a scanner and parser for HTML that should accept at least the HTML that comprises the page you are now viewing: (If you need a quick guide to the language, try the bare bones guide).
      1. [10 points] What are the classes of tokens (the terminal alphabet) you would use to parse HTML?
      2. [5 points] What are the regular expressions for finding those tokens? (You need not create a working scanner for this exam.)
      3. [10 points] Write a context-free grammar for this subset of HTML (the one that includes at least the markups for the page you are now viewing, and turn that in as part of this problem.
      4. [10 points] Is your grammar suitable for recursive-descent parsing? (It need not be suitable, don't go to trouble to make it suitable). Specifically, why is it suitable or not suitable?
      5. [5 points] Run the grammar you wish to turn in through CUP, and turn in the state dump from CUP. Notes:
         • You need not create a working parser for this exam, but your grammar must be processed by CUP.
         • You can run CUP by yourself as a jar file, or use the studio setup and supply the grammar file to CUP that way.
      6. [15 points] Is your grammar ambiguous? If so, show one string that has more than one parse. If it is not ambiguous, was your grammar acceptable to CUP? If not, explain why.