Ch3&5

Question 1

Define syntax and semantics.

Answer 1

Syntax: Form of its expressions, statements, and program units.
Semantics: Meaning of these expressions, statements, and program units.

Question 2

What is the difference between a sentence and a sentential form?

Answer 2

Sentence: Strings of symbols belonging to a language; a sentential form containing only terminal symbols.
Sentential Form: Any string of symbols that appear in a derivation. May contain non-terminal symbols.

Question 3

Define a left-recursive grammar rule.

Answer 3

A grammar is left-recursive if some non-terminal A will eventually derive a sentential form with itself (A) as the left-most symbol.

Question 4

What three extensions are common to most EBNFs?

Answer 4

Optional parts: [ ]
Repetitions: { }
Alternatives: |

Question 5

Distinguish between static and dynamic semantics.

Answer 5

Static semantics: Can be determined at compile time (e.g., type checking).
Dynamic semantics: Can only be determined at run time (the program’s behavior during execution).

Question 6

What purpose do predicates serve in an attribute grammar?

Answer 6

Specify conditions that must be true for a rule to be valid (static semantic constraints).

Question 7

What is the difference between a synthesized and an inherited attribute?

Answer 7

Synthesized attribute: Its value is computed from its children in the parse tree (information flows up).
Inherited attribute: Its value is passed down from its parent or siblings (information flows down).

Question 8

How is the order of evaluation of attributes determined for the trees of a given attribute grammar?

Answer 8

By the dependencies between attributes. An attribute is evaluated after its dependencies are evaluated.

Question 9

What is the primary use of attribute grammars?

Answer 9

To define the static semantics of programming languages.

Question 10

Explain the primary uses of a methodology and notation for describing the semantics of programming languages.

Answer 10

Programmer understanding.
Compiler construction.
Program verification.
Language design.

Question 11

Why can machine languages not be used to define statements in operational semantics?

Answer 11

They are too low-level and machine-dependent. Operational semantics aims for abstraction.

Question 12

Describe the two levels of uses of operational semantics.

Answer 12

Natural operational semantics: Describes the overall effect of program execution.
Structural operational semantics: Describes the step-by-step execution.

Question 13

In denotational semantics, what are the syntactic and semantic domains?

Answer 13

Syntactic domains: Sets of syntactic objects (programs, statements).
Semantic domains: Sets of meanings (numbers, functions).

Question 14

What is stored in the state of a program for denotational semantics?

Answer 14

The values of variables and other program data.

Question 15

Which semantics approach is most widely known?

Answer 15

Operational semantics.

Question 16

What two things must be defined for each language entity in order to construct a denotational description of the language?

Answer 16

A semantic domain.
A semantic function.

Question 17

Which part of an inference rule is the antecedent?

Answer 17

The part above the horizontal line (the premises).

Question 18

What is a predicate transformer function?

Answer 18

Maps a postcondition to a precondition.

Question 19

What does partial correctness mean for a loop construct?

Answer 19

If the loop terminates, the postcondition will be true.

Question 20

On what branch of mathematics is axiomatic semantics based?

Answer 20

Mathematical logic (predicate calculus).

Question 21

On what branch of mathematics is denotational semantics based?

Answer 21

Domain theory.

Question 22

What is the problem with using a software pure interpreter for operational semantics?

Answer 22

They can be complex, slow, and may not be sufficiently abstract.

Question 23

Explain what the preconditions and postconditions of a given statement mean in axiomatic semantics.

Answer 23

Precondition: What must be true before execution.
Postcondition: What will be true after execution.

Question 24

Describe the approach of using axiomatic semantics to prove the correctness of a given program

Answer 24

Derive preconditions from postconditions using inference rules. If the program’s initial state matches the derived precondition, it’s correct.

Question 25

Describe the basic concept of denotational semantics.

Answer 25

Maps syntactic components to mathematical objects (denotations).

Question 26

In what fundamental way do operational semantics and denotational semantics differ?

Answer 26

Operational: Describes execution. Denotational: Maps to mathematical meanings.

Question 27

Who are language descriptions for?

Answer 27

Programmers Compiler writers Language designers Researchers

Question 28

Describe the operation of a general language generator.

Answer 28

Takes a grammar as input. Produces valid sentences (programs) that adhere to that grammar. Starts with a start symbol and applies grammar rules to derive strings.

Question 29

Describe the operation of a general language recognizer.

Answer 29

Takes a grammar and a string as input. Determines if the string is a valid sentence in the language defined by the grammar (parses the string).

Question 30

The two mathematical models of language descriptions are generation and recognition. Describe how each can define the syntax of a programming language.

Answer 30

Generation: is a device that generates sentences of a language. Recognition: is able to read a sentence/string from a given alphabet.

Question 31

What are the design issues for names?

Answer 31

Case sensitive, and; Reserved words or keywords.

Question 32

What is the potential danger of case-sensitive names?

Answer 32

Reduced readability: Names that differ only in case can be easily confused. Portability issues: Code that works on one platform may not work on another if the platforms handle case sensitivity differently.

Question 33

In what way are reserved words better than keywords?

Answer 33

Reserved words: Cannot be used as identifiers, preventing ambiguity. Keywords: Can be used as identifiers if context allows, which can lead to confusion. Therefore reserved words provide greater language clarity.

Question 34

What is an alias?

Answer 34

An alias is when two or more names refer to the same memory location.

Question 35

Which category of C++ reference variables is always aliases?

Answer 35

C++ reference variables passed as parameters to functions are always aliases.

Question 36

What is the l-value of a variable? What is the r-value?

Answer 36

l-value: The address of a variable (its location in memory). r-value: The value stored in the variable's memory location.

Question 37

Define binding and binding time.

Answer 37

Binding: An association between an attribute and an entity (e.g., a variable and its type, a variable and its value). Binding time: The time at which a binding takes place.

Question 38

After language design and implementation [what are the four times bindings can take place in a program?]

Answer 38

Compile time: Bindings made by the compiler (e.g., type bindings in static languages). Load time: Bindings made by the loader (e.g., linking external libraries). Link time: Binding of external subprograms. Run time: Bindings made during program execution (e.g., dynamic type binding).

Question 39

Define static binding and dynamic binding.

Answer 39

Static binding: Occurs before run time and remains unchanged throughout program execution. Dynamic binding: Occurs 1 during run time and can change during program execution.

Question 40

What are the advantages and disadvantages of implicit declarations?

Answer 40

Advantages: Convenience, shorter code. Disadvantages: Reduced readability, increased risk of errors (e.g., misspelled variable names).

Question 41

What are the advantages and disadvantages of dynamic type binding?

Answer 41

Advantages: Flexibility, generic programming. Disadvantages: Reduced reliability, increased run-time overhead.

Question 42

Define static, stack-dynamic, explicit heap-dynamic, and implicit heap-dynamic variables. What are their advantages and disadvantages?

Answer 42

Static variables: Bound to memory locations before run time, remain bound throughout execution. Advantages: Efficiency. Disadvantages: Lack of flexibility. Stack-dynamic variables: Bound to memory locations when their declaration statements are elaborated (executed). Advantages: Flexibility (e.g., local variables in subprograms). Disadvantages: Run-time overhead of allocation and deallocation. Explicit heap-dynamic variables: Allocated and deallocated by explicit instructions (e.g., new and delete in C++). Advantages: Flexibility, dynamic data structures. Disadvantages: Programmer responsibility (memory leaks, dangling pointers). Implicit heap-dynamic variables: Bound to heap storage when they are assigned values. Advantages: very high flexibility. Disadvantages: Highest amount of run time overhead.

Question 43

Define lifetime, scope, static scope, and dynamic scope.

Answer 43

Lifetime: The time during which a variable is bound to a memory location. Scope: The region of a program within which a variable is visible. Static scope: The scope of a variable is determined by its position in the source code. Dynamic scope: The scope of a variable is determined by the calling sequence of subprograms.

Question 44

How is a reference to a nonlocal variable in a static-scoped program connected to its definition?

Answer 44

The compiler searches enclosing scopes, starting with the innermost scope, until the variable's declaration is found.

Question 45

What is the general problem with static scoping?

Answer 45

It can lead to unexpected behavior if a variable's declaration is hidden by another declaration in an inner scope.

Question 46

What is the referencing environment of a statement?

Answer 46

The collection of all names that are visible at that statement.

Question 47

What is a static ancestor of a subprogram? What is a dynamic ancestor of a subprogram?

Answer 47

Static ancestor: An enclosing subprogram in the static scope sense. Dynamic ancestor: A calling subprogram in the dynamic scope sense.

Question 48

What is a block?

Answer 48

A section of code with its own local variables and scope. A section of code with its own local variables and scope.

Question 49

What is the purpose of the let constructs in functional languages?

Answer 49

To introduce local names and scopes.

Question 50

What is the difference between the names defined in an ML let construct from the variables declared in a C block?

Answer 50

ML let constructs define immutable names (bindings cannot be changed), while C block variables are mutable.

Question 51

Describe the encapsulation of an F# let inside a function and outside all functions.

Answer 51

Inside a function: the let creates a local binding, only usable inside of that function. Outside all functions: The let creates a binding that is available to all code within that file.

Question 52

What are the advantages and disadvantages of dynamic scoping?

Answer 52

Advantages: Flexibility, code reuse. Disadvantages: Reduced readability, increased risk of errors, difficult to reason about.

Question 53

What are the advantages of named constants?

Answer 53

Improved readability, increased reliability, easier maintenance.

Question 54

Some programming languages are typeless. What are the obvious advantages and disadvantages of having no types in a language?

Answer 54

A programming language without types would likely exhibit characteristics similar to languages with dynamic type binding. Advantages: Increased programming flexibility: Programs can be written generically to handle data of any type, as variables can be bound to different types at different times. Simpler syntax (potentially): The need for explicit type declarations is eliminated. Disadvantages: Reduced reliability: The compiler cannot detect type errors, leading to potential run-time errors that might be difficult to diagnose. Increased run-time overhead: Type checking must be performed at run time, and each variable might need a descriptor to maintain its current type. Storage might also need to be of varying size.

Question 55

Dynamic type binding is closely related to implicit heap-dynamic variables. Explain this relationship.

Answer 55

The relationship lies in the fact that with dynamic type binding, the storage requirements of a variable can change as its type changes. The heap is a region of memory that allows for dynamic allocation and deallocation of storage at run time. Therefore, when a variable's type is dynamically bound, the system often needs to allocate or reallocate storage on the heap to accommodate the value of the new type being assigned.

Question 56

Describe a situation when a history-sensitive variable in a subprogram is useful.

Answer 56

A history-sensitive variable in a subprogram is one whose value is retained between different calls to the subprogram. This is useful in situations where a subprogram needs to maintain state across invocations.