PL FINALS REVIEWER PART 1

Basic Semantics and Syntax Reviewer (1-62)

Semantics

has to do with meaning, which can be subtle and open to interpretation

Language reference manual

This is the most common way to specify semantics.

Identifier

A name assigned by the programmer to denote language entities or constructs such as variables, procedures, and constants. It serves as a fundamental abstraction mechanism in programming languages.

Value

are any storable quantities, such as the integers, the reals, or even array values consisting of a sequence of the values stored at each index of the array.

Location

A place in memory where a value can be stored. Are akin to addresses in a computer’s memory and are essential for storing and accessing values in programming.

Attribute

A property or characteristic associated with a name in a programming language that contributes to its meaning. Examples include data type, scope, and value.

Binding

The process of associating an attribute with a name.

Binding Time

The point during the translation or execution process when an attribute is bound to a name. It determines when a name gets its associated property or value.

Static Binding

A type of binding that occurs before program execution, usually during compilation. The attribute bound statically remains unchanged throughout execution.

Dynamic Binding

A type of binding that occurs during program execution. The attribute may change or be determined at runtime.

Static Attribute

An attribute that is bound to a name at compile time. It does not change during program execution.

Dynamic Attribute

An attribute that is bound to a name at runtime and can vary during the execution of the program.

Declaration

Are principal method for establishing bindings

definition

• Declarations that bind all potential attributes

• A special kind of declaration that binds all potential attributes of a name, including both type and implementation or value. For example, assigning a function body or an initial variable value.

declaration

declarations that only partially specify attributes

block

A language construct consisting of a sequence of declarations followed by a sequence of statements. Blocks are usually enclosed by syntactic markers like {} in C-style languages or begin-end pairs in others.

local declaration

Declarations that are associated with a specific block.

non-local declaration

Declarations in surrounding blocks (or global declarations)

scope

The region of a program where a particular binding between a name and its attributes remains valid. It defines where the name can be used to refer to the bound entity.

Lexical Scope

A scoping rule where the visibility of a binding is determined by the physical structure of the program code, particularly the placement of blocks and declarations. The scope is defined at compile time based on the program’s text.

Symbol Table

• is like a dictionary

• A data structure used in a compiler or interpreter to store information about identifiers, such as names and their associated attributes. It supports operations like insertion, lookup, and deletion of bindings.

Scope Analysis

The process of managing the visibility and lifetime of bindings as the program enters and exits blocks. It involves updating the symbol table by adding new bindings on block entry and removing them on block exit to restore any previous bindings.

Environment

The mapping between names and the entities they refer to (such as memory locations or values) during program execution. It may be constructed statically, dynamically, or with a combination of both depending on the programming language.

Static Environment

An environment where all bindings are determined at load time, before execution. FORTRAN is an example of a language with a completely static environment.

Dynamic Environment

An environment where bindings are determined at execution time. This approach allows more flexibility but requires runtime management.

Declaration

Are used to construct the environment as well as the symbol table..

In a Compiler

The declarations are used to indicate what allocation code the compiler is to generate as the declaration is processed.

In an interpreter

The symbol table and the environment are combined, so attribute binding by a declaration in an interpreter includes the binding of locations.

Variable

Is an object whose stored value can change during execution.

box-and-circle diagram

A visual representation used to illustrate the key attributes of a variable—name, location, and value. It highlights how a variable's name is bound to a memory location, and how that location stores a value.

Assignment Statement

A programming construct used to update the value of a variable. In the form x = e, the expression e is evaluated to produce a value, which is then stored in the memory location associated with the variable x.

Assignment by Sharing

A form of assignment in which the location (not the value) of one variable is copied to another. After the assignment x = y, both x and y refer to the same memory location, meaning changes to one affect the other.

Assignment by Cloning

A form of assignment where a new memory location is allocated, the value of the source variable is copied into it, and the destination variable is bound to this new location. Thus, x = y makes x and y independent after the assignment.

Constant

Is a language entity that has a fixed value for the duration of its existence in a program.

Constnat

A symbolic name that represents a fixed value in a program. Once bound, the value associated with a constant does not change throughout program execution.

Static Constant

One whose value can be computed prior to execution,

Dynamic Constant

Has a value that can be computed only during execution.

Backus-Naur Form (BNF)

A formal notation used to describe the syntax of programming languages. It was developed by John Backus and Peter Naur and first used to define the syntax of Algol60. BNF expresses context-free grammars in a structured and precise way.

Lexical Structure

The set of rules that define the basic elements (tokens or words) of a programming language, such as identifiers, keywords, operators, and symbols.

Scanning Phase

A translator collects sequences of characters from the input program and forms them into tokens.

Parsing Phase

The translator then processes these tokens, thereby determining the program’s syntactic structure.

reserved words

sometimes called keywords, such as if and while

literals or constants

such as 42 (a numeric literal) or "hello" (a string literal)

special symbols

such as “ ; ”, “ <= ”, or “ + ”

identifiers

such as x24, monthly_balance , or putchar

predefined identifiers

are all standard data types in Ada, such as integer and boolean , and in Python, such as round and print

token delimiters or white space

The principle of longest substring requires that certain tokens be separated by what?

free-format language

one in which format has no effect on the program structure

fixed format

all tokens must occur in pre-specified locations on the page

concatenation, repetition, and choice or selection

3 basic operation of regular expressions

nonterminals

names for phrase structures (like sentence)

Grammar rules

also called productions, since they “produce” the strings of the

language using derivations

language of the grammar

context-free grammar defines a language

Metasymbol “→”

A symbol used in grammar rules to separate the left-hand side (nonterminal) from the right-hand side (its expansion). It indicates how the nonterminal can be rewritten.

syntax-directed semantics

process of associating the semantics of a construct to its syntactic structure

parse tree

a graphical depiction of the replacement process in a derivation

Abstract Syntax Tree

abstract the essential structure of the parse tree

Parse tree

Abstract Syntax Tree

ambiguous

two distinct parse (or syntax) trees are possible for the same string

left-recursive

left-recursive rule for an operation causes it to left-associate

right-recursive

rule causes it to right-associate