Syntax and Semantics Flashcards

Vocabulary flashcards covering programming language syntax, semantics, error types, grammars, and formal language classifications from the lecture transcript.

Syntax

The structure and form of valid programs; the grammar and set of rules that dictate how code must be written for a computer to understand and execute it.

Semantics

The meaning, logic, and behavior of syntactically correct programs and what instructions actually do when executed.

Concrete Syntax

The exact notation used by programmers when writing code in a programming language.

Abstract Syntax

A simplified structural representation of code that removes surface details such as parentheses, commas, and keywords.

Backus-Naur Form (BNF)

A formal grammar notation used as a tool for defining syntax.

Parse Trees

Structures that show how source code conforms to grammar rules and illustrate the derivation process for a string.

Ambiguity in Syntax

A condition that occurs when a string can be parsed in more than one way, such as the dangling else problem.

Operational Semantics

A type of semantics that defines program meaning by describing how a program executes on an abstract machine.

Denotational Semantics

A type of semantics that maps programs to mathematical functions.

Axiomatic Semantics

A type of semantics that uses logic, such as Hoare logic, to describe program behavior.

Syntax Error

An error that occurs at compile-time when code fails to follow the language's structural rules, preventing compilation or execution.

Semantic Error

An error that occurs when code is syntactically correct but produces unintentional results, flawed logic, or runtime crashes during execution.

Sentence

A string of characters over some alphabet that constitutes a legal statement in a language.

Language

A set of sentences, or a group of words that can be combined along with the rules for combining those words.

Lexeme

The lowest level syntactic unit of a language, such as $*$, sum, begin, for, or $=$.

Token

The language category assigned to a set of lexemes, such as identifiers.

Recognizer

A device that reads input strings of a language and decides whether the input strings belong to that language.

Generator

A device that generates legal and meaningful sentences of a language to determine if syntax is correct by comparison.

Chomsky Hierarchy

A classification system that divides formal languages into four types based on the computational power required to recognize them.

Regular Languages

Type 3 formal languages in the Chomsky Hierarchy that are generated by regular grammars, represented by regular expressions, and accepted by finite automata.

Regular Grammar

A grammar that grows on only one side of the string, categorized as either Right Linear Grammar or Left Linear Grammar.

Context-Free Languages

Type 2 formal languages in the Chomsky Hierarchy that can be generated by Context Free Grammars and recognized by Pushdown Automata.

Context-Free Grammar (CFG)

A formal grammar defined by a 4-tuple $G = (V, T, S, P)$, where $V$ is non-terminal symbols, $T$ is terminal symbols, $S$ is the start symbol, and $P$ is production rules.

Leftmost Derivation

A derivation process in Context Free Grammar where replacement of non-terminal symbols proceeds from the left.

Rightmost Derivation

A derivation process in Context Free Grammar where replacement of non-terminal symbols proceeds from the right.