Difference between revisions of "Compiler Construction With Embedded Xinu"

From Embedded Xinu
Jump to navigation Jump to search
(Created a page for the compiler course with XINU. NOTE: this page is NOT DONE! i'm just saving what I've written so far)
 
(not finished yet...)
Line 9: Line 9:
  
 
=== Topics ===
 
=== Topics ===
*  
+
* Lexical Analysis
 
+
* Syntax Analysis
* Overview of operating systems
+
* Semantic Analysis
* Operating system principles
+
* IR Translation
* Concurrency
+
* Instruction Selection
* Scheduling and dispatch
+
* Register Allocation
* Memory management
 
* Device management
 
* Security and protection
 
* File systems
 
* Evaluating system performance
 
  
 
=== Learning Objectives ===  
 
=== Learning Objectives ===  
* Recognizing various classes of grammars, languages, and automata.
+
* Recognize various classes of grammars, languages, and automata, and employ these to solve common software problems.
* Ability to use existing compiler tools to scan and parse source code into abstract syntax trees.
+
* Explain the major steps involved in compiling a high-level programming language down to a low-level target machine language.
* Implementing a type-checker that enforce the type rules in a given grammar.
+
* Construct and use the major components of a modern compiler.
* Translating an abstract syntax tree into an intermediate representation ready for assembling.
+
* Work together effectively in teams on a substantial software implementation project.  
* Understanding the principles and techniques behind register allocation.
 
*
 
  
* Discuss the history of operating systems.
+
== Potential Course Structure ==
* Overview of the general and specific purpose of an operating system.
+
The course outlined below describes a compiler construction course focusing on a semester long project in which students build most of the pieces of a complete working compiler. For this example course we take the compiler project from Appel and Palsberg's [http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=052182060x Modern Compiler Implementation in Java] [[Compiler Construction With Embedded Xinu#References|[2]]] and modify it to target a MIPS platform running the Xinu operating system.
* Understanding concurrency and state flow diagrams.
 
* Understanding deadlock and starvation.
 
* Ability to decipher between scheduling algorithms.
 
* Understanding the use of memory and virtual memory.
 
* Characteristics of serial and parallel devices.
 
* Deciphering the concepts behind various file systems
 
* Understanding the necessity of security and locating potential system security holes
 
  
== Potential Course Structure ==
 
An Operating Systems course using the below course outline or something similar will introduce students to some fundamental concepts of operating systems combined with the basics of networking and communications. Topics include: memory management, scheduling, concurrent processing, device management, file systems, networking, security, and system performance. A similar course structure is followed by [http://www.mscs.mu.edu/~brylow Dr. Dennis Brylow] at Marquette University in his sophomore level Operating Systems course. Most of the assignments where students are building Embedded Xinu are done in teams of two.
 
 
===== Course Outline =====
 
===== Course Outline =====
 
{|
 
{|
| Week || || || Topics || || || || Assignments Track One || Assignments Track Two
+
| Week || || || Topics || || || || Assignments Track One  
 
|-
 
|-
| 01 || || || C (basics) and OS Structures, Processes || || || || [[Assignment: C Basics|C Basics]] || [[Assignment: C Basics|C Basics]]
+
| 01 || || || Introduction || || || || Project 1: Interpreter
 
|-
 
|-
| 02 || || || C (functions, control flow) and Processes ||  
+
| 02 || || || Lexical Analysis, Automata || || || || [[Assignment: Scanner|Project 2: Scanner]]
 
|-
 
|-
| 03 || || || C (pointers, arrays, structs) and Threads || || || || [[Assignment: C Structs and Pointers|C Structs and Pointers]] || [[Assignment: C Structs and Pointers|C Structs and Pointers]]
+
| 03 || || || Syntax Analysis, Grammars || || || || [[Assignment: Automata and Grammars|Homework 1: Automata and Grammars]]
 
|-
 
|-
| 04 || || || CPU Scheduling || || || || [[Assignment: Synchronous Serial Driver|Synchronous Serial Driver]] || [[Assignment: Synchronous Serial Driver|Synchronous Serial Driver]]
+
| 04 || || || Parser Generators || || || || [[Assignment: Parser|Project 3: Parser]]
 
|-
 
|-
| 05 || || || CPU Scheduling ||
+
| 05 || || || Abstract Syntax Trees ||
 
|-
 
|-
| 06 || || || Process Synchronization || || || || [[Assignment: Context Switch and Non-Preemptive Scheduling|Context Switch and Non-Preemptive Scheduling]] || [[Assignment: Context Switch and Non-Preemptive Scheduling|Context Switch and Non-Preemptive Scheduling]]
+
| 06 || || || Semantic Analysis || || || || [[Assignment: Semantic Analysis|Project 4: Semantic Analysis]]  
 
|-
 
|-
| 07 || || || Deadlocks || || || || [[Assignment: Priority Scheduling and Process Termination|Priority Scheduling and Process Termination]] || [[Assignment: Priority Scheduling and Preemption|Priority Scheduling & Preemption]]
+
| 07 || || || Activation Records ||
 
|-
 
|-
| 08 || || || Main Memory and Virtual Memory ||   
+
| 08 || || || IR Translation ||   
 
|-
 
|-
| 09 || || || File System Interface || || || || [[Assignment: Preemption and Synchronization|Preemption & Synchronization]]
+
| 09 || || || Basic Blocks || || || || [[Assignment: Translation|Project 5: Translation]]
|| [[Assignment: Synchronization and Interprocess Communication|Interprocess Communication]] or [[Assignment: LL/SC|LL/SC]]
 
 
|-
 
|-
| 10 || || || File System Implementation ||  
+
| 10 || || || Instruction Selection || || || || [[Assignment: Activation Records| Homework 2: Activation Records]]
 
|-
 
|-
| 11 || || || Mass-Storage Structure || || || || [[Assignment: Delta Queues|Delta Queues]] || [[Assignment: Delta Queues|Delta Queues]]
+
| 11 || || ||Liveness Analysis ||  
 
|-
 
|-
| 12 || || || I/O Systems || || || || [[Assignment: Heap Memory|Heap Memory]] || [[Assignment: Heap Memory|Heap Memory]]
+
| 12 || || || Register Allocation ||  
 
|-
 
|-
| 13 || || || Protection, Security and Distributed System Structures || || || || [[Assignment: Asynchronous Device Driver|Asynchronous Device Driver]] || [[Assignment: Ultra-Tiny File System|Ultra-Tiny File System]]
+
| 13 || || || Register Allocation || || || || [[Assignment: Instruction Selection|Project 6: Instruction Selection]]  
 
|-
 
|-
| 14 || || || Distributed System Structures ||  
+
| 14 || || || Advanced Topics ||  
 
|-
 
|-
| 15 || || || Distributed File Systems || || || || [[Assignment: Ultra-Tiny File System|Ultra-Tiny File System]] || [[Assignment: Basic Networking - Ping|Basic Networking - Ping]]
+
| 15 || || || Advanced Topics || || || || [[Assignment: Register Allocation|Homework 3: Register Allocation]]  
 
|}
 
|}
  
 
===== Books =====
 
===== Books =====
*[http://www.os-book.com/ Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, Operating Systems Concepts, 7th Edition, John Wiley & Sons, ISBN #0-471-69466-5.]
+
*[http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=052182060x Andrew W. Appel and Jens Palsberg, Modern Compiler Implementation in Java, 2nd Edition, Cambridge University Press, 2002]
 
 
*[http://netlib.bell-labs.com/cm/cs/cbook/ Brian W. Kernighan and Dennis M. Richie, The C Programming Language, Prentice-Hall, 1978.]
 
  
 
==References==
 
==References==
 
[1] Course topics and learning objectives have been adapted from the ACM's [http://www.acm.org/education/education/education/curric_vols/cc2001.pdf Computing Curricula 2001 Computer Science].
 
[1] Course topics and learning objectives have been adapted from the ACM's [http://www.acm.org/education/education/education/curric_vols/cc2001.pdf Computing Curricula 2001 Computer Science].
  
 +
[2] [http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=052182060x Andrew W. Appel and Jens Palsberg, Modern Compiler Implementation in Java, 2nd Edition, Cambridge University Press, 2002]
 +
 +
[3] A. V. Aho, M. Lam, R. Sethi, and J. D. Ullman. ''Compilers: Principles, Techniques and Tools''. Pearson, 2nd edition, 1985.
 +
 +
[4] S. Muchnick. ''Advanced Compiler Design and Implementation''. Morgan Kaufmann, 1997.
  
 
----
 
----
  
 
<small><small>This work funded in part by NSF grant DUE-CCLI-0737476.</small></small>
 
<small><small>This work funded in part by NSF grant DUE-CCLI-0737476.</small></small>

Revision as of 23:51, 27 July 2010

Overview

Having students construct a compiler which targets a runtime that uses their own, or a provided, Xinu operating system is one of the potential tracks for a professor that is Teaching With Xinu.

Including Embedded Xinu in a compiler construction course allows students to explore the compilation of high level language constructs that rely on interacting with the underlying runtime. Many traditional compilers courses simply target a processor or simulator, but by targeting a platform (a processor and operating system combination) one can extend the source language to include more advanced language features such as I/O operations and thread creation, manipulation, and concurrency. This also allows students to run their test cases on real hardware and see these programs actually interacting with a real runtime. In modern programming these high level language features are vital, and it is important for students to see what the processor and runtime are doing when they use these features in their own programs.

Course Outcomes

Course development can parallel learning objectives and topics associated with many Programming Language Translation or Compiler Construction courses. [1] However, by targeting a platform students can also focus on learning how compilers interact with the runtime to achieve thread concurrency and synchronization; topics which many traditional compilers courses avoid. [2, 3, 4]

Topics

  • Lexical Analysis
  • Syntax Analysis
  • Semantic Analysis
  • IR Translation
  • Instruction Selection
  • Register Allocation

Learning Objectives

  • Recognize various classes of grammars, languages, and automata, and employ these to solve common software problems.
  • Explain the major steps involved in compiling a high-level programming language down to a low-level target machine language.
  • Construct and use the major components of a modern compiler.
  • Work together effectively in teams on a substantial software implementation project.

Potential Course Structure

The course outlined below describes a compiler construction course focusing on a semester long project in which students build most of the pieces of a complete working compiler. For this example course we take the compiler project from Appel and Palsberg's Modern Compiler Implementation in Java [2] and modify it to target a MIPS platform running the Xinu operating system.

Course Outline
Week Topics Assignments Track One
01 Introduction Project 1: Interpreter
02 Lexical Analysis, Automata Project 2: Scanner
03 Syntax Analysis, Grammars Homework 1: Automata and Grammars
04 Parser Generators Project 3: Parser
05 Abstract Syntax Trees
06 Semantic Analysis Project 4: Semantic Analysis
07 Activation Records
08 IR Translation
09 Basic Blocks Project 5: Translation
10 Instruction Selection Homework 2: Activation Records
11 Liveness Analysis
12 Register Allocation
13 Register Allocation Project 6: Instruction Selection
14 Advanced Topics
15 Advanced Topics Homework 3: Register Allocation
Books

References

[1] Course topics and learning objectives have been adapted from the ACM's Computing Curricula 2001 Computer Science.

[2] Andrew W. Appel and Jens Palsberg, Modern Compiler Implementation in Java, 2nd Edition, Cambridge University Press, 2002

[3] A. V. Aho, M. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Pearson, 2nd edition, 1985.

[4] S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.


This work funded in part by NSF grant DUE-CCLI-0737476.