"Formale Sprachen und Parsing Algorithmen 001.ps.gz" - читать интересную книгу автораFormale Sprachen Miroslaw Kutylowski SS 1994 0 . b V e r s i no 3 LATEX 2"-Version Dieses Skriptum ist nach einer Mitschrift der Vorlesung entstanden. Es ist weitestgehend vollst"andig, aber nat"urlich nicht fehlerfrei! Falls jemand einen oder mehrere Fehler in diesem Skript findet, so m"oge er oder sie bitte eine E-Mail an eine der untenstehenden Adressen schicken. Die Fehler werden in regelm"assigen Abst"anden korrigiert und eine neue Version wird dann in das Netz eingespielt. Version von 31.5.96 Dirk Freykamp ([email protected]) Frank Freykamp ([email protected]) i Inhaltsverzeichnis 1 Regul"are Sprachen 1 1.1 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Besondere endliche Automaten . . . . . . . . . . . . . . . . . . . . . 4 1.3 Softwaresimulation von DEA . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Optimierung von DEA . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Regul"are Ausdr"ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Eigenschaften der regul"aren Sprachen . . . . . . . . . . . . . . . . . 15 1.7 Entscheidungsprobleme f"ur regul"are Sprachen . . . . . . . . . . . . . 17 2 Kontextfreie Sprachen 19 2.1 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Eigenschaften von kontextfreien Sprachen . . . . . . . . . . . . . . . 29 2.4 Abgeschlossenheit bei Boolschen Operationen . . . . . . . . . . . . . 30 3 Parsing 35 3.1 Shift-Reduce-Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Top-down-Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Pr"adiktive Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4 LR(0)-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5 LR(0)-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6 LR-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.7 Simple-LR-Parsing-Tabelle (SLR) . . . . . . . . . . . . . . . . . . . 57 3.8 Kanonische LR-Parsing-Tabelle . . . . . . . . . . . . . . . . . . . . 58 3.9 Look-Ahead-LR-Parsing (LALR) . . . . . . . . . . . . . . . . . . . 59 3.10 LR(k)-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 |
|
|