Autor Beitrag
Fortuna
Hält's aus hier
Beiträge: 5



BeitragVerfasst: Di 07.03.06 00:16 
Hallo. Ich hab einen Scanner programmiert. Eigentlich sollte es ein endlicher Automat werden. Ist er aber nicht ganz. Mein Scanner hat eine vordefinierte Tokenliste, die er schon kennt. Er scannt das Programm nach Tokens ab und merkt sich diese in einer Scanliste mit der entsprechenden Zahl. Ist ein aufgefundenes Token im Programm, z.B. eine Variable, noch nicht in der Tokenliste bekannt, legt er diese als neues Token in der Tokenliste an und natürlich auch entsprechende Zahl in der Scanliste. Der Scanner unterscheidet zw. Operatoren, Wörtern und Zahlen. Meine Programme können erstmal nichts komplexeres. Wenn er erkennt hat um welchen Fall es sich von den dreien handelt, speichert er dies auch noch in den 2dimensionalen Array der Tokenliste (muss ich aber noch in meinem Programm ergänzen.) Das soll die Vorbereitung für den Parser sein. Ich schreib nächste Woche Vorabi und ich könnte mir Vorstellen, dass da als Frage kommt, wie man einen Parser programmiert und wie das alles aufgebaut sein muss. Doch ich habe null Ahnung. Wie wären erstmal in Worte gefasst jetzt die Schritte, die der Parser vollziehen muss? Nach welchen Schritten soll ich ihn programmieren? Was muss er alles machen? In welcher Reihenfolge und wie umsetzen?

Bitte helft mir schnell. Scanner im Anhang.

THX
Einloggen, um Attachments anzusehen!
digi_c
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Di 07.03.06 11:22 
Wie Vorabi und Parser? An was für einer Schule bist du denn?
Ich war an einer Technischen Berufsschule und habe da ABI+Staatlichen Abschluss gemacht aber so ins Detail sind die auf keinen Fall gegangen.

Wie wäre es mit:
delphi.zsg-rottenburg.de/parser.html
Suche bei Google DELPHI PARSER

Was soll den dein Parser genau machen, ein Bild darstellen, Berechnungen druchführen, was identifizieren,...?
Fortuna Threadstarter
Hält's aus hier
Beiträge: 5



BeitragVerfasst: Mi 08.03.06 14:07 
Ich bin aufm Gymnasium und mein Info Lehrer übertreibts vom Anspruch find ich :-(
Mein Parser soll halt die Syntax zu einer Sprache prüfen. Mein Delphie-Programm muss ja zum Glück nicht viel können, sonst wär es total kompliziert. Nur Variablen, Zuweisungen, Rechnungsterme (ohne negative Zahlen), keine Schleifen und so. Ich hab ja ein Programm Beispiel und meinen Scanner im Anhang. Halt der passende Parser dazu. Er soll halt mit der Tokenliste, also bzw. bei mir heißt die Scanliste, das ist die Liste, die die Zahlen der Tokens auflistet, z.B. Program =1
also z.B:
1
13
5
2

wär jetzt die Liste für
Programm Rechnung;
Begin

Aber das ist ja alles aus meinem Anhang erkennbar.
Der Parser soll wohl irgendwie diese Liste vom Scanner nehmen und jetzt das Programm rekursiv auf korrekte Syntax überprüfen.
Indem er z.B. zerlegt

P= {
PROGRAMM ::= prog name semikolon BLOCK punkt,
BLOCK ::=begin ZUWEISUNG end,
ZUWEISUNG::=name zuweisungsop AUSDRUCK,
AUSDRUCK ::=TERM|TERM strichoperator AUSDRUCK,
TERM ::=FAKTOR|FAKTOR punktoperator TERM,
FAKTOR ::=name | zahl | klammerauf AUSDRUCK klammerzu,
}
Eigentlich sollen wir es noch mit Potenz machen:
POTENZ::=name | zahl | klammerauf AUSDRUCK klammerzu
dann muss Faktor und die anderen verändert werden, aber ich bin total durcheinander. Keine Ahnung wie und keine Ahnung, wie ich diesen Parser programmieren soll. Hab nur ein dickes ? in meinem Kopf.

LG

ASO, noch ne Frage:
Wenn ich jetzt in Worten beschreiben sollte, bzw. eine logische Struktur als Vorüberlegung aufschreiben soll, was die Arbeitsschritte eines Codierers zu meinem Compiler wären, wie könnt ich das machen?
digi_c
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Mi 08.03.06 16:54 
Nun wenn euer Lehrer euch drangsaliert dann hat er es zumindest gesschaft, denn dein Code sieht ja wirklich ziemlich gut aus :) Und auch die Frage nach dem Herangehen und nicht nach "Cooooodddeee" zeigt doch von einer gewissen Professionalität. Wäre froh gewesen, wenn ich solche hochkarätigen Themen zu futtern bekommen hätte.

Ich stecke nicht so drin in der Materie aber ich weiß nicht, ob das so gut ist, die Token draußen hin zu legen.
Denn du kannst den Befehlsumfang ja nicht einfach erweitern, indem du ein neues Wort reinschreibst, da ja da auch eine gewisse Funktionalität in deinem Programm sein muss, die diesen Befehl ausführt.

Meines erachtens nach geht das so:

  1. Programmdatei laden
  2. Zeile einlesen
  3. Befehl identifizieren
  4. =>Befehlsparameter
  5. diese auslesen
  6. Diese Parameter einem "internen" Befehl übergeben (also du hast einen Befehl "addieren" also baust du eine function add (a,b:integer);
Fortuna Threadstarter
Hält's aus hier
Beiträge: 5



BeitragVerfasst: Do 09.03.06 15:56 
hi,
sorry, ich versteh nicht so ganz, was du meinst :-(
1. Was meinst du mit, dass ich die Token draußen hingelegt habe?
Ich habe bekennte Token in einer Liste(bei mir sind es anfangs 12) und diese wird erweitert, sobald er ein Token liest, was er noch nicht kennt. Dies kann eine bloße Variable sein, wie z.B. der Programmname Rechnung. Das Token ergänzt er in der bekannten Liste an die 13. Stelle im Array, somit hat Rechnung den Tokencode 13 und dieser wird in der anderen Scancodeliste dann auch natürlich vermerkt. Letztere Liste, ist ja die, die der Parser zum bearbeiten bekommt.
Sorry, das untere versteh ich nicht so ganz. Wie üperprüft der Parser so die Syntax?
Rechnet der Parser denn schon aus oder nicht erst der Codierer? Sorry, hab immer noch ein riesen ?:-/
Was muss der Parser denn mit diesen Tokencodes machen? Wie strukturiert er? Wie prüft er? Warum und wie ist die rekursive Struktur umzusetzen?
*help* ?:-(

THX
digi_c
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Do 09.03.06 16:48 
Vielleicht reden wir von zwei verschiedenen Sachen. Du willst doch ein Programm schreiben, dass das ausführt, was in der Anweisungsdatei ist? Also z.B. addiere 2 + 3 subdrahiere 5 usw...
Fortuna Threadstarter
Hält's aus hier
Beiträge: 5



BeitragVerfasst: So 19.03.06 19:43 
nee. nur nen parser, der auf korrekte syntax kontrolliert
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: So 19.03.06 20:52 
Ein 'Scanner' erzeugt aus einer Inputdatei die 'Token', damit der 'Parser' die Syntax anhand der Token prüfen kann. Er erzeugt dabei als Abfallprodukt zwangsläufig einen Syntaxbaum der dann als Grundlage für ein Kompilat oder einen Interpreter herhalten kann.

Scanner zu bauen ist leicht. Gute (=schnelle) Scanner schon etwas schwerer. Parser sind imho für Schüler zu schwer. Nicht weil ihr zu blöd wärd (seit ihr ja nicht), sondern weil man das ganze Hintergrundwissen über Grammatiken, Lookaheads LL,LR, LL(0) etc. kennen sollte. Denn was bringt es, ohne dieses Hintergrundwissen einen dann völlig exotischen und an den Haaren herbeigezogenen Algorithmus implementieren zu müssen?

Parser sind ne echt feine Sache, wer die Sache mit den Grammatiken kapiert hat, ist ziemlich weit Vorne in der Algorithmik.

Na gut, wenn euer Lehrer so ein Schnösel ist. Bitte sehr. Wie war doch gleich die Frage? Ach ja, der Parser.

Wenn die Grammatik das zulässt, programmiert man einen Parser am Einfachsten 'straightforward', indem man die Grammatik 1:1 als Funktionsaufrufe implementiert:
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
P= {
PROGRAMM ::= prog name semikolon BLOCK punkt,
BLOCK ::=begin ZUWEISUNG end,
ZUWEISUNG::=name zuweisungsop AUSDRUCK,
AUSDRUCK ::=TERM|TERM strichoperator AUSDRUCK,
TERM ::=FAKTOR|FAKTOR punktoperator TERM,
FAKTOR ::=name | zahl | klammerauf AUSDRUCK klammerzu,
}


ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
Function IsProgramm (Var S : TSyntaxbaum) : Boolean;
Var
  sName : String;
Begin
  Result := False;
  If IsToken (tkPROG) Then
    If IsIdentifier (sName) Then Begin
      S.AddProgramName (sName);
      If IsSemicolon Then
         If IsBlock (S) Then
           If IsPoint Then
              Result := true;
      End;
End;

Function IsBlock (Var S : TSyntaxbaum) : Boolean;
Begin
  Result := False;
  If IsToken (tkBEGIN) Then
    If IsZuweisung (S) Then 
      If IsToken (tkEND) Then
        Result := True
End;
....

Das Prinzip dürfte klar sein. Dabei ist die Fehlerbehandlung (und vor allen Dingen das korrekte Wiederaufsetzen nach einem Fehler) das große Problem. Denn wer will schon immer nur den ersten Syntaxfehler sehen...?

Die Fehlerbehandlung sähe so aus, das man für jedes 'IF' einen Else-Teil implementieren muss, der dann eben ausgibt (z.B.) 'Identifier erwartet'...

Sei noch anzumerken, das diese 'funktionale Implementierung' bei leibe nicht die Beste ist. Erstens ist sie fehleanfällig, zweitens nicht gut für die Fehlerbehandlung und drittes gibt es Programme, die fertige Scanner, Parser und Compiler als C/Delphi-Code ausspucken. Die bekanntesten Vertreter sind LEX/YACC für C sowie COCO/R für Pascal. Bei www.torry.net bin ich vor ewigen Zeiten mal fündig geworden.

_________________
Na denn, dann. Bis dann, denn.