Grammatiken

1. Einrichten

Lege im Terminal (StrgJ) einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/grammatiken

2. Regeln, die Sätze bauen

Eine Grammatik für eine winzige Sprache, deren Sätze aus drei Wörtern bestehen:

sentence = subject verb object
subject  = "Pip" | "Bello"
verb     = "findet" | "sucht"
object   = "Bello" | "die Lampe" | "den Weg"

Jede Zeile ist eine Regel. Links vom = steht ein Name, ein Nichtterminal: Es steht für einen Teil des Satzes, der noch gebaut werden muss. In Anführungszeichen stehen Terminale, die so, wie sie sind, im Satz landen. | heißt »oder«. Die erste Regel ist die, mit der man anfängt; ihr Name heißt Startsymbol. Die Namen im Code sind englisch, so wie die Namen der Funktionen, die du gleich daraus machst.

Einen Satz baut man, indem man beim Startsymbol beginnt und immer ein Nichtterminal durch das ersetzt, was rechts in seiner Regel steht, bei | durch eine der Möglichkeiten. Sind nur noch Terminale übrig, ist der Satz fertig. Diese Kette heißt Ableitung:

sentence
⇒ subject verb object
⇒ "Pip" verb object
⇒ "Pip" "findet" object
⇒ "Pip" "findet" "die Lampe"

Alle Sätze, die sich so ableiten lassen, sind die Sprache der Grammatik.

Dieselbe Ableitung als Baum heißt Syntaxbaum. Oben steht das Startsymbol, darunter, wodurch es ersetzt wurde. Nichtterminale stehen in eckigen Kästen, Terminale in runden; von links nach rechts gelesen ergeben die runden Kästen den Satz:

sentence(subject("Pip") verb("findet") object("die Lampe"))

Die Grammatik erlaubt auch »Bello findet Bello«. Der Satz ist richtig gebaut, aber ob er etwas Sinnvolles sagt, steht nicht in der Grammatik. Wie ein Text gebaut ist, heißt seine Syntax, was er bedeutet, seine Semantik. In Programmen ist es genauso: print(1 / 0) ist nach der Grammatik von Python ein richtiges Programm, und erst beim Ausführen stellt sich heraus, dass es nichts bedeutet, was der Rechner tun könnte.

Diese Schreibweise geht auf John Backus zurück. 1959 schlug er sie vor, um die Programmiersprache ALGOL festzulegen, und Peter Naur benutzte sie 1960 im Bericht über ALGOL 60, den er herausgab. Seitdem heißt sie Backus-Naur-Form, kurz BNF.

Mehr dazu

• Wikipedia: Peter Naur
• masswerk.at
• Wikipedia: Backus–Naur form

Peter Naur (1928–2016), dänischer Informatiker, zuerst Astronom. 1960 gab er den Bericht über die Programmiersprache ALGOL 60 heraus und legte darin die ganze Sprache mit der Schreibweise von John Backus fest, die seitdem Backus-Naur-Form heißt. Dafür bekam er 2005 den Turing Award.

Das Wort »computer science« mochte er nicht und schlug »datalogi« vor; in Dänemark und Schweden heißt die Informatik bis heute so.

Foto: Eriktj, 2008, CC BY-SA 3.0, zugeschnitten (Wikimedia Commons)

3. Wörter ohne Ende

Die Sprache der Sätze oben hat nur endlich viele Wörter. Für eine Programmiersprache reicht das nicht: Es gibt unendlich viele Programme. Dafür hat die Schreibweise drei Klammern, mit denen auch Ein Rechner für Ausdrücke arbeitet:

Weil die Klammern zur Schreibweise gehören, steht eine Klammer, die selbst im Wort vorkommt, in Anführungszeichen: "(" ist ein Terminal, ( gehört zur Regel. Mit diesen Klammern heißt die Schreibweise EBNF, erweiterte Backus-Naur-Form; vorgeschlagen hat sie Niklaus Wirth 1977.

Die Klammerwörter aus dem Kellerautomaten, (), (())() und so weiter, beschreibt eine einzige Regel:

brackets = { "(" brackets ")" }

Ein Klammerwort ist eine Reihe von Klammerpaaren, beliebig viele, und in jedem Paar steht wieder ein Klammerwort. Die Regel benutzt sich selbst, sie ist rekursiv. So beschreibt eine Grammatik mit einer einzigen Zeile unendlich viele Wörter. Der Syntaxbaum von (())(): Das äußere brackets nimmt zwei Paare, das linke enthält ein Paar, alle anderen keins.

brackets("(" brackets("(" brackets ")") ")" "(" brackets ")")

4. Syntaxdiagramme

Niklaus Wirth hat Grammatiken auch gezeichnet, zuerst für seine Sprache Pascal. Ein Syntaxdiagramm liest man von links nach rechts, die Linien entlang: Wo sich ein Weg teilt, wählst du einen. Ein runder Kasten ist ein Terminal, das so im Wort steht. Ein eckiger ist ein Nichtterminal: Dort gehst du durch dessen eigenes Diagramm und kommst danach zurück. So sieht eine Grammatik für Zahlen aus:

number = digit { digit }
digit  = "0" | "1" | … | "9"

number = digit { digit }
digit  = "0" | "1" | … | "9"

Bei number geht es einmal durch digit und danach unten zurück, so oft du willst. So zeichnete Wirth x { x }: Ein Pfeil auf dem Weg zurück zeigt die Richtung. Die … stehen für die Ziffern 2 bis 8, die das Bild auslässt.

Mehr dazu

• ethz.ch
• Wikipedia: Niklaus Wirth
• Wikipedia: Algorithms + Data Structures = Programs
• Wikipedia: Pascal (programming language)
• Wikipedia: Wirth's law
• Wikipedia: Turing Award

Niklaus Wirth (1934–2024), Schweizer Informatiker an der ETH Zürich. Er entwarf Pascal als Sprache, an der man sauberes Programmieren lernt. Eines seiner Bücher heißt Algorithms + Data Structures = Programs: Ein Programm, das sind Algorithmen plus Datenstrukturen.

1995 warb er für schlanke Software und zitierte einen Kollegen: Software werde schneller langsamer, als die Hardware schneller wird. Der Satz heißt heute Wirthsches Gesetz. 1984 bekam er den Turing Award, den wichtigsten Preis der Informatik.

Foto: Robert M. McClure, CC BY-SA 3.0, zugeschnitten (Wikimedia Commons)

Ein Syntaxdiagramm und eine Regel in EBNF sagen dasselbe; man kann jedes in das andere übersetzen. Diese Zahlen haben ein Vorzeichen, wenn man will, und ein Komma, wie man sie im Deutschen schreibt:

decimal = [ "-" ] digit { digit } [ "," digit { digit } ]

Jetzt in die andere Richtung. Dieses Diagramm beschreibt Listen von Zahlen zwischen spitzen Klammern, mit Semikolons dazwischen:

list = "<" [ number { ";" number } ] ">"

5. Ein Programm für jede Regel

Aus einer Grammatik lässt sich fast von selbst ein Programm machen, das prüft, ob ein Wort zur Sprache gehört. Jede Regel wird eine Funktion. Sie bekommt das Wort und einen Index i und liest ab dort, was ihre Regel erlaubt. Zurück gibt sie den Index hinter dem, was sie gelesen hat, und wenn das Wort an der Stelle nicht passt, nichts. Ein Nichtterminal in der Regel wird ein Aufruf seiner Funktion. Eine kleine Hilfsfunktion peek zeigt das nächste Zeichen, ohne es zu lesen; am Ende des Worts gibt sie einen leeren String zurück.

So wird jedes Stück einer Regel zu Code:

# Wörter aus Klammerpaaren, nach der Grammatik
#   brackets = { "(" brackets ")" }
# Jede Funktion liest ab dem Index i, was ihre Regel erlaubt, und gibt den
# Index dahinter zurück, oder nil, wenn das Wort dort nicht passt.

# Das Zeichen am Index i, am Ende des Worts ein leerer String
def peek(word, i)
    word[i] || ''
end

# brackets = { "(" brackets ")" }
def brackets(word, i)
    while peek(word, i) == '('
        i = brackets(word, i + 1)
        return nil if i.nil? || peek(word, i) != ')'
        i += 1
    end
    i
end

# Das Wort gehört dazu, wenn brackets es bis zum Ende liest
def accepts(word)
    brackets(word, 0) == word.length
end

['(())()', '(()', '())', ''].each do |word|
    puts "#{word.inspect} #{accepts(word)}"
end

# Wörter aus Klammerpaaren, nach der Grammatik
#   brackets = { "(" brackets ")" }
# Jede Funktion liest ab dem Index i, was ihre Regel erlaubt, und gibt den
# Index dahinter zurück, oder None, wenn das Wort dort nicht passt.

# Das Zeichen am Index i, am Ende des Worts ein leerer String
def peek(word, i):
    return word[i] if i < len(word) else ''


# brackets = { "(" brackets ")" }
def brackets(word, i):
    while peek(word, i) == '(':
        i = brackets(word, i + 1)
        if i is None or peek(word, i) != ')':
            return None
        i += 1
    return i


# Das Wort gehört dazu, wenn brackets es bis zum Ende liest
def accepts(word):
    return brackets(word, 0) == len(word)


for word in ['(())()', '(()', '())', '']:
    print(repr(word), accepts(word))

"(())()" true
"(()" false
"())" false
"" true

Bei ()) liest brackets ein Paar und hört vor der zweiten ) auf, weil danach keine ( mehr kommt. Es gibt 2 zurück, das Wort ist aber 3 Zeichen lang: Darum prüft accepts, ob das ganze Wort gelesen ist.

Jetzt du: Zahlen

# Zahlen aus Ziffern, nach der Grammatik
#   number = digit { digit }
#   digit  = "0" | "1" | … | "9"

# Das Zeichen am Index i, am Ende des Worts ein leerer String
def peek(word, i)
    word[i] || ''
end

# hier: digit und number

p number('123', 0)
p number('12a', 0)
p number('a1', 0)

def digit(word, i)
    return nil unless …
    i + 1
end

def number(word, i)
    i = digit(word, i)
    return nil if i.nil?
    i = digit(word, i) while …
    i
end

# digit = "0" | "1" | … | "9"
def digit(word, i)
    return nil unless peek(word, i).between?('0', '9')
    i + 1
end

# number = digit { digit }
def number(word, i)
    i = digit(word, i)
    return nil if i.nil?
    i = digit(word, i) while peek(word, i).between?('0', '9')
    i
end

# Zahlen aus Ziffern, nach der Grammatik
#   number = digit { digit }
#   digit  = "0" | "1" | … | "9"

# Das Zeichen am Index i, am Ende des Worts ein leerer String
def peek(word, i):
    return word[i] if i < len(word) else ''


# hier: digit und number

print(number('123', 0))
print(number('12a', 0))
print(number('a1', 0))

def digit(word, i):
    if not …:
        return None
    return i + 1


def number(word, i):
    i = digit(word, i)
    if i is None:
        return None
    while …:
        i = digit(word, i)
    return i

# digit = "0" | "1" | … | "9"
def digit(word, i):
    if not '0' <= peek(word, i) <= '9':
        return None
    return i + 1


# number = digit { digit }
def number(word, i):
    i = digit(word, i)
    if i is None:
        return None
    while '0' <= peek(word, i) <= '9':
        i = digit(word, i)
    return i

6. Ausdrücke

Jetzt eine Sprache, die schon nach Programmieren aussieht: Ausdrücke aus Zahlen mit +, * und runden Klammern, ohne Leerzeichen, etwa 2+3*4 oder (1+2)*3.

expression = term { "+" term }
term       = factor { "*" factor }
factor     = number | "(" expression ")"

expression = term { "+" term }
term       = factor { "*" factor }
factor     = number | "(" expression ")"

Ein Ausdruck ist eine Summe aus Termen, ein Term ein Produkt aus Faktoren, und ein Faktor ist eine Zahl oder wieder ein ganzer Ausdruck in Klammern. Dass Multiplizieren stärker bindet als Plus, steht damit in der Grammatik selbst: Ein Term sammelt alle Faktoren mit * ein, bevor das nächste + drankommt. Der Syntaxbaum von 2+3*4 zeigt es: Das * hängt tiefer, in einem Term, und wird zuerst gerechnet.

expression(term(factor(number("2"))) "+" term(factor(number("3")) "*" factor(number("4"))))

Die Zahlen sind hier Blätter; ihre Ziffern bis hinunter zu digit lässt der Baum weg.

['2+3*4', '(1+2)*3', '2+', '(1+2', '2*+3'].each do |word|
    puts "#{word.inspect} #{accepts(word)}"
end

for word in ['2+3*4', '(1+2)*3', '2+', '(1+2', '2*+3']:
    print(repr(word), accepts(word))

def expression(word, i)
    i = term(word, i)
    while !i.nil? && peek(word, i) == '+'
        i = …
    end
    i
end

def factor(word, i)
    return … unless peek(word, i) == '('
    i = expression(word, i + 1)
    return nil if i.nil? || peek(word, i) != ')'
    …
end

def expression(word, i):
    i = term(word, i)
    while i is not None and peek(word, i) == '+':
        i = …
    return i


def factor(word, i):
    if peek(word, i) != '(':
        return …
    i = expression(word, i + 1)
    if i is None or peek(word, i) != ')':
        return None
    return …

Eine Funktion, die sich als Erstes selbst aufruft, mit demselben Index, kommt nie zu einem Zeichen: Sie ruft sich auf, bis der Stack der Aufrufe voll ist. Darum schreibt man solche Regeln in EBNF mit { … }, als Schleife. Ein Programm, das so für jede Regel eine Funktion hat und die Funktionen sich gegenseitig aufrufen lässt, heißt rekursiver Abstieg: Es steigt von der Regel für das Ganze zu den Regeln für die Teile hinab.

7. Ein Ausdruck, zwei Bäume

Warum so umständlich mit term und factor? Kürzer ginge es so:

expression = expression "+" expression | expression "*" expression | number

expression(expression(number("2")) "+" expression(expression(number("3")) "*" expression(number("4"))))

expression(expression(expression(number("2")) "+" expression(number("3"))) "*" expression(number("4")))

8. Grammatiken und Automaten

Noam Chomsky, ein Sprachwissenschaftler, hat 1956 Grammatiken danach geordnet, was ihre Regeln dürfen. Jede Stufe passt zu einer Art von Automaten, der genau ihre Sprachen erkennt:

Diese Ordnung heißt Chomsky-Hierarchie. Jede Stufe enthält die darunter: Eine reguläre Grammatik ist auch kontextfrei. Alle Grammatiken auf dieser Seite sind kontextfrei; was Programmiersprachen brauchen, liegt auf Stufe 2.

Mehr dazu

• Wikipedia: Chomsky hierarchy
• Wikipedia: Noam Chomsky
• doi.org
• Wikipedia: Context-free grammar

Noam Chomsky (geboren 1928), amerikanischer Sprachwissenschaftler am MIT. Er beschrieb Sprachen durch Regeln, die alle ihre Sätze erzeugen, durch Grammatiken, und machte das 1957 mit seinem Buch Syntactic Structures bekannt.

1956 ordnete er Grammatiken danach, was ihre Regeln dürfen; die Ordnung heißt heute Chomsky-Hierarchie. Die Syntax von Programmiersprachen beschreibt man seit ALGOL 60 mit kontextfreien Grammatiken, ihrer Stufe 2.

Foto: unbekannt, 1961, aus The Technology Review, MIT Museum, gemeinfrei, zugeschnitten (Wikimedia Commons)

9. Zusammenfassung

• Eine Grammatik besteht aus Regeln. Nichtterminale werden ersetzt, Terminale stehen im Wort, das Startsymbol ist die Regel, mit der man anfängt. Eine Ableitung ersetzt so lange, bis nur Terminale übrig sind; als Baum heißt sie Syntaxbaum.
• EBNF schreibt Regeln mit |, { … }, [ … ] und ( … ). Ein Syntaxdiagramm zeichnet dieselbe Regel: runde Kästen für Terminale, eckige für Nichtterminale.
• Die Grammatik legt die Syntax fest, wie ein Text gebaut ist, nicht die Semantik, was er bedeutet.
• Rekursiver Abstieg: Jede Regel wird eine Funktion, jedes Nichtterminal ein Aufruf, { … } eine Schleife. Wie tief die Aufrufe gerade gehen, merkt sich der Stack der Aufrufe.
• Eine Grammatik, nach der ein Wort zwei Syntaxbäume hat, ist mehrdeutig.
• Die Chomsky-Hierarchie ordnet Grammatiken: reguläre zu endlichen Automaten, kontextfreie zu Kellerautomaten, beliebige zu Turingmaschinen.

10. Wie geht es weiter?

• Ein Rechner für Ausdrücke. In Ein Rechner für Ausdrücke bekommt dieselbe Grammatik noch - und /. Die Funktionen geben dort nicht nur zurück, ob ein Ausdruck passt, sondern bauen seinen Syntaxbaum, und am Ende rechnet der Rechner ihn aus.
• Eine echte Grammatik lesen. Auf json.org steht das Datenformat JSON ganz als Syntaxdiagramme. Versuch, ein Stück JSON aus dem Handbuch unter JSON mit dem Finger auf den Diagrammen nachzufahren.