CompilerbauSkriptumzurVorlesungStudiengangInformatikProf.Dr.WinfriedBantelSommersemester2011Stand23.Marz2011Inhaltsverzeichnis1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.1 DerKomplex FormaleSprachen-Automatentheorie-Compilerbau. . . . . . 131.2 Beispielef urCompilerbau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3 Begrisbildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 DieProgrammiersprachePL/0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1 DieSyntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Programmbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3Ubungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Wiederholung AutomatentheorieundFormaleSprachen . . . . . . . . . . . . . 193.1 FormaleSprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.2 NotationsformenvonGrammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.1.3 NotationindiesemScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.4 GrammatikenundAutomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2 EndlicheAutomaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.1 Grundbegrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.2 ModelleineserkennendenAutomaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2.3 Darstellungsformen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2.4 Eineinf uhrendesBeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2.5 EndlicheAutomatenundFormaleSprachen. . . . . . . . . . . . . . . . . . . . . . . 273.2.6 GrundalgorithmuseinesEndlichenAutomaten. . . . . . . . . . . . . . . . . . . . 273.3 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4Ubungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.1 UPN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2 ScannerundParser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.1 ZusammenspielvonScannerundParser. . . . . . . . . . . . . . . . . . . . . . . . . . 314 Inhaltsverzeichnis4.3 PrimitiveScanner-zeichenbasiert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.4 PrimitiveScanner-wortbasiert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4.1 PrinzipieneinesScanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.4.2 ImplementierungvonScannern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.4.3 FehlerbehandlungbeiScannern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.5 Bootstrapping-DasHenne-Ei-Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6 RegulareAusdr ucke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.7 RegulareAusdr uckeinC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.8Ubungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 EndlicheAutomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.1 Grundbegrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 Darstellungsformen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.2.1 TabellarischeDarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.2.2 GraphischeDarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.3 AlgorithmuseinesendlichenAutomaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.4 Eineinf uhrendesBeispiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4.1 DeterministischeendlicheAutomaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.4.2 NichtdeterministischeendlicheAutomaten . . . . . . . . . . . . . . . . . . . . . . . . 435.5 EndlicheAutomatenmitAusgabe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.5.1 Moore-Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.5.2 Mealey-Automaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.6 Anwendungenvonendlichenautomaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.6.1 Erkennen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.6.2 Suchen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.6.3 Scannen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.7Ubungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 Keller-Automaten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.2 NativeKonstruktion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.3 LL-Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.3.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.3.2 FIRSTundFOLLOW. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.3.3 Programm-gesteuertesLL(1)-Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.3.4 LL-ParsingmitStackverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.3.5 EliminationderLinks-Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.3.6 Tabellen-gesteuertesLL-Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.4 LR-Parsing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.5 Operator-Prioritats-Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86Inhaltsverzeichnis 57 Symboltabellen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.2 MethodenderSymboltabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.3 AufbaueinesSymboltabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907.4 Fehlermoglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917.5 Namens-Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917.6 EineSymboltabelleaufBasisderC++-STL-Map . . . . . . . . . . . . . . . . . . . . . . . . 918 Zwischencode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938.2 ASTf urTerme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948.3 ASTf urPL/0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 998.4 Neu- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008.4.1 DieKnotenarten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1009 Speicherverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039.1 Einf uhrung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039.2 G ultigkeitsbereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039.3 StatischeSpeicherverwaltung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079.4 DynamischeSpeicherverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079.4.1 MethodenimHauptspeicher. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109.5 Statischevs.DynamischeSpeicherverwaltung. . . . . . . . . . . . . . . . . . . . . . . . . . . 11110 Code-Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11310.1OptimierungderKontrollstrukturen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11310.2OptimierungvonSpr ungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11310.2.1OptimierungvonNOPs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11310.2.2EliminierungunnotigerSpr unge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11310.3OptimierungvonAusdr ucken. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11410.4OptimierungdesSpeicherzugris. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11511 Code-Erzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11711.1Interpretierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11711.2Assembler-Erzeugung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11711.2.1DerEmitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11811.2.2Ausdr ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11811.2.3if-Statement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11811.2.4if-else-Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11911.3Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11911.4Variablenzugri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12011.5Funktionsaufruf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12111.6Spr unge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216 Inhaltsverzeichnis12 Generator-Tools. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12312.1Einleitung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12312.2Generator-Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12312.3Lex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.3.1Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.3.2GrundaufbaueinerLex-Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.3.3Denitionsteil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.3.4Regelteil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12412.3.5RegulareAusdr ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12512.3.6Lex-Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12512.3.7Lex-Funktionenund-Makros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12512.3.8Startbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12512.3.9Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12612.4Yacc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12712.4.1Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12712.4.2GrundaufbaueinerYacc-Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12812.4.3Denitionsteil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12812.4.4Yacc-Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12912.5KonikteinYacc-Grammatiken. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12912.5.1Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129A DerPL/0-Modellcompiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135A.1 DieModuledesCompilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135A.2 Quellcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135B ASCII-Tabelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157C Abk urzungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161Abbildungsverzeichnis1.1 PhaseneinesCompilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1 HierarchiederSprachennachChomsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Syntaxbaum DieKatzeschnurrt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.3 Syntaxbaum DerHundjagtdieKatze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 AutomatzurZahlenerkennung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.1 TaschenrechnerHP12C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2 ZusammenspielzwischenScannerundParser . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.1 ModelleinesendlichenAutomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 AlgorithmuseinesendlichenAutomaten-StopbeiEndezustand . . . . . . . . . . . . 405.3 AlgorithmuseinesendlichenAutomaten-StopbeiEingabeende . . . . . . . . . . . . 415.4 ModellMoore-undMealey-Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.5 EinfacheTextsuche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.6 Aloisius-ScanneralsMealey-Automat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526.1 EndlicherAutomatf urL = anbn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.2 ModelleinesKellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.3 SyntaxbaumbeilinksrekursionsfreierGrammatik . . . . . . . . . . . . . . . . . . . . . . . . . 687.1 AufbaueinerSymboltabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908.1 Compiler-CollectionohneSchnittstelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948.2 Compiler-CollectionmitSchnittstelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948.3 Syntaxbaumf urTerm1 + 2 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958.4 Datenstrukturf urbinarenOperator-Baum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958.5 ASTf urPL/0-Programmggt.pl0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008.6 ZwischencodezurVerzweigung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028.7 ZwischencodezurkopfgfesteuertenSchleife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1029.1 SchachtelungsmoglichkeitenvonFunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048 Abbildungsverzeichnis9.2 SymboltabellebeistatischerHauptspeicherverwaltung(Listing9.1). . . . . . . . . 1079.3 StatischerHauptspeicherglokalzuf(Listing9.1) . . . . . . . . . . . . . . . . . . . . . . . . 1079.4 LeererHauptspeicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1089.5 Hauptspeicherglokalzuf(Listing9.1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099.6 Hauptspeichergundflokalzumain(Listing9.2) . . . . . . . . . . . . . . . . . . . . . . . . . 1099.7 Hauptspeicherflokalzug(Listing9.3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11011.1 AblaufplanEinfacheVerzweigung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11911.2 AblaufplanVerzweigungmitAlternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11911.3 Ablaufplankopfgesteuerteschleife. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12012.1 VerarbeitungeinerLex-Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12312.2 VerarbeitungvonYacc-undLex-Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Tabellenverzeichnis6.1 Parsing-Vorgang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706.2 Parsing-VorgangmitCode-Erzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706.3 LL(1)-Parsetabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716.4 ParstabellezutabellengesteuertemLL(1)-ParsenmitRekursion. . . . . . . . . . . . 746.5 LR-Tabellef urAusdr ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796.6 LR-Parse-Vorgang1+2*3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809.1 Vor-undNachteilevonstatischerunddynamischerSpeicherverwaltung . . . . . 111Listings2.1 RekursiveFakultatinPL/0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 GrotergemeinsamerTeiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.1 EinzeichenbasierterScanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2 Scannendurchstrtok-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.3 Beispielf urMaximum-Match-Methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.4 DemozurBenutzungvonRegularenAusdr uckeninC . . . . . . . . . . . . . . . . . . . . . 355.1 Zahlenerkennung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2 Aloisius-Scanner1(primitiv) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.3 Aloisius-Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.4 BCD-Erkenner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.5 Textsuche-Einfachstversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.6 Lola-Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.7 Aloisius-Scanner2(schnell) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.8 Scannerf urarithmetischeAusdr ucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.9 Header-DateizumTerm-Scanner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.10 Testprogrammf urScanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566.1 KellerautomatzurBerechnungarithmetischerAusdr ucke. . . . . . . . . . . . . . . . . . 626.2 ProgrammgesteuerterLL(1)-Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.3 LL(1)-ParsermitStackverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716.4 TabellengesteuerterLL(1)-Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746.5 LR-Parser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806.6 Term-GrammatikinYacc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826.7 Term-GrammatikinYacc-Zusatzinformationen . . . . . . . . . . . . . . . . . . . . . . . . . 836.8 Operator-Prazedenz-Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86./programme/ast/termast.h. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958.1 DenitionsdateizumOperator-Baum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968.2 Programm-CodezumOperator-Baum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968.3 CompilerzurOperator-Baum-Erstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979.1 glokalzuf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10412 Listings9.2 fundglokalzumain. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1059.3 flokalzug. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10610.1 KekursivesPotenzierennachLagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11411.1 Codeerzeugungf urVariablenzugri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12012.1 Lex-ProgrammzurExtraktionvonC-Inline-Kommentaren . . . . . . . . . . . . . . . . . 12612.2 PL/0-Zusweingen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12612.3 Term-ScannermitLex. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12612.4 EinTerm-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12912.5 EinTerm-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13012.6 EinTerm-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13112.7 EinTerm-Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132A.1 Hauptprogramm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135A.2 Scanner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136A.3 Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138A.4 ASTHeader. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141A.5 ASTCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142A.6 SymboltabelleCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146A.7 SymboltabelleHeader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147A.8 Fehlermodul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148A.9 Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149A.10 Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1521Einf uhrungAbbildung1.1zeigtdieverschiedenenPhaseneinesCompilersnach[ASU88].Abb. 1.1. PhaseneinesCompilersZielprogrammCode-ErzeugungCode-OptimierungZwischencode-ErzeugungSemantischeAnalyseSyntax-AnalyseLexikalischeAnalyseQuellprogrammSymbol-tabelle

``````

Fehler-behandlung``````

CompilerbauistdasschwierigsteFachgebietinderInformatik,daextremviel Theoriever-standenwerdenmuss!Compilerbauist das einfachsteGebiet der Informatik, danur hier Programmeentwickeltwerdenkonnen,diezueinenProblemeineLosungautomatischprogrammieren!1.1DerKomplex FormaleSprachen-Automatentheorie-CompilerbauDenition1.1. AbgrenzungderdreiTeilgebieteFormaleSprachen istdieWissenschaft,Sprachenzubeschreiben.Automatentheorie ist die Wissenschaft, die Syntax von Texten, die in einer formalen Sprachegeschriebensind,zu uberpr ufen.14 1 Einf uhrungCompilerbau ist die Wissenschaft, Automaten zu codieren und um einUbersetzungsmodul zuerweitern.1.2Beispielef urCompilerbau Internet-Benutzereingaben Rechen-Programme Syntax-HighlightningvonEditoren Verarbeitungvonini-Dateien SQL-Interpreter VerarbeitungvonEingabedaten Web-Browser XML-Verarbeitung1.3BegrisbildungDenition1.2 (Compiler). EinCompiler ubersetzt einineiner formalenSprache ge-schriebenesProgrammineineandereformaleSprache.Denition1.3 (Interpreter). EinInterpreter f uhrt einineiner formalenSprache ge-schriebenesProgrammaus.Mischformensindmoglich,popularstesBeispielistJava.2DieProgrammiersprachePL/0Als Programiersprache, welche sichkonsequent durchdie Beispiele zieht, verwendenwirPL/0. Hierbei handelt es sich um ein Mini-Mini-Pascal, welches Wirth in [Wir86] vorschlagt.2.1DieSyntaxGrammatik 1 zeigt die Grammatik der Programmiersprache PL/0, wie Wirth sie in [Wir86]einf uhrt.Grammatik1:PL/0program ::= block "."block ::= [ "CONST" ident "=" number {"," ident "=" number} ";"][ "VAR" ident {"," ident} ";"]{ "PROCEDURE" ident ";" block ";" } statementstatement ::= [ ident ":=" expression| "CALL" ident| "?" ident| "!" expression| "BEGIN" statement {";" statement } "END"| "IF" condition "THEN" statement| "WHILE" condition "DO" statement ]condition ::= "ODD" expression| expression ("="|"#"|"=") expressionexpression ::= [ "+"|"-"] term { ("+"|"-") term}term ::= factor {("*"|"/") factor}factor ::= ident| number| "(" expression ")"Da die Ausdr ucke keine beliebigen Vorzeichen zulassen behalten wir uns vor, die Ausdr uckegemaunsererTerm-Grammatikzuimplementieren,dieseistabwartskompatibelzuPL/0-Ausdr ucken.16 2 DieProgrammiersprachePL/0PL/0bietet wichtigeGrundlagenvonProgrammiersprachen, jedochfehlenauchwichtigeDinge: Datentypen,PL/0bietetnurint-Daten Strings ParameterundFunktionswertef urFunktionen Felder Strukturen Zeiger DynamischeHauptspeicherallokierungAmEnde der Vorlesung werdenwir einenkomplettenPL/0-Compiler bzw. -Interpreterentwickelthaben.2.2ProgrammbeispieleListing2.1. RekursiveFakultatinPL/0(pl-0/programme/fakultaet.pl0)1 ( Rekursi ve Berechnung der Fakul t at )2 VARn , f ;3 PROCEDUREf a kul t a e t;4 BEGIN5 ! n ;6 IF n>0THEN7 BEGIN8 DEBUG;9 f := f n ;10 n := n 1;11 CALL f a kul t a e t;12 n := n +1;13 DEBUG;14 END;15 END;16 BEGIN17 ? n ;18 f := 1;19 DEBUG;20 CALL f a kul t a e t;21 DEBUG;22 ! f ;23 END.Listing2.2. GrotergemeinsamerTeiler(pl-0/programme/ggt.pl0)1 ( Berechnet GGTvon zwei Zahl en )2 VARa , b , g ;3 PROCEDUREggt ;4 BEGIN5 WHILEa #bDO6 BEGIN7 IF a >bTHENa := a b ;2.3Ubungen 178 IF b>aTHENb := b a ;9 END;10 g := a ;11 END;12 BEGIN( Hauptprogramm)13 ? a ;14 ? b ;15 CALL ggt ;16 ! g ;17 END.2.3UbungenUbung2.1. KleinstesgemeinsamesVielfachesAlgorithmus1berechnetdaskleinstegemeinsameVielfache(KGV)zweierganzerZahlen:Algorithmus1:KleinstesgemeinsamesVielfachesEingabea,bx=a,y=b

x>>>>>>.`` - `` - ZR,E,PP ZRR,E,P P,RE E Z ZZ= {0, 1, 2, 3, 4, 5}E= {E, Z, P, R}= EZPR0 4 14 41 5 12 42 4 34 43 5 34 4z0=0F= {4, 5}Satz1. ZujederregularenSprache(Chomsky-Typ-3)kanneinaquivalenterendlicherAu-tomatkonstruiertwerden,derdieSyntaxdieserSprache uberpr uft.3.2.5EndlicheAutomatenundFormaleSprachenSatz2. zujedemendlichenAutomatenkanneineregulareGrammatikentwickeltwerden,diedievondiesemAutomatakzeptierteSprachebeschreibt.3.2.6GrundalgorithmuseinesEndlichenAutomatenAlgorithmus2:Grundalgorithmus1einesendlichendeterministischenAutoma-tenzustand=z0solangezustand/ FliesEingabezeichenzustand= (zustand, Eingabezeichen)28 3 Wiederholung AutomatentheorieundFormaleSprachenAlgorithmus3:Grundalgorithmus2einesendlichendeterministischenAutoma-tenzustand=z0solangenichtamEingabeendeliesEingabezeichenzustand= (zustand, Eingabezeichen)3.3KellerautomatenSatz3. Zu jeder kontextfreien Sprache (Chomsky-Typ-2) kann ein aquivalenter Kellerauto-matkonstruiertwerden,derdieSyntaxdieserSprache uberpr uft.Satz4. ZujedemKellerautomatenkanneinekontextfreienGrammatik(Chomsky-Typ-2)entwickeltwerden,diedievondiesemAutomatakzeptierteSprachebeschreibt.3.4UbungenGegebenistGrammatik12:Grammatik12:MathematischerTermE T {(+ | -)T}TF {(* | /)F}F zahl | (E) | -F | +FDabeisindE,TundFNon-Terminals,zahlunddieZeichen+,-,*,/,(und)sindTerminals.12isteineGrammatikzurBeschreibungarithmetischerTerme.Ubung3.4. Grammatik-ArtVonwelchemChomsky-Typist12?Ubung3.5. SyntaxbaumErstellenSiedenSyntaxbaumf urdenTerm (1 2).Ubung3.6. BNF-UmformungFormenSie12inBNFum.Ubung3.7. SyntaxdiagrammeZeichnenSiedieSyntaxdiagrammef ur12.4Grundlagen4.1UPNUPNsteht f urUmgekehrtePolnischeNotation, imenglischenSprachgebrauchentspre-chendRPNgenannt.einweitersSynonymist Postx-Notation.UPNhatf urmaschinelleVerarbeitungentscheidendeVorteile: EsgibtOperatorenkeinerleiPrioritatsregelnwie PunktvorStrich. EsgibtkeinePrioritatsklammern.Aus diesemGrundwurdenundwerdenProzessorengerne als Register-Stack-Maschinenentwickelt. Die Firma Hewlett-Packard baute lange Zeit Taschenrechner, die in UPN bedientwurden, Abbildung 4.1 zeigt exemplarisch das Modell HP 12C. Wie zu erkennen ist, hat derTaschenrechner weder eine Gleichheits- noch Klammertasten, daf ur aber die Enter-Taste diezumTrennenderEingabedient.UbrigensverwendendieklassischenTaschenrechnerkeineAbb. 4.1. TaschenrechnerHP12C30 4 GrundlagenreineInx-Notation, sondernbei NutzungvonFunktionenebenfallsdiePostx-Notation.ZurBerechnungdesTerms32+ 42istdieWurzeltastezuletztzudr ucken.UPNwirdfolgendermaenabgearbeitet: Zahlen(Operanden)werdenaufdenStackgelegt. Bei OperatorenwirdjenachWertigkeit desOperators(unaroderbinar) dieentspre-chendeZahlvonOperandenvomStackgeholt,entsprechenddemOperatormiteinanderverkn upftunddasErgebniswiederaufdenStackgelegt. Bei Funktionen wird je nach Anzahl der Funktionsparameter die entsprechende Zahl vonOperanden vom Stack geholt, entsprechend der Funktion miteinander verkn upft und dasErgebniswiederaufdenStackgelegt.Ausdr uckem ussenf urRegister-Stack-MaschineninReverse-Notation(UPN)umgewandeltwerden:Ausdruck Maschinencode1+2*3LOADC 1LOADC 2LOADC 3MULTADD(1+2)*(3+4)LOADC 1LOADC 2ADDLOADC 3LOADC 4ADDMULTDieUmsetzungkanndurchdenSyntaxbaumerfolgen.123//``*//``+Wird dieser Baum im Postorder-Verfahren Durchlaufen, so ergibt sich die Abfolge 1 2 3 * +,wasdemobigenMaschinencodeentspricht.12//``+34//``+//``*Wird dieser Baum im Postorder-Verfahren Durchlaufen, so ergibt sich die Abfolge 1 2 + 3 4 + *,wasdemobigenMaschinencodeentspricht.4.2 ScannerundParser 314.2ScannerundParserGrammatik13isteineModikationvonGrammatik12(Seite28).Dabeiwurdedaster-minaleSymbolzahldurcheinweiteresNon-Terminalersetzt:Grammatik13:Term-Grammatik1E T {(+-)T}TF {(*/)F}F Z(E)-FZ (01...9){01...9}NunkonnteeinKellerautomatentwickeltwerden,derdieSyntaxeinesEingabetextes uber-pr uft,wobeiderEingabetextzeichenweiseverarbeitetwerdenkann.inderPraxisistdiesesVorgehenaberausverschiedenenGr undenunpraktisch: DieAnzahlderNon-Terminalsistunnotighoch. In Programmiersprachen entsteht ein Konikt zwischen Bezeichnern und Schl usselwortern(sieheetwadiePL/0-Grammatik1. Sog. whitespace-Zeichen m ussen uberlesen werden und w urden eine Grammatik unnotigkompliziertermachen.Daher wird man diejenigen Regeln einer Grammatik, die f ur sich genommen vom Chomsky-Typ2sind,ausderGrammatikherausnehmenundgesondertbehandeln: DiealsTyp2darstellbarenRegelnwerden uberdiesog.lexikalischeAnalyseerkannt. DierestlichenRegelnwerdenvondersyntaktischenAnalyseerkannt.DielexikalischeAnalyse ubernimmtdersog.Scanner,diesyntaktischeAnalysederParser.Denition4.1 (Scanner). ScannerzerlegeneineEingabeinihreBestandteile.EserfolgtkeineUberpr ufungobdiegefundenenTeileSinnergeben. DiesenVorgangnenntmanauchLexikalischeAnalyse.Denition4.2 (Parser). Parser uberpr ufeneineFolgevonZeichenihres Eingabealpha-betsaufkorrekteReihenfolge.DiesenVorgangnenntmanauch SyntaktischeAnalyseoderGrammatikalischeAnalyse.Denition4.3. DieElementeeinerSprache,dieeinScannerndet,nenntmanToken.4.2.1ZusammenspielvonScannerundParserAbb. 4.2. ZusammenspielzwischenScannerundParserScanner9867Scanner9867InputToken32 4 GrundlagenScannerundParsersolltenzweckslogischerTrennunginzweiunterschiedlichenFunktionenimplementiertwerden.DerR uckgabewertvonScannerzumParser(dassog. Token)wirdvonDatentypintangelegt.DerScannerwirdvomParsermehrfachaufgerufenundliefertdasjeweilsnachjsteTokenzur uck. Vom Modell her liest er einfach aus der Eingabe. Ist die Eingabe eine Datei (ein FILE-Zeiger), so ubernimmt das Betriebssystem die Verwaltung des Lesezeigers. Wird dagegen auseinem Speicherbereich gelesen, so muss uber scanner-interne statische Variablen die aktuelleLesepositiongespeichertwerden.AlsBeispielsolldieToken-Folgef urdenC-Text if (a>2)betrachtetwerden: Token if Token Klammerauf Token Bezeichner,Wert= a Token Operator> Token Konstante,Wert=2 Token KlammerzuBei vielenGrammatikenistjedochdasTokenalsR uckgabeungen ugend. Unter4.2wurdediskutiert, die Grammatik einer formalen Sprache nicht bis ins letzte Zeichen zu formulieren,sondern einzelne Regeln, die f ur sich genommen eine Typ-2-Grammatik darstellen, durch denScanner zu verarbeiten. daraus folgt aber, dass Scanner einer typischen Programmiersprachewuie PL/0 oder C alle Bezeichner durch ein- und dasselbe Token an den Parser melden unddieserdamitkeineMoglichkeithat, deneigentlichenNamendesBezeichnerszuerfahren.GenausoverhaltessichmitZahlen.Aus diesem Grund geben Scanner in der Praxis nicht nur einen Tokenwert sondern zusatzlichdengescanntenTextoderZahlenwerteoderahnlicheszur uck.4.3PrimitiveScanner-zeichenbasiertHaug machen Scanner nichts anderes, als verschiedene Zeichen zu einer Gruppe oder Klassezusammenzufassen,d.h.derScannerliestimmergenaueinZeichenausdemEingabestrom.DieseScannersindsehreinfachaufgebaut, dasieimmernureinenVergleicheineseinzel-nenZeichensmachenm ussen. Betrachtenwirnocheinmal denAutomatinAbbildung3.4(Seite27), soerkennenwir, dassimgesamtenAutomatendieZiern0bis9immergleichbehandelt werden. W urde man nun alle Ziern im Eingabealphabet Eangeben, so ware diedelta-Tabelle13Spaltenbreit.SetztmanabereinenzeichenbasiertenScannerein,deralleZiernzueinemTokenT Ezusammenfasst, kommtdiedelta-TabellemitvierSpaltenaus. EinScanner f ur diesenAutomat solltealsoeines der Tokens Z(Zier), P(Punkt),E(Ende)undR(Rest)zur uckliefern. DerScannerselbstistinListing4.1codiert, wobeidas HauptprogrammkeinenAutomatendarstellt, sondernlediglichdenAufruf des Scan-nersdemonstriert.InZeile28desProgrammswirdlediglicheinZur ucksetzendesScannersdurchgef uhrt,inZeile31erfolgtdereigentlicheAufrufdesScanners.Listing4.1. EinzeichenbasierterScanner(grundl-scanner-xkommazahl.c)1 /2 Scanner f ur Fixkommazahl3 /4 #i nc l ude 56 t ypedef enum{ t ende, t z i f f e r , t punkt, t r e s t } token ;4.4 PrimitiveScanner-wortbasiert 3378 token f i xkomma scanner ( char i nput, i nt reset ) {9 s t a t i c char p ;10 t oken t ;11 i f ( r e s e t ) {12 p =i nput 1;13 ret urn t ende ; // Keine Verarbei t ung !14 }15 i f ((++p) >= 0 && p2)m usste if(a>2)codiertwerden.Durch das Weglassen der trennenden Whitespace-Zeichen kann es aber zu Mehrdeutigkeitenbeim Scannen f uhren. So kann der C-Text if_avom Scanner entweder in die Token-FolgeSchl usselworztif - Bezeichner aoderaberindieToken-FolgeBezeichnerifazerlegtwerden.DasVerhalteneinesScannersineinemsolchenFallistDenitionssache:Denition4.4. Ein Scanner wahlt immer das Token, das den langsten Eingabetext abbildet.Diesnenntmandas Maximum-Match-Prinzip.AlsBeispielf urMaximum-MatchdientderAusdruckinZeile4Listing4.3.Listing4.3. Beispielf urMaximum-Match-Methode(grundl-maximum-match.c)1 #i nc l ude 2 i nt main ( ) {3 i nt a , b =1 , c =2;4 a=b+++c ; // Achtung ! ! ! !5 p r i nt f (a =%d , b =%d , c =%d\n , a , b , c ) ;6 ret urn 0;7 }Der C-Scanner zerlegt den Ausdruck in Zeile 4 in die Token-Folge Bezeichner a - Operator =- Bezeichner b - Operator ++ - Operator + - Bezeichner c. Aus dieser Token-Folge produziertderParserdanndenfolgendenSyntaxbaum:4.7 RegulareAusdr uckeinC 35ab++c

+...

=DasMaximum-Match-ProblemtrateauchinZeile6auf,wenndasLeerzeichennichteinge-geben worden ware. In Diesem Fall w urde der Scanner statt der Token-Folge Schl usselwortreturn-Int-Konstante0dieTokenfolge Bezeichnerreturn0liefern.Scanner m ussen - wenn gefordert wird, moglichst keine Leerzeichen einzugeben - oft voraus-schauendagieren.BeispielsweisewirdeinScannerimC-Ausdruck1.2E3+4biszumZeichen+davonausgehen, eine Fliekomma-Zahl einzulesen. Das +-Zeichenproduziert aber kei-nenSyntax-Fehler, sondernbeendetdasScannenderFliekommazahl undwird- f urdennachstenScan-Vorgang-indieEingabezur uckgestellt.Denition4.5. Arbeitet ein Scanner vorausschauend, so nennt man diese einen Look-Ahead.4.4.2ImplementierungvonScannernScannerbestehenmeistauseinerMengevonregularenAusdr uckenundwerdendamitambesten als endliche Automaten codiert. Diese Technik sichert schnelle Scan-Vorgange, da dieLaufzeitproportionalzurEingabestromlangeist.SchlechteScannerarbeitenmiteinfachenString-Vergleichen.Da die -Tabellen der Automaten meist sehr gro sind, werden zur Codierung von ScannerngerneToolswieLexeingesetzt.Desweiteren uberlesenScannerWhitespace-Zeichen,weshalbdiesenichtinderGrammatikdesParsersvorkommen.4.4.3FehlerbehandlungbeiScannern4.5Bootstrapping-DasHenne-Ei-Problem4.6RegulareAusdr ucke4.7RegulareAusdr uckeinCListing4.4. DemozurBenutzungvonRegularenAusdr uckeninC(regex.c)1 /2 Demonstri er Regul are Ausdr ucke mit C3 /4 #i nc l ude 5 #i nc l ude 6 #i nc l ude 78 i nt main( i nt argc, char argv [ ] )36 4 Grundlagen9 {10 char i nput [ 255] , rp [ 255] =[ 0 9] +(\\. [ 0 9] +)?$ , e r r o r t e x t[ 2 5 5 ] ;11 r e g e x t r egexpr ;12 i nt rc ;1314 p r i nt f ( Brauche Input : ) ;15 f g e t s ( i nput, 254 , s t di n ) ;16 i nput [s t r l e n ( i nput ) 1] = \0 ;17 p r i nt f ( Input : %s \nRegExp : %s \n , i nput, rp ) ;18 i f ( ( rc =regcomp(&regexpr, rp , REGEXTENDED| REG NOSUB) ) != 0) {19 r eger r or ( rc , &regexpr, e r r or t e x t , 254) ;20 p r i nt f ( Problem beim Ausdruck %s : %s \n , rp , e r r o r t e x t) ;21 }22 el se {23 rc =r egexec(&regexpr, i nput, 0 , NULL, 0) ;24 r eger r or ( rc , &regexpr, e r r or t e x t , 254) ;25 p r i nt f ( Antwort : %d %s \n , rc , e r r o r t e x t) ;26 }27 r e g f r e e (&r egexpr ) ;28 r et ur n 0;29 }4.8UbungenUbung4.6. SyntaxbaumeSetzenSiediefolgendenMathematischenTermeinSyntaxbaumeundUPNum, arbeitenSieanschlieenddenUPN-Codeab.a=11b+1cx1= b +b24ac2aUbung4.7. ScannerSpielenSief urfolgendenC-CodeScanner:i nt main ( ) {i nt a =125 , b =250;whi l e ( a != b )i f ( a >b )a =b ;e l s eb =a ;p r i nt f (%d , a ) ;ret urn 0;}Ubung4.8. GrammatikGegebenistdiefolgendeSprache:S ::= E {O E}4.8Ubungen 37E ::= F {(A | N) F}F ::= W | ( E )O ::= (O | o) (R | r)N ::= (N | n) (O | o) (T | t)A ::= (A | a) (N | n) (D | d)W ::= B {B}B ::= A | a | B | b | ... | Z | zDie Grammatik enthalt die Schl usselworter AND, OR und NOT, wobei Gro-Kleinschreibungunbedeutendist, bei derRegel Wsinddiedrei Schl usselworterausgenommen. DenierenSie,welchederRegelnvoneinemScannerundwelchevoneinemParserverarbeitetwerdensollten.5EndlicheAutomatenWieeingangserwahnt,sindformaleSprachenundAutomatenengmiteinanderverbunden.ZujederregularenGrammatikkanneinendlicherAutomatkonstruiertwerden, derdieseGrammatikerkennt. AndersherumkannzujedemendlichenAutomateneineGrammatikangegebenwerden.Wie man zu regularen Sprachen Automaten konstruiert und wie man zu Automaten regulareSprachenentwickeltsollhiernichtGegenstandsondernVoraussetzungsein.5.1GrundbegrieEinendlicherAutomatisteinSystem, dasinterneZustandeabhangigvoneinerEingabeannimmt.Abbildung5.1zeigtdasModelleinesAutomaten.EinendlicherAutomatAistdamiteinF unftupelA=(Z,E,,z0,F).ZistdieMengederZustandeindenensichderAutomatAbendenkann.EistdasEingabealphabetdesAutomaten(dieMengederEingabesymbole). istdieUbergangsfunktion,diejederKombinationausZustandundEingabesymboleinenFolgezustandzuordnet.Z E Z.z0istderStartzustand,indemsichderAutomatamAnfangbendet.FistdieMengederEndezustande(F Z).KommteinAutomatineinenEndezustandsohorteraufzuarbeiten.Abb. 5.1. ModelleinesendlichenAutomatenEingabebandAutomat`40 5 EndlicheAutomaten5.2DarstellungsformenAbbildung 3.4 auf Seite 27 zeigte bereits einen endlichen Automaten sowohl in grascher alsauchintabellarischerDarstellungsform.5.2.1TabellarischeDarstellungDieUbergangsfunktionkannalsTabelledargestelltwerden. Dabei werdendieZustandemeistalsZeilenunddasEingabealphabetalsSpaltendargestellt.F ur Endezustande gibt es keine Zeilen(daaus diesenZustandennicht mehr gewechseltwird).DietabellarischeDarstellungistf urunsMenschenweniger ubersichtlich, lasstsichjedocheinfacherineinProgrammcodieren.5.2.2GraphischeDarstellungDieUbergangsfunktionkannalsUbergangsgraph(Diagramm)dargestelltwerden. DabeiwerdendieZustandealsKreise(doppelteLinienf urEndezustande)dargestellt. DieUber-gangsfunktionwirddurchPfeiledargestellt,diePfeilewerdenmiteinemZeichenausdemEingabealphabetbeschriftet.VonEndezustandenf uhrenkeinePfeileweg.DerStartzustandkanndurcheinenInitialpfeilmarkiertwerden.DiegraphischeDarstellungistf urunsMenschensehr ubersichtlich, lasstsichjedochnichtsoeinfachineinProgrammcodieren.5.3AlgorithmuseinesendlichenAutomatenEndlicheAutomatenwerdenauf zwei verschiedeneArtencodiert, dieindenAbbildungen5.2und5.3dargestelltsind.JenachAufgabe-Erkennen,Suchen,Scannen,...-istmaldieeineundmaldieandereVariantezubevorzugen.Abb. 5.2. AlgorithmuseinesendlichenAutomaten-StopbeiEndezustandErkennenderAutomatGeheinStartzustandZustandkeinEndezustandLiestokenvonScannerGeheinFolgezustand(zustand,token)---------------.............. .ZustandeinFehlerzustand?Ja NeinAusgabeFehlermeldung AusgabeOK5.4 Eineinf uhrendesBeispiel 41Abb. 5.3. AlgorithmuseinesendlichenAutomaten-StopbeiEingabeendeErkennenderAutomatGeheinStartzustandNichtamEingabeendeLiestokenvonScannerGeheinFolgezustand(zustand,token)---------------.............. .ZustandeinEndezustand?Ja NeinAusgabeOK AusgabeFehlermeldung5.4Eineinf uhrendesBeispielDer Automat zur ErkennungvonFixkommazahlen(Abbildung3.4Seite 27) soll gemaAbbildung5.2codiertwerden.DerregulareAusdruckf urdiesenAutomatenlautet[0-9]+("."[0-9]+)?.DasfolgendeProgrammhat-umdieUnterschiedezuverdeutlichen-denendlichenAuto-matenzweimalimplementiert:Tabellengesteuert Inder Funktionautomatt wirdder Automat tabellengesteuert imple-mentiert.Die-FunktiondesAutomatenwirdineinemzweidimensionalenFeldgespei-chert. DieZeilenentsprechendenZustanden, dieSpaltendenTokensderlexikalischenAnalyse.Programmgesteuert InderFunktionautomatpwirdderAutomatprogrammgesteuertim-plementiert.DazuwerdenMehrfachverzweigungeninzweiEbenenineinandergeschach-telt. DieauereMehrfachverzweigungentsprichtdemZustand, dieinnerejeweilsdemTokenderlexikalischenAnalyse.Listing5.1. Zahlenerkennung(automaten-zahlenerkennung.c)1 /2 Erkennung von Fixkommazahlen3 Regul arer Ausdruck :4 [ 0 9] +(. [ 0 9] +)?5 /6 #i nc l ude 78 i nt scanner ( char , i nt) ; // Prototypen9 i nt automat t ( char ) ;10 i nt automat p ( char ) ;1112 enum{E, Z, P, R} ; // Token , Ei ngabeal phabet1314 i nt main ( ) {15 char i nput [ 2 5 5 ] ;1617 whi l e ( p r i nt f (\ nInput : ) , s canf (%s , i nput ) !=EOF) {18 p r i nt f (\nT:%s OK! , ( ! aut omat t ( i nput ))? : ni cht ) ;19 p r i nt f (\nP:%s OK! , ( ! automat p ( i nput ))? : ni cht ) ;42 5 EndlicheAutomaten20 }21 pr i nt f (\n ) ;22 r et ur n 0;23 }2425 i nt automat t ( char in) { // Tab e l l e ng e s t e ue r t e r Automat26 // R uckgabe 0: ei ngabe OK; R uckgabe 1: Ei ngabe NICHTOK27 i nt zust and =0;28 i nt d e l t a[ ] [ 4 ] ={/ 0 1 2 3 Token/29 / Zustand 0/ {4 , 1 , 4 , 4 } ,30 /Zustand 1/ { 5 , 1 , 2 , 4 } ,31 /Zustand 2/ { 4 , 3 , 4 , 4 } ,32 /Zustand 3/ { 5 , 3 , 4 , 4 } };3334 scanner ( in , 1 ) ;35 while ( zustand >>>1,E,F

E,F`1,E,FE,F

E,F>>>>>.E,F 0 1 2 3E 0 1 F0 7 1 4 81 8 2 2 82 8 3 3 83 8 0 0 84 8 5 8 85 8 6 8 86 8 0 0 8DasEingabealphabetdesAutomatenist Ende, 0, 1und Fehler(falscheZeichen).Listing5.4. BCD-Erkenner(automaten-bcd.c)1 /2 BCDErkenner vi a Automat3 /4 #i nc l ude 56 i nt bcd scanner ( char , i nt) ;7 i nt bcd par s er ( char ) ;89 i nt main ( ) {10 char i nput [ 2 5 5 ] ;1112 whi l e ( p r i nt f (BCDInput : ) , f g e t s ( i nput, 255 , s t di n )!=NULL)13 p r i nt f (%sOK! \ n , ( bcd par s er ( i nput ))? Ni cht : ) ;1415 p r i nt f (\n) ;16 ret urn 0;48 5 EndlicheAutomaten17 }1819 i nt bcd par s er ( char in) {20 i nt zust and =0;21 s t a t i c i nt pt ab l e[ 7 ] [ 4 ] ={ /0/ {7 , 1 , 4 , 8 } ,22 /1/ { 8 , 2 , 2 , 8 } ,23 /2/ { 8 , 3 , 3 , 8 } ,24 /3/ { 8 , 0 , 0 , 8 } ,25 /4/ { 8 , 5 , 8 , 8 } ,26 /5/ { 8 , 6 , 8 , 8 } ,27 /6/ { 8 , 0 , 0 , 8 } };28 bcd scanner ( in, 1 ) ; // ScannerReset29 while ( zustand >>

T

``T

E

''

E

E $

SDerParserverhaltsichnunfolgendermaen: WennaufTOSeinTerminalist: WennTOS=tokendannloscheTOSundliesweiter, andernfallsFEHLER! Andernfalls(TOSistNon-Terminal) WenninParser-Tabelle(TOS,token) Regel eingetragendannlosche TOSundlegeRegelr uckwartsaufStack andernfallsFEHLER! WiederholedieerstenzweiPunktebisStackundEingabeleersind.6.3 LL-Parsing 69Algorithmus6:LL-1-AlgorithmusmitStackverwaltungGegeben:PTABLE[TOS][token]LegeEnde-TokenaufStackLegeStartregelr uckwartsaufStackLiestokenerror=0EingabenichtleerANDerror=0

TOSistTerminalJa Nein

TOS=token?Ja Neinliestoken error=1

>>>>>>>>PTABLE[TOS][token]gesetzt?Ja NeinloscheTOSLegeRegelPTABLE[TOS][token]r uckwartsaufStackerror=1Voraussetzungf urdenAlgorithmusisteinelinksrekursionsfreieGrammatik.Anwendung von Algorithmus 4 zur Berechnung der FIRST-Mengen bzw. Algorithmus 5 zurBerechnungderFOLLOW-MengenaufGrammatik16ergibtFIRST(E) = {(, id}FIRST(E

) = {+, }FIRST(T) = {(, id}FIRST(T

) = {, }FIRST(F) = {(, id}FOLLOW(E) = {$, )}FOLLOW(E

)= {$, )}FOLLOW(T) = {+, $, )}FOLLOW(T

) = {+, $, )}FOLLOW(F) = {, +, $, )}Tabelle6.2zeigt,wietabellengesteuertCodeausgegebenwerdenkann.TerminaleSymbolewerden beim Weiterlesen ausgegeben, zu nicht-terminalen Symbolen kann in der Grammatikein Ausgabetext hinterlegt werden, welcher dann ausgegeben wird, wenn das Symbol auf demStackgeloschtwird(Algorithmus6).DieGrammatikmitAusgabeistin17dargestellt.Grammatik17:LinksrekurionsfreieTerm-GrammatikinBNFmitAusgabeS E$E TEE +TEADD | T FTT *FTMULT | F (E) | zahlDieKonstruktionderParse-Tabellenach[ASU88], Seite231istinAlgorithmus7darge-stellt.70 6 Keller-AutomatenTabelle6.1. Parsing-VorgangStapel Eingabe Aktion$E 1+2*3$E TE

$E

T 1+2*3$T FT

$E

T

F 1+2*3$F zahl$E

T

zahl 1+2*3$$E

T

+2*3$ T

$E

+2*3$ E

+TE

$E

T+ +2*3$$E

T 2*3$ T FT

$E

T

F 2*3$ T zahl$E

T

zahl 2*3$$E

T

*3$ T

FT

$E

T

F *3$$E

T

F 3$ F zahl$E

T

zahl 3$$E

T

$ T

$E

$ E

$ $Tabelle6.2. Parsing-VorgangmitCode-ErzeugungStapel Eingabe Aktion Ausgabe$E 1+2*3$E TE

$E

T 1+2*3$T FT

$E

T

F 1+2*3$F zahl$E

T

zahl 1+2*3$ 1$E

T

+2*3$ T

$E

+2*3$ E

+TE

$E

ADDT+ +2*3$$E

ADDT 2*3$ T FT

$E

ADDT

F 2*3$ T zahl$E

ADDT

zahl 2*3$ 2$E

ADDT

*3$ T

FT

$E

ADDT

MULTF *3$$E

ADDT

MULTF 3$ F zahl$E

ADDT

MULTzahl 3$ 3$E

ADDT

MULT$ T

MULT$E

ADD$ E

ADD$ $Algorithmus7:LL(1)-TabelleerstellenF urjederRegelA derGrammatkF urjedesTerminala FIRST(A)TrageA inM[A,a]ein

FIRST()?Ja NeinF urjedesTerminalb FOLLOW(A)TrageA inM[A,b]einBeispielGrammatik18inTabelle6.36.3 LL-Parsing 71Grammatik18:MathematischerTermlinksrekursionsfreiE TEE +TEE -TEE T FTT *FTT /FTT F (E)F idTabelle6.3. LL(1)-ParsetabelleTopof TokenStack END + - * / ( ) ZAHL ERRE TE TEE+te -te T FT FTT*FT /FT F (E) zahlListing6.3implementiertdenhiererlautertenParser.Listing6.3. LL(1)-ParsermitStackverwaltung(ll1-stack.c)1 /2 Tabe l l e nge s t e ue r t e r r e k u r s i o n s f r e i e r LL(1)Parser3Ahnl i ch Grammatik 4. 11 aus Drache 1 , Se i t e 214:4 Regel 0: S : : = E $5 Regel 1: E : : =TE6 Regel 2: E : : =+TE7 Regel 3: E : : =TE8 Regel 4: E : : = eps9 Regel 5: T : : = FT10 Regel 6: T : : = FT11 Regel 7: T : : = / FT12 Regel 8: T : : = eps13 Regel 9: F : : = ( E )14 Regel 10: F : : = zahl15 /16 #i nc l ude 17 #i nc l ude termscanner . h18 #i nc l ude termscanner . c19 #i nc l ude genprogs t ack . h20 #i nc l ude genprogs t ack . c2122 enum{nt E =256 , nt E2 , nt T , nt T2 , nt F} ; // NonTermi nal s23 i nt n t o f f s e t =256;2425 i nt par s e t abl e[ 5 ] [ 9 ] ={26 / END + / ( ) z ahl err /27 /E / { 1, 1, 1, 1, 1, 1 , 1, 1 , 1} ,28 /E / { 4 , 2 , 3 , 1, 1, 1, 4 , 1, 1},72 6 Keller-Automaten29 /T / { 1, 1, 1, 1, 1, 5 , 1, 5 , 1},30 /T / { 8 , 8 , 8 , 6 , 7 , 1, 8 , 1, 1} ,31 /F / { 1, 1, 1,1, 1, 9 , 1, 10 , 1} ,32 };3334 i nt g [ 1 1 ] [ 4 ] ={ // Grammatik35 /0/ { nt E , END, 1 } ,36 /1/ { nt T , nt E2 , 1 } ,37 /2/ { PLUS, nt T , nt E2 , 1 } ,38 /3/ { MINUS, nt T , nt E2 , 1 } ,39 /4/ {1 } ,40 /5/ {nt F , nt T2 , 1 } ,41 /6/ {MAL, nt F , nt T2 , 1 } ,42 /7/ {DIV, nt F , nt T2 , 1 } ,43 /8/ {1 } ,44 /9/ {KLA AUF, nt E , KLA ZU, 1 } ,45 /10/{ZAHL, 1 } ,46 };4748 s t ack s ;4950 voi d r e g e l a uf s t a c k ( i nt r ) {51 i nt i ;52 i =1;53 p r i nt f ( r e g e l %d\n , r ) ;54 whi l e ( i ++, g [ r ] [i ] >=0);55 f or ( i ; i >=0; i )56 s t ack pus h(&s , &(g [ r ] [i] ) ) ;57 }5859 voi d i nt pr i nt ( i nt i ) { // f ur s t ac k pr i nt Funkti on60 p r i nt f (%4d , i ) ;61 }6263 i nt main ( ) {64 char i nput[ ] = (1 2)2 +3;65 char t e x t[ 2 5 5 ] ;66 i nt token, er r or =0 , r , t os ;6768 s t a c k i n i t (&s , s i z e o f ( i nt ) , 100 , i n t p r i n t) ;69 t ermscanner ( i nput, NULL) ; // ScannerI ni t70 t oken =t ermscanner (NULL, t e x t) ;7172 r e g e l a u f s t a c k( 0) ; // St a r t r e g e l auf St ack73 whi l e ( ! er r or &&s t a c k h e i g h t (&s ) ) {74 i f ( s t ack pop(&s , &t os ) , t os < n t o f f s e t ) // Terminal !75 i f ( t os ==t oken )76 t oken =t ermscanner (NULL, t e x t) ;77 e l s e78 er r or =1;79 e l s e // NonTerminal80 i f ( ( r = p a r s e t a b l e [ t os n t o f f s e t ] [ t oken ] ) >=0)81 r e g e l a u f s t a c k ( r ) ;82 e l s e6.3 LL-Parsing 7383 er r or =1;84 }85 pr i nt f ( Parsee r ge bni s : %d\n , e r r or) ;86 s t a c k de l (&s ) ;87 r et ur n 0;88 }6.3.5EliminationderLinks-RekursionAlgorithmus8:EliminationderLinks-RekursionGegeben: A A1|A2| . . . |Am|1|2| . . . |n(KeinibeginntmitA)Verfahren:ErsetzeA A1|A2| . . . |Am|1|2| . . . |ndurchA 1A

|2A

| . . . |nA

undf ugehinzuA

1A

|2A

| . . . |mA

|Siehe[ASU88],Seite214.6.3.6Tabellen-gesteuertesLL-ParsingSieheauch[Wir96],Seite22.Am einfachsten basierend auf Syntaxgraphen der Regeln. F ur jede Pfeilspitze wird ein Vier-tupelangelegt: ArtdesKnotens(TerminaloderNon-Terminal), NrdesentsprechendenEintrags, Alternative,fallskeinMatch, Fortsetzung,fallsMatch.Damit kann der Recursive-Descent-Parser unabhangig von der konkreten Grammatik imple-mentiertwerden:Algorithmus9:Tabellen-gesteuertesLL-ParsingLL1-parser(knoten)solangeknoteng ultig

Terminal-Knotenundtoken=knoten?Ja Neintoken=scanner()knoten=nachfolger

Non-Terminal-Knotenundtoken FIRST(knoten)?Ja NeinLL1-parser(knoten)knoten=nachfolgerknoten = Nachste Alter-native74 6 Keller-AutomatenAls Nebeneekt der beschriebenenDatenstruktur f ur dieSyntaxdiagrammeerscheint dieTatsache,dassdieFIRST-Mengeneinfachberechnetwerdenkonnen.Listing6.4implemen-tierteinentabellengesteuertenLL(1)-Parser,derkomplettunabhangigvonderGrammatikcodiertist.Als Beispiel soll f ur die Term-Grammatik 15(Seite 66) ein Parser entwickelt werden. DazuwirdSyntax-Diagramm7entwickelt.Syntaxdiagramm7:Term-GrammatikS:E0

$1E:T2

+3

4T5

T:F6

7

/8F9

F:

zahl10

(11E12

)13

14 F15Tabelle6.4. ParstabellezutabellengesteuertemLL(1)-ParsenmitRekursionRegel Knoten Typ Wert Alt. Nachf. FIRSTS 0 NT 2 e 1 {zahl,(,+,-}1 T $ e xE 2 NT 6 e 3 {zahl,(,+,-}3 T + 4 54 T - x 55 NT 6 e 3T 6 NT 10 e 7 {zahl,(,+,-}7 T * 8 98 T / x 99 NT 10 e 7F 10 T zahl 11 x {zahl,(,+,-}11 T ( 14 1212 NT 2 e 1313 T ) e x14 T - e 1515 NT 10 e xListing6.4. TabellengesteuerterLL(1)-Parser(ll1-tabellarisch.c)1 /2 Tabe l l ar i s c h g e s t e ue r t e r LL(1)Parser3 ToDo: Fi r s t Mengen aus Tabel l e kons t r ui e r e n !4 /6.3 LL-Parsing 755 #i nc l ude termscanner . c6 #i nc l ude 78 i nt LL1 f i r s t ( node t abl e, i nt act node, i nt token ) {9 i nt f i r s t s e t[ 256] ={0} , nt [ 2 5 6 ] ={0} , i , ok =0;10 do{11 nt [ act node ] =1;12 whi l e ( act node >=0) {13 i f ( t a b l e [ act node] .t ype ==t er mi nal )14 f i r s t s e t[ t a b l e [ act node] . nr ] =1;15 e l s e i f ( t a b l e [ act node] .t ype ==nont ermi nal )16 i f ( nt [ t a b l e [ act node] . nr ] ==0)17 nt [ t a b l e [ act node] . nr ] =2; // Noch abar bei t en !18 act node = t a b l e [ act node] .a l t;19 }20 act node =1; // Jet z noch unbear bei t et NTRegel n suchen21 while (++act node =0) {24 f or ( i =0; i =0 &&! er r or ) {44 // p r i nt f ( act node =%d , t oken =%d\n , act node, t oken ) ;45 i f ( t a b l e [ act node] .t ype ==t er mi nal46 &&t a b l e [ act node] . nr ==t oken ) {47 act node = t a b l e [ act node] .next ;48 t oken =scanner ( t e x t) ;49 }50 e l s e i f ( t a b l e [ act node] .t ype ==nont ermi nal51 && ( 1 | |LL1 f i r s t ( t ab l e, act node, t oken ) ) ) {52 er r or =LL1 parser ( t ab l e, t a b l e [ act node] . nr , scanner ) ;53 act node = t a b l e [ act node] .next ;54 }55 e l s e {56 act node = t a b l e [ act node] .a l t;57 }58 }76 6 Keller-Automaten59 ret urn er r or | | ( act node ==1);60 }6.4LR-ParsingImGegensatzzumTop-Down-ParsingwirdbeimBottom-Up-Parsingversucht, ausgehendvondenBlatterneinesSyntaxbaumsdurchR uckwarts-AnwendungderProduktionsregelnderGrammatik(durchReduzieren),einenEingabetextaufdasStartsymbolzureduzieren.Handlssinddabei rechteSeiteneinerRegel.AhnlichwiebeimtabellengesteuertenLL(1)-Parsingm ussendieProduktionsregelndahereinfachaufgebautsein.BetrachtenwirGrammatik19(Beispielaus[ASU88]Seite267:Grammatik19:EinfacheTerm-GrammatikinBNF1)E E+T2)E T3)TT*F4)TF5)F (E)6)F zahlEinLR-KellerautomatkenntvierAktionen:Reduziere dasHandleamStackendeanhandeinerRegelSchiebe dasnachsteEingabeelementaufdenStackAkzeptiere dieEingabeFehler inderEingabeStack Input Aktion1 + 2 * 3 $s1 + 2 * 3 $ r6F + 2 * 3 $ r4T + 2 * 3 $ r2E + 2 * 3 $ sE + 2 * 3 $ sE + 2 * 3 $ r6E + F * 3 $ r4E + T * 3 $ s(!!!)E + T * 3 $ sE + T * 3$ r6E + T * F$ r3E + T $ r1E $ aInteressant ist der mit !!! markierte Zustand. Man hatte hier zwar das Handle T uber Regel2zuEreduzierenkonnen, daaberein*-ZeichenalsEingabeanliegtunddasHandleausRegel5mit T*beginntmachtessinn,aufdiesesHandlezusetzen.DieEntscheidung,welcheOperationdurchgef uhrtwird,hangtalsoeinerseitsvonmehrerenElementenamEndedesStacksundandererseitsvonderEingabeab.ZuerstsollderSyntaxbaumf urdenAusdruck1 + 2 3erstelltwerden:6.4 LR-Parsing 771j+ 2 * 31 + 2 * 3Fj1 + 2 * 3FTj1 + 2 * 3FTEj1 +j2 * 3FTEj1 +j2j* 3FTEj78 6 Keller-Automaten1 +j2 * 3FTEjFj1 +j2 * 3FTEjFTj1 +j2 *j3FTEjFTj1 +j2 *j3jFTEjFTj1 +j2 *j3FTEjFTjFj1 +j2 * 3FTEjFTFT````

j6.4 LR-Parsing 791 + 2 * 3FTEFTFT````

E

j1FTE+2FT*3F...

T..........

EDanundieSuchenachdemoptimalenHandlezeitaufwendigist, werdenParse-Tabellenentwickelt, die lediglich anhand des letzten Stack-Elements operieren konnen. Das ErstellendieserTabellen,dief urtypischeProgrammiersprachenwiePascaloderCmehrerehundertZeilen enthalten, ist in der Praxis zu aufwandig. Daher werden diese Tabellen von Compiler-generatorenerstellt.F ureinVerstandnisderCompilergeneratorenistabereinprinzipiellesVerstandnisdiesesVerfahrennotwendig.Tabelle6.5. LR-Tabellef urAusdr uckeZustand Aktion Sprungz + * ( ) $ E T F0 s5 s4 1 2 31 s6 a2 r2 s7 r2 r23 r4 r4 r4 r44 s5 s4 8 2 35 r6 r6 r6 r66 s5 s4 9 37 s5 s4 108 s6 s119 r1 s7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r580 6 Keller-AutomatenAlgorithmus10:LR-AlgorithmusLR-AlgorithmusGegeben:aktion-undsprung-Tabellestack-push(Zustand0);token=scanner();zustand=stack-tos()a=aktion[zustand][token]

a=shiftz2Ja Neinstack-push(token)stack-push(z2)token=scanner()

a=reduceAJa NeinLosche2||Stackelementez2=stack-tos()stack-push(A)stack-push(sprung[z2][A])solangeaktion =accept,aktion =errorWendet man nun Algorithmus 10 auf Tabelle 6.4 und die Eingabe 1 +2 3 an so ergibt sichderinTabelle6.6dargestellteParse-Vorgang:Tabelle6.6. LR-Parse-Vorgang1+2*3Stack Input Aktion0 1 + 2 * 3 $s50z5 + 2 * 3 $ r60F3 + 2 * 3 $ r40T2 + 2 * 3 $ r20E1 + 2 * 3 $ s60E1+6 2 * 3 $ s50E1+6z5 * 3 $ r60E1+6F3 * 3 $ r40E1+6T9 * 3 $ s70E1+6T9*7 3 $ s50E1+6T9*7z5 $ r60E1+6T9*7F10$ r30E1+6T9 $ r10E1 $ aListing6.5. LR-Parser(keller-lr-parser.c)1 /2 LRParser3 Zu Drache S 2674 /5 #i nc l ude termscanner . c6 #i nc l ude genprogs t ack . c78 char akt i on[ 1 2 ] [ 9 ] [ 4 ] ={9 / $ + / ( ) z ahl err10 / 0/ { er , er , er , er , er , s4 , er , s5 , er } ,6.4 LR-Parsing 8111 / 1/ {ac , s6 , s6 , er , er , er , er , er , er } ,12 / 2/ {r2 , r2 , r2 , s7 , s7 , er , r2 , er , er } ,13 / 3/ {r4 , r4 , r4 , r4 , r4 , er , r4 , er , er } ,14 / 4/ {er , er , er , er , er , s4 , er , s5 , er } ,15 / 5/ {r6 , r6 , r6 , r6 , r6 , er , r6 , er , er } ,16 / 6/ {er , er , er , er , er , s4 , er , s5 , er } ,17 / 7/ {er , er , er , er , er , s4 , er , s5 , er } ,18 / 8/ {er , s6 , s6 , er , er , er , s11 , er , er } ,19 / 9/ {r1 , r1 , r1 , s7 , s7 , er , r1 , er , er } ,20 /10/ {r3 , r3 , r3 , r3 , r3 , er , r3 , er , er } ,21 /11/ {r5 , r5 , r5 , r5 , r5 , er , r5 , er , er } };2223 i nt sprung [ 1 2 ] [ 3 ] ={ / 0/ { 1 , 2 , 3} ,24 / 1/ {1,1,1} ,25 / 2/ {1,1,1} ,26 / 3/ {1,1,1} ,27 / 4/ { 8 , 2 , 3} ,28 / 5/ {1,1,1} ,29 / 6/ {1, 9 , 3} ,30 / 7/ {1,1,10} ,31 / 8/ {1,1,1} ,32 / 9/ {1,1,1} ,33 /10/ {1,1,1} ,34 /11/ {1,1,1} };3536 enum{nt E , nt T , nt F} ;37 s t r uc t { i nt nt ; i nt l; } g [ 7 ] ={{1, 1} , // ni cht verwendet38 /R1/ {nt E , 3} ,39 /R2/ {nt E , 1} ,40 /R3/ {nt T , 3} ,41 /R4/ {nt T , 1} ,42 /R5/ {nt F , 3} ,43 /R6/ {nt F , 1} };4445 voi d i nt pr i nt ( voi d p) { // F ur StackProgramme46 p r i nt f (%d , ( i nt ) p ) ;47 }4849 i nt main ( ) {50 i nt token, i, r , t os, a , dummy, z2 ;51 char t o s can[ ] =1 2 +3 , t e x t[ 1 0 ] ;52 s t ack s ;5354 s t a c k i n i t (&s , s i z e o f ( i nt ) , 100 , i n t p r i n t) ;55 dummy =0 , s t ack pus h(&s , &dummy) ;5657 t ermscanner ( t o scan, NULL) ;58 t oken =t ermscanner (NULL, t e x t) ;5960 do {61 s t a c k t o s (&s , &t os ) ;62 p r i nt f ( t os =%2d t oken =%d akt i on =%s \n ,63 t os, token, akt i on [ t os] [ t oken ] ) ;64 a =akt i on [ t os] [ t oken] [ 0 ] ;82 6 Keller-Automaten65 r = at oi ( akt i on [ t os] [ t oken ] +1);66 i f ( a == s ) { // Schi ebe67 s t ack pus h(&s , &t oken ) ;68 s t ack pus h(&s , &r ) ;69 t oken =t ermscanner (NULL, t e x t) ;70 }71 el se i f ( a == r ) { // Reduzi ere72 f or ( i =0; i token, p>t e x t) ;28 }293031 i nt main ( ) {32 char i nput[ ] =(1 +2) 3 , t e x t[ 1 0 0 ] ;33 s t ack s ;34 s t ack el em next, t os, el em ;35 i nt er r or ;3637 s t a c k i n i t (&s , s i z e o f ( s t ack el em ) , 15 , t ok e n pr i nt ) ;3839 t ermscanner ( i nput, NULL) ;40 next . t oken =t ermscanner (NULL, next . t e x t) ;4142 er r or =0;43 t os . t oken =0 , t os . t e x t[ 0 ] = \0 , s t ack pus h(&s , &t os ) ;44 // s t a c k p r i nt (&s ) ;45 whi l e ( ! er r or &&( ( s t a c k t o s (&s , &t os ) , t os . t oken !=END) ) | | next . t oken !=END) {46 p r i nt f (TOS: %d (\%s \) , t os . token, t os . t e x t) ;47 p r i nt f ( i nput : %d (\%s \)\n , next . token, next . t e x t) ;48 i f ( p r i o r i t y[ t os . t oken ] [ next . t oken ] == 1 | | p r i o r i t y[ t os . t oken ] [next . t oken ] ==0) {49 s t ack pus h(&s , &next ) ;50 next . t oken =t ermscanner (NULL, next . t e x t) ;51 p r i nt f (\ t push \n) ;52 // s t a c k p r i nt (&s ) ;53 }54 el se i f ( pr i o r i t y[ t os . token] [next . token ] ==+1) {55 do {56 s t ack pop(&s , &el em ) ;57 p r i nt f (\ t pop %d (\%s \)\n , el em . token, el em . t e x t) ;58 } while ( s t ac k t os (&s , &t os ) , p r i o r i t y[ t os . token] [ elem . token ] !=1);5960 }61 el se62 e r r or =1;88 6 Keller-Automaten63 f f l u s h ( st dout ) ;6465 }6667 r et ur n 0;68 }7Symboltabellen Problem:VerwendungvonBezeichnernnicht uberGrammatikkontrollierbar. Beispiel: ! a. Grammatik,dieBezeichnernamenbeinhaltet,warezukomplex Abhilfe:Symboltabelle ErsetztalleBezeichnerdurchint-Werte WegenRekursionzur Compilezeit aber nochkeine Errechnung eines HS-PLatzesmoglich F urjedenBezeichneristeinTripelzuverwalten: Level-DeltaimstatischenCode Oset,laufendeNrimjeweiligenLevel TypdesBezeichnersErsetzeninProgramm9.1(Seite104)alleBezeichnerdurchTyp/Level/Oset7.1Einf uhrungWichtigbeiderDiskussionderSymboltabellesindBegriewie NamensbereichevonBezeichnern(CT) LokaleundglobaleBezeichner LebenszeiteinesBezeichners(RT)7.2MethodenderSymboltabelleEineSymboltabellehatprinzipielldiefolgendenvierMethoden: Einf ugenvonneuenBezeichnern:insert SuchenvonBezeichnern:lookup BetreteneinesneuenNamensbereichs:level-up VerlasseneinesNamensbereichs:level-down90 7 Symboltabellen7.3AufbaueinesSymboltabelleVorstellung: Die Symboltabelle ist eine zweidimensionale Tabelle, die in der einen DimensiondieSymboleundinderanderenDimensiondieNamensbereicheverwaltet.PraktischwirdmaneineSymboltabellesonichtcodieren, daf uralleNamensbereicheeinefestefestemaximaleZahlvonBezeichnern.DieTabellebeinhaltet NameundTypeinesBezeichners. DiewichtigenWerteLevel undOsetergebensichausderPositioneinesBezeichnersinderSymboltabelle.Abb. 7.1. AufbaueinerSymboltabelle43210Level *Ebene0 Ebene1 Ebene2 Ebene3In Zeile 2 von Listing 9.1 werden die Variablen a und d lokal im Hauptprogramm deklariert,inZeile4kommtdieProzedurfdazu.DieSymboltabellehatnunfolgendesAussehen:432 f proc1 d var0 a varLevel *Ebene0 Ebene1 Ebene2 Ebene3In Zeile 4 wird ein neuer Namensbereich betreten, in Zeile 5 die Variablen b und d deklariertundinZeile7dieProzedurglokalzufdeklariert:432 f proc g proc2 d var d var0 a var b varLevel Ebene0 *Ebene1 Ebene2 Ebene3InZeile 7wirddanneinneuer Namensraumbetretenundlokal die Variablenc undddeklariert:432 f proc g proc1 d var d var d var0 a var b var c varLevel Ebene0 Ebene1 *Ebene2 Ebene3BeidenVariablenzugrienindenZeilen10bis14ergibtsichnunf uradasBitupel(Level2,Oset0),f urcdasBitupel(Level0,Oset0)undf urddasBitupel(Level0,Oset1).WirdbeiderCompilierungZeile17erreicht,sosihtdieSymboltabellewiederauswienachErreichendesNamensraumsvonProzedurf. F uraergibtsichjetztdasBitupel (Level 1,Oset0),f urbdasBitupel(Level0Oset0),f urdergibtsich(Level0,Oset1)undf urg(wasjaeineProzedurist!)(Level0,Oset2).7.6 EineSymboltabelleaufBasisderC++-STL-Map 917.4FehlermoglichkeitenInsert: KeinSpeicherplatzmehrvorhanden BezeichnernamenimaktuellenLevelbereitseingetragenLookup: Bezeichnernichtvorhanden BezeichnerfalscherTypLevel-Up: KeinSpeicherplatzmehrLevel-Down: BereitsinLevel07.5Namens-SucheBei derSymboltabelleistdieschnelleSuchenachStringsnotig. Bei kleinenProgrammen,die ubersetztwerden, isteineinfacherString-Vergleichproblemlos. Kritischwirdesaber,wennetwamit einemC-Compiler einganzes Betriebssystemmit mehrerenzehntausendZeilenQuellcodecompiliertwerdenmuss.IneinemsolchenFallmussderText-SucheinderSymboltabellebesondereBedeutungzugemessenwerden.MoglichkeitenzurBeschleunigungwaren Hash-Verfahren SortierteIndex-Felderf urbinareSuche DynamischeGenerierungendlicherAutomatenzurIndexierung7.6EineSymboltabelleaufBasisderC++-STL-MapDieSymboltabellewirdauseinemArrayausMaps(sieheC++-STL)aufgebaut.DasArraybildet die verschiedenen Level der Symboltabelle ab. Die einzelnen Maps - die aus Key-Value-Paarenaufgebautsind-habenalsZugris-KeydenNamendesSymbolsundalsValuedasTupel {Eintragsart; LaufendeNr.}. DiejeweiligeaktuelleHohederSpaltenwirdineinemArrayheightgespeichert.UberdieMaps- dieintern uberB-Baumerealisiertsind- sindnunezienteString-Suchenmoglich.ListingA.7zeigtdieKlassendeklaration,ListingA.6denCodederKlasse.8ZwischencodeBetrachten wir wieder einmal Abbildung 1.1 auf Seite 13. Im Frontend des Compilers ben-densichScannerundParser,imBackenddie(nochzubehandelnde)Codeerzeugung.Bei kleinen Compilern wird die Code-Generierung gerne direkt in den Parser integriert, diesspartArbeitundmachtdengesamtenCodedesCompilerskompakt. EsgibtabereinigeguteGr unde, warumder Parse-Vorgang(das Frontend) vonder Code-Generierung(demBackend)getrenntwerdensollte: Soll nicht nur ein einzelner, isolierter Compiler erstellt werden, sondern eine ganzeCompiler-CollectionwieetwadieGCC, som usstenf ur nQuellsprachenundmZiel-systeme (n m) verschiedene Compiler erstellt werden. Abbildung 8.1 zeigt diesen Sach-verhalt.WirdstattderdirektenIntegrationvonFront-undBackendaberzwischendiesenMo-duleneinesauberdenierteundvorallemf uralleQuellsprachenundZielsystemeein-heitliche Schnittstelle verwendet, so reduziert sich der Aufwand auf die Erstellung von nFrontendsundmBackends.DieswirdinAbbildung8.2dargestellt.Anderungen in der Vorgehensweise des Compilers ziehen viele Vreanderungen nach sich.SoistesinderRegelnichteinfachmoglich,einenRecursive-Descent-ParserdurcheinenBottom-Up-Parserzuersetzen.DiesresultiertausderTatsache,dassdieGrammatikenmeist f urbestimmteParse-Technikenangepasst werdenm ussen. SohabenwirbereitsverschiedeneGrammtikenf urarithmetischeTermekennengelernt, etwaGrammatik12(Seite28)oderGrammatik18(Seite71).Aus diesen Gr unden wird die Codeerzeugung vom Parser getrennt und ein sog. ZwischencodealsSchnittstellezwischenFront-undBackendeingesetzt.8.1Einf uhrungLeider existiert f ur den Zwischencode nicht eine so schone Theorie wie die der Formalen Spra-chen oder der Automatentheorie, diese Theorien hatten die lexikalische und die syntaktischeAnalyse einfach werden lassen. Stattdessen muss eine allgemeine Schnittstelle gefunden wer-den. BeimBetrachtenvonAbbildung8.2wirdklar, dassdieseSchnittstellesowohl C- alsauchFortran-,Pascal-undweitereProgrammeabbildenkonnenmuss.InderPraxisistZwischencodehaug einZielsystem-unabhangigerPseudo-Assembler-Code f urRegister-Stack-Maschinen f urZwei-Adress-Maschinen94 8 ZwischencodeAbb. 8.1. Compiler-CollectionohneSchnittstelleFortranPascalCARMInterpreterMotorola68kIntelx86

>>>>>>>>>>>>

>>>>>>>>>>>>``````````````````

Abb. 8.2. Compiler-CollectionmitSchnittstelleFortranPascalCARMInterpreterMotorola68kIntelx869867Zwischen-Code

`````` ...

`````````- f urDrei-Adress-Maschinen einSyntaxbaumSyntax-BaumesindmitSicherheitdiebeste, aberauchdieschwierigsteVariantevonZwi-schencodes. Bei Syntax-Baumenist es sehr wichtig, dass sie die Sprache abbildenundnichtdieGrammatik.AndernfallswareeinAustauschdesParserswieobendiskutiertnichtmoglich.DarausresultiertdieNamensgebung AbstrakterSyntaxbaum.8.2ASTf urTermeGewahltwirdnichtderSyntaxbaumderGrammatik,sondernderRechenbaum(Operator-baum).DieRegelnzumErstelleneinesSyntaxbaumssinddiefolgenden:8.2 ASTf urTerme 95 Es ist bzgl. Operatorprioritat und -assoziativitat der schwachste Operator zu suchen undoben im Baum einzutragen. F ur jeden Operanden wird ein AST nach unten1gezeichnet. F urjedenOperandenwird dieseramEndedesAstseingetragen,fallsderOperandeineZahlist, einTeilbaumgezeichnet,fallsderOperandeinTeilausdruckist.Als Beispiel soll der Syntaxbaum f ur den Ausdruck 1 +2 3 erstellt werden: Der schwachsteOperator ist der +-Operator. Der linkeOperandist dieZahl 1, der rechteOperandderTeilausdruck2 3. DadiesernurnocheinenOperatorenthaltistdieErstellungdesent-sprechendenTeilbaumstrivial. DergesamteSyntaxbaumistinAbbildung8.3dargestellt.Abb. 8.3. Syntaxbaumf urTerm1 + 2 312 3``...``+In diesen Syntaxbaumen sind keine Klammern mehr vorhanden. Diese werden uber die FormdesSyntaxbaumsabgebildet.HateinCompilereinenSyntaxbaumerstellt, sokannineinenzweitenSchrittdieserabge-arbeitetwerden. Durchlauft man den Baum im Inorder-Verfahren unter Ber ucksichtigung der verschiede-nenOperatorensokanndasErgebnisdesTermserrechnetwerden. AnalogkanndurchdasInorder-VerfahrenauchDrei-Address-Codeerzeugtwerden. Durchlauft man den Baum im Postorder-Verfahren so kann die UPN-Syntax ausgegebenwerden.DaOperatorenzweiOperandenhaben(mitderAusnahmederunarenVorzeichen,dienureinenOperandenhaben),bietetsicheinedynamischeDatenstrukturf urdieAbbildungdesBaumsan.Abb. 8.4. Datenstrukturf urbinarenOperator-Baum

-```Textlrt ypedef s t r uc t s node as t ;t ypedef s t r uc t s node as t node ;s t r uc t s node {char t e x t[ 1 0 ] ;as t l;as t r ;} ;1InderInformatikstehenBaumeimmeraufdemKopf!96 8 ZwischencodeImTextwirdentwederderZahlenwertoderaberderOperatoralsASCII-Textgespeichert,wobeif urdasunareMinusderText CHS(Change-sign)eingesetztwird.IndenBlatt-knoten sind l- und r-Zeiger auf NULL gesetzt, beim unaren Minus ist nur der l-Zeiger gesetzt.Diese Datenstruktur ist als struct nodeinListing8.1deniert. Der Code ndet sichinListing8.2.Listing8.1. DenitionsdateizumOperator-Baum(ast/term-ast.h)1 /2 HeaderDatei zumSyntaxbaum3 /4 #i f nde f TERMTREEH5 #de f i ne TERMTREEH 16 t ypedef s t r uc t s node as t ;7 t ypedef s t r uc t s node as t node ;8 s t r uc t s node {9 char t e x t[ 1 0 ] ;10 as t l;11 as t r ;12 } ;13 // Prototypen14 voi d t r e e out put ( as t , i nt) ;15 voi d t r e e f r e e ( as t ) ;16 voi d t r e e c ode ( as t ) ;17 doubl e t r e e r e s u l t ( as t ) ;18 as t newnode ( char , ast, as t ) ;1920 #e ndi fListing8.2. Programm-CodezumOperator-Baum(ast/term-ast.c)1 /2 Syntaxbaum Bi bl i ot he k3 /4 #i nc l ude 5 #i nc l ude 6 #i nc l ude 7 #i nc l ude termas t . h89 voi d t r e e out put ( as t p , i nt n) {10 // BaumTraversi erung Fi rs t Order11 i f ( p !=NULL) {12 p r i nt f (%s , +142n ) ;13 p r i nt f (%s \n , p>t e x t) ;14 t r e e out put ( p>l , n+1);15 t r e e out put ( p>r , n+1);16 }17 }1819 voi d t r e e c ode ( as t p) {20 // BaumTraversi erung PostOrder i n UPN21 i f ( p !=NULL) {22 t r e e c ode ( p>l) ;23 t r e e c ode ( p>r ) ;24 p r i nt f (%s \n , p>t e x t) ;8.2 ASTf urTerme 9725 }26 }2728 doubl e t r e e r e s u l t ( as t p) {29 doubl e erg ;30 s wi t ch ( p>t e x t[ 0 ] ) {31 case + : erg = t r e e r e s u l t ( p>l ) + t r e e r e s u l t ( p>r ) ; break ;32 case : erg = t r e e r e s u l t ( p>l ) t r e e r e s u l t ( p>r ) ; break ;33 case : erg = t r e e r e s u l t ( p>l ) t r e e r e s u l t ( p>r ) ; break ;34 case / : erg = t r e e r e s u l t ( p>l ) / t r e e r e s u l t ( p>r ) ; break ;35 case C : erg = t r e e r e s u l t ( p>l) ; break ; // ChangeSi gn36 d e f a u l t : erg = at of ( p>t e x t) ; // Zahl37 }38 r et ur n erg ;39 }4041 as t newnode ( char t , as t l , as t r ) {42 as t p =( as t ) mal l oc ( s i z e o f ( as t node ) ) ;43 i f ( p !=NULL) {44 p>l =l , p>r =r ;45 s t r c py ( p>t ext , t ) ;46 }47 r et ur n p ;48 }4950 voi d t r e e f r e e ( as t p) { // Baum l os chen51 i f ( p !=NULL) {52 t r e e f r e e ( p>l) ;53 t r e e f r e e ( p>r ) ;54 f r e e ( p ) ;55 }56 }EinCompiler,derineinemerstenSchrittdenOperator-Baumerstelltunddiesenanschlie-endmehrfachverarbeitenlasstndetsichinListing??.Listing8.3. CompilerzurOperator-Baum-Erstellung(ast/term-treegen.c)1 /2 RDParser f ur Terme3 Baut bi naren OperatorSyntaxbaum aus TermAusdruck4 /5 #i nc l ude 6 #i nc l ude termas t . h7 #i nc l ude termscanner . h89 // Prototypen10 voi d scanner ( ) ;11 as t f s t a r t( ) ;12 as t f f a c t o r( ) ;13 as t f e xpr e s s i o n( ) ;14 as t f t er m ( ) ;1516 // Gl obal e Daten17 char zahl[ 2 0 ] ;98 8 Zwischencode18 i nt token, e r r or ;1920 // Hauptprogramm21 i nt main ( ) {22 char t e x t[ 1 0 0 ] ;23 as t s ;2425 whi l e ( p r i nt f ( Input : ) , f g e t s ( t ext, 255 , s t di n )!=NULL) {26 t ermscanner ( t ext , NULL) ; // ScannerReset27 s = f s t a r t( ) ;28 i f ( ! er r or ) {29 p r i nt f ( Syntaxbaum: \ n) ;30 t r e e out put ( s , 0) ;31 p r i nt f (UPNCodeausgabe\n) ;32 t r e e c ode ( s ) ;33 p r i nt f ( Ergebni s : %l f \n , t r e e r e s u l t ( s ) ) ;34 }35 el se36 pr i nt f ( Syntax ni cht OK, e r r or=%d\a\n , e r r or) ;37 t r e e f r e e ( s ) ;38 }39 r et ur n 0;40 }4142 // Funkti onen4344 voi d scanner ( ) {45 t oken =t ermscanner (NULL, z ahl ) ;46 }4748 as t f f a c t o r ( ) {49 as t p ;50 i f ( t oken ==PLUS) {51 scanner ( ) ;52 p = f f a c t o r( ) ;53 }54 el se i f ( token ==MINUS) {55 scanner ( ) ;56 p =newnode (CHS , f f a c t o r ( ) , NULL) ;57 }58 el se i f ( token ==ZAHL) {59 p =newnode ( zahl , NULL, NULL) ;60 scanner ( ) ;61 }62 el se i f ( token ==KLA AUF) {63 scanner ( ) ;64 p = f e x p r e s s i o n( ) ;65 i f ( t oken ==KLA ZU)66 scanner ( ) ;67 e l s e68 er r or =1;69 }70 el se e r r or =2;71 r et ur n p ;8.3 ASTf urPL/0 9972 }7374 as t f t er m ( ) {75 as t p , p2 ;76 char t x t;77 p = f f a c t o r( ) ;78 whi l e ( t oken ==MAL| | t oken ==DIV) {79 t x t =( t oken ==MAL) ? : /;80 scanner ( ) ;81 p =newnode ( t xt , p , f f a c t o r( ) ) ;82 }83 r et ur n p ;84 }8586 as t f e xpr e s s i o n ( ) {87 as t p , p2 ;88 i nt t oken2 ;89 p =f t er m ( ) ;90 whi l e ( t oken ==PLUS | | t oken ==MINUS) {91 t oken2 =t oken ;92 scanner ( ) ;93 p =newnode ( ( t oken2 ==PLUS) ? + : , p , f t er m ( ) ) ;94 }95 r et ur n p ;96 }9798 as t f s t a r t( ) {99 scanner ( ) , er r or =0;100 as t p = f e x p r e s s i o n( ) ;101 i f ( t oken !=END)102 er r or =3;103 ret urn p ;104 }8.3ASTf urPL/0MehrereKnoten-Arten: Block-Knoten ZweigeraufVar-Knoten Var-Knoten ZweigeraufVar-Knoten statement-Knoten ZweigeraufStatement-Knoten Expression-KnotenanaolgzuarithmetischenTermen ZweigeraufExpression-KnotenAbbildung8.5zeigtdenSyntaxbaumf urdasGGT-Programm(Listing2.2),Seite16).Der Syntaxbaumsolltebereits dieLevel-Oset-Werteder Symboltabelleenthalten, dannwirddiespatereWeiterverarbeitungeinfacher.100 8 ZwischencodeAbb. 8.5. ASTf urPL/0-Programmggt.pl0Blockggtvaravarbvargblockggtstmtwhile expr#``expridaexpridbstmtif expr>``expridaexpridbstmta:= expr-``expridaexpridbstmtif expr>``expridbexpridastmta:= expr-``expridbexpridastmt?astmt?bstmtCggtstmt!a expridgenum{cmdend , cmd wri te, cmd read , cmd assi gn, cmd i f, cmd whi l e } ;s t r uc t as t node {i nt t ype ; // Bef ehli nt s t l; // Level der Symb ol t ab e l l e f ur as s i gn und readi nt s t o ; // Of f s e t der Symb ol t ab e l l e f ur as s i gn und reads t r uc t as t node next ; // Nachst er Bef ehls t r uc t as t node cond ; // Abhangi ge Ket t e f ur i f und whi l e} ;8.4Neu-8.4.1DieKnotenartenBefehlsknoten Eingabe Ausgabe Funktionsaufruf BedingterSprung UnbedingterSprung Sprungziel ZielderZuweisung(Symboltabellen-Informationen,zweiInt) WertderZuweisungEXPR-Zeiger8.4 Neu- 101 NrderFunktion(Symboltabellen-Informationen,zweiInt) NamederFunktionString ZielderEingabe(Symboltabellen-Informationen,zweiInt) WertderZuweisungEXPR-Zeiger Sprungziel(EineindeutigeintoderLabel= WertderBedingungEXPR-Zeiger Sprungziel(EineindeutigeintoderLabel) Sprungziel(EineindeutigeintoderLabel)Die Srtuktur der Knoten kann entweder als C-Struktur (Vereinigungsmenge aller Statement-knoten)oderalsC++-Klasse(perVererbung)realisiertwerden.Code-Erzeugungvoi d c adr var ( i nt s t l , i nt sto, char name) {i nt i ;emi t ( s e t I31 , P0 [ 0 ] #Adr Var + s t r i ng (name) +: Sym+ s t r i ng ( i t oa ( s t l ))+/+s t r i ng ( i t oa ( s t o ) ) ) ;f or ( i =0; i < s t l; i ++)emi t ( s e t I31 , P0[ I31 ] ) ;emi t ( sub I31 , + s t r i ng ( i t oa ( s t o +2)));}orthandAusdruck-KnotenAusdruck-KnotenenthalteneinederdreiMoglichkeiten: Operator(innererKnoten) Konstante(Blattknoten) Variable(Blattknoten)Programmstruktur-KnotenVARa ;BEGIN? a ;IF a 0, bungeradeListing10.1. KekursivesPotenzierennachLagrange(ueb-lagrange.c)1 #i nc l ude 23 i nt l agr ange pot enz ( i nt a , i nt b) {4 i nt p ;5 i f ( b ==0)6 p =1;7 e l s e i f ( b %2 ==0) // b >0 und gerade8 p = l agr ange pot enz ( a , b / 2) , p=p ;9 e l s e // b >0 und ungerade10 p = l agr ange pot enz ( a , ( b1) / 2) , p= ( a p ) ;11 ret urn p ;12 }1314 i nt main ( ) {15 i nt bas i s, exponent ;16 p r i nt f ( Gib Basi s und Exponent ei n : ) ;17 s canf (%d%d , &bas i s, &exponent ) ;18 p r i nt f (%d %d =%d\n , bas i s, exponent, l agr ange pot enz ( bas i s, exponent ) ) ;19 ret urn 0;20 }10.4 OptimierungdesSpeicherzugris 115

v0FlugbahnshDiephysikalischenFormelnlauten:h=(v0sin)22gs=v20sin2g Wird die Quadrierung uber die Potenzierung abgebildet so wird uber Logarithmen lang-samgerechnet. WirddieQuadrierung uberMultiplizierungabgebildetsom usseninsgesamtdreiMulti-plikationendurchgef uhrtwerdenundsin()musszweimalberechnetwerden.DieBerechnungvonhgehtamschnellsten ubereinetemporareVariable:temp := v0 * sin(alpha);h = temp * temp / (2 * g);Auf dieseWeisewerdennurzwei Multiplpikationenbenotigtundsin()mussnureinmalberechnetwerden.10.4OptimierungdesSpeicherzugrisRAM/Register/HEAP/Stack11Code-ErzeugungAmEnde einer Comilierungsphase muss der ASTinirgendeiner Formineine Ausgabegebracht werden. Dies geschieht in der sog. Code-Erzeugung (siehe auch Abbildung 1.1 Seiteg phasen compiler). Wir werden drei grundsatzlich verschiedene Arten der Code-Erzeugungdiskutieren: DirekteInterpretierungdesAST ErzeugungvonAssembler-Code ErzeugungeineranderenHochspracheNat urlichwarennochweitereArtenderVerarbeitungmoglich,etwaErzeugungvonCross-ReferenzTabelleno.a.11.1InterpretierungSprachendiekeinerlei Spr ungekennen, konnendirektwahrenddesParse-Vorgangsinter-pretiertwerden.EntferntmanausderPL/0-Grammatik(Grammatik1Seite15)ausderBlock-Regel die Prozedur-Deklaration sowie die BefehleIF undWHILE so entsteht ein linearablaufendesProgramm.11.2Assembler-ErzeugungDerzuerzeugendeAssemblerwurdebereitsinKapitel??vorgestellt.SollAssembler-oderMaschinencodeerzeuigtwerden,somusszwischenzweigrundsatzlichverschiedenenZiel-Sprachenunterschiedenwerden: SprachenmitsymbolischenSprungzielLOADR0JMPLTLABEL AREADLABEL ANOPWRITE SprachenmitnumerischemSprungziel0000 LOADR00001 JMPLT0003118 11 Code-Erzeugung0002 READ0003 NOP0004 WRITEDas Problem entsteht bei den Vorwarts-Spr ungen des JMPLT-Befehls. Wenn die Zielsprachesymbolische Sprungziele unterst utzt sind Vorwarts-Spr unge einfach zu generieren. Die Code-Ausgabe erzeigt eineindeutiges Sprungziel (einsog. Label) - etwadurchErhoheneinesglobalenZahlers-underzeugtdiezeiCode-ZeilenmitSprungundSprungziel.Wesentlichschwierigerwirddiesbei numerischenSprungzielen, alsoderkonkretenZeilen-nummmer.DadieZahlderCode-Zeilen,die ubersprungenwerdensollen,nichtbekanntist,bleibtnur, dieSprunganweisungzweimal auszugeben. Zumerstenmal miteinemvorlau-gen(falschen!!!!)Sprungziel. ErstwenndannspaterdasSprungziel bekanntist, kanndasSprungzieldererstenAusgabekorrigiertwerden.R uckwarts-Spr ungesindeinfacherzugenerieren.BeisymbolischenSprungzielenwirdeben-falls ein Label generiert und spater beim JUMP referenziert. M ussen Sprungziele numerischangegebenwerdensohilfteineMerk-Variable.11.2.1DerEmitteri nt emi t ( i nt nr, commandcode cmd, i nt arg, char comment ) ;Ist die ubergebene Zeilen-Nummer _nr negativ, so wird an das Ende der Ausgabe angehangtunddieNummerderausgegebenenZeilezur uckgegeben.ImanderenFall-beieinerZeilen-Nummer 0 wird in genau diese Zeile ausgegeben. Damit kann bei numerischen Sprungzie-lendiespatereKorrektureinesSprungseinfacherfolgen.11.2.2Ausdr uckeAusdr ucke werden wie schon behandelt (bei Register-Stack-Masachinen) in UPN umgesetzt.11.2.3if-StatementDerCode if () mufolgendermaenumgesetztwerden:if a > 0 thenb := 1;01 LOADV a02 LOADC 003 CMPGT04 JUMPZ 0705 LOADC 106 STOREV 207 NOP1 void f i f( ) {2 match( t i f , e i f r e q) ; // Li es wei t er3 f c o ndi t i o n( ) ; // CodeAusgabe der Bedingung4 match( t then, e t he n r e q) ; // Li es wei t er5 l nr 1 =emi t ( 1, cmdJMPZ, 0 , ) ; // Spr ungz i el f a l s c h! !6 f s t at e me nt( ) ;7 l nr 2 =emi t ( 1, cmdNOP, 0 , Spr ungzi el ) ;8 emi t ( l nr1, cmdJMPZ, l nr, ) ; // Spr ungz i el r i c h t i g9 }11.3 Schleifen 119Abb. 11.1. AblaufplanEinfacheVerzweigungAblaufplanifhAAusdruck

```

```Nein JaJUMPZBlockNOPhB11.2.4if-else-StatementAbb. 11.2. AblaufplanVerzweigungmitAlternativeAblaufplanif-elsehAAusdruck

```

```Nein JaJUMPZif-Blockelse-BlockNOPhB11.3SchleifenDer Code while ( ) mu folgendermaen umgesetzt werden:120 11 Code-ErzeugungAbb. 11.3. AblaufplankopfgesteuerteschleifeAblaufplanwhile-StatementhANOPAusdruck

```

```Nein JaJUMPZBlockNOPhB11.4VariablenzugriWirddynamischeSpeicherverwaltungeingesetztsoistderVariablenzugrirelativkompli-ziert,dadieAdresseeinerVariablenerstzurRuntimeerrechnetwerdenkann.JenachdemwiekompliziertderCodeistundabhangigdavon,wieeinfachinderZielspracheeinUnter-programmaufrufistbietensichzweiMoglichkeitenan: DerCodekann ubereinUnterprogramminderCodeausgabef urjedenVariablenzugrigeneriertwerden DerCodekann ubereinUnterprogramminderZielspracheeinmaliggeneriertwerden,diesesUnterprogrammwirdnun ubereinenFunktionsaufrufinderZielspracheaufgeru-fen.ImBeispiel-AssemblerderVorlesungistderFunktionsaufruf mitzwei Parameternminde-stenssokompliziertwiediedirekteCode-Ausgabe, diesebestehtminimal - abhangigvonder-InformationderSymboltabelle-ausf unf Assemblerbefehlen. Listing11.1zeigtdenZugri.Listing11.1. Codeerzeugungf urVariablenzugri1 voi d c adr var ( i nt s t l , i nt sto, char name) {2 i nt i ;3 char comment [ 2 5 5 ] ;4 s p r i n t f ( comment , Adr Var %s : Sym%d/%d , name , s t l , s t o ) ;5 emi t (1, cmd LOADR, 0 , comment ) ;6 f or ( i =0; i < s t l; i ++)7 emi t (1, cmdLOADS, 0 , ) ;8 emi t (1, cmd LOADC, 2 , Of f s e t wegen SL/DL/RS) ; // Of f s e t anpassen9 emi t (1, cmdSUB, 0 , ) ;10 emi t (1, cmd LOADC, st o, SymtabOf f s e t ) ;11 emi t (1, cmdSUB, 0 , ADRVAR) ;11.6 Spr unge 12112 }NachAbarbeitungdesvonListing11.1erzeugtenCodesliegtdieAdressederVariablenaufdemStack, danachkannmitLOADSderWerrderVariablenaufdenStackgeladenwerdenbzw. mit STORES der (vorher errechnete und damit unter der Adresse auf dem Stack liegende)Wertgespeichertwerden.11.5Funktionsaufruf DerSpeicherbedarfdesStack-Segmentsmussermitteltwerden NeuerDL:=AlterTOS NeuerSL:=AlterTOSundmalentlangderSL-Kettegehen EvtlR ucksprung-AdresseaufStacklegen TOSerhohen11.6Spr ungeBeiderCodeerzeugungm ussenSpr ungeindieAusgabeeingebautwerden.Nunmussmanunterscheiden, obdieSprungzielewieineinem ublichenAssemlersymbolischseinkonnenoderobbereitseineZeilennummeralsSprungzielangegebenwerdenmuss.SokonntederAssemblercodef ureineeinfacheVerzweigungIF a < 0 THENa := -a;analogAbbildung11.1folgfendermaenaussehen:LOADV aLOADC 0CMTLTJUMPZ LBL_1LOADV aCHSSTOREV aLBL_1 NOPDurcheinefortlaufendeNumerierungderLabels(numerischoderalphabetisch)istdieCo-deerzeugungeinfachzubewerkstelligen.void f_if() {int label = get_next_label();match(t_if);f_expression();printf(" JUMPZ LBL_%d\n", label);match(t_then);f_statement();printf("LBL_%d NOP\n");}122 11 Code-ErzeugungDieCodeausgabef ureineVerzweigungbestehtalsonurauseinembedingtenSprungundeinemSprungziel.DasSchachtelnvonVerzweigungenundSchleifeninderQuellspracheistunkritisch,dadieVariablelabelinobigemCodefragmentlokalist.Anders sieht es aus, wennkeine symbolischenSprungziele erlaubt sind, sondernbereitsZeilennummernalsSprungzielangegebenwerdenm ussen.DerAssemblercodesiehtindannbeispielhaftwiefolgtaus:0000 LOADV a0001 LOADC 00002 CMTLT0003 JUMPZ 00070004 LOADV a0005 CHS0006 STOREV a0007 NOPHierentstehtnundasProblem,dassdasSprungzieldesbedingtenSprungszumZeitpunktder Ausgabe noch gar nicht bekannt sein kann. Daher muss der Sprung erst einmal mit einemfalschen(danichtbekannten)Sprungziel ausgegebenwerden. NachdemnunderCodedesStatementsausgegebenistkannerstdasSprungziel ausgegebenwerdenundanschlieendmuss der Bedinge Sprung noch einmal ausgegeben werden. Man benotigt daher eine spezielleFunktionf urdieAusgabe,diesog.Emitter-Funktiondiebeispielhaftsoaussehenkonnte:i nt emi t ( i nt nr, char txt, char arg ) {const i nt l i ne wi dt h =23; // Fr Windows anpassens t a t i c i nt nr =1; // Nr der Aus gabez ei l ei f ( nr UPN4 /5 #i nc l ude 6 #i nc l ude 7 %}8 %uni on {char t [ 1 0 0 ] ; }9 %token KLA AUFKLA ZUPLUSMINUSMALDIVENDFEHLER10 %token ZAHL11 %%12 e xpr e s s i on : term13 | e xpr e s s i on PLUS term { p r i nt f (+\n) ; }14 | e xpr e s s i on MINUS term { p r i nt f (\n) ; }15 ;1617 term : f a c t o r18 | termMAL f a c t o r { p r i nt f (\n) ; }19 | termDIVf a c t o r { p r i nt f (/\n) ; }20 ;2122 f a c t o r: ZAHL { p r i nt f (%s \n , $1 ) ; }23 | KLA AUF e xpr e s s i on KLA ZU24 | PLUS f a c t o r25 | MINUS f a c t o r { p r i nt f (CHS\n) ; }26 ;27 %%28 #i nc l ude l e x . yy . c2930 i nt yyer r or ( char s ) {31 p r i nt f (%s \n , s ) ;3233 }3435 i nt main ( ) {36 i nt rc ;37 rc =yyparse ( ) ;38 i f ( rc ==0)39 p r i nt f ( Syntax OK\n) ;40 e l s e41 p r i nt f ( Syntax ni cht OK\n) ;42 ret urn rc ;43 }12.5 KonikteinYacc-Grammatiken 131EinTerm-RechnerListing12.6. EinTerm-Parser(lexyacc/term-rechner.y)1 %{2 /3 I nt e r pr e t e r f ur ar i t hme t i s c he Ausdr ucke4 /5 #i nc l ude 6 #i nc l ude 7 %}8 %uni on {char t [ 1 0 0 ] ; doubl e x ; }9 %token KLA AUFKLA ZUPLUSMINUSMALDIVENDFEHLER10 %token ZAHL11 %type f a c t o r term e xpr e s s i on12 %%13 i nput : e xpr e s s i on { p r i nt f (Erg : %l f \n , $1 ) ; }14 ;1516 e xpr e s s i on : term {$$ =$1 ; }17 | e xpr e s s i on PLUS term {$$ =$1 +$3 ; }18 | e xpr e s s i on MINUS term {$$ =$1$3 ; }19 ;2021 term : f a c t o r {$$ =$1 ; }22 | termMAL f a c t o r {$$ =$1 $3 ; }23 | termDIVf a c t o r {$$ =$1 / $3 ; }24 ;2526 f a c t o r: ZAHL {$$ = at of ( $1 ) ; }27 | KLA AUF e xpr e s s i on KLA ZU {$$ =$2 ; }28 | PLUS f a c t o r {$$ =$2 ; }29 | MINUS f a c t o r {$$ = $2 ; }30 ;31 %%32 #i nc l ude l e x . yy . c3334 i nt yyer r or ( char s ) {35 p r i nt f (%s \n , s ) ;3637 }3839 i nt main ( ) {40 i nt rc ;41 rc =yyparse ( ) ;42 i f ( rc ==0)43 p r i nt f ( Syntax OK\n) ;44 e l s e45 p r i nt f ( Syntax ni cht OK\n) ;46 ret urn rc ;47 }EinTerm-AST-Generator132 12 Generator-ToolsListing12.7. EinTerm-Parser(lexyacc/term-ast-gen.y)1 %{2 /3 Kons t r ui er t AST f ur ar i t hme t i s c he Ausdr ucke ( OperatorBaum)4 /5 #i nc l ude 6 #i nc l ude 7 #i nc l ude termas t . h8 #i nc l ude termas t . c9 s t r uc t node t r e e ;10 %}11 %uni on {char t [ 1 0 0 ] ; s t r uc t node p ; }12 %token KLA AUFKLA ZUPLUSMINUSMALDIVENDFEHLER13 %token ZAHL14 %type f a c t o r term e xpr e s s i on15 %%16 i nput : e xpr e s s i on { t r e e =$1 ; }17 ;1819 e xpr e s s i on : term {$$ =$1 ; }20 | e xpr e s s i on PLUS term {$$ =newnode (+, $1 , $3 ) ; }21 | e xpr e s s i on MINUS term {$$ =newnode(, $1 , $3 ) ; }22 ;2324 term : f a c t o r {$$ =$1 ; }25 | termMAL f a