COP 4020 Midterm Langley

What is a defining characteristic of the functional programming style we discussed the first week of class? 

It tends to avoid or "shy away" from the traditional variable assignment paradigm.

Imperative languages like C, Ada, and Fortran can be described as belonging to the "von Neumann" family. What would this imply?

They are based on the variable assignment paradigm and are conceptually close to the hardware.

What is a practical benefit of studying different programming languages?

It helps you avoid the "when you only have a hammer, everything looks like a nail" problem in computer science.

What is a common characteristic of scripting languages like Perl, Python, and Ruby?

They usually have outstanding library capabilities and are suitable for one-off, lightweight programming tasks.

Syntax analysis (parsing) takes the stream of tokens from the lexer and organizes them into what kind of data structure?

A parse tree.

In the C compilation toolchain, using the gcc -E command would stop the process after which phase?

After the preprocessor has run.

The techniques developed for parsing programming languages have another common and practical application. What is it?

Parsing configuration files for applications.

Which of the following best lists the first three phases of a typical compiler?

Lexical Analysis (Scanning), Syntax Analysis (Parsing), and Semantic Analysis.

Besides the fact that we "learn better ways and evolve," what is another major reason mentioned for the existence of so many different programming languages?

The need for specialization in a particular problem space, such as TeX for typesetting or Perl for regular expressions.

What is a general, high-level distinction between a compiler and an interpreter?

Compilers transform source code into a new, directly executable form, while interpreters execute the source code more directly.

What is a key characteristic of the "stored program" paradigm in modern digital computers?

Data and instructions are fundamentally the same thing, represented as bits, and instructions can be treated as data.

A scanner (lexer) converts a stream of characters into a stream of tokens. What is a formal method often used to specify the patterns for these tokens?

Regular expression

Regular expressions are built from concatenation, alternation, and repetition. What additional mechanism do context-free grammars (CFGs) add?

Recursion

In the C family of languages, what are tokens like parentheses bizarrely called?

Punctuators

What are the two fundamental actions performed in bottom-up parsing?

Shift and Reduce

The "scanning" phase of compilation is described as fast and relatively easy. What is one of its most important functions besides identifying tokens?

Removing the "detritus of comments."

A parser's primary job is to act as a language "recognizer." According to the notes, parsing has generally been the arena for what formalism?

Context-Free Grammars (CFGs)

A grammar that can produce a string in more than one way (i.e., has more than one parse tree for a single sentence) is called:

Ambiguous

Scanner generators like flex often first create a non-deterministic finite automaton (NFA) from a specification. What is the next step such scanners then typically perform?

Convert the NFA to a Deterministic Finite Automaton (DFA).

Which style of parser is typically written by hand as a set of mutually recursive functions?

LL (Top-down)

Some languages, like older FORTRAN, had rigid line formatting rules. What modern languages are mentioned as caring about indentation for semantic meaning?

Python and Haskell

In the context of interpreters and interactive programming environments, what does the acronym REPL stand for?

Read-Evaluate-Print-Loop

In an LL-family parser, action routines can be embedded at arbitrary points of a production rule's right-hand side.

True

Most modern programming languages are free format.

Which of the following is not free format?

Python

A ______ is the shortest string of characters that have meaning in a language.

Token

What category of programming language is C?

Imperative language

An LR-family parser is a

Bottom-up

Consider the following Haskell session:

Prelude> let (+) a b = a - b
Prelude> 9 + 7
2

Certainly 9 + 7 does not usually equal 2. What’s going on here?

This is an instance of Haskell allowing the built-in “+” operator to be redefined.

What is the role of the lexical analyzer (or scanner) in a compiler?

To remove comments and identify tokens from the raw source code.

Which of the following are among Donald Knuth's arguments for the relevance of assembly/machine language, especially in regard to his multivolume work The Art of Computer Programming?

Modern high-level languages go in and out of fashion over relatively short periods of time.

High-level languages are often weak for expressing low-level machine-specific concerns.

Programmers tend to prefer constructions that are simplest in a given high-level language, rather than those that are best for the machine.

Why have projects like GCC and Clang moved from using parser generators (like Bison) to hand-written recursive-descent parsers?

For complex languages like C++, hand-written parsers can provide better error messages and are easier to debug and maintain.

A compiler that performs __________  of boolean expressions will generate
code that skips the second half of a computation when the overall value can be determined
from the first half alone.

short-circuit evaluation

In a language with ______ scoping, the binding of variable names can be determined at compile time by examining the text of the program, without consideration of the flow of control at run time.

static / lexical

Code Sample 1:

int f(int y);  // This is a forward declaration


x[f(z)] = x[f(z)] + 1;

Code Sample 2:

int f(int y); // This is a forward declaration


int s = x[f(z)]; 

x[s] = x[s] + 1;

---

Consider the above C code samples 1 and 2. Clearly both of these are subject to the array index possibly going out of bounds. However, the first code sample is liable to another possible problem that the second is not. What is the possible problem?

The function f() may not be pure, and may not necessarily return the same value each time it is called with the value "z".

tuple → "(" number " ," number ") "
number → one digit*
digit → zero | one
zero → "0"
one → "1"

Consider the above regular grammar. Terminals are indicated by quote marks (i.e., "0" indicates a literal zero); non-terminals begin with a lower-case letter. Of the following examples, which would be recognized as a tuple in the above regular grammar (please indicate all of the correct answers)?

(11,10001)

(1,1)

Orthogonality in a programming language refers to all of these characteristics except:

features must be linearly dependent.

Which of the two answers fits better into the empty node above?

Interpreter

In a context-free grammar, the symbols that appear on the left-hand side of a production rule are called what?

Non-terminals

Consider the following Haskell interactive session:

Prelude> let x = [1..]
Prelude> let y = [2..]
Prelude> x == y
False

Clearly, the interpreter has concluded that these two infinite lists are not the same. What mechanism in Haskell is used to perform this feat?

lazy evaluation

A type ________ occurs when a language silently converts a value of one type to a second
type when the second type is necessary in a particular context.

coercion

Which of the following contribute to the success of a programming language?

Being easy to learn. Having excellent compilers and/or interpreters. Patronage from a large economic entity, such as Microsoft's support for C#. Expressiveness and the ability to abstract at a useful level.

int x = 1;

int *y;

y = &x; // y points to x

x = 2; // x's value changes

printf("*y == %d\n", *y);

Consider the above C code block. When it is executed, it prints "*y == 2". This is an example of:

an alias

Consider the following code:

x = y - z;

a = x + z;

When can a compiler safely rewrite these two lines to:

x = y - z;

a = y;

If the compiler can guarantee that there are no issues with precision, overflow, underflow, or unrepresentable values (e.g., NaN).

What category of programming language is Scheme?

Functional, with some imperative characteristics.

When might the use of a linear jump table for a case/switch statement be a poor idea?

when the labels are non-dense, such as when you have a few labels spanning a very large range like 0 to 2^24.

Which of the following is not an iterative mechanism?

an "if" statement

The lexical scanner is responsible for discovering:

tokens

True or false: In a one-pass compiler, scanning, parsing, and semantic analysis are all interleaved.

True

If a programmer can pass a hint on to the compiler that a function is both not directly and indirectly recursive and thus can use static storage rather than allocating space for each activation with a separate activation record, this is an example of

a pragma

A programming language construct is said to have a ___________ if it influences subsequent computation in any way other than by returning a value for use in the surrounding context.

side effect

If a recursive routine in C declares a static variable, can that variable’s storage be allocated statically?

Yes, since the point of such a variable is to allow activations to share state

Consider this Haskell session:

Prelude> let min a b = if a < b then a else b

Prelude> min 9 11

9

Prelude> min 11 9

9

Prelude> min "xyz" "abc"

"abc"

Note that the function min is defined over all totally ordered types although there is no direct specification of this when we define min in the first line (the other lines just show what happens when you evaluate min against the pairs (9,11), (11,9), and ("xyz","abc")). This illustrates what concept in Haskell?

polymorphism

In C, a void * is

a universal reference type.

The languages Perl, Ruby, and Python all fall into

the scripting language family

Conventionally, what we would call the slash “/” in the following fragment of C?

int x = a / b;

operator

In Perl, consider the following code:

$x = "1" + 2

This is perfectly legitimate code, and will produce a value of 3 for $x. This is an example of:

coercion

Programs that fail to reclaim space for objects that are no longer needed are said to

"leak memory".

Identify what the following code fragment is:

((lambda (x) (* x x)) 3)

A lambda expression being evaluated against the number 3.

Arrays are ubiquitous in programming languages; among the common attributes of arrays are

discrete index types.

The idea of having exception handling as a part of the semantics of a programming language was motivated by three of the following; which one was not such a motivation?

Inability of single-pass compilers to find exceptions that have yet to be declared.

Lazy evaluation

is useful for expressing “infinite” data structures.

What is the function of the ellipsis (. . .) in the following C code?

int fail(char *format, ...) {

to allow a variable number of arguments for the function fail.

Pascal’s with statement was used to

declutter use of deeply nested records.

If a recursive routine declares an “own” or “static” variable, can that variable’s storage be allocated statically?

Yes

Records (also known as structures or structs) are used to

aggregate data.

What are reference counts used for?

garbage collection.

The above cartoon, "THE COMPILER BAR", illustrates which primary concept from our course material?

The sequential phases of a typical compiler, from lexical analysis to code generation.