CS-280-Midterm

Given the BNF:
Foo ::= Bar $ Foo | Bar
Bar ::= Bar # Baz | Baz
Baz ::= x | y | ( Foo )

Which operator has higher precedence, $ or #?

# has higher precedence because it appears in the Bar rule, which is deeper in the grammar (closer to the terminals) than Foo where $ appears.

Given the BNF:
Foo ::= Bar $ Foo | Bar
Bar ::= Bar # Baz | Baz
Baz ::= x | y | ( Foo )

What is the associativity of the $ operator?

Right associative. The rule Foo ::= Bar $ Foo is right recursive (Foo appears to the right of $).

Given the BNF:
Foo ::= Bar $ Foo | Bar
Bar ::= Bar # Baz | Baz
Baz ::= x | y | ( Foo )

What is the associativity of the # operator?

Left associative. The rule Bar ::= Bar # Baz is left recursive (Bar appears to the left of #).

Given the BNF:
Foo ::= Bar $ Foo | Bar
Bar ::= Bar # Baz | Baz
Baz ::= x | y | ( Foo )

Is this grammar ambiguous or unambiguous?

Unambiguous. Each operator has a single fixed associativity and precedence level, so every valid string has exactly one parse tree.

How does a compiler determine operator precedence from a BNF grammar?

Operators in rules closer to the start symbol have lower precedence. Operators in rules closer to the terminals (deeper nesting) have higher precedence.

How does a compiler determine operator associativity from a BNF grammar?

Left recursion (e.g., A ::= A op B) → left associativity.
Right recursion (e.g., A ::= B op A) → right associativity.

What is BNF?

Backus-Naur Form — a metalanguage used to formally describe the syntax of programming languages.

What role does BNF play in compiler design?

Compilers use BNF grammars to build parsers that verify source code structure and produce parse trees.

What is an ambiguous grammar?

A grammar that can produce two or more distinct parse trees for the same sentential form.

What is an unambiguous grammar?

A grammar that produces exactly one parse tree for every valid string it generates.

What are attribute grammars?

Extensions to context-free grammars that attach semantic attributes and evaluation rules to grammar symbols.

What problem do attribute grammars solve that BNF alone cannot?

They allow specification of context-sensitive features like type checking and mixed-mode expression evaluation.

What is a reserved word?

A special word in a language that cannot be used as a user-defined name (e.g., if, while, class).

How does the lexical analyzer handle reserved words?

It uses table lookup to check whether a recognized identifier string matches an entry in the reserved words table.

In dynamic scoping, how does the runtime system resolve a variable reference?

It searches the chain of currently active subprogram activations (the call stack) in reverse order until it finds a local declaration of that variable name.

What does the symbol table store?

Attributes of declared identifiers: name, type, scope, and memory location.

When is the symbol table built and consulted?

Built during lexical/syntax analysis; consulted during semantic analysis and code generation for type checking, scope resolution, and memory allocation.

What does row-major order mean for multidimensional arrays?

Rows are stored contiguously in memory. C, C++, and Java use row-major order.

Given int table[5][8] at base address 100, 4 bytes per int, row-major order. What is the address of table[3][4]?

100 + (3 * 8 + 4) * 4 = 100 + 28 * 4 = 212

Why does Binary Coded Decimal (BCD) take more storage than binary?

BCD encodes each decimal digit separately using 4 bits, while binary encodes the entire number as a single base-2 value.

Given the BNF rule A ::= A α | β, why can't a recursive-descent parser use it directly?

The left recursion causes the parser subprogram for A to call itself immediately without consuming input, resulting in infinite recursion.

In a language with dynamic typing, when are type errors detected?

At run time, because variable types are not bound until assignment, so the compiler cannot verify type compatibility.

Why does a compiled program generally execute faster than one run by a pure interpreter?

A compiler translates the entire source into optimized machine code before execution. An interpreter decodes and executes each statement at runtime, adding per-statement overhead.

What defines the imperative programming language category?

Sequential execution of statements that change program state, directly reflecting the von Neumann architecture (processor + memory + fetch-execute cycle).

What have been the strongest influences on programming language design?

Both computer architecture (especially the von Neumann model) and programming design methodologies (structured programming, OOP).

What was the first high-level programming language?

FORTRAN (1957), developed by John Backus at IBM.

Given the BNF rule:
term ::= term * factor | term / factor | term % factor | factor

What is the correct EBNF equivalent?

term ::= factor { ( * | / | % ) factor }

How do you convert a left-recursive BNF rule to EBNF?

1. Identify the non-recursive alternative as the base.
   2. Use { } (zero or more repetitions) to capture the recursive part.
   3. Factor out common elements with ( ) and [ ].

Given the BNF:
<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>

Which operator has higher precedence?

* has higher precedence because <term> (containing *) is deeper in the grammar hierarchy than <expr> (containing +).

What regex matches one or more A's or B's followed by zero or one C?

[AB]+C?

What regex matches zero or more even digits followed by one or more letters?

[02468]*[a-zA-Z]+

What regex matches a sequence of digits containing hello anywhere within it?

[0-9]*hello[0-9]*

What regex matches a string beginning with G, ending with !, with one or more letters in between?

G[a-zA-Z]+!

Given the grammar:
S → AaBb
A → Ab | b
B → aB | a

Which sentence is valid: (a) baab (b) bbbab (c) bbaaaa (d) bbabb?

(a) baab. Derivation: S → AaBb → baBb → baab.

Given the grammar rule F → aF | bG | aFb, why does it fail the pairwise disjointness test?

Two alternatives (aF and aFb) both begin with terminal a, so a parser using one-character lookahead cannot determine which production to choose.

What is the pairwise disjointness test?

A test checking whether the FIRST sets of all alternatives in a grammar rule are disjoint (no two alternatives begin with the same terminal).

Why does the pairwise disjointness test matter for recursive-descent parsing?

If two alternatives share a starting terminal, the parser cannot decide which production to use with a single lookahead token.

Given:
int *ptr;
int x = 5;
ptr = &x;

What is the r-value of ptr?

The address (l-value) of x — the memory location where x is stored.

Given:
int *ptr;
int x = 5;
ptr = &x;

What is the l-value of ptr?

The memory address where the pointer variable ptr itself is stored.

Given int value = 0;, which correctly declares a C++ reference?
(a) int &valRef = value;
(b) int &valRef = &value;
(c) int *valRef = value;
(d) int *valRef = &value;

(a) int &valRef = value; — A reference uses & before the name and is initialized to the variable directly, not to its address.

What is the storage binding category of local variables in C++ functions?

Stack-dynamic — storage is allocated from the runtime stack when the function is called and deallocated when it returns.

Where are Java class objects allocated in memory?

On the heap, explicitly created using the new operator. Only the reference variable itself is on the stack.

Given int z[] = {8, 4, 7, 5};, what is the value of *(z + 2)?

7. Pointer arithmetic: z + 2 points to index 2, which holds the value 7.

Which C++ primitive data type is not directly supported by hardware?

bool. Hardware natively supports int, float, and double via ALU/FPU; bool is a software abstraction.

What is a variable in terms of memory?

An abstraction of a memory cell characterized by six attributes: name, address, value, type, lifetime, and scope.

Not all variables have a ___. Give an example.

Not all variables have a name. Anonymous heap variables created with new have no name and are accessed only through pointers.

What are aliases?

Two or more variable names that can access the same memory location.

Why are aliases considered dangerous?

Modifying one alias silently changes the value seen through the other, making programs harder to understand and verify.

What is the l-value of a variable?

The value representing the variable's memory location (its address).

What is the r-value of a variable?

The actual data value currently stored at the variable's memory location.

How does the r-value differ between a pointer and a regular variable?

For a regular variable, the r-value is its stored data. For a pointer, the r-value is the address of another variable (i.e., the l-value of the pointed-to variable).

What is static (early) binding?

An association resolved at compile time (e.g., variable types, overloaded function resolution).

What is dynamic (late) binding?

An association resolved at run time (e.g., virtual method dispatch in polymorphism).

What is an explicit declaration?

A statement in the program that directly specifies a variable's type (e.g., int x;).

What is an implicit declaration?

A default mechanism that assigns types using conventions (e.g., in Fortran, variables starting with I–N are integers).

What is the lifetime of a global variable declared outside all functions in C++?

The entire program execution time (static lifetime). Allocated before main() begins, deallocated after the program terminates.

What is the lifetime of a local variable declared inside a C++ function?

The function call execution time. Allocated when the function is entered, deallocated when it returns.

What is the lifetime of a variable declared in a C++ for-loop header (for(int i = 0; ...))?

The for-statement block execution time. Created when the loop begins, destroyed when the loop exits.

Given nested scopes:
Def 1: int a, b, c; (function level)
Def 2: int b, d; (inside while)
Def 3: int e, a; (inside if)

What variables are visible at Point 1 (inside the if)?

a, e from Def 3; b, d from Def 2; c from Def 1. Inner declarations of a and b hide the outer ones.

What is static (lexical) scoping?

Variable visibility is determined by the textual structure of the program. The compiler searches outward through enclosing blocks at compile time.

How does static scoping differ from dynamic scoping?

Static scoping resolves variables based on textual nesting (compile time). Dynamic scoping resolves variables based on the calling sequence (run time), searching back through active activation records.

What is a data type?

A collection of data objects and a set of predefined operations on those objects.

What is a descriptor in the context of data types?

A record of the collection of attributes of a variable, used by the compiler/runtime for type checking and memory allocation/deallocation.

What is an access function for an array?

A mapping from subscript expressions to the memory address of a specific element.

What is a dangling pointer?

A pointer that references memory that has already been deallocated, risking undefined behavior if dereferenced.

What is a memory leak (garbage)?

Allocated heap memory that no pointer in the program references, making it impossible to free.

How does a dangling pointer differ from a memory leak?

A dangling pointer points to freed memory (risk: undefined behavior on access). A memory leak is unreachable allocated memory (risk: wasted resources, eventual exhaustion).

What is a C++ reference type?

A constant pointer that is implicitly dereferenced. Declared with & and must be initialized at creation.

What is the most common use of C++ reference types?

Passing function parameters by reference to avoid copying while allowing modification of the original argument.

What is a compatible type?

A type that is either legal for the operator or can be implicitly converted to a legal type by the compiler.

What is coercion?

Automatic (implicit) type conversion performed by compiler-generated code when operand types differ.

What is a type error?

The application of an operator to an operand of an inappropriate type that the language rules do not allow.

Given:
enum Season { Summer, Fall, Winter, Spring };
Season thisSeason;

Which causes a syntax error?
(a) thisSeason = Winter;
(b) res = Spring;
(c) thisSeason = (Season)2;
(d) thisSeason = 2;

(d) thisSeason = 2; — C++ does not allow implicit conversion from int to an enum type without an explicit cast.

Given int list[10]; int *ptr = list;, is *(ptr + 1) equivalent to list[1]?

Yes. Array names decay to pointers, so *(ptr + 1) and list[1] access the same element.

Given int list[10]; int *ptr = list;, is ptr[index] equivalent to list[index]?

Yes. Subscript notation on a pointer works identically to subscript notation on an array name.

Given:
int *ptr1 = new int; *ptr1 = 4;
int *ptr2 = new int; *ptr2 = 8;
ptr1 = ptr2;

What is the problem?

The memory originally allocated for *ptr1 (value 4) becomes a memory leak — no pointer references it. Also, ptr1 and ptr2 now alias the same memory.

Given:
Student astud;
Student *stptr = &astud;

Which access is incorrect?
(a) astud.name
(b) (*stptr).name
(c) stptr->name
(d) *stptr->name

(d) *stptr->name — The -> operator already dereferences the pointer; adding * tries to dereference the resulting string, which is not a pointer.

Given obj2 = x * obj1; where x is int and obj1 is class One. Must operator* be a member or global function?

A global (friend) function: One operator*(int val, One obj); — Because the left operand x is not an object of class One, it cannot invoke a member function.

In C++, what does it mean for functions to be overloaded?

Multiple functions share the same name but differ in the number or types of their parameters.

Do overloaded functions in C++ need to differ in return type?

No. They must differ in parameter number or types. The compiler cannot resolve overloading based solely on return type.

What does a lexical analyzer generate?

Tokens. It reads the character stream, groups characters into lexemes, and classifies each lexeme as a token.

What is the difference between a lexeme and a token?

A lexeme is the actual character string in source code (e.g., count). A token is the classification of that lexeme (e.g., IDENTIFIER).

Most existing programming languages can be tokenized using ___ character(s) of lookahead.

One-character lookahead.

When an FSA representing a token pattern reaches its final (accepting) state, what has happened?

The token has been determined — the input character sequence matches the pattern for a specific token type.

Can a lexical analyzer be automatically generated from regular expression descriptions of tokens?

Yes. Tools like Lex/Flex take regex definitions and generate a DFA-based lexical analyzer program.

Every regular expression can be expressed as a ___.

Deterministic finite automaton (DFA). Regular expressions and DFAs are equivalent in expressive power.

What does lexical analysis (scanning) do?

Breaks source code into tokens using regular expressions and finite automata.

What does syntax analysis (parsing) do?

Checks that the token sequence conforms to a context-free grammar and produces a parse tree.

Lexical analyzers are combined DFAs recognizing multiple patterns at once. True or False?

True. A single combined DFA simultaneously tests input against all token patterns, accepting the longest match.

What is a recursive-descent parser?

A top-down parser with one subprogram (function) for each nonterminal in the grammar.

What does an LL grammar guarantee about parsing?

It can be parsed by a top-down parser reading input Left to right, producing a Leftmost derivation.

A recursive-descent parser has a subprogram for each ___ in the grammar.

Nonterminal. Terminals are matched directly against the input.

What does a compiler's optimizer do?

Reorganizes intermediate code to eliminate unnecessary calculations and reduce redundant operations. It does not find syntax errors, enforce language rules, or record symbols.

What does a C++ constructor return?

Nothing — constructors have no return type (not even void).

When is a C++ constructor called?

When memory is bound to the object: at declaration for stack objects, or when new is invoked for heap objects.

When is a C++ destructor called?

When the object's memory is about to be deallocated: at end of scope for stack objects, or when delete is invoked for heap objects.

What is a copy constructor in C++?

A constructor that creates a new object as a copy of an existing instance. Its parameter is typically const ClassName&.

What is a static member variable inside a class?

A variable with only one instance shared by all objects of the class, stored in the data segment.

How does a static member variable differ from a regular member variable?

Static: one shared copy (data segment). Regular: separate copy per object instance (stack or heap with the object).

What are explicit heap-dynamic variables in C++?

Variables allocated with new and deallocated with delete by the programmer. They reside on the heap.