Principles of Programming Languages
COSC 303: Principles of Programming Languages
1st Semester Reviewer | Midterm Departmental Examination A.Y. 2026-2027
Overview of Study Topics
Definition of a Programming Language (PL)
Reasons to Study Programming Languages
Characteristics of a Good Language
Effects of Environment on Languages (Classes of Environments)
Programming Language Paradigms
Describing Syntax and Semantics
Bindings and Binding Time Categories
Backus-Naur Form (BNF), Derivations, and Ambiguity
Stages in Program Translation
Variables, Attributes, Lifetime Categories, and Scopes
Primitive and Structured Data Types
CHAPTER 01: OVERVIEW OF PROGRAMMING LANGUAGES
1-1 Nature of Programming Languages
Programming Language (PL): A formal system of notation used to describe algorithms that a computer can interpret and execute. It connects human logical thinking with machine operations and provides a structured way to express instructions, manipulate data, and control program behavior.
Key Elements of a Programming Language
Formal notation: Follows strict rules that define valid statements.
Purpose: Used to specify, organize, and reason about computational processes.
Role in computing: Provides tools for expressing algorithms, manipulating data, and controlling system behavior.
Three Important Concepts
Syntax: Refers to the structure or grammar rules of a programming language. It determines whether a statement is written correctly according to the language's rules.
Semantics: Refers to the meaning or behavior of a syntactically valid statement. It explains what a program statement does when interpreted or executed.
Example: int age = 18;
Syntax: Follows the grammatical rules of C.
Semantics: Declares an integer variable named age and initializes it to 18.
Pragmatics: Using a descriptive variable name makes the program easier to understand.
Pragmatics: Refers to how a programming language is used effectively in real-world programming. It concerns the practical application of language features.
1-2 Importance of Studying Programming Languages
Studying programming languages develops conceptual understanding of computation and improves problem-solving flexibility. It helps programmers:
Improve algorithmic thinking: Develop logical and efficient solutions to problems.
Use existing languages more effectively: Write code that is readable, maintainable, and optimized.
Expand their vocabulary of programming constructs: Learn different tools for solving problems, such as loops, recursion, objects, and closures.
Choose appropriate programming languages: Select a language that fits the requirements of a project.
Learn new languages more easily: Understand common concepts that appear across different languages.
Understand language design: Develop foundational knowledge of syntax, semantics, implementation, and compiler design.
Why It Matters
Understanding programming language principles is more valuable than memorizing syntax alone.
Different languages offer different ways to represent and solve problems.
Knowledge of programming concepts makes it easier to adapt to new technologies and development environments.
1-3 Characteristics of a Good Programming Language
A good programming language supports clarity, efficiency, reliability, and ease of use.
Clarity, Simplicity, and Unity: Easy to read, understand, and use. Rules should minimize unnecessary complexity and ambiguity.
Orthogonality: Language features should consistently combine without unexpected interactions. A small number of consistent rules makes programs easier to understand and maintain without memorizing special exceptions.
Naturalness for the Application: Suits the problem domain or intended application.
Python: Artificial intelligence and general-purpose programming.
C: Systems programming.
Support for Abstraction: Allows data and operations to be organized into self-contained, reusable units (e.g., functions and classes). Reduces complexity and supports modular programming.
Ease of Program Verification (Reliability): Programs behave correctly under expected conditions; behavior is testable and verifiable.
Cost Efficiency: Total cost includes programmer training, development time, compilation and execution, testing and debugging, and maintenance.
1-4 Programming Environments
A programming environment influences language design based on the hardware, operating system, and intended application:
Batch Environment: Programs execute sequentially without direct user interaction during execution.
Interactive Environment: Allows users to interact with a program and receive immediate feedback (e.g., Python REPL).
Embedded Environment: Designed for devices with limited resources and specific functions (e.g., C for microcontrollers).
Distributed Environment: Supports network-based computing and coordination among multiple computers/processes (e.g., Java, Go).
Web-Based Environment: Supports development of websites and internet applications (e.g., JavaScript, PHP, TypeScript).
1-5 Programming Language Paradigms
A programming paradigm is a style or philosophy of programming:
Imperative or Procedural: Focuses on instructions that change program state using assignments, loops, and conditional statements (e.g., C, Python).
Object-Oriented Programming (OOP): Organizes code around objects containing data and behavior using classes and methods (e.g., Java, C++).
Functional Programming: Emphasizes functions, pure functions, and immutability (e.g., Haskell, Lisp).
Logic-Based Programming: Uses facts, rules, and logical inference to express solutions (e.g., Prolog).
Scripting: Commonly used for automation and integrating tasks (e.g., Python, JavaScript).
Can one language support multiple paradigms? Yes (e.g., Python supports procedural, OOP, and functional features).
CHAPTER 02: DESCRIBING SYNTAX AND SEMANTICS
2-1 Nature of Syntax and Semantics
Syntax: Structure and grammar rules defining symbol/keyword arrangements. Violations cause syntax errors.
Semantics: Meaning or behavior of syntactically valid statements.
Pragmatics: Practical use in real-world programming (readability, maintainability).
2-2 Terminology
Lexeme: The actual sequence of characters in source code that matches a token pattern.
Token: A category assigned to a lexeme (Keyword, Identifier, Operator, Literal, Separator).
Grammar: Collection of rules defining valid syntactic structures.
Production Rule: Describes how a grammatical element can be formed/expanded (e.g., <digit> ::= 0|1|2|3|4|5|6|7|8|9).
|---|---|---|---|---|---|---|---|of applying grammar rules to produce a sentence.Parse Tree: Visual representation of the grammatical structure of a sentence.
Ambiguity: Occurs when a sentence can have more than one valid parse tree.
2-3 Backus-Naur Form (BNF) and Derivations
BNF is a formal notation for describing syntax through production rules:
::= means "is defined as"
| means OR
<name> represents a nonterminal
Terminal symbols are actual tokens that appear in source code.
2-4 Grammar Ambiguity and Parse Trees
Ambiguity creates multiple interpretations of an expression.
Operator Precedence: Determines which operators are evaluated first.
Associativity: Determines grouping for operators of equal precedence (Left vs. Right associativity).
2-5 Programming Language Semantics & Translation Stages
Approaches to Semantics
Operational Semantics: Describes step-by-step execution and state changes.
Denotational Semantics: Maps language constructs to mathematical objects.
Axiomatic Semantics: Uses mathematical logic (pre/post-conditions) to reason about correctness.
Stages in Program Translation
Lexical Analysis: Identifies lexemes and classifies them into tokens.
Syntactical Analysis (Parsing): Verifies if token sequences follow grammar rules.
Semantic Analysis: Checks meaning rules (type checks, symbol table queries).
Synthesis: Generates intermediate/machine code and performs optimization.
Symbol Table: Stores metadata about identifiers (types, scopes, names).
CHAPTER 03: NAMES, BINDINGS, TYPE CHECKING, AND SCOPE
3-1 Names, Variables, and Attributes
Variable: Abstraction of a memory cell.
Attributes: Name, Address, Value, Type, Lifetime, Scope.
3-2 Binding and Binding Time
Binding is an association between an element and an attribute.
Binding Times: Language design time, Language implementation time, Compile time, Link time, Load time, Run time.
3-3 Type Checking
Static Type Checking: Performed before execution (compile time).
Dynamic Type Checking: Performed during execution (runtime).
3-4 Lifetime Categories of Variables
Static: Storage exists throughout program execution.
Stack-Dynamic: Storage allocated when function/block becomes active, deallocated when it ends.
Explicit Heap-Dynamic: Allocated and freed explicitly by programmer (malloc/free).
Implicit Heap-Dynamic: Allocated and managed automatically by runtime/garbage collector.
3-5 Scope of a Variable
Static (Lexical) Scope: Determined by textual structure of code.
Dynamic Scope: Determined by runtime calling sequence of functions.
3-6 Referencing Environments & Named Constants
Referencing Environment: Set of visible variables/bindings at a given execution point.
Named Constants: Identifiers bound to values that cannot be reassigned (Static/Manifest vs Dynamic).
CHAPTER 04: PRIMITIVE AND STRUCTURED DATA TYPES
4-1 Primitive Data Types
Integer, Floating-Point, Complex, Rational, Boolean, Character.
4-2 Structured Data Types
Array: Fixed/variable collection of homogeneous elements (Row-major vs Column-major memory arrangement).
Record / Structure: Groups heterogeneous fields under one name.
List: Ordered collection, often dynamic in size.
String: Sequence of characters.
Pointer: Stores the memory address of another variable.