Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key


Play button


Play button




Click to flip

80 Cards in this Set

  • Front
  • Back
What are the two broad categories of Programming Languages?
Declarative and Imperative Languages
What are the categories of Declarative Languages? List a programing language within each category.
Functional Languages: Lisp, Scheme, Haskell, ML

Logical Languages: Prolog, VisiCalc
What are the categories of Imperative Languages? List a language from each category.
Von Neuman or Procedural Languages:
Fortran, Pascal, Basic, C, Perl

object-Oriented Languages:
Smalltalk, Eiffel, C++, Java, Python, Ruby
What is compilation?
Compilation occurs when a compiler translates a source program (high level source code) into a target program (machine language or object code)

The Locus of control during compilation is on the compiler. During execution the locus of control is on the target program.
What are the stages of compilation?
The preproccesor generates intermediate source code with removed comments and expanded macros.
The intermediate source code is then translated into an object file
The Object file is then linked with other object files via the linker.
What is an interpreter?
An Interpreter is a program which reads statements from the source program language and executes them.
The locus of control is always on the interpreter.
The interpretter implements a "virtual machine language" whose "machine language is the high level programming language.
Is java a compiled or interpreted language?
A little bit of both.

javac compiles java source code into java byte code. java implements java byte code into machine dependent executable code.
Contrast Compilation vs. Interpretation.
-Better Performance/Optimization
--Can Make compile time rather than just run time decisions

-Better diagnostics due to source code being executed directly.
--How is source code debugged in compilled enviroment.
-Easier to make your source code platform independent.
What is Machine Language (ML)? What were its characteristics?
Intructions gave directly to the proccesor as sequence of binary, hex, or octal instructions.

It was very tedious and extremely error prone.

27bdffd0 afbf0014 0c1002a8 00000000
What is assembly language? What were its characteristics?
Operations now expressed as mnemonic abbreviations. (1 to 1 correspondence between machine instructions and mnemonic opcode)

Aseembler handles mnemonic -> ML translation

instructions still unique to specific proccesor (like machine code).

addiu sp, sp, -32
What is a High Level Language (HLL)? When were (HLL's) first created, as what language?
A high level language is any language that has the possibility of machine independence (eg, no assembly or less).

Numerical computations can be expressed as mathematical computations.

Early Players:
Fortran (1954), Algol 58 (1958), Lisp (1958), Basic (1964), Prolog (1970), C (1971), Scheme (1975), c++ (1983), Java (1995), C# (2000)
Why are there so many programming Language?
-Computer science is less than 50 years old
-Were constantly finding better ways to do things
-Improvments in tech. allow us to do more with less
Special Purposes:
-Lisp is good for manipulating symbolic data and complex data structures.
-Snobol and Perl are good for manipulating character strings.
-C is good for low-level system programming.
-Prolog is good for reasoning about logical relationships among data.
-Java is good at cross platform web development.
-Python is good for rapid prototype implemenation.
Personal Preferences:
-People are often religious about their language of choice.
-We're creatures of habit. Once we learn something one way, we tend to stick to it.
What four broad categories make a language succesfull? What does each of these categories mean?
Expressive Power:
-Language features affect a programmers ability to write clear, concise, readable code.
-Abstraction facilities play a key role
Ease of Implementation:
-Low learning curve.
-Easily available and (ussually) free.
Excellent Compilers:
-Fortran set the precedent.
-Optimize code to maximize performance and minimize overhead.
Economics, Patronage and Inertia:
-Corporate Backing
--Fortran, Cobol and PL/I backed by IBM
--ADA owes existence to USDOD
List as many Language Desiderata as you can.
-Efficiency of Execution.
-Expressivness/programming (people) efficiency
--Generality -avoid special cases
--Orthogonality -construct behavior should not depend on context
--Uniformity -Consistency of appearance and behavior
-Consistency with accepted conventions
-Precisness -standardization
-Machine Independence
Loosely define Declarative Languages.
Declarative Languages focus on what the system is supposed to do.

It describes the problem as a set of conditions and lets the computer figure out how to satisfy them.

Other way of doing it is just defining functions and sorta letting them work together to solve a problem.

Declarative is considered more "high level" than imperative.
Loosely define Imperative Languages.
Focus on how the computer should do it.

Computation is described in terms of program state and statements that change behavior.

Predominant over declarative primarily for performance reasons.
Define Declarative Functional Languages.
Treats computation as teh evaluation of mathematical functions

A program is considered a function from input to output, defined in terms of simpler functions.

Functions do not modify the arguments, they simply return new values.
Define Declarative Logical Languages.
A set of attributes that a solution should have are specified, rather than a set of steps to obtain such a solution.

Facts + Rules = Results

Monkey and Banana Problem
What is the Von Neuman Computer Architecture?
The Von Neuman Computer Architecture is made up of Memory and the CPU. Memory contains instructions and data. CPU contains the control unit and the ALU. The control unit reads instructions, then reads data, passes data to ALU, and then writes ALU's compuation to memory.
Loosely define Imperative Object Oriented Languages.
Computation is performed as interactions between semi-independent objects, each of which has its own internal state (data) and behaviors (methods) to manage that state.

OOP refers primarily to the practice of viewing software as the objects it manipulates, rather than the actions it performs.
What are the major phases of compilation? Also include the synonym's they are known by.
Lexical Analysis (Scanning)

Syntax Analysis (Parsing)

Semantic Analysis

Target Code Generation
What is the role of the Scanner?
The Role of the Scanner is to read characters from the source program and group them into tokens.

Tokens are identified using Reular Expressions
What is a Token?
A token is the smallest meaningfull unit of a program
-the "words" of the language
What is a regular Expression? What kind of Regular Expressoin does a compiler use?
A regular expression is a way of defining a string or group of strings.

Bachus Normal Form (BNF) is the form used to form strings in computer science. It is of the form
<exp> ::= <exp> + <exp> | <number>
What is Syntax analysis?
Syntax Analysis organizes tokens into a parse tree that represents constructs in terms of their constituents.

Constituents combine by a set of potentially recursive rules known as context-free grammars.
What is a context Free Grammar?
A context free grammar is any grammar where nonterminals appear singly on the left side of the productions.
What is a Parse Tree? How do you build one?
A Parse tree describes graphically the replacement process for a derivation. All the terminals and nonterminals of a derivation are included in the parse tree. The Nonterminals are within the tree and the terminals make up the leafs. The terminals should be equivilant to the sentence in question.
What is a (abstract) syntax tree?
An (abstract) syntax tree is a tree such that only the important information is shown.
What does Semantic Analysis Involve?
The discovery of the meaning of a program:
-Recognize which identifiers map to which program entities
-Does type checking on oth identifiers and expressions
-Most of the compile errors are generated here

Builds and Maintains a Symbol Table:
-A data structure that includes each identifiers type, internal structure, and scope.
What does Target Code Generation involve?
Crates the target language from the symbol table and syntax tree:
-Traverses the symbol table to assign locations to variables
-Traverses the syntax tree
--Generates loads and stores for variable references interspersed with appropriate arithmetic operations, loads and branches. (Machine/Assembly Code)
What are reserved/Key words?
Reserved/Key words are words that cannot be used as the name of anything in a definition.
What are Predefined Identifiers?
Predefined Identifiers have special meanings, but can be redefined (though they probably should not be).
examples are anything in java.lang, or packages such as String, Object, System, Integer.
What is a regular Language? What is a context Free Language?
A regular expression is any set of strings that can be specified by the following three rules:
-Concatenation -Combining
-Alternation/Selection -choosing between a finite set of alternatives
-Kleene closure -Repetition a arbitrary number of times.

A context Free Language is a regular language that also has the possibility of recursion.
What is a Kleene star?
A kleen star in a regular expression indicates zero or more repetitions of the symbol to the left.
What is Backus Naur Form?
Backus Naur Form is the computer scientist's notation for a Context-Free Grammar.

A series of rules called productions that relate structures called nonterminals to other nonterminals and irreducible structures called terminals.
What is a derivation?
A string of terminals in the language of the grammar.
what is => in a production rule?
=> is known as a meta symbol. Other meta symbols include the vertical bar | and the Kleene star *.
What do the BNF extentions [ ] and { } mean?
repetitive items are inclosed in a curly braces.

optional items are inclosed in brackets
How does the concepts of a variable relate to the Von Neuman Computer Architecture?
Variables are the abstraction of the "Memory" in a Von Neuman machine
What are the six properties a variable has?
Important Characteristics of a Variables Address?
A address is often known as the variables L-Value because that is what is required on the left side of an assignment statement.

The same variable name can be associated with different addresses at different places and different times during a programs execuition.
What is an alias?
When more than one variable can be used to access the same memory location, the names are called aliases.
What is the value of a variable?
The value of a variable is the contents of the abstract memory cell/s associated with the variable

A variables value is often referred to as its R-value, because it is required when the variable is used on the right side of an assignment statement

To access the R-value, the L-value must be determined first
What is Binding?
Binding is an association between an attribute and an entity, or between an operation and a symbol
Binding time is the time at which binding takes place. How many types of binding times are there? What are they? briefly describe each.
Language Design Time:
- * means multiply operation

Language Implementation Time
- int is bound to the range of –2147483648 and 2147483648

Compile Time
-A variable is bound to a particular data type

Load Time
-A variable is bound to a storage cell

Link Time
-A call to a library subprogram is bound to that subprogram’s code

Run Time
-The value is bound to a variable as a result of a statement

Note that in an interpreted language, the variable is not usually bound at load time (Java).
Static vs Dynamic Bindings
A binding is static if it first occurs before run time and remains unchanged throughout program execution

If a binding occurs during run time or can change during the course of program execution, it is dynamic
Explicit vs Implicit Declarations. Why are explicit declarations possibly better?
An explicit declaration is a statement in a program that lists variable names and specified their type

double gpa; /* Java double */
$count = 1; # Perl scalar

An implicit declaration is a means of associating variables with types through default conventions

I = 5 ! Fortran Integer
A = 3.99 ! Fortran Real

Implicit declarations can be detrimental to reliability because they prevent the compilation process from detecting typographical errors
Difference between definition and declaration.
int x = 0; (definition)
int f(double); (declaration)

Definitions specifies data type, intial value, scope, and location in memory (explicitly and implicitly)

Declarations only specify type, they are not working code.
What is the scope of a declaration (variable)?
The scope of a declaration is the region of the program to which the bindings established by the declaration apply.
What is a block structured language. What characteristics of variables does it concern itself with?
In a block-structured language, the scope is typically the code from the end of the declaration to the end of the "block" (indicated by braces {…} in C and Java) in which the declaration occurs.

Scope can extend backwards to the beginning of the block in certain cases (class declarations in Java and C++, top-level declarations in Scheme).
What is Dynamic Type Binding? What property of Variables does it relate to? What are it's disadvantages?
Dynamic type binding occurs when the variable is assigned a type when it is assigned a value in an assignment statement

Duh Type

-Type checking must be done at run time
-The storage used for a variable must be of varying size
-Languages must be implemented using pure interpreters rather than compilers
Allocation vs Dealocation. What do these two concepts relate to?
Allocation is binding a variable to a memory cell from the available memory pool

Deallocation is process of placing a memory cell that has been unbound from a variable, back into the pool

The lifetime of a variable is the time during which the variable is bound to a specific memory location
What are static Variables? Advantages and Disadvantages?
Static variables are bound to memory cells before program execution begins
-Global variables are the classic example.

Advantage –
efficient because no need for indirect addressing
No run-time overhead for allocation and deallocation

Disadvantages –
Doesn’t support recursive subprograms
Storage cannot be shared/reused by different variables
What are Stack Variables?
Stack variables are dynamic variables whose storage bindings are created when their declaration statements are elaborated
What are heap Variables? What are they used for? What are their main disadvantage?
Heap Variables are nameless, abstract memory cells that are allocated and deallocated from the heap by explicit run-time instructions

int *intnode;

intnode = new int(5);

delete intnode;

Used for dynamic structures: lists, trees, etc.

Disadvantages are difficulty of use and cost
What is Scope?
The scope of a variable is the range of statements in which the variable is visible
What does it mean for a variable to be visible?
A variable is visible in a statement if it can be referenced in that statement
What are scope rules?
The scope rules of a language determine how a particular occurrence of a name is associated with a variable
What does local mean?
Variables are local to the block they are declared in
what are non-local variables?
Non-local variables are those that are visible within a block different from the one in which they are declared
static vs dynamic scope
If scope is managed statically (prior to execution), the language is said to have static or lexical scope ("lexical" because it follows the layout of the code in the file).

If scope is managed directly during execution, then the language is said to have dynamic scope.
What is a scope hole?
Under either lexical or dynamic scope, a nested or more recent declaration can mask a prior declaration creating a scope hole
What is the symbol table? When is it maintained? What is it called during translation? What is it called during execution?
The Symbol Table is a dictionary or table is used to maintain the identifier/attribute bindings.

It can be maintained either during translation or execution or both. (Pre-translation entities are entered into the initial or default table.)

During translation this table is called the symbol table.

During execution this table is called the environment.

If both are maintained, the environment can usually dispense with names, keeping track only of locations (names are maintained implicitly).
Differences of the symbol table when dealing with lexical vs dynamic scoping.
Symbol table is constructed as declarations are encountered (insert operation).

With lexical scope, insertions follow static structure of source code.

With dynamic scope, insertions follow the execution path.

With lexical scope, lookups occur either as names are encountered in the symbol table to that point (declaration before use—C), or all lookups are delayed until after the symbol table is fully constructed (Java class—scope applies backwards to beginning of class).

With dynamic scope, lookups occur as names are encountered (in symbol table to that point).
What is Overloading? How does it relate to the symbol table?
Overloading is a property of symbol tables that allows them to successfully handle declarations that use the same name within the same scope.

It is the job of the symbol table to pick the correct choice from among the declarations for the same name in the same scope. This is called overload resolution.

It must do so by using extra information, typically the data type of each declaration, which it compares to the probable type at the use site, picking the best match.

If it cannot successfully do this, a static semantic error occurs.
What does a typical enviroment contain?
A stack, heap, and area for global static variables.
What is a complete record of a call on a stack called?
A complete record of a call on the stack is called an activation record or frame.
How can tokens for any language be specified?
by regular expressions.
What is the form of a regular expression? (Use a Right regular expression)
Regular expressions have three basic operations: concatenation, repetition, and choice or selection.

OR for a RIGHTformal grammar (N, Σ, P, S), all P are of the form:
1. A → a where A a non-terminal in N and a a terminal in Σ
2. A → aB where A and B in N and a in Σ
3. A → ε where A in N.
What are the three types of symbols in a production? describe each of them.
Terminal symbols (or terminals):
-symbols (lexical elements or tokens) fromt the language being defined.
-in case of english this would be all words in dictionary.

Metavariables (or non-terminals):
-Represents linguistic concepts from the language.
-in case of english include concepts such as "sentence", "noun", etc

-Punctuation to identify parts of production.
What is a parse tree, how is it constructed?
A parse tree is a graphical derivation of the semantics of a program (its meaning). It is built by starting at the topmost level of a context free language and going down until all Metavariables have become Terminal symbols.
What is an abstract syntax tree?
An abstract syntax tree is a parse tree that has been reduced to only essential structures. In other words all cascades have been removed.
Using a example define the difference between a context free language and a context free grammar.
Context-Free Language: {(a^n)(b^n) :n >= 0)

Context-Free Grammar: S-> aSb | (NULL)
What are the two types of translators? How are they different?
A translator that executes a program directly is called a interpreter. A translator that produces a equivilant program suitable for execution is called a compiler.
What is ambiguity, how can it be detected?
Ambiguity is when picking a different order of evaluation can result in the same sentence but differnet evaluation orders.
What is setential form?
where the derivation is shown like this:
S -> w1 -> w2 -> w3
What does cannoical form mean?
a rightmost derivation
What does yield mean?
Yield means the final setential form, consisting solely of terminals.
What is type checking?
Type checking is making sure that a value passed as an argument or assigned to a value matches the expected type of the value. Many type checking can be done statically, some must be done dynamically.
What is coercion?
Coercion is the proccess of converting one variable to a desired type.