CSC Programming Languages – Chapter 3: Syntax & Semantics

What is syntax?

The structure or form of expressions, statements, and program units.

What is semantics?

The meaning of expressions, statements, and program units.

What is a sentence?

A string of characters over some alphabet.

What is an alphabet?

A set of symbols used to construct sentences.

What is a language?

A set of valid sentences.

What is a lexeme?

The lowest-level syntactic unit of a language (e.g., *, sum, begin).

What is a token?

A category of lexemes, such as identifier.

What is a recognizer?

A program that determines whether a string belongs to a language (used in compilers).

What is a generator?

A device that generates valid sentences of a language.

What is a Context-Free Grammar (CFG)?

A grammar used to describe the syntax of programming languages.

What are the four parts of a CFG?

N (non-terminals), T (terminals), P (production rules), S (start symbol).

What is Backus-Naur Form (BNF)?

A formal notation used to write context-free grammars.

How are grammar rules written in BNF?

Using a left-hand side non-terminal and a right-hand side of terminals and/or non-terminals.

What is an example of BNF for an expression grammar?

→ + | → * |

What is a derivation?

The step-by-step application of grammar rules to generate a sentence.

What is a leftmost derivation?

A derivation that always expands the leftmost non-terminal first.

What is a rightmost derivation?

A derivation that always expands the rightmost non-terminal first.

What is a parse tree?

A hierarchical tree representation of a derivation showing structure.

What is an ambiguous grammar?

A grammar in which a string can have more than one parse tree.

How is ambiguity reduced in grammars?

By using operator precedence and associativity rules.

What is operator precedence?

Rules that determine which operations are evaluated first.

What is operator associativity?

Rules that determine evaluation order for operators of the same precedence.

What is Extended BNF (EBNF)?

A simplified form of BNF that reduces the number of grammar rules.

What does the EBNF optional symbol [ ] indicate?

It indicates optional elements.

What does the EBNF repetition symbol { } indicate?

It indicates zero or more repetitions.

What does the EBNF alternatives symbol ( | ) indicate?

It indicates choices.

What is static semantics?

Language rules that cannot be expressed by context-free grammars.

What is an example of static semantics?

Variables must be declared before they are used.

What is an attribute grammar?

A context-free grammar extended with semantic information.

What is a synthesized attribute?

An attribute computed from child nodes upward.

What is an inherited attribute?

An attribute passed from parent nodes downward.

What is operational semantics?

Defines program meaning by describing execution.

What is denotational semantics?

Defines program meaning using mathematical functions.

What is axiomatic semantics?

Defines program meaning using logic, preconditions, and postconditions.