CS 4337 FINAL EXAM QUESTIONS ANSWERED CORRECTLY LATEST UPDATE 2026

CS 4337 FINAL EXAM QUESTIONS ANSWERED CORRECTLY LATEST UPDATE 2026 Language - Answers A set of strings (sentences) over an alphabet; may be unbounded (open) or finite (closed). Grammar - Answers A formal description of a language used for generation or recognition. Generation - Answers Using a grammar to produce valid sentences in a language. Recognition - Answers Using a grammar to determine if a string belongs to a language. Non-terminal - Answers An abstract symbol in a grammar that can be expanded via production rules (e.g., expr). Terminal - Answers An actual token or character in the language; cannot be expanded further (e.g., +, id). Production rule - Answers A rule mapping a non-terminal to a sequence of terminals and non-terminals. BNF (Backus-Naur Form) - Answers A notation for describing programming language syntax using non-terminals, terminals, and production rules with ::= and |. CFG (Context-Free Grammar) - Answers A grammar where each production has a single non-terminal on the left-hand side; BNF describes CFGs. Derivation - Answers A sequence of production rule applications starting from the start symbol to produce a sentence. Parse tree - Answers A tree showing the hierarchical structure of a derivation; leaves are terminals. Ambiguous grammar - Answers A grammar where a single string can produce more than one parse tree. Operator precedence - Answers The binding strength of operators; encoded in BNF by grammar hierarchy — deeper rules have higher precedence. Left associativity - Answers Operators of equal precedence group left-to-right; encoded by left recursion in BNF (e.g., expr ::= expr + term). Right associativity - Answers Operators of equal precedence group right-to-left; encoded by right recursion in BNF. EBNF - Answers Extended BNF — adds { } for zero or more repetitions, [ ] for optional, ( ) for grouping; eliminates recursion from BNF rules. EBNF { } - Answers Zero or more repetitions of the enclosed content. EBNF [ ] - Answers Zero or one occurrence of the enclosed content (optional). Axiomatic Semantics - Answers Defines program meaning using formal logic (predicate calculus) via assertions before and after statements. Precondition - Answers An assertion that must be true before a statement executes. Postcondition - Answers An assertion guaranteed to be true after a statement executes. Weakest precondition (wp) - Answers The least restrictive precondition that guarantees a given postcondition; wp(x := E, Q) = Q with x replaced by E. Hoare triple - Answers {P} S {Q}: if P is true before S executes, Q is true after. — Chapter 4 - Answers Recursive Descent Parsing — Top-down parsing - Answers Parsing strategy that starts at the start symbol and expands productions to match input left to right. Recursive descent parser - Answers A top-down parser where each non-terminal is implemented as a procedure; procedures call each other recursively. Pairwise disjointness test - Answers For each non-terminal, the FIRST sets of all its alternatives must be pairwise disjoint (no overlap) for recursive descent to work without backtracking. FIRST set - Answers The set of terminals that can appear as the first symbol of any string derived from a given grammar symbol. Name - Answers A string of characters used to identify a program entity such as a variable or function. Keyword - Answers A word reserved by the language with a fixed meaning; cannot be used as an identifier. Variable (sextet) - Answers An entity with six attributes: name, address, type, value, lifetime, and scope. Address (l-value) - Answers The memory location associated with a variable. Value (r-value) - Answers The contents stored at a variable's memory location. Binding - Answers The association of an attribute (e.g., type, value, address) to a program entity. Static binding - Answers Binding that occurs before runtime and does not change during execution. Dynamic binding - Answers Binding that occurs at runtime and may change during execution. Static type binding - Answers A variable's type is fixed at compile time (e.g., C, Java). Dynamic type binding - Answers A variable's type is determined at runtime and can change (e.g., Python, JavaScript). Static variable - Answers Bound to memory before execution begins; persists for the entire program lifetime. Stack-dynamic variable - Answers Bound to memory when its declaration is reached at runtime; freed when the scope exits (local variables). Explicit heap-dynamic variable - Answers Allocated by the programmer at runtime using new/malloc; must be manually freed. Implicit heap-dynamic variable - Answers Allocated when assigned; managed by the runtime (e.g., Python strings). Scope - Answers The textual region of a program where a variable is visible and can be referenced. Local variable - Answers A variable declared within the current scope. Non-local variable - Answers A variable visible in the current scope but declared in an enclosing scope. Static (lexical) scope - Answers Scope determined at compile time by the physical structure of the program; search: current scope → enclosing scopes → global. Dynamic scope - Answers Scope determined at runtime by the call stack; search: current call frame → calling function's frame → etc. Block - Answers A section of code (e.g., { }) that can contain local declarations and introduces a new scope. Referencing environment - Answers The collection of all variables visible at a specific point in a program. Named constant - Answers A variable bound to a value exactly once; cannot be reassigned after initialization. Lifetime - Answers The time period during which a variable is bound to a memory location. Language design time - Answers bind operator symbols to operations Language implementation time - Answers bind floating point type to a representation Compile time - Answers bind a variable to a type in C or Java Load time - Answers bind a C or C++ static variable to a memory cell Runtime - Answers bind a non-static local variable to a memory cell explicit - Answers declaration is a program statement used for declaring the types of variables implicit declaration - Answers is a default mechanism for specifying types of variables through default conventions, rather than declaration statements. Data type - Answers A set of values together with a set of operations defined on those values. Integer - Answers Whole number type; typically stored in binary two's complement. Variants: short, int, long. Floating-point - Answers Approximate real numbers stored per IEEE 754 standard; float (32-bit), double (64-bit). Boolean - Answers A type with exactly two values: true and false. Character - Answers A type representing a single symbol; stored as a numeric code (ASCII or Unicode). Static-length string - Answers String whose length is fixed at compile time. Dynamic-length string - Answers String whose length can vary at runtime with no fixed maximum (e.g., Python str). Enumeration type - Answers A type whose values are a programmer-defined list of named constants (e.g., enum Color {RED, GREEN, BLUE}). Subrange type - Answers A contiguous subsequence of an ordinal type used as a type (e.g., 1..12 for months). Array - Answers An ordered, indexable collection of elements of the same type. Static array - Answers Subscript range and storage both fixed at compile time. Fixed stack-dynamic array - Answers Subscript range fixed at compile time; storage allocated at runtime on the stack. Heap-dynamic array - Answers Both subscript range and storage can change at runtime (e.g., Python list). Row-major storage - Answers Multi-dimensional array stored row by row in memory (C, Java). Column-major storage - Answers Multi-dimensional array stored column by column (Fortran). Associative array - Answers An unordered collection of key-value pairs; accessed by key, not index (e.g., Python dict). Record (struct) - Answers A collection of fields of possibly different types grouped under one name; accessed via dot notation. Tuple - Answers A fixed-size ordered collection of elements of possibly different types; accessed by position, not name. Free union - Answers A type that can hold values of different types, with no type tag — unsafe, no type checking (e.g., C union). Discriminated union - Answers A union with a type tag (discriminant) indicating which variant is active — type-safe. Pointer - Answers A variable that stores a memory address; dereferenced to access the value at that address. Reference - Answers Similar to a pointer but automatically dereferenced; cannot be null or reassigned (C++). Dangling pointer - Answers A pointer to memory that has already been freed; accessing it is undefined behavior. Memory leak (lost heap variable) - Answers Memory that was allocated but no pointer to it remains; cannot be freed. Pointer arithmetic - Answers Adding/subtracting integers from a pointer; advances by n * sizeof(type) bytes. Type checking - Answers Verifying that operands of operators have compatible types; can be static (compile time) or dynamic (runtime). Strong typing - Answers A language is strongly typed if ALL type errors are detected — either at compile time or runtime. Weak typing - Answers Type errors can go undetected at both compile and runtime (e.g., C with unsafe casts).