Intro to Programming Languages: History & Paradigms

Introduction to Programming Languages

• This module covers the history, paradigms, and tools of programming languages (Module 1)

Learning Objectives

• Understand the history and evolution of programming languages.
• Differentiate between procedural, object-oriented, and functional programming paradigms.
• Explain the difference between compilers and interpreters.
• Set up and test development environments for Python, C++, and C.

History and Evolution of Programming Languages

• 1st Generation programming languages used machine code (binary) in the 1940s.
• 2nd Generation programming languages used assembly language (1940s-1950s).
• 3rd Generation languages used high-level languages like Fortran and COBOL (1950s-1960s).
• 4th Generation involved declarative languages such as SQL and MATLAB (1970s).
• 5th Generation programming used logic-based/AI-focused languages like Prolog (1980s onward).
• Examples include C (1972), Python (1991), and JavaScript (1995).

Programming Paradigms

• Procedural programming involves linear execution, as seen in C and Fortran.
• Object-Oriented Programming (OOP) encapsulates data and functions, as in Python and Java.
• Functional programming focuses on immutability and pure functions, exemplified by Haskell and Lisp.

Compilers vs. Interpreters

• Compilers convert entire code into machine code before execution (C, C++).
• Interpreters execute code line-by-line (Python, JavaScript).

Activities Overview

• Compare paradigms (procedural, object-oriented, functional) in a group discussion.
• Research a language, create a timeline using Canva or Google Slides (e.g., Python, C++).
• Install Python, C++, and C environments; run "Hello, World!" programs.

Timeline Example: Python Evolution

• 1991: Created by Guido van Rossum.
• 2000: Python 2.0 introduced.
• 2008: Python 3.0 released with major updates.
• 2020: Python 2 reached end-of-life.

Environment Setup Instructions

• Python:
  • Download from python.org.
  • Test installation with python --version.
  • IDE suggestion: VS Code or PyCharm.
• C/C++:
  • Install GCC/Clang (MinGW or Visual Studio Code).
  • Test with a simple "Hello, World!" program.

Deliverables & Deadlines

• Group Presentation: Paradigms Comparison Table.
• Individual Assignment: Programming language timeline.
• Screenshots: Installed environments and program outputs.

Module 2: Syntax and Semantics

• Understand grammar and syntax rules in programming languages.
• Explain context-free grammars and Backus-Naur Form (BNF).
• Perform lexical analysis by identifying tokens, keywords, and identifiers.
• Construct and analyze syntax rules and parsing techniques.
• Differentiate between syntax and semantics in program execution.
• Develop a BNF grammar for arithmetic expressions.

Grammar and Syntax Rules

• Definition of grammar in programming languages Structure of syntax rules
• Common syntax errors and how they are handled

Context-Free Grammars and Backus-Naur Form (BNF)

• Definition of context-free grammars (CFGs)
• Writing grammar rules using BNF
• Examples of CFGs in programming languages

Lexical Structure: Tokens, Keywords, and Identifiers

• Tokenization process in programming languages
• Differences between keywords and identifiers
• Examples of token breakdown in Python

Syntax: Grammar and Parsing

• Syntax trees and abstract syntax trees (ASTs)
• Parsing strategies: top-down vs bottom-up parsing
• Writing grammar rules for a subset of a language

Semantics: Meaning and Execution of Programs

• Difference between syntax and semantics
• Types of semantics: operational, denotational, and axiomatic
• How semantic errors affect program execution

Grammar and Syntax Rules in Programming

• In programming, grammar refers to the set of rules that define how statements and expressions are written in a given language.
• Grammar is usually defined using formal language theories, such as Backus-Naur Form (BNF) or Context-Free Grammars (CFGs).

Grammar in Programming: Backus-Naur Form (BNF) and Context-Free Grammars (CFGs)

• Programming languages have grammar rules that define valid syntax.
• These rules are often described using formal language theories, such as: Backus-Naur Form (BNF), Context-Free Grammars (CFGs)
• Why Use Formal Grammars?
  • They help define and parse programming languages, ensure consistency across different compilers/interpreters and they provide a structured way to check syntax errors.

Backus-Naur Form (BNF)

• BNF is a notation used to define the syntax of programming languages.
• It describes rules for valid expressions in a hierarchical manner.
• Each rule consists of: Non-terminals, Terminals

Basic BNF Syntax

• A BNF grammar consists of productions (rules) in the format: <symbol> ::= expression

Defining Arithmetic Expressions in BNF

• simple arithmetic expressions using BNF: <expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term> <term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor> <factor> ::= <number> | "(" <expression> ")" <number> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Context-Free Grammars (CFGs)

• A context-free grammar (CFG) is a set of recursive rules that define valid syntax for a language.
• A CFG consists of: Terminals, Non-terminals, Production rules and Start symbol

Structure of Syntax Rules

• Syntax defines how symbols, keywords, and operators should be arranged.
• Every programming language has lexical, syntactic and semantic rules

Common Syntax Errors and How They Are Handled

• Types of Syntax Errors: Missing symbols, Indentation Errors, Misspelled Keywords or Functions and Data Type Mismatch

Handling Syntax Errors

• Most programming languages handle syntax errors in the compilation or interpretation phase.
• Interpereted languages errors are detected line by line during execution.
• Compiled languages erros are caught before execution during compilation

Activities

• Token Identification Activity Objective: Understand lexical structure by breaking down a Python program into tokens and manually identify and classify tokens
• Writing BNF Grammar for Arithmetic Expressions Objective: Learn how to represent programming language syntax using BNF by defining a BNF grammar for arithmetic expressions involving multiplication, and division
• Laboratory Activity: Writing Grammar Rules for a Simple Language Subset Objective: Define a formal grammar for a subset of a programming language by defining grammar rules for simple arithemtic expressions and test the grammar with different expressions.

Assessment

• Quiz: Multiple-choice and short-answer questions on syntax, semantics, and grammar.
• Coding Task: Write a simple parser that verifies arithmetic expressions using the defined BNF grammar. Project: Develop a basic lexical analyzer that tokenizes a given input string based on defined grammar rules.

Module 4: Syntax: Grammar and Parsing

• Syntax Trees and Abstract Syntax Trees (ASTs)
• Syntax trees and abstract syntax trees (ASTs) are data structures that represent the syntactic structure of source code.
• There are two primary representations used in parsing: Parse Trees and Abstract Syntax Trees (ASTs)

Understanding Parse Trees

• These trees represent the full grammatical structure of an expression based on the grammar rules.

Abstract Syntax Trees

• These trees focus on the essential structure, eliminating unnecessary nodes for simplification.

Abstract Syntax Tree : Example

• In the case of more complex expressions, the Abstract Syntax Tree (AST) can become significantly more compact due to its focus on structural relationships rather than the raw syntax of the expression. This is particularly evident when handling expressions with multiple operators, function calls, or nested structures.

Parsing Stategies : Top Down vs. Bottom Up

• There are two primary parsing approaches—Top-Down Parsing and Bottom-Up Parsing.
• Top-Down Parsing (Recursive Descent Parsing)- Top-down parsing starts at the root (the start symbol of the grammar) and attempts to match the input using production rules

Top Down Parsing : How it works

• Starts from the highest-level rule and recursively expands rules to match the input.
• Uses recursive functions to process different parts of the expression.
• Handles operator precedence by ensuring that higher precedence operators are evaluated first.
• Works well with LL(k) grammars (left-to-right scanning with leftmost derivation).
• Bottom-Up Parsing (Shift-Reduce Parsing) Bottom-up parsing starts with tokens and attempts to construct a parse tree by reducing them according to grammar rules

Bottom UP Parsing : How It Works

• Uses a stack to shift tokens and reduce when a valid grammar rule matches.
• Works well with LR(k) grammars (left-to-right scanning, rightmost derivation in reverse).
• Shift: Moves the next token onto the stack.
• Reduce: Applies a grammar rule when a matching sequence of tokens is found.
• Bottom-up parsing is efficient for complex grammars, as used in compiler implementations

5. Semantics: Meaning and Execution of Programs

• Syntax and Semantics
• Syntax: Structure and form of code (e.g., parentheses matching, keyword usage). Semantics: Meaning and behavior of the code

Types of Semantics

• There are three types of semantics:
  • Operational: Describes how a program executes step by step.
  • Denotational: Maps program constructs to mathematical functions.
  • Axiomatic: Uses logical assertions to reason about program behavior

Step-by-step Execution

• Operational semantics defines the execution process of a program by specifying how the state of computation changes.

Denotational Semantics

• Denotational semantics translates program constructs into mathematical functions. Axiomatic Semantics (Logical Assertions for Verification)

3. Axiomatic Semantics (Logical Assertions for Verification)

• Axiomatic semantics uses preconditions and postconditions to formally verify program correctness.

To demonstrate the concepts above, implementation of a basic interpreter for a simple arithmetic-based language requires

• 6.1 Tokenizer (Lexical Analysis) This tokenizer converts input into meaningful tokens. A simple parser to verifiy airthmatic expressions
• ASTs remove unnecessary syntax elements, making evaluation faster and more efficient.
• What are the benefits of removing redundant symbols in an AST?
• How would you extend the parser to handle variables?