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

  1. 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.

  2. 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.

  3. 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.



  1. Clarity, Simplicity, and Unity: Easy to read, understand, and use. Rules should minimize unnecessary complexity and ambiguity.

  2. 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.

  3. Naturalness for the Application: Suits the problem domain or intended application.

    • Python: Artificial intelligence and general-purpose programming.

    • C: Systems programming.

  4. 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.

  5. Ease of Program Verification (Reliability): Programs behave correctly under expected conditions; behavior is testable and verifiable.

  6. 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:



  1. Batch Environment: Programs execute sequentially without direct user interaction during execution.

  2. Interactive Environment: Allows users to interact with a program and receive immediate feedback (e.g., Python REPL).

  3. Embedded Environment: Designed for devices with limited resources and specific functions (e.g., C for microcontrollers).

  4. Distributed Environment: Supports network-based computing and coordination among multiple computers/processes (e.g., Java, Go).

  5. 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:



  1. Imperative or Procedural: Focuses on instructions that change program state using assignments, loops, and conditional statements (e.g., C, Python).

  2. Object-Oriented Programming (OOP): Organizes code around objects containing data and behavior using classes and methods (e.g., Java, C++).

  3. Functional Programming: Emphasizes functions, pure functions, and immutability (e.g., Haskell, Lisp).

  4. Logic-Based Programming: Uses facts, rules, and logical inference to express solutions (e.g., Prolog).

  5. 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

  1. Operational Semantics: Describes step-by-step execution and state changes.

  2. Denotational Semantics: Maps language constructs to mathematical objects.

  3. Axiomatic Semantics: Uses mathematical logic (pre/post-conditions) to reason about correctness.

Stages in Program Translation

  1. Lexical Analysis: Identifies lexemes and classifies them into tokens.

  2. Syntactical Analysis (Parsing): Verifies if token sequences follow grammar rules.

  3. Semantic Analysis: Checks meaning rules (type checks, symbol table queries).

  4. 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

  1. Static: Storage exists throughout program execution.

  2. Stack-Dynamic: Storage allocated when function/block becomes active, deallocated when it ends.

  3. Explicit Heap-Dynamic: Allocated and freed explicitly by programmer (malloc/free).

  4. 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.