Compilers Exam 1 Def

Compiler

A program that accepts source code and translates it into machine code for a target computer architecture.

Source Code

The original program written in a programming language that is given to the compiler as input.

Target Architecture

The computer architecture for which the compiler generates machine code, such as x86, ARM, or MIPS.

Portability

The ability of a compiler to support different source languages or target architectures without redesigning the entire compiler.

Intermediate Representation (IR)

A machine-independent internal representation of a program used between the compiler's front end and back end.

Front End

The part of the compiler that analyzes source code and translates it into an intermediate representation.

Back End

The part of the compiler that translates the intermediate representation into code for a specific target architecture.

Scanning

The compiler phase that groups input characters into tokens.

Parsing

The compiler phase that recognizes sequences of tokens according to a grammar and determines their syntactic structure.

Semantic Analysis

The compiler phase that checks whether variables, functions, types, and other program elements are used consistently with the language's rules.

Type Checking

The process of verifying that operations and expressions use compatible data types.

Optimization

The process of improving intermediate code without changing the program's meaning.

Instruction Selection

The back-end phase that maps intermediate representation instructions into assembly instructions.

Code Optimization

The process of improving generated assembly code using techniques such as control-flow analysis, data-flow analysis, and register allocation.

Code Generation

The compiler phase that generates machine code from assembly code.

Object File

A file containing generated machine code that may still contain unresolved references to external symbols.

Linking

The process of combining object files and libraries into one executable and resolving external references.

Loading

The process of placing an executable into memory, initializing the program environment, and beginning execution.

Scanner

The component that performs lexical analysis by grouping source-code characters into lexemes and assigning tokens to them.

Lexical Analysis

The process of dividing program text into its basic words or tokens.

Lexeme

The actual sequence of characters in source code corresponding to a token.

Token

A category assigned to a lexeme, such as keyword, identifier, integer, or operator.

Scanner Generator

A tool that automatically creates a scanner from token specifications written using regular expressions.

JFlex

A scanner generator for Java that generates a lexical analyzer from regular-expression specifications.

Alphabet (Σ)

A finite set of symbols from which strings in a language are constructed.

String

A finite sequence of symbols from an alphabet.

Empty String (ε)

A string containing zero symbols.

Empty Language (∅)

A language containing no strings.

Language

A set of strings over an alphabet.

Regular Language

A language that can be represented by a regular expression or recognized by a finite automaton.

Regular Expression (RE)

A notation used to describe a regular language using symbols and regular operations.

Union (∪)

A regular operation that represents strings belonging to either of two languages.

Concatenation (∘)

A regular operation that combines a string from one language with a string from another language.

Kleene Star (*)

A regular operation representing zero or more repetitions of strings from a language.

Regular Expression Precedence

The order of RE operations from highest to lowest is Kleene star, concatenation, then union.

Closure

A collection is closed under an operation if applying the operation to members of the collection always produces another member of that collection.

Closure of Regular Languages

Regular languages remain regular when operations such as union, concatenation, and Kleene star are applied to them.

Finite Automaton

A mathematical machine with a finite number of states used to recognize strings belonging to a language.

Deterministic Finite Automaton (DFA)

A finite automaton with exactly one transition for each state and input-symbol combination.

DFA 5-Tuple

A DFA is formally defined as (Q, Σ, δ, q₀, F).

Q

The finite set of states in a finite automaton.

Transition Function (δ)

A function that determines which state the automaton moves to based on its current state and input.

Start State (q₀)

The state where a finite automaton begins processing input.

Accepting States (F)

The states in which an automaton accepts an input after the entire string has been consumed.

DFA Acceptance

A DFA accepts a string when consuming the entire input causes it to finish in an accepting state.

Error State

A nonaccepting state that acts as a black hole; once entered, the DFA cannot escape.

Transition Table

A table that specifies the next state for each combination of current state and input symbol.

Nondeterministic Finite Automaton (NFA)

A finite automaton that may have multiple transitions for the same input symbol and may contain ε-transitions.

ε-Transition

A transition that allows an NFA to change states without consuming an input symbol.

NFA Acceptance

An NFA accepts a string if at least one possible path consumes the entire input and finishes in an accepting state.

DFA and NFA Equivalence

DFAs and NFAs have the same expressive power; every NFA has an equivalent DFA recognizing the same language.

Equivalent Automata

Two automata are equivalent if they recognize exactly the same language.

Subset Construction

The method used to convert an NFA into an equivalent DFA where each DFA state represents a set of NFA states.

ε-Closure(s)

The set of NFA states reachable from state s using only ε-transitions, including s itself.

ε-Closure(T)

The set of states reachable from any state in set T using only ε-transitions.

move(T, a)

The set of NFA states reachable from states in T by consuming input symbol a.

RE to DFA Conversion

The usual process is Regular Expression → NFA → DFA → optionally minimize the DFA.

State Minimization

The process of converting a DFA into an equivalent DFA containing as few states as possible.

Unreachable State

A state that can never be reached from the DFA's start state and can therefore be removed during minimization.

Equivalent DFA States

States that behave identically for all possible future inputs and can therefore be combined during minimization.

Parser

The compiler component that receives tokens from the lexer and determines whether they follow the language's grammatical structure.

Parser Input

A sequence of tokens produced by the lexical analyzer.

Parser Output

A representation of the program's syntactic structure, typically a parse tree or similar tree structure.

Parse Tree

A tree representing how a sequence of tokens is generated according to a grammar.

Regular Language Limitation

Regular languages cannot naturally represent recursive or nested structures such as balanced parentheses and nested expressions.

Context-Free Grammar (CFG)

A formal grammar used to describe recursive syntactic structures in programming languages.

CFG 4-Tuple

A context-free grammar is formally defined as (N, T, R, S).

Nonterminal

A grammar symbol representing a syntactic category that can be replaced using production rules.

Terminal

A grammar symbol corresponding to an actual token that cannot be replaced by another grammar production.

Production Rule

A rule describing how a nonterminal may be replaced by a sequence of terminals and nonterminals.

Start Symbol

The designated nonterminal from which generation or parsing of strings begins.

Yield (⇒)

A relationship where one string is transformed into another using one production-rule substitution.

Derivation (⇒*)

A sequence of zero or more production-rule substitutions used to generate a string.

Leftmost Derivation

A derivation in which the leftmost nonterminal is replaced at every step.

Rightmost Derivation

A derivation in which the rightmost nonterminal is replaced at every step.

Ambiguous Grammar

A grammar in which at least one string can have more than one parse tree.

Associativity

A rule determining how repeated operators of the same precedence are grouped.

Operator Precedence

A rule determining which operators bind more strongly and are evaluated first.

Top-Down Parsing

A parsing approach that begins with the start symbol and attempts to derive the input tokens.

Bottom-Up Parsing

A parsing approach that begins with the input tokens and repeatedly reduces them until reaching the start symbol.

Predictive Parsing

A top-down parsing technique that uses the current input token to predict which grammar production should be applied.

Recursive-Descent Parsing

A top-down parsing method that generally uses one procedure for each nonterminal in the grammar.

Left Recursion

A grammar structure where a nonterminal can derive a string beginning with itself, which can cause infinite recursion in recursive-descent parsing.

Left Recursion Elimination

The process of rewriting a left-recursive grammar into an equivalent form suitable for predictive or recursive-descent parsing.

Predictive Parsing Table

A table M[X, token] that specifies which production to use based on the current nonterminal and input token.

End-of-Input Symbol ($)

A special symbol used by a parser to indicate the end of the input.

FIRST(α)

The set of terminals that can appear first in strings derived from the symbol sequence α.

FOLLOW(X)

The set of terminals that can immediately follow nonterminal X in a legal derivation.

Shift-Reduce Parser

Another name for a bottom-up parser because its two main operations are shifting input and reducing handles.

Shift

The bottom-up parsing action that pushes the current input token and advances to the next token.

Reduce

The bottom-up parsing action that replaces symbols matching the right-hand side of a production with that production's left-hand side.

Handle

A sequence of symbols that matches the right-hand side of a production and can be reduced during bottom-up parsing.

ACTION Table

The shift-reduce parsing table that determines whether the parser should shift, reduce, accept, or report an error based on the current state and token.

GOTO Table

The shift-reduce parsing table that determines which state to enter after reducing to a particular nonterminal.

ACTION vs. GOTO

ACTION handles transitions involving terminals and parser actions, while GOTO determines state transitions involving nonterminals after reductions.

Item

A production containing a dot that indicates how far the parser has progressed through that production.

Itemset

A set of items representing all grammar productions that could currently be applicable during parsing.

Dot at Beginning of an Item

Indicates that none of the right-hand side of that production has been recognized yet.

Dot in Middle of an Item

Indicates that symbols before the dot have been recognized and the parser expects the symbol immediately after the dot.

Dot at End of an Item

Indicates that the entire right-hand side has been recognized and a handle has been found for reduction.