1.1 Alphabet, Strings, and Grammar: First, Define What Counts as Valid

Start with an intentionally small language: it permits only a and b, and every string must begin with a and end with b. Before writing a parser, define "valid input" as a rule that can actually be decided.

That is also where compiler work starts. Specify the allowed symbols and accepted sequences before implementing recognition. Otherwise, faster code may just deliver the wrong interpretation sooner.

Learning Objectives

• Distinguish between an alphabet, a string, and a language;
• Use basic notations such as concatenation, length, and closure;
• Understand how grammars generate languages;
• Differentiate between "generating a string" and "recognizing a string".

1. An Alphabet Defines the Available Symbols

Alphabet $\mathrm{\Sigma }$ is a finite, non-empty set of symbols. Symbols do not need to be letters from natural languages:

• A binary alphabet can be $\{0,1\}$;
• A token alphabet may include IDENTIFIER, NUMBER, PLUS;
• Protocol state sequences can use SYN, ACK, FIN.

The symbols in an alphabet are indivisible abstract units. If Unicode code points, UTF-16 code units, or lexical tokens are treated as "a single symbol," one ends up with different levels of language models. The level must be fixed before implementation.

2. Strings are finite sequences of symbols

A string over an alphabet $\mathrm{\Sigma }$ is a finite sequence of symbols from that alphabet. The empty string is denoted $\epsilon$ and has length 0; the length of a string $w$ is written $|w|$.

Two strings can be concatenated. If $x=ab$ and $y=ba$, then:

$$xy=abba.$$

Concatenation is associative but generally not commutative. The empty string acts as the identity element for concatenation:

$$w\epsilon =\epsilon w=w.$$

Common set notations:

Symbol	Meaning
${\mathrm{\Sigma }}^0$	The set containing only the empty string $\{\epsilon \}$
${\mathrm{\Sigma }}^n$	The set of all strings of exact length $n$
${\mathrm{\Sigma }}^{\ast }$	The set of all finite-length strings, including the empty string
${\mathrm{\Sigma }}^{+}$	The set of all non-empty strings, i.e., ${\mathrm{\Sigma }}^{\ast }\setminus \{\epsilon \}$

If $\mathrm{\Sigma }=\{a,b\}$, then ${\mathrm{\Sigma }}^{\ast }$ is an infinite set, but every string in it has finite length.

3. Language is a Set of Strings

A formal language $L$ is any subset of ${\mathrm{\Sigma }}^{\ast }$:

$$L\subseteq {\mathrm{\Sigma }}^{\ast }.$$

For example, the language of strings that begin with a and end with b can be written as:

$$L=\{awb\mid w\in \{a,b{\}}^{\ast }\}.$$

Thus, ab, aab, and abb are members of $L$, while the empty string, a, and ba are not.

A language only specifies which strings are valid, it does not dictate how to verify them. Regular expressions, grammars, finite automata, and programs are all possible ways to describe or recognize a language.

Languages can also be combined using set operations:

• Union $L_1\cup L_2$: strings belonging to either language;
• Intersection $L_1\cap L_2$: strings belonging to both languages;
• Complement ${\mathrm{\Sigma }}^{\ast }\setminus L$: strings that are invalid relative to the full alphabet;
• Concatenation $L_1{L}_2=\{xy\mid x\in L_1,y\in L_2\}$;
• Kleene star $L^{\ast }=\bigcup _{n\ge 0}{L}^n$, where $L^0=\{\epsilon \}$ and $L^{n+1}=L^{n}L$.

The complement requires a specified universe. Changing the alphabet changes the complement of the same rule. Also, the empty language's star closure ${\varnothing }^{\ast }$ still contains the empty string: choosing zero strings to concatenate is allowed.

4. A Grammar Can Generate an Infinite Language with Finite Rules

Formal grammars are typically written as a quadruple:

$$G=(V,\mathrm{\Sigma },P,S).$$

• $V$: the set of nonterminals, representing structures that haven't yet been expanded;
• $\mathrm{\Sigma }$: the set of terminals, the symbols that appear in the final strings;
• $P$: the set of production rules;
• $S$: the start symbol, a member of $V$.

Here, $V$ and $\mathrm{\Sigma }$ are finite and disjoint, and $P$ is finite. A grammar need not generate an infinite language; recursive rules make an infinite set possible.

For example, the following grammar generates one or more a:

S → aS | a

Repeatedly substitute nonterminals starting from $S$:

S ⇒ aS ⇒ aaS ⇒ aaa

We denote $S{\Rightarrow }^{\ast }w$ as deriving $w$ in zero or more steps. The language generated by the grammar is:

$$L(G)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid S{\Rightarrow }^{\ast }w\}.$$

The rules are finite, yet recursion allows the grammar to describe infinitely many strings. The expression syntax, statement blocks, and type structures in programming languages are all organized through this recursive mechanism.

5. Derivation Is Not Parsing

A grammar generates a string from its start symbol; a parser takes an input string and attempts to find whether it conforms to a valid derivation, and if so, reconstructs its structure. They are dealing with the same underlying relationship, just in opposite directions:

Generation: S  ⇒*  token sequence
Parsing: token sequence  ⇒  whether it belongs to L(G); if yes, reconstruct the structure

A string may have multiple derivation paths. For a context-free grammar, two different parse trees for the same terminal string establish ambiguity. Different expansion orders alone do not: with S → AB, A → a, and B → b, expanding A first or B first yields ab with the same tree. Chapter 3 addresses practical issues such as operator precedence and "dangling else" scenarios.

6. The Compiler Continuously Replaces the Alphabet

Take code total = price + 1 as an example:

1. At the source file level, bytes, encodings, and characters are processed;
2. Lexical analysis groups characters into tokens IDENTIFIER ASSIGN IDENTIFIER PLUS NUMBER;
3. Syntactic analysis organizes the token sequence into assignment and addition expressions;
4. Semantic analysis then verifies whether names are declared and whether types can be added together.

Between lexing and parsing, a finite set of token kinds can serve as the alphabet, with names and values stored as token attributes. Later ASTs are trees; describing every compiler stage as a change of alphabet is an analogy, not a literal string model. Trying to encapsulate all these issues into a single regular expression or a set of grammars quickly leads to unmanageable error boundaries and implementation complexity.

7. A Precise Identifier Language

If we temporarily restrict identifiers to ASCII, we can define:

letter     = A..Z | a..z | _
digit      = 0..9
identifier = letter (letter | digit)*

This definition still does not address Unicode, keywords, maximum length, or normalization forms. It illustrates that "formalization" is not about writing symbols that look mathematically elegant; it's about clearly specifying ranges and assumptions.

The lexer should first consume the longest identifier, then consult the keyword table: if is a keyword, while ifx remains one identifier rather than if followed by x. Keywords are typically recognized first as identifiers, then reclassified via a keyword table; alternatively, they can be given higher priority in the automaton's accepting states. The outcome of either approach must align with the language specification.

Common Misconceptions

• The alphabet is the same as a character set: Tokens, instructions, and even events can serve as abstract symbols.
• An empty string equals an empty set: $\epsilon$ denotes a string of length zero, while $\varnothing$ represents a set with no elements.
• A grammar is a parsing algorithm: A grammar defines a language, but a parsing algorithm must also consider decidability, complexity, and error recovery.
• Code that runs is conformant to a language specification: Implementations may accept extended syntax or contain bugs; language specifications and implementation behavior must be treated as separate concerns.

Exercise

1. For the alphabet $\mathrm{\Sigma }=\{0,1\}$, write out ${\mathrm{\Sigma }}^0$, ${\mathrm{\Sigma }}^1$, and ${\mathrm{\Sigma }}^2$.
2. Define the language of binary strings containing an even number of 1 characters, and express it both using set notation and in natural language.
3. Write a grammar that generates the language $\{a^{n}b\mid n\ge 1\}$, and provide a derivation using aaab.
4. Give one "symbol" example each for characters, tokens, and syntactic structures in JSON.

Summary

The alphabet defines building blocks, strings are sequences of those blocks, a language selects valid sequences, and a grammar generates those sequences with finite rules. Instead of immediately building a parser, the next lesson asks: how much memory does each rule require, and which computational model is best suited to handle it.