programming class ch3

15 question-and-answer flashcards covering key points on syntax, semantics, grammars, and semantic description methods from Chapter 3.

What is the difference between syntax and semantics in a programming language?

Syntax is the form/structure of expressions, statements, and program units, whereas semantics is their meaning.

What are a lexeme and a token? Give an example of each.

A lexeme is the lowest-level syntactic unit (e.g., "begin", "*"), while a token is a category of lexemes (e.g., IDENTIFIER).

Name the two formal devices used to define languages and state how they differ.

Recognizers decide if an input string belongs to a language; generators produce all valid sentences of the language.

Who introduced context-free grammars, and for what original purpose?

Noam Chomsky (mid-1950s) developed context-free grammars to describe the syntax of natural languages.

What is Backus-Naur Form (BNF) and how does it relate to context-free grammars?

BNF, invented by John Backus (1959) for Algol-58, is a notation that is equivalent to context-free grammars.

In BNF rules, what are terminals and nonterminals, and which appears on the left-hand side (LHS)?

Terminals are actual lexemes/tokens; nonterminals are syntactic variables. A rule’s LHS must be a single nonterminal.

Define a derivation and explain a leftmost derivation.

A derivation is successive application of grammar rules from the start symbol to a sentence; a leftmost derivation always expands the leftmost nonterminal first.

When is a grammar considered ambiguous?

A grammar is ambiguous if it can generate at least one sentential form that has two or more distinct parse trees.

How can grammars enforce operator precedence and associativity?

By structuring nonterminals (e.g., → - | ) and separating levels, ambiguity is removed and associativity/precedence are fixed.

List the three additional metacharacters of Extended BNF (EBNF) and their meaning.

[ ] for optional parts, (A | B | …) for alternatives, and { } for repetitions (0 or more).

Why can’t context-free grammars express all static semantics? Give an example.

Some constraints are cumbersome or non-CF, such as operand type compatibility (CF but awkward) and declaring a variable before use (non-CF).

What is an attribute grammar and what is its primary use?

An attribute grammar augments a CFG with attributes, semantic rules, and predicates; it is mainly used to specify and check static semantics during compilation.

Compare operational, denotational, and axiomatic semantics in one sentence each.

Operational: meaning via state changes on an (ideal) machine; Denotational: meaning via mathematical functions mapping constructs to mathematical objects; Axiomatic: meaning via logical assertions enabling correctness proofs.

In denotational semantics, what constitutes the state of a program?

The set of all current variable–value pairs, e.g., s = {

What is a loop invariant in axiomatic semantics and what properties must it satisfy?

A loop invariant is an assertion true before and after each iteration; it must hold initially, be preserved by loop evaluation and body execution, and with loop exit condition must imply the postcondition.