Homework 3

CS536-S24 Intro to PLs and Compilers

Question 1 | Question 2 | Question 3

Question 1

This question concerns the following grammar:

stmt → ID = exp ;
exp → ID tail | ID
tail → + exp | - exp

The terminal symbols are ID, =, ;, +, and -

Part a

Convert this grammar to CNF (Chomsky Normal Form).

Part b

Using your grammar from Part a, run the CYK algorithm covered in class to parse the input a = b + c - d; (i.e., fill in this parse table).

Question 2

Suppose that your grades are kept in a file with the following format:

• The file contains one or more student records.
• Each student record has one student's name, then their ID number, then zero or more grades, separated by commas.
• Each grade is an integer value followed by zero or more stars (to represent the number of days late).

This being a course on compilers, the TAs decided to write a parser to read the grades, making it easy to summarize. Here's a CFG for the grade file format that they came up with. The grade file is updated after every assignment is graded.

file → record tail
tail → file | ε
record	→ NAME IDNUM optGrades
optGrades → grades | ε
grades → oneGrade | oneGrade COMMA grades
oneGrade → INTLIT optLate
optLate → stars | ε
stars → STAR | stars STAR

Part a

Although the grade file CFG given above is not LL(1), some correct inputs can be parsed by a predictive parser. This is because those inputs never cause the parser to look at a table entry that contains two or more CFG rules.

1. Give the shortest such grade file input (as a sequence of tokens, ending with EOF).
2. Draw the parse tree that the parser would build for the input you gave for Part (i). (Do not include the EOF token in the parse tree.)

Part b

The TAs ran into problems parsing this file at some point in the course because the CFG is not LL(1). What is the earliest point in the course at which the parser broke (i.e., a sequence of tokens that is a prefix of a valid input, but for which the parser would not know how to continue to build the parse tree top-down because it looks at a table entry that contains two or more CFG rules)? To answer this question, give all of the following:

1. The sequence of tokens (a prefix of a valid input).
2. The (partial) parse tree that the predictive parser would have built before being stumped.
3. The CFG rules that the predictive parser can't choose between to continue to grow the parse tree.

Part c

One problem with the grade file CFG is that it has not been left factored. Find the CFG rules with a common prefix and transform them by doing left factoring.

Part d

Another problem with the grade file CFG is that is has immediate left recursion. Find the CFG rules that cause this and transform them to remove the left recursion.

Question 3

This question concerns the following grammar:

program → { stmts } EOF
stmts → stmt stmts 
      | ε
stmt → ID = exp ; 
     | IF ( exp ) stmt 
exp → ID tail
tail → + exp 
     | - exp 
     | ε

Compute the FIRST and FOLLOW sets for the non-terminals of this grammar.

Last Updated: 3/7/2024     © 2024 CS 536