DeutschesFachbuch.de : Formale Sprachen, abstrakte Automaten und Compiler Lehr- und Arbeitsbuch für Grundstudium und Fortbildung Von Christian Wagenknecht, Michael Hielscher

INHALTSVERZEICHNIS | öffnen

Inhaltsverzeichnis
1 Einleitung 1
1.1 Theoretische Informatik und ihre Anwendungen 1
1.2 AtoCC - unsere Lernumgebung 4
2 Struktur von Programmen 5
2.1 Sprache, Syntax, Semantik und Pragmatik 5
2.2 Konkrete Syntax 7
2.3 Abstrakte Syntax 12
2.4 Syntaxanalyse 14
3 Grundbegriffe 17
3.1 Alphabet und Zeichen 17
3.2 Wort, Wortlänge und Verkettung 19
3.3 Wortmenge 21
3.4 Sprache 25
4 Definition unendlicher Mengen 27
4.1 Muster und formale Grammatiken 27
4.2 Ableitung und definierte Sprache 30
4.3 Nichtdeterminismus des Ableitungsprozesses 32
4.4 Mehrdeutigkeit kontextfreier Grammatiken 35
4.5 CHOMSKY-Hierarchie 36
4.6 ε-Sonderregelungen 38
4.7 Das Wortproblem 41
4.8 Recognizer und Parser für kontextfreie Sprachen 44
5 Sprachübersetzer 47
5.1 Compiler und Interpreter 47
5.2 Die Sprache eines Zeichenroboters 48
5.3 Modellierung von Übersetzungsprozessen 49
5.4 Scanner und Parser 56
6 Endliche Automaten und reguläre Sprachen 61
6.1 Aufbau abstrakter Akzeptoren 61
6.2 Deterministischer Endlicher Automat (DEA, EA) 63
6.3 Endlicher Automat und reguläre Grammatik 67
6.4 Nichtdeterministischer endlicher Automat (NEA) 70
6.5 Konstruktion eines äquiv. DEA aus einem NEA 76
6.6 Minimalautomaten 80
6.7 NEA mit e-Übergängen 89
6.8 Das Pumping Lemma für reguläre Sprachen 96
6.9 Endliche Maschinen 99
7 Reguläre Ausdrücke 105
7.1 Definition 105
7.2 Klammersparregeln 107
7.3 Äquivalente reguläre Ausdrücke 107
7.4 Reguläre Ausdrücke und endliche Automaten 108
7.5 Reguläre Ausdrücke in der Praxis 114
7.6 Anwendungsgebiete für reguläre Ausdrücke 118
7.7 Reguläre Ausdrücke in Scannergeneratoren 120
8 Kellerautomaten und kontextfreie Sprachen 127
8.1 Grenzen endlicher Automaten 127
8.2 Nichtdeterministischer Kellerautomat (NKA) 128
8.3 Äquivalenz von NKA und kontextfreier Grammatik 135
8.4 Parsing kontextfreier Sprachen 142
8.5 Deterministischer Kellerautomat (DKA) 146
8.6 Deterministisch kontextfreie Sprachen 148
8.7 Parsergeneratoren für dkf-S 151
8.8 Optimierung kontextfreier Grammatiken 153
8.9 CHOMSKY-Normalform 156
8.10 Das Pumping Lemma für kontextfreie Sprachen 157
9 LL(k)-Sprachen 161
9.1 Deterministische Top-down-Syntaxanalyse 161
9.2 Begriff 162
9.3 LL(1)-Forderungen 164
9.4 Top-down-Parser für LL(1)-Grammatiken 169
9.5 Methode des Rekursiven Abstiegs 171
9.6 Grammatiktransformationen 180
10 LR(k)-Sprachen 187
10.1 Begriff 187
10.2 Deterministische Bottom-up-Syntaxanalyse 187
10.3 Tabellengesteuerte LR(k) -Syntaxanalyse 191
10.4 Automatisierte Parsergenerierung 195
10.5 Compiler 198
[weiter lesen]

REGISTER | öffnen

Sachverzeichnis
AAbleitungsbaum, 15
Abstraktion, 2 action, 192
Akzeptanzverhalten EA, 64
Akzeptor, 61
Alphabet, 17
AST, 12
AtoCC, 4
- Attribute, 199
- ererbte, 199
- synthetisierte, 199
Ausdruck
- regulärer, 1, 105, 106
Automat
abstrakter, 3, 61
- endlicher, 63
- mit Ausgabe, 3
- nichtdet. endlicher, 71
- zellularer, 104
BBacktracking, 34
Backus-Naur-Form, 11
Bandlöschmaschine, 235
Berechenbarkeitstheorie, 2, 222
Bootstrapping, 53
Bottom-upAnalyse, 59, 187
Brute force, 40
busy beaver, 233
CChart, 143
Chart-Parser, 143
Chomsky, Noam, 36
Chomsky-Hierarchie, 36
CNF, 156
Compiler, 3, 14, 46, 47
- inkrementelle, 47
Compilerbau, 6
Compilergenerator, 3
Cross-Compiler, 54, 57
CYK, 156
Ddangling-else-Problem, 36, 182
DEA, 63
DTD, 44
dynamisches Programmieren, 142
EEaley-Algorithmus, 34
Earley-Parser, 143
EBNF, 11
Effizienz, 2, 231
Eingabevalidierung, 1, 118
Endzustand, 64
Entscheidungsproblem, 41
ε-Hülle, 91
ε-freie Regeln, 40
FFalle, 65
FIRST, 165
FOLLOW, 167
Ggoto, 192
Grammatik, 5, 28
- äquivalente, 35
- kontextfreie, 29, 37
- kontextsensitive, 37
- mehrdeutige, 35
- reduzierte, 58
- reguläre, 37
- unbeschränkte, 37
Grammatiktransformationen, 153
HHandle, 190
Iinhärent mehrdeutig, 36
Interpreter, 47, 208
JJIT-Compiler, 48
KKeller, 127
Kellerautomat, 120
Kettenregeln, 154, 155
kfG, 29
Komplexitätstheorie, 2, 231
Komposition, 7
Konfigurationenfolge, 65, 130
Konkatenation, 21
Kopplung von Turingmaschinen, 235
LLängenmonotonie, 38
LALR(1)-Sprachen, 195
LALR-Sprachen, 194
Lesekopf, 63
Lex, 196
lex, 3
Lexem, 58
Linguistik, 5
Linksableitung, 32
Linksfaktorisierung, 185
LL(1)-Forderung 2, 167
LL(1)-Forderung 1, 165
LL(1)-Parser, 164
LL(1)-Sprachen, 164
LOGO, 49
lookahead, 161
Lookahead-LR(1)-Sprachen, 195
LR(k)-Sprachen, 187
LR(1)-Sprachen, 194
LR-Parsetabelle, 191
MMaschine
- endliche, 100
- virtuelle, 47, 51
MEALY, 100
mehrdeutig, 35
Mehrdeutigkeit
- syntaktische, 14
Mehrdeutigkeit, semantische, 5
Memoizing, 170
Menge
- überabzählbar unendlich, 24
- abzählbar unendlich, 23
Mini Java-Script, 8
Minimalautomat, 80
MOORE, 100
NNachfolgermaschine, 233
NEA, 71
Nichtterminale, 11, 28
- unnütze, 154
Notensprache, 207
OOperatorbaum, 14
Ordnung
- längenlexikografische, 23
PParsergenerator, 46, 120, 172
Parsergeneratoren, 152
Parsing, 14
Pattern matching, 27, 115
Petri-Netz, 104
Phrasenstrukturgrammatik, 38
PL/0, 172
pop, 127
POSIX, 116
Postscript, 49, 202
Potenzmenge, 71
Pragmatik, 5
Produktion, 11
Produktionen, 28
Programme, 6
Protokoll, 6
- Pumping Lemma, 96
- für kfS, 157
push, 127
QQuellsprache, 14, 47
RRückwärtsreferenz, 116
Rechtsableitung, 32
Recognizer, 45
reduce, 188
reduce/reduce-Konflikt, 194
Regel, 11
Regeln, 28
- semantische, 199
RegExp Edit, 110
rekursiv aufzählbar, 228
rekursiver Abstieg, 171
Rucksackproblem, 143
SS-Attribute, 199
Sackgasse, 34
Satz von KLEENE, 108
Satzform, 28
Satzsymbol, 28
Scanner, 57
Scanner-Beschreibung, 122
Scanner-Simulation, 122
Scannergenerator, 120
Semantik, 5
Semi-Thue-System, 38
Semiotik, 5 shift, 188
shift/reduce-Konflikt, 194
Simultanableitung, 40
SLK(1)-Sprachen, 194
SLR-Sprachen, 194
Spielkonsole, 54
Spitzensymbol, 28
Sprachdesign, 7
- Sprache, 25
- akzeptierte, 65
- deterministisch-kontextfrei, 161
- formale, 6, 17
- kontextfreie, 33
- rekursiv aufzählbar, 229
Sprachklassen, 37
Stapel, 127
stark-LL(k) -Sprache, 163
Startsymbol, 28
SVG, 49, 214
Syntaktik, 7
Syntax, 5
- abstrakte, 12
- konkrete, 7
- Syntaxanalyse, 3, 14
- prädiktive, 161
Syntaxbaum
- abstrakter, 12
Systeme
- eingebettete, 54
TT-Diagramm, 49
tabellengesteuerte Analyse, 178
TDiag, 49
Terminale, 11, 28
Token, 58
Token-Pränx, 122
Tokenklasse, 122
Tokenliste, 58
[weiter lesen]