Programming Language Paradigms exam 1

Three Categories of Languages

Natural Human (ambiguous), Constructed Human, Programming (unambiguous).

Lexicon

The vocabulary of a language.

Syntax

The rules that govern how words combine to form phrases, clauses, and sentences.

Grammar

The whole system and structure of a language.

Semantics

The meaning of words, phrases, and sentences.

6 Reasons to Study Programming Language Concepts

1. Increased ability to express ideas. 2. Better background for choosing appropriate languages. 3. Increased ability to learn new languages. 4. Better understanding of implementation significance. 5. Better use of languages already known. 6. Overall advancement of computing.

Scientific Programming Domain

Focuses on a large number of floating-point computations, often using arrays. (Ex: FORTRAN)

Business Programming Domain

Focuses on producing reports using decimal numbers and characters. (Ex: COBOL)

AI Programming Domain

Focuses on symbol manipulation (often using linked lists) rather than numbers. (Ex: LISP, PROLOG)

Systems Programming Domain

Requires high efficiency for software that is in continuous use. (Ex: C)

Language Evaluation Criteria (4 main)

Readability, Writability, Reliability, and Cost.

Readability

The ease with which a program can be read and understood.

Writability

The ease with which a language can be used to create programs.

Reliability

How well a program conforms to its specifications.

Cost (in language evaluation)

The total cost of a language over its lifecycle, including writing, compiling, executing, maintenance, and portability.

Orthogonality

A small set of primitive constructs can be combined in a small number of ways to build control and data structures. It's a key attribute affecting readability.

Abstraction

Ignoring the details of complex structures or operations to simplify programming. It's a key attribute affecting writability.

Process Abstraction

Using a subprogram (like a function or method) to avoid writing repeated code.

Data Abstraction

Representing complex data structures in a simplified way, such as using two pointers to represent a binary tree node.

Type Checking

Testing for type errors, either at compile time or runtime, to increase reliability.

Exception Handling

A mechanism to intercept runtime errors, take corrective action, and continue execution, thus increasing reliability.

Aliasing

When two or more distinct names or reference methods can be used to access the same memory cell. It is considered dangerous and reduces reliability.

von Neumann Architecture

The prevalent computer architecture that separates the CPU from memory, which heavily influenced the design of imperative languages.

von Neumann Bottleneck

The limited data transfer speed between the CPU and memory in the von Neumann architecture, which constrains the speed of computation.

Imperative Programming Languages

Languages with central features like variables, assignment statements, and iteration. Includes object-oriented, scripting, and visual languages. (Ex: C, Java, Python)

Functional Programming Languages

Languages based on applying mathematical functions to given parameters. Key concepts include avoiding state changes and using lambda calculus. (Ex: LISP, Haskell, F#)

Logic Programming Languages

Rule-based languages where rules are specified in no particular order. (Ex: Prolog)

Compilation

An implementation method where programs are translated into machine code. It features slow translation but fast execution.

Pure Interpretation

An implementation method where an interpreter program reads and executes source statements directly. It features slower execution but easier implementation.

Hybrid Implementation

An implementation method that translates high-level programs into an intermediate language, which is then interpreted. (Ex: Java, Perl)

Just-in-Time (JIT) Implementation

A hybrid method that initially translates programs to an intermediate language, then compiles methods into machine code when they are called.

Phases of Compilation

Lexical analysis, Syntax analysis, Semantics analysis, and Code generation.

Lexical Analysis (Phase 1)

Converts characters from the source program into lexical units (tokens).

Syntax Analysis (Phase 2)

Transforms the stream of tokens into parse trees to check for syntactic correctness according to the grammar.

Semantics Analysis (Phase 3)

Checks for semantic errors (like type mismatches) and generates intermediate code.

Code Generation (Phase 4)

Translates the intermediate code into the final machine code for the target machine.

Preprocessor

A program that processes code before compilation, often to expand macros or include code from other files (e.g., C's #include).

FORTRAN (1957)

The first high-level programming language, designed for scientific and engineering applications.

COBOL (1960)

A widely-used language focused on business applications, known for its verbosity and readability for business logic.

ALGOL 60

Pioneered machine independence and formal syntax definition (BNF), becoming a foundational language for modern imperative languages.

SIMULA 67

The first language to support data abstraction, introducing the core concepts for object-oriented programming.

C (1972)

A powerful and efficient language developed for systems programming at Bell Labs.

Prolog (1972)

The most well-known logic programming language, based on formal logic.

Ada (1983)

A large, complex language sponsored by the U.S. Department of Defense (DoD) for developing reliable, long-lived embedded systems.

Syntax vs. Semantics

Syntax is the form or structure of expressions and statements, while Semantics is their meaning.

Lexeme

The lowest-level syntactic unit of a language, like a variable name, an operator, or a literal value (e.g., sum, +, 10.5).

Token

A category of lexemes, such as identifier, operator, or literal.

Language Generators vs. Recognizers

Generators produce all valid sentences of a language (a top-down approach). Recognizers determine if a given string is a valid sentence in the language (a bottom-up approach).

BNF (Backus-Naur Form)

A formal notation for describing the syntax of a language using rules, non-terminals (abstractions), and terminals (lexemes/tokens).

Left Recursion Problem

A grammar rule like A -> A + B is left-recursive and will cause an infinite loop in a top-down parser. It must be eliminated.

Derivation

The process of repeatedly applying grammar rules, starting from the start symbol, to generate a sentence.

Sentential Form

Any string of symbols (terminals and/or non-terminals) that appears in a derivation.

Sentence (vs. Sentential Form)

A sentential form that contains only terminal symbols.

Leftmost vs. Rightmost Derivation

In a leftmost derivation, the leftmost non-terminal is always the one replaced. In a rightmost derivation, the rightmost non-terminal is replaced.

Ambiguous Grammar

A grammar that can generate two or more distinct parse trees for the same sentence, leading to multiple possible interpretations.

How to Remove Ambiguity

1. Specify precedence: Ensure operators with lower precedence are further from the leaves (closer to the root) of the parse tree. 2. Specify associativity: Use recursion on only one side of a rule (e.g., expr -> expr + term is left-associative).

EBNF: [ ]

In Extended BNF, square brackets enclose optional parts of a rule.

EBNF: ( ) |

In EBNF, parentheses group elements, and the vertical bar | separates choices within the group.

EBNF: { }

In EBNF, braces denote zero or more repetitions of the enclosed element.

Lexical Analyzer Role

It acts as the "front-end" of the parser. It's a pattern matcher that groups characters into lexemes and passes the corresponding tokens to the syntax analyzer.

Syntax Analyzer (Parser) Role

It checks if the stream of tokens from the lexical analyzer forms a valid sentence according to the language's grammar, typically by building a parse tree.

Top-Down Parsing (LL)

Parsing starts at the root of the parse tree (the start symbol) and grows towards the leaves. It scans the input Left-to-right and produces a Leftmost derivation.

Bottom-Up Parsing (LR)

Parsing starts at the leaves of the parse tree and reduces them up to the root. It scans the input Left-to-right and produces a reverse Rightmost derivation.

Handle

The leftmost simple phrase in a sentential form, which is the part of the string to be reduced in the next step of bottom-up parsing.

Parser Complexity

The runtime complexity for parsers of general unambiguous grammars can be O(n

3

), but parsers for common programming languages are typically in a subset that can be parsed in linear time, O(n).

LR Parser Actions (4)

1. Shift: Push the next input symbol onto the parser stack. 2. Reduce: Replace a handle on the stack with its corresponding non-terminal. 3. Accept: Parsing is complete and successful. 4. Error: A syntax error was found.

Static Semantics

The semantic rules that can be checked at compile time, such as type compatibility.

Dynamic Semantics

The meaning of expressions, statements, and program units, which can only be determined at runtime.

Attribute Grammar

A formal approach to static semantics where a context-free grammar is augmented with attributes (to hold semantic info), functions (to compute attribute values), and predicates (to check rules).

Synthesized vs. Inherited Attributes

Synthesized attributes pass semantic info up the parse tree (bottom-up). Inherited attributes pass info down the tree (top-down).

Operational Semantics

Defines the meaning of a program by describing its effects on a hypothetical machine (i.e., the sequence of state changes it causes).

Denotational Semantics

A highly rigorous method that defines the meaning of language constructs by mapping them to mathematical objects (like functions).

Axiomatic Semantics

Defines the meaning of statements based on formal logic, using assertions about the program state.

Precondition vs. Postcondition

A precondition is a logical assertion that must be true before a statement executes. A postcondition is an assertion that is true after it executes.

Weakest Precondition

The least restrictive precondition that will guarantee the validity of the associated postcondition.