CS 441G - Compilers for Algorithmic Languages
Credits: 3
Course Description
The techniques of processing, specifying, and translating high-level computer languages are studied. Topics include finite state machines and lexical analysis, context-free grammars for language specification, attributed translation grammars, language parsing, and automatic generation of compilers by SLR, LALR, and other methods for analyzing context-free grammars. Other topics may include code optimization, semantics of programming languages, and top-down parsing.
Prerequisites: CS-315 and engineering standing.
Needed Skills
Knowledge of a programming language such as C or C++, data structures, and machine organization.
Learning Outcomes
Students will learn how a compiler for an algorithmic language is organized, designed, and constructed. Specifically, students will learn how to
1. specify lexigraphical constructs describing elements of algorithmic languages.
2. specify parsing elements for algorithmic languages.
3. use regular expressions to simplify compiler generation.
4. design and implement a complete algorithmic language compiler.
5. use compiler generator tools such as lex and yacc.
6. organize memory for both static and dynamic data types, including complicated structures and data classes.
7. generate a parse tree that can be optimized before code generation.
8. generate translated code from the parse tree.
9. document a very complex programming project, including documenting what works and what does not or is not yet implemented.
Measures
These nine specific topics will be used to measure students as applied to a three part project that creates a comprehensive compiler (lexer, parser, and code generation), simple homework assignments, and possibly quizzes and/or a final examination. Topic 9 will allow the student to honestly reflect on the state of his or her project.
CAC Categories
Topic
|
Core
|
Advanced
|
Math
Fundamentals
|
0
|
0
|
Data
Structures
|
10
|
0
|
Algorithms
& Software Design
|
15
|
0
|
Computer
Organization and Architecture
|
10
|
0
|
Concepts
of Programming Languages
|
3
|
0
|
Social
and ethical issues
|
2
|
0
|
Total
|
45
|
0
|
Math Fundamentals (0): Standard arithmetic precedence must be used.
Data structures (10): Core (10): A multilevel symbol table, parse tree, and memory layout after translation must be designed and used.
Algorithms and Software (15): Core (15): Design of a large, multi-module translation system using multiple software tools, programming techniques, and algorithms; multilevel name storage/retrieval; parse tree creation/walking; final code optimization.
Computer Organization and Architecture (10): Core (15): Translate from a high level, algorithmic language to a machine language
Concepts of Programming Languages (3): Core (3): Understanding of languages for translational purposes
Social and ethical issues (2): Compilers that produce erroneous translations can cause serious problems. Who is responsible and possible social or ethical issues that can arise will be discussed. The self evaluation will teach students how to honestly offer to peers the status of a very complex project.
Oral Communication (presentations)
None required, but class participation is desired.
Written Communication
Students must be able to document a very complex set of computer programs and inputs to software tools that generate computer programs. A document must grow and evolve over the course of the semester that reflects what works and what does not or is not implemented.
Coverage
Theoretical content: 35%
· Lexers
· Parsing algorithms
· Memory organization for data (simple and complex objects)
· Code objects
· Code optimization.
Problem analysis: 15%
· Determine how complex of a compiler to implement, including language elements
· Code optimization
· Multilevel memory object usage.
Solution design: 50%
· An entire compiler.
Student evaluation and feedback
Students are evaluated on their work. Students receive back all of their work. Any papers are marked to indicate problems and they point out correct or better solutions. All work is discussed in detail in class.
Course Evaluation Questions
The course has helped me:
37. Learn how to write a regular expression.
38. Generate a lexer.
39. Generate a parser.
40. Write a code generator.
41. Design and write a complex programming project.
42. Document a large programming project, including what works and what does not or is not implemented.
Possible Textbooks
1. C. C. Douglas, Compilers for Algorithmic Languages, http://www.MGNet.org, Cos Cob, CT, 2nd Edition, 2004.
2. John R. Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly & Associates, 1992. ISBN: 1565920007.
3. Kenneth C. Louden, Compiler Construction: Principles and Practice, PWS Publishing Co., 1997