Syntax and Semantics Flashcards

Flashcards for Chapters 3 and 4 covering Syntax and Semantics

Syntax

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

Semantics

The meaning of expressions, statements, and program units in a language.

Sentence

A string of characters over some alphabet.

Language

A set of sentences.

Lexeme

The lowest level syntactic unit of a language.

Token

A category of lexemes (e.g., identifier, int_literal).

Identifiers

Names the programmer chooses.

Keywords

Names already in the programming language.

Separators (Punctuators)

Punctuation characters.

Operators

Symbols that operate on arguments and produce results.

Literals

Numeric, logical, or textual values.

Recognizer

A recognition device that reads input strings and decides whether they belong to the language.

Generator

A device that generates sentences of a language.

Context-Free Grammars

Language generators used to describe the syntax of natural languages.

Backus-Naur Form (BNF)

Equivalent to context-free grammars, used to describe the syntax of Algol 58.

Nonterminal Symbols (Nonterminals)

Syntactic variables that represent classes of syntactic structures.

Terminals

Lexemes or tokens in a grammar.

Production Rules

Defines how non-terminals can be expanded or replaced.

Left-Hand Side (LHS)

The nonterminal on the left side of a production rule.

Right-Hand Side (RHS)

A string of terminals and/or nonterminals on the right side of a production rule.

Grammar

A finite non-empty set of rules.

Start Symbol

A special element of the nonterminals of a grammar.

Derivation

A repeated application of rules, starting with the start symbol.

Sentential Form

A string of symbols in a derivation.

Sentence

A sentential form that has only terminal symbols.

Leftmost Derivation

The replaced non-terminal is always the leftmost non-terminal.

Rightmost Derivation

The replaced non-terminal is always the rightmost non-terminal.

Parse Tree

Hierarchical structure that shows the derivation process.

Ambiguous Grammar

A grammar that generates a sentential form with two or more distinct parse trees.

Specifying Precedence

Building precedence into the grammar using a different non-terminal for each precedence level.

Specifying Associativity

Allowing recursion only on either left or right non-terminal to specify the order of operations.

Dangling-Else

An optional else clause in a nested conditional structure that becomes ambiguous.

Extended BNF (EBNF)

Extensions to BNF to simplify rules without enhancing descriptive power.

Lexical Analyzer

A low-level part of a language processor; a finite automaton based on a regular grammar.

Syntax Analyzer (Parser)

A high-level part of a language processor; a push-down automaton based on a context-free grammar.

Lexical Analyzer

A pattern matcher for character strings.

Lexemes

Substrings of the source program that belong together.

Token (Lexical Analyzer Context)

Character pattern associated with a lexical category.

Lookup

Determines whether the string in lexeme is a reserved word.

GetChar

Reads the next character of the input string.

AddChar

Appends nextChar to the current lexeme.

Goals of the Parser

Find all syntax errors, produce an appropriate diagnostic message and recover quickly; produce the parse tree.

Top-Down Parser

Produces the parse tree, beginning at the root (leftmost derivation).

Bottom-Up Parser

Produces the parse tree, beginning at the leaves (reverse of a rightmost derivation).

Top-Down Parser Operation

Uses the first token produced by the A-rule to choose correct A-rule to get the next sentential form.

Bottom-Up Parser Operation

Identifies which substring of α corresponds to the right-hand side of a grammar rule.

Recursive Descent

A coded implementation of a top-down parser.

LL Algorithm

An algorithm that generates a leftmost derivation with a left-to-right scan of input.

LR Family

where L stands for a left-to-right scan of the input and a rightmost derivation is being constructed.

nextToken

The next token code is stored here by the lexical analyzer.

Left Recursion Problem

A problem where a grammar cannot be the basis for a top-down parser due to recursion.

Left Factoring

A process to eliminate common prefixes so the correct RHS can be determined with one token of lookahead.

Handle

The specific RHS in the right sentential form that must be reduced to get the previous sentential form.

Shift

Moving the next input token to the top of the parse stack.

Reduce

Replacing the handle on the top of the parse stack with its corresponding LHS.

Static Semantics

Rules that further constrain syntactically correct programs; verified at compiler time.

Attribute Grammar

Designed to describe both the syntax and the static semantics of PLs.

Attributes

Associated with grammar symbols, either terminal or nonterminal.

Attribute Computation Functions (Semantic Functions)

Associated with grammar rules; specify how attribute values are computed.

Predicate Function

Associated with grammar rules and state the static semantic rules of the language.

Synthesized Attributes

Used to pass semantic information up a parse tree (bottom up).

Inherited Attributes

Used to pass semantic information down and across a tree (top down).

Operational Semantics

Describe the meaning of a statement or program by specifying the effects of running it on a machine.

Denotational Semantics

Defines a mathematical object for each language entity and a function that maps language instances onto mathematical objects.

State of a Program

The values of all its current variables.

Axiomatic Semantics

Based on formal logic (predicate calculus) for formal program verification.

Assertions

Logical expressions stating relationships and constraints among variables.

Precondition

An assertion that states relationships and constraints among variables that are true at that point in execution, before a statement.

Postcondition

An assertion that states relationships and constraints among variables that are true at that point in execution, following a statement.

Weakest Precondition

The least restrictive precondition that will guarantee the postcondition.