![[Santa Clara University]](../images/top.gif){kind=small}
and Computer Science
|
||
|
Department of
Mathematics and Computer Science |
|
|
||
Disclaimer: This has not been updated for the syllabus in use in Spring 2000 and 2002.
VOCABULARY Page/DEFINITION
-------------------------------------------------------------------------
syntax 1-1 The rules governing what constitutes
legal code of a language, i.e.,
rules determining the "form" of language
semantics underlying meaning given to legal
code in a language
pragmatics practical use and implementation
FORTRAN F1 FORmula TRANslation
column major F4 first subscripts vary fastest
concatenation F7 putting two strings together concat(fog hat)=foghat
library function F16 built in function
BNF 2-2 Backus-Naur Form
developed for more exactness in the specification of
the form of components of a language.
language 2-3 a set of sentences composed of words from a
vocabulary formed according to the rules of a grammar.
alphabet or vocabulary 2-4 a usually finite set of symbols
(words characters)
string or sentence a sequence of (0 or more) symbols from an alphabet.
empty string a string with no characters
dictionary over an alphabet is the set of all strings from
symbols in the alphabet.
language a subset of the dictionary restricted by certain
syntactical rules (of grammar)
programs the sentences of a programming language
length of string 2-5 the total number of symbols in the string
x* Kleene closure is the concatenation of 0 or more
instances of x
x+ Positive closure is the concatenation of 1 or more
instances of x.
concatenation on A,B are sets of strings;
sets of strings AB = {xy| x in A and y in B}
phrase-structure 2-6 a quadruple: (N, T, P, S) where:
grammar
N Non terminal symbols ie <verb>
T terminal symbols ie JUMP
P finite set of productions, rewrite rules
S start symbol in N or sentence symbol
Language L(G) defined by the grammar G is the set of sentences that
can be derived from the start symbol S by applying
productions in P.
sentential form of G is S or any string that can be derived from S.
sentence of G is a sentential from that contains only terminals.
meta symbols 2-8 ::=, <, >, |
::= replace -> in production rules
<,> always surround non-terminals
| "or" indicates alternatives
other meta symbols 2-10 [],{},{}+,{}i,j
[] surround optional parts of right hand sides
{} surround a string which can be repeated 0 or more times
{}+ surround a string which can be repeated 1 or more times
{}i,j surround "" "" "" between i and j times (inclusive)
ambiguous 2-11 a grammar that produces more than one
derivation for some sentence
SNOBOL purpose S1 to allow easy character string manipulation
literal string S6 a character string enclosed in quotes
fully parenthesized S34 an algebraic expression if, for
every operator, there is a set of parentheses
enclosing it with its operands.
parameters 3-1 the standard way to transfer information
between programs and subprograms.
formal parameter the identifier used in the definition and code of a
dummy parameter subprogram. It is associated with
information when the subprogram is actually called
during execution.
actual parameter the information in the calling program which give/gets
a value to/from a (formal) parameter in the subprogram
being called and thus is associated with it.
call by value 3-3 formal parameters are treated as local variables
when the subprogram is called. The formal parameters
are initialized to the VALUE of the actual parameters
in the calling program. Memory locations are separate
for the formal and actual parameters.
call by value-result 3-4 basically identical to call by value. Formal
parameters are treated as local variables when the
subprogram is called. Formal parameters are
initialized to the value of the actual parameters in
the calling program. Memory locations are separate for
the formal and actual parameters. However, upon
exiting from the subprogram, the final values of the
formal parameters are copied
into the actual parameters.
call by reference 3-6 the formal parameters are addresses to the memory
locations of the actual parameters. Thus for each pair
of formal-actual parameters there is only ONE memory
location. Whatever is changed in the subroutine is
also changed in the calling program.
call by name 3-7 The formal parameters are associated with the
actual parameters via addresses.However, if the formal
parameters is an expression, a thunk code is created
which leaves the expression unevaluated and reference
is made to that address.
aliasing 3-9 occurs when 2 or more variables are associated
with the same data object at the same time.
LISP L1 LISt Processing
functional notation L3 f(x) = some expression
lambda calculus L3 influential mathematical notation on LISP
atom L5 primitive data structure can be literal,
numeric or NIL
S-expression concatenation of atoms and S-expressions. A binary
tree whose nodes cannot contain information.
Some are lists.
CAR L6 the left subtree of an S-expression
CDR the right subtree of an S-expression
LIST L7 an S-expression such that each CDR is a list or NIL
If every CDR of a subsections of the S-expression
which is an atom, is the special NIL.
If the right most atom of every subtree is NIL.
LISP function L12 <syntax> the first element is the function name
and the rest are arguments.
LISP program a set of functions
Predicate function L16 Logical function or operators which return T / NIL
User defined function L23 consists of several components:
1. the LISP function name which indicates the defining
of a user function;
2. the literal atom which is the name of the user
function.
3. the lambda expression which contains:
a. parameters
b. the body of the user function
lambda expression A list of 3 elements:
1. the first is a literal atom LAMBDA
2. the second is a list of parameters
3. the third is the body of the user function
function name In LISP is DEFINE which takes as one argument a QUOTEd
list.
QUOTEd list A list of two elements:
1. the first being a the suer function name
2. the second being a lambda expression
divide and conquer L25 Operation: Evaluate the car, operate on the cdr.
sequential flow L27 PROG
PROG at least two arguments:
1. a list of local variables
2. other arguments are functions executed in order
LISP param pass L33 Usually call-by-value but could be call-by-name.
Pure LISP L34 Does not use PROG and employs the primitives.
Association List L38 The way the "most recent" binding (value) of a
given variable is referenced.
The A-list is a list of dotted pairs.
The CAR of each pair is a literal atom used as a
variable.
The CDR of each pair is the present value.
New associations are added (pushed) before the CAR
of the A-list.
A-list Function Calls L39 on entry, formal parameters are
paired with actual parameters and pushed on the A-list.
on exit, these pairs are deleted.
PROG on entry, local vars are paired with NIL and pushed
on exit, these pairs are deleted.
SETQ searches A-list for first entry of variable and
replaces CDR with new value. If the variable is not
found, it creates a new pair and pushes it.
Property list L40 Each atom has an associated property list. It
contains pairs in which the CAR is the property name
and the CDR is the value. If the atom is a function
name, its property list will contain an indicator
giving the function type.
PUT three arguments
PUTPROP 1. name of atom which gets property and value
2. is the property value
3. is the property title
E.G. (PUTPROP 'SAM 18 'AGE)
GET two arguments
1. the name of the atom.
2. the name of the property.
value: the value of the property.
E.G. (GET 'SAM 'AGE) => 18.
REMPROP L41 two arguments, removes the named property from
the P-list of the indicated atom.
Object List L42 the symbol table for LISP
LAVS L42 List of AVailable Space; Heap from which memory
locations are obtained when lists are created or
expanded. When LAVS is exhausted, a garbage collection
is performed.
Variables and Bindings
Referencing Environment 4-1 The set of associations available
for referencing at a given point in the program.
Some major classes:
1. Local Environment (new) associations created on entry to
the block or subprogram and including formal
parameters, local variables, internal subprograms.
2. Non-local environment (active and therefore) usable
associations previously created.
3. global environment associations created on entry to the
main program and still available.
BINDING 4-2 refers to associations between variable names and
memory locations which are in effect. The type of
binding determines the referencing environment.
GIVEN A BINDING STRATEGY AND A REFERENCING ENVIRONMENT:
Visible Identifiers refers to those active associates which are in the
referencing environment.
Invisible identifiers refers to those inactive associations which exist,
but are not in the referencing environment.
BINDING STRATEGIES 4-3
Deep Binding "most closely nested" uses static scope rules to
determine the referencing environment. It uses the
declaratives in the closest enclosing block which
defines that identifier. Defined at compile time.
Shallow Binding "most recently instantiated" binding. A dynamic
binding strategy in which associations are determined
at execution-time. uses "most recently called" block.
VISIBILITY 4-5
invisible an identifier association which is valid Immediately
Before the execution of a program block, but Not
During its execution, and becomes valid Immediately
After the ending of the program block.
static scope 4-6 The static scope of a declaration is that part of
the program text in which it is valid.
dynamic scope of a declaration is the set of active program blocks
in which it is visible.
COBOL C13
Data Transfer move data from one variable to another
Arithmetic Expression an expression which contains any arithmetic
calculations
Verb format C14 any arithmetic expression using the words for
the operators rather than the arithmetic signs
String manipulation C15 taking a string and being able to do thing
with it or to it (i.e. take it apart, concatenate,
etc.)
String Concatenation C16a taking two strings and putting them
together to make one string.
editing when one type of string is moved to another
(i.e. where the picture clauses are different)
legal moves C16b any move from one string type to another that
is allowed
Data Division C17 the third major division in a COBOL program that
contains the information for the compiler (data
dependent, but machine dependent)
File Section the section of the Data Division that specifies
the files being used for input and output
Working-Storage Section C18 the section of the Data Division
that has all of the variable declarations.
Level Numbers C19 the number next to the variable when it's
declared in the Working-Storage Section. used
indicate the relationship of data items to one
another (esp. subdivisions)
Independent Data Item a variable that is not a subdivision or is not
subdivided
Picture Clause C21 used to indicate the size of the data item
(i.e. maximum number of char/spaces/letters)
also indicates the type of variable
must have the key word PIC before the description
multiplication factor C23 a number in parenthesis AFTER the
type to indicate how many chars/digits
Value Clause C24 clause that comes after the PIC clause
to initialize the variable
Occurs Clause clause that appears in the declaration of
arrays and record
Records C27 a variable that has more than one field
associated with it
Qualification C28 telling the compiler which subdivision to
use when there are more than one with the same name in
different records to do this use
IN or OF or CORRESPONDING
Tables C29 in COBOL tables are the same thing as arrays
three subscripts max; uses []
cannot contain an expression in it
Path Name C30 the sequence of names used to identify a name that
is used more than once goes specific to general
Procedure Division C32 Section of the program that contains the user
defined paragraphs
Open C33 Command used to open files for INPUT or OUTPUT
INPUT Reserved word used to identify an input file
OUTPUT Reserved word used to identify an output file
READ Reserved work used to read information from
the input file
WRITE C34 Reserved word used to write information to the
output file
DISPLAY Reserved word used to display variables on the screen
Data Encapsulation 5-1 how to prevent data structures from being
manipulated by outside programmers
Parallel Processing Machine
possibility of simultaneous or concurrent
execution of diff sections/operations
Software Engineering large scale programming
global variables 5-4 variables that can be used throughout the
program
Parallelism P1 the ability of a machine to execute more than
one major code segment at the same time
Path-Pascal object P2 one version of parallel extension to Pascal
data type which encapsulates local variables
and internal subprograms
process subprogram with an independent execution sequence
associated with it
PATH-EXPRESSION P3 a structure which enables the programmer to
specify the synchronization of a subprogram within
objects
Instantiation PM* a process works like a procedure
it is called as if it were a procedure
Process Storage Consideration
storage from any process is acquired from the
heap of its parent
Process Lifetime the time that the process is being activated
Parameter Restriction the scope of an actual parameter which is
passed by reference to a process that must contain
scope of the process's declaration
Priority the order which the processes are to be executed
Simulated Time the time for which the delay statement runs
Interrupt Process suspension of a process while a delay is being
executed
C FG1 a language developed by Bell Labs Pascal like
MODULA-2 FG2 developed by Nicklaus Wirth, author Pascal
separately-compiled Modules
MODUlar LAnguage
designed for the LILITH
ADA Department of Defense
uses Packages
case sensitive the compiler considers upper and lower case letters
different (i.e. reserved words must be upper case)
Definition Module FM3 module that defines variables and procedures
Implementation Module module that gives the code for the definitions
in the definition module
Lambda Calculus LC-1 a model of computation and a tool for formal
language definition.
SYNTAX OF LC LC-3 Lexpr -> variable | L var Lexpr |(Lexpr Lexpr)
bound LC-7 A variable in Lexpr E if
a) it immediately follows L or
b) E contains a L-expr, LxE' and x is in E'
free not bound
Renaming Rule LC-8 E can be replaced by E(x=y) provided that
a) E contains no free occurrence of x
b) E contains no occurrence of y
Substitution Rule LC-9 An expression of the form (LxEA) can be
replaced by E(x=A) provided that
a) x is free in E
b) free variables in A are free in E
If a) or b) is not satisfied, apply the
renaming rule.
GRAMMARS AGAIN 6-1
Phrase Structure Grammar G a quadruple (N,T,P,S)
Non-Terminals N
Terminals T
Productions P
Start symbol S
Sentential form of G is either S or any string that can be derived
from S using rules of P.
Sentence of G is a sentential form containing only terminals.
Language L(G) is the set of all sentences of G.
Type 0 Grammar 6-3 no restrictions - PSG
Type 1 Grammar Context Sensitive Grammar
for each production a->b we have |a| <= |b|
Type 2 Grammar Context Free Grammar
each production is of the form A -> b and A is a N
Type 3 Grammar Right Linear Grammar
each production is of the form A -> x or A->xB
A,B in N and x is a string of terminals
Chomsky Hierarchy 6-4 The previous classification of grammars.
Notes: Every RLG is a CFG; every CFG is a CSG
all are PSG
Type n language defined by a type n grammar
Automata theory 6-6 the study of mathematical machines
Finite State Automata the simplest type of machine a
quintuple:(S,s,T,E,e)
S is the set of states
s the "start state"
T a subset of S, the set of terminal states
E (SIGMA) the set of input symbols
e (sigma) the "transition function" e: ExS->S
Type 3 Language/Grammar machine is finite state automaton
Type 2 Language/Grammar machine is deterministic push-down stack
automaton
Type 1 Language/Grammar machine is non-deterministic p d s a
Type 0 Language/Grammar machine is a Turing Machine (TAPE)
Leftmost derivation 6-8 the leftmost non-terminal in a sentential
form is replaced at each step.
Rightmost derivation the rightmost non-terminal in a
sentential form is replaced at each step.
Understanding Sentences 6-10 1."parse" the sentence
2. derive meaning from the resulting structure of
the parse tree
Prune 6-11 replace the leaves of a node with their meaning
Complete compiling process 6-14
1. Identify groups of single characters as "lexemes"
2. Parse the lexeme version into a tree
3. Give meaning to the tree
Phrase 6-15 u if A =*> u, and A is a Non terminal
Simple phrase u if there is a rule A->u in P an element of G
Handle the leftmost simple phrase in sentential form
Compiling repeatedly finding handles in a sentential form.
Right Recursive 6-27 a grammar that permits a derivation X =+> bX
Left Recursive a grammar that permits a derivation X =+> Xb
Self-embedding a grammar that permits s derivation x =+> bXa
cycle free a CFG if there is NO derivation of the form A =+> A
Lambda free a CFG is if 1. L isn't used or
2. S -> L is used and neither S nor L appear in any
other productions on the right hand side.
useless symbol Y in a CFG if there is NO derivation S =*> aYb =*> ayb
and a,y,b are elements of T*.
proper CFG if it is cycle free, Lambda free, and has no useless
symbols.
n n m m
Parikh's Theorem 6-30 L={a b a b | m,n >=1}
Disambiguate a grammar 6-31
1. specify the precedence rules of the operators, and
the associativity rules.
2. incorporate the rules into the grammar, usually
through stratification.
Precedence rules Expression is Expression + Term
Term is Term times a Factor
Factor is Primary ^ Factor
Primary is a or ( Expression )
Stratification involves introducing new non-terminals for each
priority/precedence level. The start symbol production
should head to the lowest precedence operator.
Markov Algorithm a program of steps-each similar to a production rule.
1. a re-write step is applied to the left-most
sub-string (which matches the pattern).
2. each step in the program (starting at the first) is
an attempt to be applied until one actually succeeds
with the (present-state of the) string.
Regular Expressions RE-1 Describe precisely the Right Linear languages.
Also used as a bridge between machines and grammars.
Class of RE's 1. the empty set, @@, is a reg expression;
2. the empty string, L, is a reg expression;
3. the single character, a in T, is a reg expression;
4. If P and Q are sets of reg expressions, then the
following are also:
a) P|Q = P+Q = P U Q
b) pq = {xy | x in P and y in Q}
c) p* = L + i=1 to inf U p(i)
5. Nothing Else is a reg expression.
Properties RE-2
1. p+q = q+p
2. a) p+(q+r) = (p+q)+r = p+q+r
b) p(qr) = (pq)r = pqr
3. a) p(q+r) = pq + pr
b) (p+q)r = pr + qr
4. a) @@ + p = p = p + @@ = p + p
b) Lp = p = pL
5. a) p + p(*) = p(*) = (p(*))*
b) @@p = @@
* has precedence over concatenation which has
precedence over +.
Usefulness abstract language theory RE-3
1. it provides a theoretical foundation for "real"
computer language concerns.
2. Some aspects provide helpful ways to describe
certain language concepts.
3. some aspects provide helpful ways to describe ways
to interpret languages.
Arden's Theorem RE-8 Given an equation of the form X = PX + Q,
1. X = P(*)Q is the solution
2. this solution is unique if L is not in P
3. if L is in P, then X = P(*)(Q+R) for R arbitrary
SAXPY LN-5 Sum of AX Plus Y
This page is maintained by Dennis C. Smolarski, S.J.
dsmolarski@math.scu.edu
Last updated: 17 April 2000. Minor updating: 1 March 2002.