Flash Cards For Plc Exam 1

Front 1

What are the two broad categories of Programming Languages?

Back 1

Declarative and Imperative Languages

Front 2

What are the categories of Declarative Languages? List a programing language within each category.

Back 2

Functional Languages: Lisp, Scheme, Haskell, ML

Logical Languages: Prolog, VisiCalc

Front 3

What are the categories of Imperative Languages? List a language from each category.

Back 3

Von Neuman or Procedural Languages:
Fortran, Pascal, Basic, C, Perl

object-Oriented Languages:
Smalltalk, Eiffel, C++, Java, Python, Ruby

Front 4

What is compilation?

Back 4

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.

Front 5

What are the stages of compilation?

Back 5

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.

Front 6

What is an interpreter?

Back 6

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.

Front 7

Is java a compiled or interpreted language?

Back 7

A little bit of both.

javac compiles java source code into java byte code. java implements java byte code into machine dependent executable code.

Front 8

Contrast Compilation vs. Interpretation.

Back 8

Compilation:
-Better Performance/Optimization
--Can Make compile time rather than just run time decisions

Interpretation:
-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.

Front 9

What is Machine Language (ML)? What were its characteristics?

Back 9

Intructions gave directly to the proccesor as sequence of binary, hex, or octal instructions.

It was very tedious and extremely error prone.

ex)
27bdffd0 afbf0014 0c1002a8 00000000

Front 10

What is assembly language? What were its characteristics?

Back 10

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).

ex)
addiu sp, sp, -32

Front 11

What is a High Level Language (HLL)? When were (HLL's) first created, as what language?

Back 11

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)

Front 12

Why are there so many programming Language?

Back 12

Evolution:
-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.

Front 13

What four broad categories make a language succesfull? What does each of these categories mean?

Back 13

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.
-Portable.
-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

Front 14

List as many Language Desiderata as you can.

Back 14

-Efficiency of Execution.
-Readibility/Maintainability
-Implementability
-Expressivness/programming (people) efficiency
-Regularity
--Generality -avoid special cases
--Orthogonality -construct behavior should not depend on context
--Uniformity -Consistency of appearance and behavior
-Simplicity
-Extensibility
-Restrictability
-Consistency with accepted conventions
-Precisness -standardization
-Machine Independence
-Security

Front 15

Loosely define Declarative Languages.

Back 15

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.

Front 16

Loosely define Imperative Languages.

Back 16

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.

Front 17

Define Declarative Functional Languages.

Back 17

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.

Front 18

Define Declarative Logical Languages.

Back 18

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

Front 19

What is the Von Neuman Computer Architecture?

Back 19

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.

Front 20

Loosely define Imperative Object Oriented Languages.

Back 20

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.

Front 21

What are the major phases of compilation? Also include the synonym's they are known by.

Back 21

Lexical Analysis (Scanning)

Syntax Analysis (Parsing)

Semantic Analysis

Target Code Generation

Front 22

What is the role of the Scanner?

Back 22

The Role of the Scanner is to read characters from the source program and group them into tokens.

Tokens are identified using Reular Expressions

Front 23

What is a Token?

Back 23

A token is the smallest meaningfull unit of a program
-the "words" of the language

Front 24

What is a regular Expression? What kind of Regular Expressoin does a compiler use?

Back 24

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>

Front 25

What is Syntax analysis?

Back 25

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.

Front 26

What is a context Free Grammar?

Back 26

A context free grammar is any grammar where nonterminals appear singly on the left side of the productions.

Front 27

What is a Parse Tree? How do you build one?

Back 27

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.

Front 28

What is a (abstract) syntax tree?

Back 28

An (abstract) syntax tree is a tree such that only the important information is shown.

Front 29

What does Semantic Analysis Involve?

Back 29

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.

Front 30

What does Target Code Generation involve?

Back 30

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)

Front 31

What are reserved/Key words?

Back 31

Reserved/Key words are words that cannot be used as the name of anything in a definition.

Front 32

What are Predefined Identifiers?

Back 32

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.

Front 33

What is a regular Language? What is a context Free Language?

Back 33

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.

Front 34

What is a Kleene star?

Back 34

A kleen star in a regular expression indicates zero or more repetitions of the symbol to the left.

Front 35

What is Backus Naur Form?

Back 35

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.

Front 36

What is a derivation?

Back 36

A string of terminals in the language of the grammar.

Front 37

what is => in a production rule?

Back 37

=> is known as a meta symbol. Other meta symbols include the vertical bar | and the Kleene star *.

Front 38

What do the BNF extentions [ ] and { } mean?

Back 38

repetitive items are inclosed in a curly braces.

optional items are inclosed in brackets

Front 39

How does the concepts of a variable relate to the Von Neuman Computer Architecture?

Back 39

Variables are the abstraction of the "Memory" in a Von Neuman machine

Front 40

What are the six properties a variable has?

Back 40

Name
Address
Value
Type
Lifetime
Scope

Front 41

Important Characteristics of a Variables Address?

Back 41

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.

Front 42

What is an alias?

Back 42

When more than one variable can be used to access the same memory location, the names are called aliases.

Front 43

What is the value of a variable?

Back 43

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

Front 44

What is Binding?

Back 44

Binding is an association between an attribute and an entity, or between an operation and a symbol

Front 45

Binding time is the time at which binding takes place. How many types of binding times are there? What are they? briefly describe each.

Back 45

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).

Front 46

Static vs Dynamic Bindings

Back 46

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

Front 47

Explicit vs Implicit Declarations. Why are explicit declarations possibly better?

Back 47

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

Front 48

Difference between definition and declaration.

Back 48

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.

Front 49

What is the scope of a declaration (variable)?

Back 49

The scope of a declaration is the region of the program to which the bindings established by the declaration apply.

Front 50

What is a block structured language. What characteristics of variables does it concern itself with?

Back 50

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).

Front 51

What is Dynamic Type Binding? What property of Variables does it relate to? What are it's disadvantages?

Back 51

Dynamic type binding occurs when the variable is assigned a type when it is assigned a value in an assignment statement

Duh Type

Disadvantages:
-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

Front 52

Allocation vs Dealocation. What do these two concepts relate to?

Back 52

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

Front 53

What are static Variables? Advantages and Disadvantages?

Back 53

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

Front 54

What are Stack Variables?

Back 54

Stack variables are dynamic variables whose storage bindings are created when their declaration statements are elaborated

Front 55

What are heap Variables? What are they used for? What are their main disadvantage?

Back 55

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

Front 56

What is Scope?

Back 56

The scope of a variable is the range of statements in which the variable is visible

Front 57

What does it mean for a variable to be visible?

Back 57

A variable is visible in a statement if it can be referenced in that statement

Front 58

What are scope rules?

Back 58

The scope rules of a language determine how a particular occurrence of a name is associated with a variable

Front 59

What does local mean?

Back 59

Variables are local to the block they are declared in

Front 60

what are non-local variables?

Back 60

Non-local variables are those that are visible within a block different from the one in which they are declared

Front 61

static vs dynamic scope

Back 61

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.

Front 62

What is a scope hole?

Back 62

Under either lexical or dynamic scope, a nested or more recent declaration can mask a prior declaration creating a scope hole

Front 63

What is the symbol table? When is it maintained? What is it called during translation? What is it called during execution?

Back 63

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).

Front 64

Differences of the symbol table when dealing with lexical vs dynamic scoping.

Back 64

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).

Front 65

What is Overloading? How does it relate to the symbol table?

Back 65

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.

Front 66

What does a typical enviroment contain?

Back 66

A stack, heap, and area for global static variables.

Front 67

What is a complete record of a call on a stack called?

Back 67

A complete record of a call on the stack is called an activation record or frame.

Front 68

How can tokens for any language be specified?

Back 68

by regular expressions.

Front 69

What is the form of a regular expression? (Use a Right regular expression)

Back 69

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.

Front 70

What are the three types of symbols in a production? describe each of them.

Back 70

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

Metasymbol:
-Punctuation to identify parts of production.

Front 71

What is a parse tree, how is it constructed?

Back 71

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.

Front 72

What is an abstract syntax tree?

Back 72

An abstract syntax tree is a parse tree that has been reduced to only essential structures. In other words all cascades have been removed.

Front 73

Using a example define the difference between a context free language and a context free grammar.

Back 73

Context-Free Language: {(a^n)(b^n) :n >= 0)

Context-Free Grammar: S-> aSb | (NULL)

Front 74

What are the two types of translators? How are they different?

Back 74

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.

Front 75

What is ambiguity, how can it be detected?

Back 75

Ambiguity is when picking a different order of evaluation can result in the same sentence but differnet evaluation orders.

Front 76

What is setential form?

Back 76

where the derivation is shown like this:
S -> w1 -> w2 -> w3

Front 77

What does cannoical form mean?

Back 77

a rightmost derivation

Front 78

What does yield mean?

Back 78

Yield means the final setential form, consisting solely of terminals.

Front 79

What is type checking?

Back 79

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.

Front 80

What is coercion?

Back 80

Coercion is the proccess of converting one variable to a desired type.