CPSC 3520

Moore's Law

Stated 1965 by Gordon Moore, computer hardware doubles in performance every 18 months (factor of 100 every 10 years). No corollary for software. Postulates doubling computer hardware every 18 months.

Babbage Difference Engine

Digital device operated on discrete digits. Early mechanical computer

ENIAC

First programmable general-purpose electronic digital computer. Early tube-based computer.

Program

A syntactically and semantically correct string from a language.

Programming Language

Notational system for human-machine interaction

Formal Grammar

Rules defining syntax

Alphabet

The list of symbols that can be used to form words and sentences

Generative

Mode of using grammar where the grammar is used to create a string of terminal symbols using P; a sentence in the language of the grammar is thus generated.

Analytic

Mode of using grammar where given a sentence together with the specification of G, one seeks to determine if the sentence was generated by G and if so, the structure of the sentence

G(Vt,Vn,S,P). What is Vt?

a set of terminal or primitive symbols, these are the elemental 'building blocks' of the grammar

G(Vt,Vn,S,P). What is Vn?

a set of non-terminal symbols or variables which are used as intermediate quantities in the generation of an outcome consisting solely of terminal symbols

G(Vt,Vn,S,P). What is P?

a set of productions which govern how strings may be formed, gives grammar its 'structure'

G(Vt,Vn,S,P). What is S?

a starting symbol

L(G)

Language generated by grammar G, is the set of all strings which satisfy that each string consists solely of terminal symbols from Vt of G and each string was produced from S using P of G

V*

is denoted the closure set of V and V+ = V* - {E} is often called the positive closure of V

T0 Language

all grammars, all touring computable languages

T1 Language

context sensitive grammars (CSG)

T2 Language

context free grammars (CFG), push-down automata

T3 Language

regular grammars, finite-state automata

Context-sensitive language

restricts productions to ααiβ → αβiβ, meaning βi replaces αi in the context of α and β where α, β ∈ (VN ∪ VT )∗ , αi ∈ VN and βi ∈ (VN ∪ VT )∗ − {#}

Context-free language

production restrictions are α1 = S1 ∈ VN, |S1| ≤ |β2|

Regular Language

productions are of the form a -> by where Where a is an element of VN, b is an element of VT and g is an element of VN U

Finite State Automata

machine that has a finite set of states, a set of transitions between states, and input tape and an output tape. The machine reads one symbol (which is then discarded) each cycle from the input tape. The symbol read is used with the current state to decide what state to go to next, and a single symbol is written to the output tape. Neither tape can be read ahead or behind the current position on the tape.

Push-down automata

Includes all of the same features as a finite state automata, plus a stack structure. In each cycle, in addition reading, writing, and changing state, the machine can either push or pop symbols onto or off of the stack. There is not normally any ability to peek at the stack, though in some compiler implementations the ability to peek at the stack and look ahead in the input affords some degree of optimization.

Regular Expression

are a shorthand notation for describing the strings from regular languages, and thus the languages themselves

Atom: A symbol from the alphabet is a RE: a

Represents matching the symbol

Concatenation: two RE adjacent to one another is a RE: ab

Represents one RE followed by the other RE

Alternation: two RE separated by a vertical line is a RE: a|b

Represents selection of one RE or the other RE

Kleene star: an RE followed by an asterisk is a RE: a*

Represents zero or more copies of the RE

Parenthesization: a RE in parenthesis is a RE: (a)

Represents grouping and scope for other operators

Lexical

structure that indicates the constraints on the tokens, or lexical units, which define the basic "words" or (multi-symbol) terminals of the language.

Syntax

Defines how tokens are combined into sentences

Semantics

Defines the logical meaning of sentences

Parser

A grammatical recognizer. Parsing is to see if the string of tokens is derivable according to the non-lexical syntax of the language

Scanner

Scanning is used to see if we can recognize all terminals in the program.

Top-down parse

Filling the interior of the tree from the top down (from the root of the tree)

Bottom-up parse

Working from the bottom up (begin with the terminal symbols)

Imperative Language

Composed of step-by-step instructions for the computer. C or Java (aka procedural programming)

Declarative Language

The desired result is described directly (Prolog)

Functional Language

Have a mathematical style. Applies functions to arguments (ML)

Rule-Based Language

Programs are composed by a set of rules.

Event-driven language

Entities (objects, services, etc) communicate indirectly by sending messages to one another through an intermediary

Parallel Language

Either uses message passing to communicate or manipulates shared memory variables

What does BNF stand for?

Backus Naur Form

What is BNF?

A language for writing programming language grammars

What does CFL stand for?

Context Free Language

What is CFL?

A language generated by a context-free grammar and gets accepted by a pushdown automata

What does CNF stand for?

Chomsky Normal Form

What is CNF?

Each production of G must be in either A -> BC or A -> a form

What does CYK stand for?

Cocke-Younger-Kasami

What is CYK?

A parsing approach which will parse string x in a number of steps proportional to |x|^3. Requires the CFG to by in CNF.

Dynamic programming

Breaking down an optimization problem into simpler sub-problems and storing the solution to each sub-problem so that each one is only solved once

Token

Lexical units which define the basic "words" or multi-symbol terminals of the language (aka basic component of source code e.g. operators, constants, etc.)

Terminal

(A) Primitive symbols. Elementary symbols of the language defined as a part of a formal grammar

Non-terminal

(letter) are replaced by groups of terminal symbols according to the production rules.

Identifier

A name for a variable or type

Reserved Word

Cannot be used an an identifier (int)

Expression

Syntatic entity in a programming language that may be evaluated to determine its value

Conditional

if statements

Production

rules that govern how strings may be formed

Moore's Law

Stated 1965 by Gordon Moore, computer hardware doubles in performance every 18 months (factor of 100 every 10 years). No corollary for software. Postulates doubling computer hardware every 18 months.

Babbage Difference Engine

Digital device operated on discrete digits. Early mechanical computer

ENIAC

First programmable general-purpose electronic digital computer. Early tube-based computer.

Program

A syntactically and semantically correct string from a language.

Programming Language

Notational system for human-machine interaction

Formal Grammar

Rules defining syntax

Alphabet

The list of symbols that can be used to form words and sentences

Generative

Mode of using grammar where the grammar is used to create a string of terminal symbols using P; a sentence in the language of the grammar is thus generated.

Analytic

Mode of using grammar where given a sentence together with the specification of G, one seeks to determine if the sentence was generated by G and if so, the structure of the sentence

G(Vt,Vn,S,P). What is Vt?

a set of terminal or primitive symbols, these are the elemental 'building blocks' of the grammar

G(Vt,Vn,S,P). What is Vn?

a set of non-terminal symbols or variables which are used as intermediate quantities in the generation of an outcome consisting solely of terminal symbols

G(Vt,Vn,S,P). What is P?

a set of productions which govern how strings may be formed, gives grammar its 'structure'

G(Vt,Vn,S,P). What is S?

a starting symbol

L(G)

Language generated by grammar G, is the set of all strings which satisfy that each string consists solely of terminal symbols from Vt of G and each string was produced from S using P of G

V*

is denoted the closure set of V and V+ = V* - {E} is often called the positive closure of V

T0 Language

all grammars, all touring computable languages

T1 Language

context sensitive grammars (CSG)

T2 Language

context free grammars (CFG), push-down automata

T3 Language

regular grammars, finite-state automata

Context-sensitive language

restricts productions to ααiβ → αβiβ, meaning βi replaces αi in the context of α and β where α, β ∈ (VN ∪ VT )∗ , αi ∈ VN and βi ∈ (VN ∪ VT )∗ − {#}

Context-free language

production restrictions are α1 = S1 ∈ VN, |S1| ≤ |β2|

Regular Language

productions are of the form a -> by where Where a is an element of VN, b is an element of VT and g is an element of VN U

Finite State Automata

machine that has a finite set of states, a set of transitions between states, and input tape and an output tape. The machine reads one symbol (which is then discarded) each cycle from the input tape. The symbol read is used with the current state to decide what state to go to next, and a single symbol is written to the output tape. Neither tape can be read ahead or behind the current position on the tape.

Push-down automata

Includes all of the same features as a finite state automata, plus a stack structure. In each cycle, in addition reading, writing, and changing state, the machine can either push or pop symbols onto or off of the stack. There is not normally any ability to peek at the stack, though in some compiler implementations the ability to peek at the stack and look ahead in the input affords some degree of optimization.

Regular Expression

are a shorthand notation for describing the strings from regular languages, and thus the languages themselves

Atom: A symbol from the alphabet is a RE: a

Represents matching the symbol

Concatenation: two RE adjacent to one another is a RE: ab

Represents one RE followed by the other RE

Alternation: two RE separated by a vertical line is a RE: a|b

Represents selection of one RE or the other RE

Kleene star: an RE followed by an asterisk is a RE: a*

Represents zero or more copies of the RE

Parenthesization: a RE in parenthesis is a RE: (a)

Represents grouping and scope for other operators

Lexical

structure that indicates the constraints on the tokens, or lexical units, which define the basic "words" or (multi-symbol) terminals of the language.

Syntax

Defines how tokens are combined into sentences

Semantics

Defines the logical meaning of sentences

Parser

A grammatical recognizer. Parsing is to see if the string of tokens is derivable according to the non-lexical syntax of the language

Scanner

Scanning is used to see if we can recognize all terminals in the program.

Top-down parse

Filling the interior of the tree from the top down (from the root of the tree)

Bottom-up parse

Working from the bottom up (begin with the terminal symbols)

Imperative Language

Composed of step-by-step instructions for the computer. C or Java (aka procedural programming)

Declarative Language

The desired result is described directly (Prolog)

Functional Language

Have a mathematical style. Applies functions to arguments (ML)