Assignment #2

Due Date: Tuesday, July 3, 2007, before or on 3:00 PM
Submission Requirements:

• computerized (word-processor-application-generated)
• printed in short bond paper
  
• text uses:
• font: Garamond
• size: 12 pt.
• source code uses:
• font: Courier
• size: 10 pt.
• including your test suite (input/output)

PROBLEM:
Write a lex program and definitions named regular expressions for floating point numbers with optional decimal point and exponent.

Test your program with inputs and outputs.

Assignment #1

1. Identify the lexemes that make up the tokens in the following program. Give reasonable attribute values for the tokens.

int max(int i, int j)
/* return maximum of integers i and j */
{
return i > j ? i : j;
}

2. Describe the languages denoted by the following regular expressions:

• 0(0|1)*0
• ((epsilon|0)1*)*
• (0|1)*0(0|1)(0|1)
• 0*10*10*10*
  

3. Write regular definitions for the following languages.

• All strings of letters that contain the five vowels in order.
• All strings of letters in which the letters are in ascendinglexicographical order.
• Comments consisting of a string surrounded by /* and */ without anintervening */ unless it appears inside the quotes " and ".
  

4. Write down the shortest five strings in the following languages (E is empty).

• (nerk | bob)(s | sled)
• a(ab) * | E
• (f | E)(i | E)(s | E)(h | E)

5. Bracket the regular expression aab*|b.
6. Write a regular expression giving all strings of a's and b's with exactly two a's.

The Dragon Book

Download

• Compilers: Principles, Techniques and Tools
  

New Schedule

The schedule for the lecture is temporarily moved because of unavailability of rooms. See below.

OLD Schedule

Days: Tuesday/Friday
Time: 09:00 ~ 10:30 AM
Building - Room: COE - Rm. TBA

NEW Schedule

Days: Tuesday/Friday
Time: 03:00 ~ 04:30 PM
Building - Room: COE - Rm. TBA

The class will meet on Friday, June 22, 2007.

Machine Problem #1

Due Date: Wednesday, June 27, 2007, before or on 3:00 PM
Submission Requirements:

• computerized (word-processor-application-generated)
• printed in short bond paper
  
• text uses:
• font: Garamond
• size: 12 pt.
• source code uses:
• font: Courier
• size: 10 pt.
• including your test suite (input/output)
  

PROBLEM:
Write a program that will act like a scanner using the C representation below. Test your program with the following inputs:

1. mid = (hi + lo) / 2;
2. degc = (degf - 32) * (5.0 / 9);
3. your sample 5 inputs.

REPRESENTING TOKENS IN C

typedef enum {
   IDENT, INT_CONST, BINOP, LEFTPAREN, . . .
} TokenKind;

typedef union {
   char *name;
   int int_const;
   . . .
} TokenValue;

typedef struct {
   TokenKind kind;
   TokenValue value;
} Token;

Schedule

LECTURE

Days: Tuesday/Friday
Time: 09:00 ~ 10:30 AM
Building - Room: COE - Rm. 317

LABORATORY

Days: Wednesday
Time: 12:00 ~ 03:00 PM
Building - Room: COE - Computer Laboratory 1

Course Syllabus

COURSE NUMBER: 153
TITLE: Assemblers, Interpreters and Compilers
CREDITS: units
SEMESTER AND SCHOOL YEAR: Semester, S.Y. 2007-2008
INSTRUCTOR: Mr. Cyrus G. Gabilla

Prerequisites
You must be familiar with a high level block-structured language. If you are not proficient in C or C++ then you must be prepared to learn it quickly. You should understand general programming concepts (e.g., recursion, parameter passing). You should have experience using data structures such as pointers, linked lists, trees, hash tables, and stacks.

Goals
Satisfactory completion of this course requires demonstration of the following skills:

• understand syntax directed programs,
• be able to construct a lexical analyzer (scanner) using regular expressions and a scanner generator tool,
• be able to construct a parser from a context-free grammar and a parser generator tool; and
• be able to construct and use a symbol table to support the parsing of context sensitive constructs.

Theoretical Component
The theoretical component provides an opportunity to acquire the domain knowledge and to demonstrate comprehension of and the ability to apply the acquired knowledge through problem sets, papers/reports, tests, and presentations and/or interviews.

Practical Component (labs and projects)
The practical component involves both interpersonal and communication skills for effective teamwork and an opportunity to demonstrate the design and collaboration skills necessary to analyze a problem, create and evaluate alternative designs, and implement a solution to the problem.

GRADING CRITERIA
Theoretical Component

• Homework/Problem Sets 20%
• Report/Exams/Quizzes 30%
  

Practical Component

• Project/Laboratory 40%
• Attendance 10%
  

TEXTBOOK
Compilers: Principles, Techniques and Tools, Aho, Sethi, and Ullman, Addison-Wesley, 1986

OTHER RESOURCES

• Compiler Construction using Flex and Bison, Anthony Aaby, 1996 (http://cs.wwc.edu/~aabyan/464/Book/index.html)
• A Compact Guide to Lex and Yacc, Tom Niemann (http://epaperpress.com/lexandyacc/index.html)