Programing Languages chapter 6

Syntax

The structure and rules that define how statements are constructed in a programming language.

Context-free grammars

Introduced by Noam Chomsky in the 1950s.

BNF

Backus-Naur Form, a notation for describing the grammar of programming languages.

Variations of BNF

Original BNF, Extended BNF (EBNF), and syntax diagrams.

Lexical structure

Defines the tokens or words of a language, handled during the scanning phase of compilation.

Tokens vs. Syntactic structure

Tokens are the basic words or symbols; syntax is how tokens are arranged to form valid statements.

Types of tokens

Reserved words, literals/constants, special symbols, identifiers, predefined identifiers.

Principle of longest substring

The scanner collects the longest possible string of nonblank characters to form a token.

Whitespace effect on token recognition

Whitespace separates tokens and can affect how tokens are recognized; in some languages, indentation matters.

Free-format language

A language where the format does not affect program structure, except for the longest substring rule.

Fixed-format language

A language where tokens must appear in specific locations on the page.

Tokens description

Described formally by regular expressions, which use concatenation, repetition (*), choice (|), range (-), optional (?), and any character (.).

Regular expression for an integer constant

A sequence of digits 0-9.

Context-free grammar

A set of rules with a single nonterminal on the left and a sequence of terminals/nonterminals on the right.

Production in grammar

A single rule in a context-free grammar or BNF.

Parse tree

A graphical representation of the syntactic structure of a string according to a grammar.

Abstract syntax tree (AST)

A simplified version of a parse tree that captures the essential structure for translation or analysis.

Grammar ambiguity

Occurs when two distinct parse trees (or leftmost derivations) can be constructed for the same string.

Associativity

The order in which operations of the same precedence are performed (left or right).

Precedence

A ranking that determines which operations are performed first in an expression.

Removing grammar ambiguity

Can be done by revising grammar rules or disambiguating them, such as introducing new nonterminals for precedence.

Leftmost derivation

A derivation where the leftmost nonterminal is replaced at each step, leading to a unique parse tree.

EBNF additions to BNF

Adds curly braces for repetition, square brackets for optional parts, making some rules clearer.

Syntax diagram

A graphical way to represent grammar rules, using shapes for terminals/nonterminals and arrows for sequence.

Recognizer in parsing

A tool that accepts or rejects strings as legal according to a grammar.

Bottom-up parsing

A parsing technique that builds parse trees from the leaves upward (shift-reduce parsing).

Top-down parsing

A parsing technique that builds derivations from the root downward.

Parser generator

A tool that automates parser creation, such as YACC or Bison.

Recursive-descent parsing

A parsing method where nonterminals become mutually recursive procedures matching input tokens to grammar rules.

Difference between lexics, syntax, and semantics

Lexics: token recognition; Syntax: structure; Semantics: meaning, sometimes context-sensitive.

Reserved word

A word that cannot be used as an identifier in a program.

Predefined identifier

An identifier with an initial meaning that can be redefined in a program.

TinyAda

A small language used to illustrate high-level syntactic features, with a syntax analyzer that checks correctness independently of semantics.