Ein Alphabet $\Sigma$ ist eine endliche, nicht leere Menge von Zeichen. Ein Wort ist eine endliche Folge von Zeichen aus $\Sigma$. Das leere Wort $\varepsilon$ hat keine Zeichen. $\Sigma^*$ bezeichnet alle Wörter über $\Sigma$. Eine formale Sprache ist eine Teilmenge von $\Sigma^*$.

Die Syntax legt fest, welche Wörter zur Sprache gehören, also wie sie aufgebaut sind. Die Semantik legt fest, was sie bedeuten. Natürliche Sprachen sind gewachsen: Sie haben Ausnahmen, Sätze können mehrdeutig sein, und die Bedeutung hängt vom Zusammenhang ab. Formale Sprachen sind genau festgelegt, ihre Wörter haben eine eindeutige Bedeutung, und eine Maschine kann ihre Syntax prüfen.

Eine Grammatik ist ein Tupel $G = (N, T, P, S)$:

• N ist die Menge der Nichtterminale: Platzhalter, die noch ersetzt werden.
• T ist die Menge der Terminale: die Zeichen des Alphabets, aus denen die fertigen Wörter bestehen. N und T haben keine gemeinsamen Elemente.
• P ist die Menge der Produktionsregeln $\alpha \to \beta$: Ersetze $\alpha$ durch $\beta$.
• $S \in N$ ist das Startsymbol.

Ein Ableitungsschritt $u \Rightarrow v$ wendet eine Regel auf einen Teil von u an. Die erzeugte Sprache $L(G)$ besteht aus allen Wörtern aus Terminalen, die sich in endlich vielen Schritten aus S ableiten lassen. Mehrere Regeln für dasselbe Nichtterminal schreibt man kurz mit einem Strich: $S \to aSb \mid \varepsilon$. Hier steht links stets ein einzelnes Nichtterminal.

Der Bau der Regeln bestimmt die Art der Grammatik. In einer kontextfreien Grammatik hat jede Regel die Form $A \to \beta$: links ein einzelnes Nichtterminal, rechts eine beliebige Folge aus Terminalen und Nichtterminalen. „Kontextfrei“ heißt: A wird ersetzt, egal was daneben steht. In einer regulären Grammatik hat jede Regel eine der Formen $A \to aB$, $A \to a$ oder $A \to \varepsilon$ (a Terminal, A und B Nichtterminale). Jede reguläre Grammatik ist kontextfrei. Die Grammatik $S \to aSb \mid \varepsilon$ ist kontextfrei, aber nicht regulär, denn bei $S \to aSb$ steht ein Terminal hinter dem Nichtterminal.

Zu jedem DFA gibt es eine reguläre Grammatik für dieselbe Sprache und umgekehrt. Aus dem Automaten wird die Grammatik so gebaut: Jeder Zustand wird ein Nichtterminal, der Startzustand das Startsymbol. Zu jedem Übergang vom Zustand A mit dem Zeichen x nach B gehört die Regel $A \to xB$. Für jeden Endzustand A kommt $A \to \varepsilon$ hinzu. Die Ableitung folgt dem Weg des Automaten. Ein Fangzustand braucht keine Regeln: Wo keine Regel passt, entsteht kein Wort.

Die EBNF (erweiterte Backus-Naur-Form) schreibt kontextfreie Regeln kompakt. Ein Gleichheitszeichen verbindet Nichtterminal und rechte Seite, ein Punkt beendet die Regel. Ein senkrechter Strich trennt Alternativen, Terminale stehen in Anführungszeichen. Eckige Klammern $[\ldots]$ markieren Optionales (null- oder einmal), geschweifte Klammern $\{\ldots\}$ eine Wiederholung (null- oder mehrmals), runde Klammern fassen zusammen. Beispiel für einfache Terme:

• $\texttt{ausdruck = term \{ "+" term \} .}$
• $\texttt{term = faktor \{ "*" faktor \} .}$
• $\texttt{faktor = zahl | "(" ausdruck ")" .}$
• $\texttt{zahl = ziffer \{ ziffer \} .}$

Ein Syntaxdiagramm zeigt dieselbe Regel grafisch: ein Diagramm je Nichtterminal, ein eckiger Kasten für ein Nichtterminal, ein runder für ein Terminal, eine Verzweigung für den Strich, eine Schleife für die geschweifte Klammer.

Ein Ableitungsbaum zeigt, wie ein Wort entsteht. Die Wurzel ist das Startsymbol, jeder innere Knoten ein Nichtterminal, seine Kinder stehen von links nach rechts auf der rechten Seite der angewendeten Regel. Die Blätter sind Terminale und ergeben von links nach rechts das Wort. Hat ein Wort mehrere Ableitungsbäume, ist die Grammatik mehrdeutig.

Das Wortproblem fragt: Gehört das Wort w zu $L(G)$? Bei einer regulären Grammatik liest man w einmal durch den zugehörigen DFA, der Aufwand wächst mit der Länge von w. Bei kontextfreien Grammatiken gibt es Verfahren, die es mit polynomiellem Aufwand lösen: Man versucht, einen Ableitungsbaum für w zu bauen. Ein Programm, das das tut, ist ein Parser.

Programmiersprachen sind formale Sprachen. Ein Compiler übersetzt den ganzen Quelltext vor der Ausführung in ein anderes Programm, etwa Maschinen- oder Zwischencode. Ein Interpreter liest den Quelltext und führt ihn Schritt für Schritt aus. Beide verarbeiten den Text in Phasen:

• Der Scanner (lexikalische Analyse) zerlegt die Zeichenfolge in Token: Bezeichner, Zahlen, Operatoren, Schlüsselwörter. Dafür genügen reguläre Ausdrücke.
• Der Parser (syntaktische Analyse) prüft, ob die Folge der Token zur kontextfreien Grammatik der Sprache passt, und baut den Ableitungsbaum.
• Danach folgt die Semantik: Typen prüfen, Code erzeugen oder direkt ausführen.

Aus $\texttt{x = 3 + 42}$ macht der Scanner die Token $\texttt{x}$ (Bezeichner), $\texttt{=}$ (Zuweisung), $\texttt{3}$ (Zahl), $\texttt{+}$ (Operator) und $\texttt{42}$ (Zahl). Einen Syntaxfehler meldet der Parser, Fehler der Bedeutung zeigen sich oft erst später.