Announcement!

Deadline of the Requirements

• Submit all your requirements not later than October 17, 2007.
  
• Submit also your softcopy with an executable file to cgabilla@gmail.com. Follow this title format to your e-mail: GABILLA, CYRUS:Calculator with variable assignment
  
• Late submission will not be accepted and has a grade of ZERO.
  

Final Exam Schedule

• October 16, 2007, 3:00-4:30 PM, 3FCOE
• Coverage of the exam will be taken from your reports.

Good Luck!

Midterm Activity: Reporting

This reporting activity is worth 100 points. This is a no report no grade policy. This activity will start on August 21, 2007. There will be no any extension of date for the given schedule.

Every group (reporter) must provide handouts/materials for their classmates and for their instructor. Handouts for the instructor must have a cover page, member's assignment and other important information. Both handouts should contain the main topic, exercises & answers, and references.

The group can use the board, manila paper or other materials to present their topic in an orderly manner.

The following are the list of the reporters in ascending order:

1. Reporter No. 1
• Topic: Context-free Grammars
• Examples, Notation, Derivation Steps, and Parse-tree
• Give assignment
  
• Member: Farrell John Conejos
2. Reporter No. 2
• Topic: YACC
  
• Tokens, associativity and precedence
• Examples of YACC programs
• How to use YACC?
  
• How to use YACC with Lex?
• Give assignment (written or programming)
• Member: Arnold Jansen U. Tupac
  
3. Reporter No. 3
• Topic: Parsing Algorithms
• Types of Parsing Algorithms
• Examples of the Parsing Algorithms
• Give assignment (written or programming)
  
• Members: James S. Bolongan & Mary Jane A. Par
  
4. Reporter No. 4
   
• Topic: Attribute Grammars Part 1
• Synthesized and Inherited Attributes
• Symantic Rules
• Dependency Graph
• Attribute Evaluation
• Give assignment
  
• Members: Divine Grace O. Monte & Ma. Adelaida A. Buot
5. Reporter No. 5
• Topic: Attribute Grammars Part 2
• S-attributed Definitions and Examples
• YACC Examples
• Building Abstract Syntax Trees
• Constructing Syntax Trees
• Syntax DAG (Directed Acyclic Graph)
• Constructing DAG
• Give assignment (written or programming)
  
• Members: Jerry S. Oriente, Ken Rothwyn M. Mira, & Charlie Louie E. Luna

Assignment #4: Minimizing DFA

Due Date: August 3, 2007

EXERCISES

1. Construct DFA's for the regular expression "(a|b)*abb(a|b)*" using Algorithm 3.5 (Construction of a DFA from a regular expression r).

2. Minimize the states in the DFA's of Exercise 1 using Algorithm 3.6 (Minimizing the number of states of a DFA).

Laboratory Exercises Listing and Download

Click to download laboratory exercises from 1 through 4:

• Laboratory No. 1 - Writing a Simple Scanner.pdf

• Laboratory No. 2 - Patterns and Lexical Analysis.pdf

• Laboratory No. 3 - Programming Using LEX.pdf

• Laboratory No. 4 - Regular Expression to Deterministic Finite Automata.pdf

Groupings and Guidelines: Laboratory No. 4

Here are the list of groupings for the Laboratory No. 4:

Group No. 1
Bolongan, James S.
Conejos, Farrell John T.
Mira, Ken Rothwyn M.

Group No. 2
Buot, Ma. Adelaida A.
Luna, Charlie Louie E.
Monte, Divine Grace O.

Group No. 3
Oriente, Jerry Paulo S.
Par, Mary Jane A.
Tupac, Arnold Jansen U.


Guidelines:

• Deadline for this machine problem will be on August 15, 2007.

• Each of the group will submit a hard copy of the source code written in their chosen programming language with a documentation. The documentation must explain the semantic of every class, method, function and any part of the source code.
• Hard copy specification:
• computerized (word-processor-application-generated)
• printed in short bond paper
  
• text:
• font: Garamond
• size: 12 pt.
• source code:
• font: Courier
• size: 10 pt.
• test suite (input/output) with at least 10 examples

• The group will defend their work. If no member could answer the questions given, a point will be deducted from the total score.
• The group will prepare a presentation. It should be created in OpenOffice.org Impress.
• Each of the member of the group will present and will be asked.

Deadline: Laboratory No. 3

Deadline for the submission of Laboratory No. 3 will be on July 31, 2007.

No submission will be accepted beyond that date and will be given a score of zero.

First Preliminary Examination 2

Our preliminary exam this coming Friday, July 20, 2007 is moved on July 24, 2007. We still don't have a class this coming Friday.

First Preliminary Examination

The CSc 153 class will not meet on Tuesday, July 17, 2007.

CSc 153's first preliminary exam will be on Friday, July 20, 2007. Bring your own test booklet, ball pen (black or blue), and extra money for your test questionnaire.

Coverage of the preliminary exam are the following:

• Introduction to Compiling (Chapter 1)
  
• Lexical Analysis (Chapter 3)
• A Simple Compiler (Chapter 2)
  

Possible exam types:

• Modified True of False
• Multiple Choice
• Identification
• Fill in the Blanks
• Enumeration
• Problem Solving

Note: I am not giving you a special exam except for those who have a valid reason.

Lex Example: A C Comment Recognizer

The following is a lex program that will recognize a multi-line comment in C:

---Program Starts Here---

%option noyywrap

sc        "/*"
ec        "*/"
string    \"[^"]*\"
inside    [^*]|"*"[^/]|{string}
comment    {sc}{inside}*{ec}

%%

{comment}    {    printf("<<<%s>>>", yytext);    }
.            {    printf("%s", yytext);    }

%%

int main ()
{
 yylex();
 return 0;
}

---Program Ends Here---

Note: Check your google group. I uploaded the flex and bison binary files.

Assignment #3

Points: 20 pts.
Due Date: July 10, 2007/3:00 PM

RE = (ab|ba)[c-z0-9]*(ab|ba)

1. Create a nondeterministic finite automaton or NFA that will accept a string that is a member of the language generated by L(RE).

2. Convert your NFA N from your exercise 1 into an equivalent DFA D.

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)