CSE 3302 Exam 3 vocab

Lexical structure

the structure of the tokens, or words, of a language

Scanning phase

the phase in which a translator collects sequences of characters from the input program and forms them into tokens

Parsing phase

the phase in which the translator processes the tokens, determining the program's syntactic structure

Tokens generally fall into what several categories:

-Reserved words (or keywords)

-Literals or constants

-Special symbols, such as ";"m "<=", or "+"

-Identifiers

Predefined identifiers

identifiers that have been given an initial meaning for all programs in the language but are capable of redirection

Principle of longest substring

process of collecting the longest possible string of nonblank characters

Token delimiters (or white space)

formatting that affects the way tokens are recognized

Free-format language

one in which format has no effect on program structure other than satisfying the principle of longest substring

Fixed format language

one in which all tokens must occur in prespecified locations on the page

Tokens can be formally described by what?

regular expressions

Three basic patterns of characters in regular expressions

-Concatenation: done by sequencing the items

-Repetition: indicated by an asterisk after the item to be repeated

-Choice, or selection: indicated by a vertical bar between items to be selected

Metasymbols

symbols used to describe the grammar rules

Derivation

the process of building in a language by beginning with the start symbol and replacing left-hand sides by choices of right-hand sides in the rules

Context-free grammar

consists of a series of grammar rules

Nonterminals

names for phrase structures, since they are broken down into further phrase structures

Language of the grammar

defined by a context-free grammar

Start symbol

a nonterminal representing the entire top-level phrase being defined

Backus-Naur form

uses only the metasymbols "->" and "|"

Productions

another name for grammar rules

Syntax-directed semantics

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

Terminals

words or token symbols that cannot be broken down further

Parse tree

graphical depiction of the replacement process in a derivation

Abstract syntax trees (or syntax trees

trees that abstract the essential structure of the parse tree

Concrete syntax

ordinary syntax

Ambiguous grammar

one for which two distinct parse or syntax trees are possible

Leftmost derivation

the leftmost remaining nonterminal is singled out for replacement at each step

First rule is ______; second rule is _____

left-recursive; right-recursive

Extended Backus-Naur form (or EBNF)

introduces new notation to handle common issues

•Use curly braces to indicate 0 or more repetitions

-Assumes that any operator involved in a curly bracket repetition is left-associative

-Example: number -> digit {digit}

•Use square brackets to indicate optional parts

-Example: if-statement -> if(expression) statement [else statement]

Syntax diagram

indicates the sequence of terminals and nonterminals encountered in the right-hand side of the rule

Recognizer

accepts or rejects strings based on whether they are legal strings in the language

Bottom-up parser

constructs derivations and parse trees from the leaves to the roots

-Matches an input with right side of a rule and reduces it to the nonterminal on the left

Top-down parser

expands nonterminals to match incoming tokens and directly construct a derivation

Parser generator

a program that automates top-down or bottom-up parsing

Recursive-descent parsing

turns nonterminals into a group of mutually recursive procedures based on the right-hand sides of the BNFs

Single-symbol lookahead

using a single token to direct a parse

Predictive parser

a parser that commits itself to a particular action based only on the lookahead

Lexics

the lexical structure of a programming language

Parsing shell

applies the grammar rules to check whether tokens are of the correct types

TinyAda

a small language that illustrates the syntactic features of many high-level languages

Names (or identifiers)

a fundamental abstraction mechanism used to denote language entities or constructs

Value

any storable quantities

Location

place where value can be stored; usually a relative location

Attributes

properties that determine the meaning of the name to which they are associated

Binding

process of associating an attribute with a name

Binding time

the time when an attribute is computed and bound to a name

Static binding

occurs prior to execution

Dynamic binding

occurs during execution

Static attribute

an attribute that is bound statically

Dynamic attribute

an attribute that is bound dynamically

Symbol table

a function from names to attributes

Lexical analysis

determines whether a string of characters represents a token

Syntax analysis

determines whether a sequence of tokens represents a phrase in the context-free grammar

Static semantic analysis

establishes attributes of names in declarations and ensures that the use of these names conforms to their declared attributes

Definition

in C and C++, a declaration that binds all potential attributes

Prototype

function declaration that specifies the data type but not the code to implement it

Block

a sequence of declarations followed by a sequence of statements

Compound statements

blocks in C that appear as the body of functions or anywhere an ordinary program statement could appear

Local declarations

associated with a block

Nonlocal declarations

associated with surrounding blocks

Each declared name has a ________________containing a ____________ and an _______

lexical address, level number, offset

Scope of a binding

region of the program over which the binding is maintained

Lexical scope

in block-structured languages, scope is limited to the block in which its associated declaration appears (and other blocks contained within it)

Declaration before use rule

in C, scope of a declaration extends from the point of declaration to the end of the block in which it is located

Visibility

includes only regions where the bindings of a declaration apply

Symbol table

Must support insertion, lookup, and deletion of names with associated attributes, representing bindings in declarations

scope analysis

-On block entry, all declarations of that block are processed and bindings added to symbol table

-On block exit, bindings are removed, restoring any previous bindings that may have existed

dynamic scoping

If symbol table is managed dynamically (during execution), declarations will be processed as they are encountered along an execution path

Overload resolution

process of choosing a unique function among many with the same name

Calling context

the information contained in each call

Environment

maintains the bindings of names to locations

Activation

a call to a function

Activation record

the corresponding region of allocated memory

____________________ of an object is the duration of its allocation in the environment

Lifetime (or extent)

Pointer

an object whose stored value is a reference to another object

Heap

area in memory from which locations can be allocated in response to calls to new

Dynamic allocation

allocation on the heap

Storage class

the type of allocation

-Static (for global variables)

-Automatic (for local variables)

-Dynamic (for heap allocation)

Variable

an object whose stored value can change during execution

Box and circle diagram

focuses on name and location

Assignment statement

principle way in which a variable changes its value

Address of operator (&) in C

turns a reference into a pointer to fetch the address of a variable

Assignment by sharing

the location is copied instead of the value

Assignment by cloning

allocates new location, copies value, and binds to the new location

Constant

an entity with a fixed value for the duration of its existence in a program

-Like a variable, but has no location attribute

-Sometimes say that a constant has value semantics

Literal

a representation of characters or digits

Compile-time constant

its value can be computed during compilation

Static constant

its value can be computed at load time

Manifest constant

a name for a literal

Dynamic constant

its value must be computed during execution

Alias

occurs when the same object is bound to two different names at the same time

Side effect

any change in a variable's value that persists beyond the execution of the statement

Dangling reference

a location that has been deallocated from the environment but can still be accessed by a program

-Occurs when a pointer points to a deallocated object

Garbage

memory that has been allocated in the environment but is now inaccessible to the program

Garbage collection

process of automatically reclaiming garbage

Translation unit

external declaration

Classes,structs, and name spaces

C++

Classes and packages

in Java