Tutorial Scriptsprachen Teil 1: Unterschied zwischen den Versionen

Aus DGL Wiki
Wechseln zu: Navigation, Suche
K (nowiki-Tag für doppelte einfache Anführungszeichen)
K (Der Ausdruck ''<pascal>(.*?)</pascal>'' wurde ersetzt mit ''<source lang="pascal">$1</source>''.)
Zeile 100: Zeile 100:
  
 
'''scanner.dpr'''
 
'''scanner.dpr'''
<pascal>
+
<source lang="pascal">
 
program scanner;
 
program scanner;
 
{$APPTYPE CONSOLE}
 
{$APPTYPE CONSOLE}
Zeile 118: Zeile 118:
 
               'VAR', 'CONST', 'PROCEDURE', 'BEGIN', 'END', 'IF', 'THEN',
 
               'VAR', 'CONST', 'PROCEDURE', 'BEGIN', 'END', 'IF', 'THEN',
 
               'ELSEIF', 'ELSE', 'WHILE', 'DO', 'MODULE', 'WRITE', '');
 
               'ELSEIF', 'ELSE', 'WHILE', 'DO', 'MODULE', 'WRITE', '');
</pascal>
+
</source>
 
Zum Scanner selbst. Die Daten die wir erhalten kommen sequentiell, da wir sie aus der Quelldatei auslesen. Leerzeichen und Sonderzeichen werden übersprungen, weil für uns uninterssant. Je nach gefundenem Zeichen wird anders verfahren, z.B wird ein "Letter" (siehe EBNF) gefunden, handelt es sich um einen Bezeichner oder ein reserviertes Wort. Bei '+','-',... um Symbole.
 
Zum Scanner selbst. Die Daten die wir erhalten kommen sequentiell, da wir sie aus der Quelldatei auslesen. Leerzeichen und Sonderzeichen werden übersprungen, weil für uns uninterssant. Je nach gefundenem Zeichen wird anders verfahren, z.B wird ein "Letter" (siehe EBNF) gefunden, handelt es sich um einen Bezeichner oder ein reserviertes Wort. Bei '+','-',... um Symbole.
  
 
'''scanner.dpr'''
 
'''scanner.dpr'''
<pascal>
+
<source lang="pascal">
 
resourcestring
 
resourcestring
 
   ERR_SCANNER_UNEXPECTED_CHAR = 'Error 0: Scanner: Unexpected char found in stream';
 
   ERR_SCANNER_UNEXPECTED_CHAR = 'Error 0: Scanner: Unexpected char found in stream';
Zeile 303: Zeile 303:
 
   CloseFile(InFile)
 
   CloseFile(InFile)
 
end.
 
end.
</pascal>
+
</source>
 
GetSym ist der eigentliche Scanner. Die für den Compiler später wichtigen Variablen sind Symbol und Str. Symbol besagt immer, was der Scanner genau gefunden hat, eine Zahl, einen Bezeichner, ein reserviertes Wort, ... GetCh holt immer das nächste Zeichen nach Ch und filtert gleichzeitig Sonderzeichen heraus. Error erzeut eine Fehlermeldung und beendet das Programm. Ein Beispiel in Scriptcode wäre:
 
GetSym ist der eigentliche Scanner. Die für den Compiler später wichtigen Variablen sind Symbol und Str. Symbol besagt immer, was der Scanner genau gefunden hat, eine Zahl, einen Bezeichner, ein reserviertes Wort, ... GetCh holt immer das nächste Zeichen nach Ch und filtert gleichzeitig Sonderzeichen heraus. Error erzeut eine Fehlermeldung und beendet das Programm. Ein Beispiel in Scriptcode wäre:
  
 
'''test.script'''
 
'''test.script'''
<pascal>
+
<source lang="pascal">
 
module Test;
 
module Test;
  
Zeile 326: Zeile 326:
 
   (* Testkommentar * Test *)
 
   (* Testkommentar * Test *)
 
end Test;
 
end Test;
</pascal>
+
</source>
 
Wenn wir das Programm mit dem Scanner darüber laufen lassen, erhalten wir folgenden Output:
 
Wenn wir das Programm mit dem Scanner darüber laufen lassen, erhalten wir folgenden Output:
 
   MODULE
 
   MODULE
Zeile 373: Zeile 373:
  
 
'''parser.dpr'''
 
'''parser.dpr'''
<pascal>
+
<source lang="pascal">
 
program parser;
 
program parser;
 
{$APPTYPE CONSOLE}
 
{$APPTYPE CONSOLE}
Zeile 446: Zeile 446:
 
   CloseFile(InFile)
 
   CloseFile(InFile)
 
end.
 
end.
</pascal>
+
</source>
 
Soweit zur Kurzfassung. Der Scanner und die ErrorX Funktionen sollten übrigens in Units ausgelagert werden, da sie massenhaft Platz beanspruchen und stark die Übersicht in unserem Programm belasten. Ideal wäre jetzt natürlich, wenn ihr versuchen würdet, den Rest selber zu implementieren. Mein Werk findet ihr bei den Sources in '''parser.dpr'''. Noch ein kleiner Tipp am Rande: Wenn man glaubt, alles eingebaut zu haben sollte man auch alle Möglichkeiten der Sprache in einem Testskript ausprobiert haben, nur um sicherzugehen...
 
Soweit zur Kurzfassung. Der Scanner und die ErrorX Funktionen sollten übrigens in Units ausgelagert werden, da sie massenhaft Platz beanspruchen und stark die Übersicht in unserem Programm belasten. Ideal wäre jetzt natürlich, wenn ihr versuchen würdet, den Rest selber zu implementieren. Mein Werk findet ihr bei den Sources in '''parser.dpr'''. Noch ein kleiner Tipp am Rande: Wenn man glaubt, alles eingebaut zu haben sollte man auch alle Möglichkeiten der Sprache in einem Testskript ausprobiert haben, nur um sicherzugehen...
  
Zeile 454: Zeile 454:
  
 
'''parser_idents.dpr'''
 
'''parser_idents.dpr'''
<pascal>
+
<source lang="pascal">
 
type
 
type
 
   TIdentType = (itConstant, itVariable, itProzedure);
 
   TIdentType = (itConstant, itVariable, itProzedure);
Zeile 465: Zeile 465:
 
var
 
var
 
   Table : TIdentList;
 
   Table : TIdentList;
</pascal>
+
</source>
 
Den Zugriff auf die Tabelle wollen wir über 2 Funktionen Steuern: Position(Name) sucht die Position eines Eintrags in der Tabelle und Enter(TIdentType) fügt der Liste einen Eintrag hinzu. Der Scanner bekommt noch eine kleine Änderung verabreicht. Erkennt er einen Bezeichner, wird dessen Name in einer Variable id abgelegt, erkennt er eine Zahl, wird deren Wert in num abgelegt:
 
Den Zugriff auf die Tabelle wollen wir über 2 Funktionen Steuern: Position(Name) sucht die Position eines Eintrags in der Tabelle und Enter(TIdentType) fügt der Liste einen Eintrag hinzu. Der Scanner bekommt noch eine kleine Änderung verabreicht. Erkennt er einen Bezeichner, wird dessen Name in einer Variable id abgelegt, erkennt er eine Zahl, wird deren Wert in num abgelegt:
  
 
'''parser_idents.dpr'''
 
'''parser_idents.dpr'''
<pascal>
+
<source lang="pascal">
 
   ...
 
   ...
 
       procedure Enter(Typ : TIdentType);
 
       procedure Enter(Typ : TIdentType);
Zeile 494: Zeile 494:
 
     end;
 
     end;
 
   ...
 
   ...
</pascal>
+
</source>
 
Enter wird immer dann aufgerufen, wenn ein Bezeichner eingeführt wird (ConstDecl, VarDecl, ProcedureDecl). Position wird immer benötigt, wenn ein Bezeichner angewand wird (Statement).
 
Enter wird immer dann aufgerufen, wenn ein Bezeichner eingeführt wird (ConstDecl, VarDecl, ProcedureDecl). Position wird immer benötigt, wenn ein Bezeichner angewand wird (Statement).
  
 
'''parser_idents.dpr'''
 
'''parser_idents.dpr'''
<pascal>
+
<source lang="pascal">
 
program compiler;
 
program compiler;
 
{$APPTYPE CONSOLE}
 
{$APPTYPE CONSOLE}
Zeile 851: Zeile 851:
 
   CloseFile(InFile)
 
   CloseFile(InFile)
 
end.
 
end.
</pascal>
+
</source>
 
Ich schlage vor, hier eine kleine Pause einzulegen, bevor ihr euch an den Rest des Tutorials wagt. Ich denke nämlich, dass sich ein paar Informationen erst setzten müssen, bevor der nächste Teil in Angriff genommen werden kann. Niemand schreibt beim ersten Versuch einen Compiler an einem Tag...
 
Ich schlage vor, hier eine kleine Pause einzulegen, bevor ihr euch an den Rest des Tutorials wagt. Ich denke nämlich, dass sich ein paar Informationen erst setzten müssen, bevor der nächste Teil in Angriff genommen werden kann. Niemand schreibt beim ersten Versuch einen Compiler an einem Tag...
  

Version vom 10. März 2009, 19:14 Uhr

Einführung

Hoi, ich bin wieder aus meinem Urlaub zurück mit einem ganzen Satz neuer Ideen. Schon einmal als Gott versucht? Ihr werdet euch als Programmierer echt so fühlen... Diesmal geht es um Scriptsprachen. Sie müssen nicht nötigerweise in Spielen eingesetzt werden (siehe Emacs) ist aber häufig so, wie man an Unreal, Quake, Halflife, Tribes, etc. erkennen kann. Teilweise basiert fast das komplette Spiel auf diesen Sprachen, nur sehr zeitkritische Bereiche sind in den 'echten' Code ausgelagert, denn die Interpretierung des Scriptcodes läuft um einiges langsamer ab, als der Maschinenassembler. Andererseits können sie natürlich auch die Portierung der Spiele erleichtern, denn die Scriptsprache ist normalerweise nicht systemabhängig.

Hat man sich entschieden, eine Scriptsprache zu verwenden, steht man vor einer Entscheidung: Nehme ich eine bereits existierende Scriptsprache, wie Python für Delphi oder Innerfuse Pascal Script oder schreibe ich eine Engine selbst. Ich bin der Ansicht, als Programmierer sollte man einmal hinter die Kulissen einer Programmiersprache geschaut haben - man kann daraus viel lernen. Entsprechend stelle ich hier die Variante vor, bei der man sich nicht erst in die API einer bestehenden Sprache einarbeiten muss, sondern bei der man die API selbst entwirft. Es lohnt sich sicherlich, dieses Tutorial einmal näher unter die Lupe zu nehmen, auch wenn man nicht plant, eine Scriptsprache zu verwenden.

Erweiterte Backus-Naur Form(EBNF)

Bevor wir uns daran machen können, einen Compiler für unsere Sprache zu entwickeln, müssen wir uns ein wenig mit Programmiersprachen selbst etwas beschäftigen. Form und Aufbau der Sprache müssen festgelegt werden. Einfach darauf loszuarbeiten ist hier auf alle Fälle der falsche Weg und führt mit Sicherheit nur zu massenhaft unbrauchbarem Codeschrott. Tatsächlich gibt es spezielle Sprachen, mit denen Programmiersprachen beschrieben werden können. Algol 60 war die erste Programmiersprache die mit BNF beschrieben wurde, aber längst nicht die einzige. Es folgten z.B. PL/0, PL/1, Pascal, Oberon, Modula, Component Pascal, Object Pascal und viele andere, mehr oder weniger bekannte. EBNF eignet sich auch sehr gut unsere "eigene" Sprache zu beschreiben, doch kennen wohl die meisten unter euch EBNF noch nicht, es ist also Zeit hier eine kleine Definition zu machen:

1. Besteht A allein aus B, so schreibt man:
A = B.
2. Ein Zeichen zwischen '' oder "" bedeutet das Zeichen selbst.
Beispiel:
Punkt = '.'.
3. Besteht A aus B gefolgt von C, so schreibt man:
A = B C.
4. Besteht A aus B oder C, so schreibt man
A = B | C.
Beispiel:
Digit = '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'.
5. Besteht A aus keinem, einem, oder mehreren B, so schreibt man:
A = {B}.
Beispiel:
Vorzeichenlose Zahl = Digit {Digit}.
6. Ist A entweder leer oder gleich B, so schreibt man
A = [B].
Beispiel:
Vorzeichen = '+'|'-'.
Zahl = [Vorzeichen] PositiveZahl.
7. Runde Klammern gruppieren Elemente:
A = (B|C)(D|E).

EBNF bereitet am Anfang sicherlich Probleme und es dauert ein wenig, bis man sich in der Sprache zurecht findet. Am einfachsten übt sich der Gebrauch an einem Beispiel - an der Scriptsprache die wir implementieren wollen:

#Kleinkrams
 Digit      = "0"|..|"9".
 HexDigit   = Digit|"A"|..|"F".
 Letter     = "A"|..|"Z"|"_".
 Vorzeichen = "+"|"-".
#Zahlen
 Zahl       = (Digit {Digit}) | ("$" HexDigit {HexDigit}).
#Bezeichner, Zahlen, etc.
 Ident      = Letter {Letter|Digit}.
#Ausdrücke
 Condition       = Expression ("="|"<"|">"|">="|"<="|"#") Expression.
 Expression      = [Vorzeichen] Term {Vorzeichen Term}.
 Term            = Factor {"*"|"/" Factor}.
 Factor          = Ident | Zahl | ("(" Expression ")").
#Deklarationen, Statements, etc.
 VarDecl         = Ident {"," Ident}.
 ConstDecl       = Ident "=" Zahl.
 VarSeq          = VAR VarDecl {";" VarDecl}";".
 ConstSeq        = CONST ConstDecl {";" ConstDecl}";".
 DeclSeq         = {VarSeq | ConstSeq | ProcedureDecl}.
 ProcedureDecl   = PROCEDURE Ident";"
                   DeclSeq BEGIN StatementSeq END Ident ";".
 Statement     = ( Ident ":=" Expression ) |
               Ident | ( WRITE Expression ) |
               ( BEGIN StatementSeq END ) |
               ( IF Condition THEN StatementSeq END
                 {ELSEIF Condition THEN StatementSeq END }
                 [ELSE StatementSeq END] ) |
               ( WHILE Condition DO StatementSeq END )| ";".
 StatementSeq  = [Statement {";" Statement}]
 Comment       = "(*" ... "*)".
 Module        = MODULE Ident ";"
               DeclSeq
               BEGIN
                 StatementSeq
               END Ident ".".

Lexikalische Analyse

Eine der ersten Aufgaben die wir beim Bau unseres Compilers zu bewältigen haben ist, die Lexikalische Analyse. Die Funktion dieser ist in den Eingabedaten Wörter und Symbole zu erkennen, reservierte Wörter als solche zu markieren und Kommentare herauszufiltern.

Zuvor wieder eine kleine Entscheidung: Soll unsere Sprache einen Unterschied zwischen Groß und Kleinschreibung machen? Das beeinflusst das Aussehen unserer Sprache in hohem Maße, denn in einem Fall ist es egal ob "begin", "BEGIN", "Begin" oder "bEgIn", im anderen nicht. Ich beschließe einfach mal, sie à la Pascal nicht case sensitive zu halten.

Der erste Schritt beim Scannerbau ist, alle verwendeten Symbole zu definieren und die schreibweise der reservierten Wörter festzulegen:

scanner.dpr

program scanner;
{$APPTYPE CONSOLE}
uses
  sysutils;

type
  TSymbol = (sUnknown, sIdent, sInteger, sPlus, sMinus, sStar, sSlash, sEqual,
             sSmaller, sBigger, sBiggerEqual, sSmallerEqual, sUnEqual,
             sOpenBracket, sCloseBracket, sComma, sDot, sSemiColon, sBecomes,
             sVar, sConst, sProcedure, sBegin, sEnd, sIf, sThen,
             sElseIf, sElse, sWhile, sDo, sModule, sWrite, sNone);
const
  cSymbols : Array[TSymbol] of ShortString = ('', '', '', '+', '-', '*', '/', '=',
               '<', '>', '>=', '<=', '#',
               '(', ')', ',', '.', ';', ':=',
               'VAR', 'CONST', 'PROCEDURE', 'BEGIN', 'END', 'IF', 'THEN',
               'ELSEIF', 'ELSE', 'WHILE', 'DO', 'MODULE', 'WRITE', '');

Zum Scanner selbst. Die Daten die wir erhalten kommen sequentiell, da wir sie aus der Quelldatei auslesen. Leerzeichen und Sonderzeichen werden übersprungen, weil für uns uninterssant. Je nach gefundenem Zeichen wird anders verfahren, z.B wird ein "Letter" (siehe EBNF) gefunden, handelt es sich um einen Bezeichner oder ein reserviertes Wort. Bei '+','-',... um Symbole.

scanner.dpr

resourcestring
  ERR_SCANNER_UNEXPECTED_CHAR = 'Error 0: Scanner: Unexpected char found in stream';


var
  InFile : File;
  Line : Integer;

  procedure Error(ErrorText : String);
  begin
    WriteLn(Format('%d: ' + ErrorText, [Line]));
    ReadLn;
    Halt(0)
  end;

var
  Ch : Char;
  Str : String;
  Symbol : TSymbol;

  procedure GetSym;
    procedure GetCh;
    begin
      if not EoF(InFile) then
        BlockRead(InFile, Ch, 1)
      else
        Ch := ' ';
      //Case in-sensitive
      Ch := UpCase(Ch);

      //Zeile erhöhen?
      if Ch = #13 then Inc(Line);
      //Spezialzeichen filtern
      if Ord(Ch) < Ord(' ') then Ch := ' '
    end (*GetCh*);
  var
    I : TSymbol;
  begin
    //Überspringen von Kommentaren
    while true do
    begin
      Str := '';
      Symbol := sNone;

      while (Ch = ' ') and not EoF(InFile) do
        GetCh;

      //Wir brauchen nichts machen, wenn das Dateiende erreicht ist
      if EoF(InFile) then
        Exit;

      case Ch of
        'A'..'Z','_': begin (*Ident/Reserved Word*)
                        while Ch in ['A'..'Z','_','0'..'9'] do
                        begin
                          Str := Str + Ch;
                          GetCh
                        end;
                        Symbol := sIdent;

                        for i := sUnknown to sNone do
                          if Str = cSymbols[i] then
                          begin
                            Symbol := i;
                            Break
                          end;
                        Exit
                      end; (*Ident/Reserved Word*)
          ';','+','-','=','#',',','.', '*', '/':
                      begin (*Symbole die nur aus 1 Zeichen bestehen können*)
                        Str := Ch;
                        Symbol := sUnknown;
                        for i := sUnknown to sNone do
                          if Str = cSymbols[i] then
                          begin
                            Symbol := i;
                            Break
                          end;
                        GetCh;
                        Exit
                      end; (*Symbole die nur aus 1 Zeichen bestehen können*)
          ':','<','>': (* Zeichen die ein nachfolgendes Zeichen haben können(in diesm Falle ein = )*)
                      begin
                        Str := Ch;
                        GetCh;
                        if Ch = '=' then Str := Str + Ch;
                        GetCh;
                        Symbol := sUnknown;
                        for i := sUnknown to sNone do
                          if Str = cSymbols[i] then
                          begin
                            Symbol := i;
                            Break
                          end;
                        Exit
                      end;
          '(', ')':   begin (*Klammern oder Kommentar*)
                        Str := Ch;
                        GetCh;
                        if (Str='(') and (Ch = '*') then
                        begin
                          //Kommentar entdeckt
                          GetCh;
                          while True do
                          begin
                            GetCh;
                            if Ch = '*' then
                            begin
                              GetCh;
                              if Ch = ')' then
                              begin
                                GetCh;
                                Break
                              end
                            end
                            else if EoF(InFile) then
                              Break
                          end
                        end else
                        if Str = '(' then
                        begin
                          Symbol := sOpenBracket;
                          Exit
                        end
                        else
                        begin
                          Symbol := sCloseBracket;
                          Exit
                        end
                      end;
          '0'..'9','$': (*Zahlen*)
                      begin
                        Symbol := sInteger;
                        Str := Ch;
                        GetCh;
                        if (Str = '$') then
                        begin
                          //HexZahl
                          while Ch in ['0'..'9','A'..'F'] do
                          begin
                            Str := Str + Ch;
                            GetCh;
                          end;
                          Exit
                        end
                        else
                        begin
                          //NormaleZahl
                          while Ch in ['0'..'9'] do
                          begin
                            Str := Str + Ch;
                            GetCh;
                          end;
                          Exit
                        end
                      end; (*Zahlen*)

      else
        Error(ERR_SCANNER_UNEXPECTED_CHAR)
      end;
      Assert(Symbol <> SUnknown);
    end
  end (*GetSym*);

begin
  AssignFile(InFile, ParamStr(1));
  Reset(InFile, 1);
  //Ch mit leerzeichen initialisieren
  Ch := ' ';
  Line := 1;
  GetSym;
  while Symbol <> sNone do
  begin
    WriteLn(Str);
    GetSym
  end;
  WriteLn('Done...');
  ReadLn;
  CloseFile(InFile)
end.

GetSym ist der eigentliche Scanner. Die für den Compiler später wichtigen Variablen sind Symbol und Str. Symbol besagt immer, was der Scanner genau gefunden hat, eine Zahl, einen Bezeichner, ein reserviertes Wort, ... GetCh holt immer das nächste Zeichen nach Ch und filtert gleichzeitig Sonderzeichen heraus. Error erzeut eine Fehlermeldung und beendet das Programm. Ein Beispiel in Scriptcode wäre:

test.script

module Test;

const
  HexZahl = $12ABCDEF;
  NormaleZahl = 12345;

var
  a;

  procedure Hello;
  begin
    Write a
  end Hello;

begin
  a := 0;
  (* Testkommentar * Test *)
end Test;

Wenn wir das Programm mit dem Scanner darüber laufen lassen, erhalten wir folgenden Output:

 MODULE
 TEST
 ;
 CONST
 HEXZAHL
 =
 $12ABCDEF
 ;
 NORMALEZAHL
 =
 12345
 ;
 VAR
 A
 ;
 PROCEDURE
 HELLO
 ;
 BEGIN
 WRITE
 A
 END
 HELLO
 ;
 BEGIN
 A
 :=
 0
 ;
 END
 TEST
 ;
 Done...

Dies ist unser Beispielprogramm in einzelne Symbole zerlegt. Um den Scanner-Code besser zu verstehen, sollte man einfach einmal in den Code Debuggen und schauen was der Reihe nach passiert. In die Liste der überwachten Ausdrücke gehört dabei unbedingt: Str, Ch, Symbol.

Parsen des Quellcodes

Der nächste zu bewältigende Schritt ist das Parsen ("Satzzerlegen") des Quelltextes. Es handelt sich um die Überprüfung des Quellcodes auf syntaktische Korrektheit. Wir wollen uns erst einmal nur auf den Aufbau des Skripts konzentrieren. Die Korrektheit der Bezeichner sei erstmal noch unwichtig.

An alle, die Angst vorm Schachteln haben (besonders Phobeus ;)): Ich hoffe das wird hier nicht zu hart für euch... Danach werdet ihr Schachteln lieben, das verspreche ich ;-).

Zurück zum Parsen. Hier müssen wir wieder die EBNF zur Hand nehmen, sie wird uns gute Dienste leisten. Suchen wir uns einen Startpunkt heraus. In unserer Sprache wäre das Module. So nennen wir dann auch die entsprechende Prozedur. Diese prüft ihre paar reservierten Wörter und Bezeichner ab und ruft dann DeclSeq auf. Sobald DeclSeq abgeschlossen ist, prüfen wir ob ein BEGIN gefunden wurde und rufen StatementSeq auf... Genauso verfahren wir bei DeclSeq und StatementSeq, dadurch bleibt die Sache übersichtlich und vieles wird einfacher.

parser.dpr

program parser;
{$APPTYPE CONSOLE}
uses
  sysutils,
  symbols in 'symbols.pas',
  scanner in 'scanner.pas',
  errors in 'errors.pas';

  procedure Expect(Expected : TSymbol);
  begin
    if Symbol <> Expected then
      ErrorExpected([Expected], Symbol)
  end;

  procedure Module;

    procedure StatementSequence;
    (*  StatementSeq  = [Statement {";" Statement}]*)
    ...
    end; (*Statement Sequence*)

    procedure Declarations;
    (*
      VarSeq          = VAR VarDecl {";" VarDecl}";".
      ConstSeq        = CONST ConstDecl {";" ConstDecl}";".
      DeclSeq         = {VarSeq | ConstSeq | ProcedureDecl}.

    *)
    ...
    end; (*Declarations*)

  (*Module        = MODULE Ident ";"
                    DeclSeq
                    BEGIN
                      StatementSeq
                    END Ident ".".*)
  begin (*Module*)
    Expect(sModule);
    GetSym;
    Expect(sIdent);
    GetSym;
    Expect(sSemiColon);
    GetSym;

    Declarations;

    Expect(sBegin);
    GetSym;
    StatementSequence;
    Expect(sEnd);
    GetSym;
    Expect(sIdent);
    GetSym;
    Expect(sSemiColon);
    GetSym;
    if Symbol <> sNone then
      WriteLn(Format('%d: Code after Module END is ignored!', [Line]))
  end (*Module*);

begin
  AssignFile(InFile, ParamStr(1));
  Reset(InFile, 1);
  //Ch mit leerzeichen initialisieren
  Ch := ' ';
  Line := 1;
  GetSym;
  Module;

  WriteLn('Done, no syntax errors detected...');
  ReadLn;
  CloseFile(InFile)
end.

Soweit zur Kurzfassung. Der Scanner und die ErrorX Funktionen sollten übrigens in Units ausgelagert werden, da sie massenhaft Platz beanspruchen und stark die Übersicht in unserem Programm belasten. Ideal wäre jetzt natürlich, wenn ihr versuchen würdet, den Rest selber zu implementieren. Mein Werk findet ihr bei den Sources in parser.dpr. Noch ein kleiner Tipp am Rande: Wenn man glaubt, alles eingebaut zu haben sollte man auch alle Möglichkeiten der Sprache in einem Testskript ausprobiert haben, nur um sicherzugehen...

Ein Aufbaucheck langt nicht aus

Jetzt müssen wir unseren Parser erweitern. Wir haben vorhin beschlossen, die Überprüfung der Bezeichner erst einmal auszulassen. Das kommt nun auf uns zu. Die typische Methode Bezeichner einzubinden ist über Tabellen. Sie enthalten die für uns relevanten Inhalte: Name und Typ(Prozedur, Konstante, Variable) des Bezeichners. Für die Codeerzeugung werden wir dieses Feld erweitern müssen, doch vorerst langt uns das einmal aus. Wir müssen dabei auch bedenken, dass Prozeduren lokale Variablen haben, die für Prozeduren eines niedrigeren level nicht erreichbar sein dürfen, egal wann und wo sie definiert wurden.

parser_idents.dpr

type
  TIdentType = (itConstant, itVariable, itProzedure);
  TIdent = record
             Name : ShortString;
             Kind : TIdentType;
           end;
  TIdentList = Array of TIdent;

var
  Table : TIdentList;

Den Zugriff auf die Tabelle wollen wir über 2 Funktionen Steuern: Position(Name) sucht die Position eines Eintrags in der Tabelle und Enter(TIdentType) fügt der Liste einen Eintrag hinzu. Der Scanner bekommt noch eine kleine Änderung verabreicht. Erkennt er einen Bezeichner, wird dessen Name in einer Variable id abgelegt, erkennt er eine Zahl, wird deren Wert in num abgelegt:

parser_idents.dpr

  ...
      procedure Enter(Typ : TIdentType);
      begin
        Inc(TablePosition);
        if TablePosition > Length(Table) - 1 then
          SetLength(Table, Length(Table)+16);
        with Table[TablePosition] do
        begin
          Name := ID;
          Kind := Typ
        end
      end;
  ...
    function Position(ID : ShortString; TablePosition : Integer) : Integer;
    var
      I : Integer;
    begin
      Table[0].Name := ID;
      I := TablePosition;
      while Table[I].Name <> ID do
        Dec(I);
      Result := I
    end;
  ...

Enter wird immer dann aufgerufen, wenn ein Bezeichner eingeführt wird (ConstDecl, VarDecl, ProcedureDecl). Position wird immer benötigt, wenn ein Bezeichner angewand wird (Statement).

parser_idents.dpr

program compiler;
{$APPTYPE CONSOLE}
uses
  sysutils,
  symbols in '..\parser\symbols.pas',
  scanner in '..\parser\scanner.pas',
  errors in '..\parser\errors.pas';

type
  TIdentType = (itConstant, itVariable, itProcedure);
  TIdent = record
             Name : ShortString;
             Kind : TIdentType;
           end;
  TIdentList = Array of TIdent;

var
  Table : TIdentList;

  procedure Expect(Expected : TSymbol);
  begin
    if Symbol <> Expected then
      ErrorExpected([Expected], Symbol)
  end;

  procedure Module;

    function Position(ID : ShortString; TablePosition : Integer) : Integer;
    var
      I : Integer;
    begin
      Table[0].Name := ID;
      I := TablePosition;
      while Table[I].Name <> ID do
        Dec(I);
      Result := I
    end;

    procedure StatementSequence(TablePosition : Integer);
    (*  StatementSeq  = [Statement {";" Statement}]*)
      procedure Statement;
      (*Statement     = ( Ident ":=" (Ident | Expression) |
                  Ident | (WRITE Expression) |
                  ( BEGIN StatementSeq END ) |
                  ( IF Condition THEN StatementSeq END
                    {ELSEIF Condition THEN StatementSeq END }
                    [ELSE StatementSeq END] ) |
                  ( WHILE Condition DO StatementSeq END ) | ";". *)
        procedure Expression;
        (*Expression      = [Vorzeichen] Term {Vorzeichen Term}.*)
          procedure Term;
          (*Term            = Factor {"*"|"/" Factor}.*)
            procedure Factor;
            (*Factor          = Ident | Zahl | ("(" Expression ")").*)
            var
              IdentPos : Integer;
            begin (*Factor*)
              if (Symbol in [sIdent, sInteger]) then
              begin
                IdentPos := Position(ID, TablePosition);
                if (IdentPos = 0) then
                  Error(ERR_PARSE_UNKNOWN_IDENT);
                if Table[IdentPos].Kind = itProcedure then
                  Error(ERR_PARSE_VAR_CONSTANT_EXPECTED);
                GetSym
              end
              else if (Symbol = sOpenBracket) then
              begin
                GetSym;
                Expression;
                Expect(sCloseBracket);
                GetSym
              end
              else
                ErrorExpected([sIdent, sInteger, sOpenBracket], Symbol)
            end;  (*Factor*)

          begin(*Term*)
            Factor;
            while Symbol in [sStar, sSlash] do
            begin
              GetSym;
              Factor
            end
          end;(*Term*)
        begin (*Expresion*)
          if (Symbol in[sPlus, sMinus]) then
            GetSym;
          Term;
          while (Symbol in[sPlus, sMinus]) do
          begin
            GetSym;
            Term
          end
        end; (*Expression*)

        procedure Condition;
        (*Condition       = Expression ("="|"<"|">"|">="|"<="|"#") Expression.*)
        begin (*Condition*)
          Expression;
          if Symbol in [sEqual, sSmaller, sBigger, sBiggerEqual, sSmallerEqual, sUnequal] then
          begin
            GetSym;
            Expression
          end
          else
            ErrorExpected([sEqual, sSmaller, sBigger, sBiggerEqual, sSmallerEqual, sUnequal], Symbol)
        end; (*Condition*)

      var
        IdentPos : Integer;
        Ident : ShortString;

      begin (*Statement*)
        case Symbol of
          sIdent: begin
                    Ident := Id;
                    IdentPos := Position(ID, TablePosition);
                    if (IdentPos = 0) then
                      Error(ERR_PARSE_UNKNOWN_IDENT);
                    if Table[IdentPos].Kind = itProcedure then
                    begin
                      //Prozeduraufruf
                      GetSym
                    end else if Table[IdentPos].Kind = itVariable then
                    begin
                      GetSym;
                      Expect(sBecomes);
                      GetSym;
                      Expression
                    end
                    else
                      Error(ERR_PARSE_NO_CONST_ALLOWED)
                  end;
          sWrite: begin
                    GetSym;
                    Expression
                  end;
          sIf :   begin
                    GetSym;
                    Condition;
                    Expect(sThen);
                    GetSym;
                    StatementSequence(TablePosition);
                    Expect(sEnd);
                    GetSym;
                    while Symbol = sElseIf do
                    begin
                      GetSym;
                      Condition;
                      Expect(sThen);
                      GetSym;
                      StatementSequence(TablePosition);
                      Expect(sEnd);
                      GetSym
                    end;
                    if Symbol = sElse then
                    begin
                      GetSym;
                      StatementSequence(TablePosition);
                      Expect(sEnd);
                      GetSym
                    end
                  end;
          sWhile :
                  begin
                    GetSym;
                    Condition;
                    Expect(sDo);
                    GetSym;
                    StatementSequence(TablePosition);
                    Expect(sEnd);
                    GetSym
                  end;
          sBegin :
                  begin
                    GetSym;
                    StatementSequence(TablePosition);
                    Expect(sEnd);
                    GetSym
                  end;

        else
          (*Der Fehler darf getrost ignoriert werden*)
          //Error(ERR_PARSE_UNALLOWED_STATEMENT)
        end
      end; (*Statement*)

    begin (*Statement Sequence*)
      Statement;
      while Symbol = sSemiColon do
      begin
        GetSym;
        Statement
      end
    end; (*Statement Sequence*)

    function Declarations(TablePosition : Integer): Integer;
    (*
      VarSeq          = VAR VarDecl {";" VarDecl}";".
      ConstSeq        = CONST ConstDecl {";" ConstDecl}";".
      DeclSeq         = {VarSeq | ConstSeq | ProcedureDecl}.

    *)
      procedure Enter(Typ : TIdentType);
      begin
        Inc(TablePosition);
        if TablePosition > Length(Table) - 1 then
          SetLength(Table, Length(Table)+16);
        with Table[TablePosition] do
        begin
          Name := ID;
          Kind := Typ
        end
      end;


      procedure ProcedureDecl;
      (*ProcedureDecl   = PROCEDURE Ident";"
                          DeclSeq BEGIN StatementSeq END Ident ";".*)
      var
        ProcedureName : String;
        ProcTablePos : Integer;
      begin
        Expect(sProcedure);
        GetSym;
        Expect(sIdent);
        Enter(itProcedure);
        ProcedureName := ID;

        GetSym;
        Expect(sSemiColon);
        GetSym;
        ProcTablePos := Declarations(TablePosition);
        Expect(sBegin);
        GetSym;
        StatementSequence(ProcTablePos);
        Expect(sEnd);
        GetSym;
        Expect(sIdent);
        if ProcedureName <> ID then
          Error(Format(ERR_PARSE_WRONG_PROCEDURE_ENDED, [ProcedureName, ID]));
        GetSym;
        Expect(sSemiColon);
        GetSym
      end;

      procedure ConstDecl;
      (*ConstDecl       = Ident "=" Zahl.*)
      begin (*ConstDecl*)
        Expect(sIdent);
        GetSym;
        Expect(sEqual);
        GetSym;
        Expect(sInteger);
        Enter(itConstant);
        GetSym
      end; (*ConstDecl*)

      procedure VarDecl;
      (*VarDecl         = Ident {"," Ident}.*)
      begin (*VarDecl*)
        Expect(sIdent);
        Enter(itVariable);
        GetSym;
        while Symbol = sComma do
        begin
          GetSym;
          Expect(sIdent);
          Enter(itVariable);
          GetSym
        end
      end; (*VarDecl*)

    begin (*Declarations*)
      while Symbol in [sVar, sConst, sProcedure] do
        case Symbol of
          sVar   : begin
                     GetSym;
                     VarDecl;
                     Expect(sSemiColon);
                     GetSym;
                     while Symbol = sIdent do
                     begin
                       VarDecl;
                       Expect(sSemiColon);
                       GetSym
                     end
                   end;
         sConst  : begin
                     GetSym;
                     ConstDecl;
                     Expect(sSemiColon);
                     GetSym;
                     while Symbol = sIdent do
                     begin
                       ConstDecl;
                       Expect(sSemiColon);
                       GetSym
                     end
                   end;
          sProcedure : ProcedureDecl;
        end;
      Result := TablePosition
    end; (*Declarations*)

  (*Module        = MODULE Ident ";"
                    DeclSeq
                    BEGIN
                      StatementSeq
                    END Ident ".".*)
  var
    TablePosition : Integer;
    ModuleName : ShortString;

  begin (*Module*)
    Expect(sModule);
    GetSym;
    Expect(sIdent);
    ModuleName := Id;
    GetSym;
    Expect(sSemiColon);
    GetSym;
    TablePosition := Declarations(0);
    Expect(sBegin);
    GetSym;
    StatementSequence(TablePosition);
    Expect(sEnd);
    GetSym;
    Expect(sIdent);
    if ModuleName <> Id then
      Writeln(Format('%d: Warning: Module ID <> End ID', [Line]));
    GetSym;
    Expect(sSemiColon);
    GetSym;
    if Symbol <> sNone then
      WriteLn(Format('%d: Code after Module END is ignored!', [Line]))
  end (*Module*);

begin
  AssignFile(InFile, ParamStr(1));
  Reset(InFile, 1);
  //Ch mit leerzeichen initialisieren
  Ch := ' ';
  Line := 1;
  GetSym;
  Module;

  WriteLn('Done, no syntax errors detected...');
  ReadLn;
  CloseFile(InFile)
end.

Ich schlage vor, hier eine kleine Pause einzulegen, bevor ihr euch an den Rest des Tutorials wagt. Ich denke nämlich, dass sich ein paar Informationen erst setzten müssen, bevor der nächste Teil in Angriff genommen werden kann. Niemand schreibt beim ersten Versuch einen Compiler an einem Tag...



Nächstes Tutorial:
Tutorial Scriptsprachen Teil 2

Schreibt was ihr zu diesem Tutorial denkt ins Feedbackforum von DelphiGL.com.
Lob, Verbesserungsvorschläge, Hinweise und Tutorialwünsche sind stets willkommen.