CS 525 -- Assignment Two

Due Tuesday, June 12th @ 5pm in CS Homework Station

 

Homework Guidelines

Submission Instructions: Please hand in a hard copy of your solutions to all problems, with a suitable cover page with your name, the date, the course, and the number of the assignment. Do each problem on a separate sheet clearly labelled at the top (e.g., "Problem 3"), and staple all pages together in the upper-left-hand corner (do NOT submit solutions separately or update your solutions after handing in your assignment). For any problem statement that asks multiple questions, answer each in a separate paragraph, labelled (1), (2), etc. Submit "pencil and paper" problems into the CS 2525 mail slot (not the shelf) in the CS homework station; submit code or files produced by software using Gsubmit as specified on the course home page. A small penalty will be taken for any homework that does not follow these guidelines.

Late Policy: Both parts of the homework (pencil and paper, and electronic submission) are due at 5 pm the due date; late homeworks will be penalized at the rate of 25% for each weekday late (each day ending at 5pm, weekends not included).

Policy on Academic Honesty: Please see the end of this homework for comments on the University policy for academic honesty that I adhere to.

 

Problem 1 (5 pts)

  1. For the following grammar and string, show the parse tree, right-most derivation, and left-most derivation (this is the language of Lisp S-expressions):

    2. S --> E
    E --> id
    E --> ( L )
    L --> E L
    L --> epsilon

    String: ( id ( id ) id )

Problem 2 (5 pts each)

  1. Give a grammar generating the language uwuw' over the alphabet {a, b}, where u is of length 2, and w' is the reverse of the string w. Note that u is the same string in both occurrences.
  2. Give a grammar for the language of palindromes over the alphabet {a, b} (i.e., strings that read the same forwards as backwards).
  3. Give a grammar for the language which is the complement of the language in question 3 (i.e., non-palindromes). Hint: think about creating a palindrome, and then making sure that it goes wrong at some point.

Problem 3 (35 pts)

  1. (1) Construct First() and Follow() sets for all non-terminals in the following grammar:

    S --> A | BCD
    A --> BBA | EB
    B --> bEc | BC | BDc | epsilon
    C --> c | epsilon
    D --> a | BDb
    E --> a | bE | epsilon

  2. Construct an SLR(1) parser for the following grammar:

    S --> E
    E --> E + T
    E --> T
    T --> T * F
    T --> F
    F --> ( E )
    F --> id

  3. Show the actions for the SLR(1) parser just constructed when accepting the string ( id * id ).

Problem 4 (20 pts)

Try to build an SLR(1) parser for the following grammar:


E -> E + E | E E | E* | a | b

(This is the language of regular expressions over { a, b }, where + is disjunction.) Is it possible to resolve all shift/reduce conflicts by hand, as discussed in class, to come up with a parser which correctly parses strings so that disjunction and concatenation is left-associative, and where Kleen start is of the highest precedence, concatenation is next, and disjunction is lowest?? Be as specific as possible, in the positive case showing precisely how to resolve the conflicts, and in the negative case providing an argument as to why it is not possible.

Policy on Academic Conduct

Whenever you submit a piece of academic work and sign your name to it, you are verifying that this work is the result of your own intellectual efforts; it is Plagiarism to submit work solely under your own name in which:

In this course, I will not allow you to submit any joint work, although in other courses and in other contexts you may be permitted to do this. In general, you must always provide proper attribution of authorship by naming all persons, books, or resources that provided intellectual content towards the final result. In some cases, you will need to describe the extend of the contribution, particularly when literally copying the words or artistic artifacts of another. To fail to provide proper attribution is plagiarism. Plagiarism demeans the seriousness of what we do in class, and does not allow you as a student to obtain a fair grade for the results you worked hard for.

I will discuss the issue of plagiarism with the grader, and use, when appropriate, automated tools to check submitted programs and files for copying. I don't like to be involved in this, but it is necessary in order to provide a fair environment for your work. In cases of suspected plagiarism, I will discuss the matter with the student(s) involved and, when warrented, submit the case to the Academic Conduct Committee (of which I was chairman for three years). Unfortunately, students in my classes violate these policies several times a year on average; it is my hope that by being completely clear and straight-forward about my policy that I can reduce this number. Please take this issue serious and talk to me if you have any concerns or questions.