Assignment 3: yacc

Due Thursday, Oct. 23rd

Problem 1.

Write the grammar, lex, and yacc program for the following language of strings: Operations (explained by example) The language allows arbitrary nesting of the operations. For instance, the following program

ADD (REVERSE "ccay"), (LOWERCASE (ADD " IS", (CAPITAL "cOOL")))

produces the string "yacc is cool". Parentheses are required in the language. You may copy and use the files str and str.y in ~elenam/pub/4607 on epoxy which have some initial lex and yacc definitions for this problem.

Problem 2.

Write a yacc program to replace all for loops in a Java program by the corresponding while loops as follows: 

for (<initialization> ; <condition> ; <increment>) {
    <body>
}
rewrites to 

<initialization> 
while (<condition>) {
    <body>
    <increment>
}
Note that the condition part of a for loop cannot be empty, but the other two components can. For simplicity you may assume that the body of a for loop is always surrounded by braces.

Write a simple lex program that will be able to find necessary elements to recognize a for loop. Everything else (numbers, identifiers, punctuation symbols, etc) should be denoted by a token other which returns the value of yytext as a string.

Important note: you don't need to check the program for syntactic correctness. The initialization, the condition, the body, and the rest of the program surrounding the for loop may be complete gibberish, they should be left unchanged. However, your parser must handle nested for loops correctly.

Test your solution on any 2-3 Java programs with a few for loops in each.

Problem 3.

Consider expressions over integer numbers with two operations ! and ? defined as follows: The operations have the following properties:
  1. ! is right-associative, i.e. x ! y ! z is interpreted as x ! (y ! z).
  2. ? is left-associative, i.e. x ? y ? z means (x ? y) ? z.
  3. ! takes precedence over ?
  4. Parentheses are used to specify the non-default order of operations.

Question 1

Draw parse trees and compute the values of the following:
  1. 3 * 2 ? 4
  2. 2 * 3 * 4 ? 1
  3. 2 ? (3 ? 4) ! -1 ? 2

Question 2

Write the grammar for such expressions and implement it using lex and yacc. Helpful reminder: there are no variables in the language, only integer numbers.

Test your program at least on the examples given in Question 1.

This page is a part of CSci 4607 course at UMM.