CS 210 Programming Languages

Total Credits: 3 cr

Course Coordinator: Robert Heckendorn

URL: http://marvin.cs.uidaho.edu/~heckendo/CS210

Current Catalog Description: Major features of good programming languages, with primary emphasis on language features and their role in writing food software; programming language design alternative; various types of languages, including procedure, data-flow, functional and object-orientated languages. Prereq: CS 121

Textbook: Terrence W. Pratt and Marvin V. Zelkowitz, Programming Languages: Design and Implementation, Prentice Hall or equivalent text.

References: None.

Course Goals: Teach the major types of programming languages; their features and their particular strengths and weaknesses. Teach how basic lexical analysis, parsing, semantic analysis, error handling and optimization are approached in different programming paradigms. After taking this course, students should understand several different programming language paradigms such as procedural, functional, object-oriented, etc. They should also understand the strengths, weaknesses and the features associated with each language paradigm. They should have experience with formal languages, automata and grammars. Students will also have experience with lexical analyzers and parsers and with one or more non-procedural languages (e.g. Scheme, Lisp, Prolog, Icon, etc.)

Prerequisites by Topic:

• Experience using a compiled language
• Experience using a typed language
• Experience programming with an object-oriented language
• Knowledge of trees, graphs & linked lists
• Basic set theory

Major Topics Covered in the Course: (duration) (CC 2001 BOK reference)

• Programming language concepts (3 hours) (PL1, PL5, PL9)
• Programming language types (4 hours) (PL1, PL6, PL7)
• General structure of compilers (3 hours) (PL3, PL8)
• Automata and grammars (8 hours) (PL8)
• Lexical analyzers and parsers (6 hours) (PL3, PL8)
• Memory management for data structures (3 hours) (PL4)
• Types and type checking (2 hours) (PL4, PL9)
• Virtual machines (3 hours) (PL2)
• Specific languages (Prolog, Scheme, etc.) (8 hours) (PL7)

Laboratory projects (specify number of weeks on each):

• Lexical analysis and parsing (2 weeks)
• Automata and grammars (2 weeks)
• Specific language project (3 weeks)

Estimated Curriculum Category Content:

Area	Core	Advanced	Area	Core	Advanced
Algorithms			Data Structures
Software Design			Prog. Languages	3 cr
Computer Arch			Other

Oral and Written Communications: : None.

Social and Ethical Issues: None.

Theoretical Content: Six hours combined for the following topics:

• Formal language theory
• Automata
• Grammars
• Language parsing

Two hours for the following topic:

• Algorithmic complexity in parsing and memory management

Problem Analysis: Analysis of the language translation problem with a focus on lexical scanning and analysis and parsing.

Solution Design: Basic compiler design, language abstraction, and designing scanners and parsers. Design and implement a simple lex scanner and a Yacc parser.

Course Outcomes: The following list documents the course outcomes and crossreferences them to the BSCS program outcomes. The letter at the beginning of each reference identifies the program outcome supported. The numbers sequentially identify the course outcome for this course. After completing CS 210 a student should:

• Be able to analyze a language translation problem and identify and design lexical scanning and parsing requirements to solve it. (b-1)
• Be able to design and implement a simple lex scanner and Yacc parser. (c-1)
• Be able to describe the structure of compilers and execution environments, and know the phases of a compiler, and the purpose / products / errors of each phase. (i-1)
• Be able to convert a simple grammar and language definition into a flex/bison program. (i-2)
• Know what features must be present in any programming language; understand what are the important properties of a good programming language; understand that no one language can be good for all purposes, and be able to compare and contrast the features of artificial and natural languages. (j-1)
• Understand the implications of the Sapir-Whorf hypothesis for computer languages. (j-2)
• Understand the notation, meaning, and use of regular expressions. (j-3)
• Understand the notation, meaning and use of Backus Naur form and context free grammars and use this knowledge to write a grammar for a simple context free language. (j-4)
• Understand ambiguity; understand how to create precedence and associativity using a grammar. (j-5)
• Derive a sentence in a specific language using a parse tree. (j-6)
• Understand declaration, allocation, binding, scope and lifetime of symbols for various language paradigms. (j-7)
• Understand activation records and parameter passing. (j-8)
• Understand function signature and overloading. (j-9)
• Understand the basics of exemplar languages from the common categories such as, simple stack languages, rule based languages, imperative languages, functional languages, and object oriented languages. (j-10)
• Understand functional and data abstraction and how languages support this. (j-11)
• Understand coercion, casting and type checking. (j-12)
• Understand inheritance, interfaces, accessors, public and private methods. (j-13)
• Understand the purpose of unnamed functions and closures. (j-14)
• Understand the purpose of garbage collection and two ways to do it. (j-15)