CSE 3302 Exam 3 vocab

Syntax

The structure of a language

Important

Every modern computer scientist needs to know how to read, interpret, and apply BNF descriptions of language syntax

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 several cotegories

Reserved words (or keywords

Literals or constants

Special symbols, such as “;”m”<=”, or “+”

Identifiers

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

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

Productions

another name for grammar rules

Backus-Naur form

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

Start symbol

a nonterminal representing the entire top-level phrase being defined

Nonterminals

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

Parse tree

graphical depiction of the replacement process in a derivation

Nodes

Have at least one child are labeled with nonterminals

Leaves

(nodes with no children) are labeled with terminals

Abstract syntax trees (or syntax trees)

trees that abstract the essential structure of the parse tree

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

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

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(EBNF)

Recursive-descent parsing

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

YACC

A widely used parser generator

• Freeware version is called Bison

• Generates a C program that uses a bottom-up algorithm to parse the grammar

Generates a procedure yypars(EBNF) from the grammar, which must be called from a main procedure

Assumes that tokens are recognized by a scanner procedure called yylex (Regex→Tokens), which must be provided

Names (or identifiers)

a fundamental abstraction mechanism used to denote language entities or constructs

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

aoccurs prior to execution

Dynamic binding

occurs during execution

Static attribute

an attribute that is bound statically; can be bound during translation, during linking, or during loading of the program

Dynamic attribute

an attribute that is bound dynamically; can be bound at different times during execution, such as entry or exit from a procedure or from the program

Lexical analysis

determines whether a string of characters represents a token (scanning)

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; selected (“that”)

Nonlocal declarations

associated with surrounding blocks

Scope of a binding

region of the program over which the binding is maintained

(region where the name is meaningful)

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

Overload resolution

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

Activation

a call to a function (Block)

Activation record

the corresponding region of allocated memory (stack frame)

Pointer

an object whose stored value is a reference to another object (address)

Heap

locations can be allocated in response to calls to new

Dynamic allocation

allocation on the heap