Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Di Mär 19, 2024 08:07

Foren-Übersicht » Sonstiges » Projekte
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 11 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: [Tool] BTCC
BeitragVerfasst: Fr Jun 19, 2015 11:10 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Projekt: BTCC

Hallo allerseits,

es wird einmal wieder Zeit fuer einen Projekt-Thread. Dieses mal moechte ich euch
ein kleines Tool von mir vorstellen an dem ich gerade arbeite. Das Ganze ist eine
Art Compiler fuer eine neue Programmiersprache welche ich parallel dazu entwickle.

Das Tool selbst kann keine ausfuehrbaren Dateien erstellen. Stattdessen generiert
es Objekte die dann vom Compiler in die jeweilige Zielsprache uebersetzt werden. Es
verhaelt sich also im Prinzip wie aeltere C++ Compiler die den Code nach C
uebersetzten und dann den C-Compiler aufrufen. Nur das man halt mit ein paar Anpassungen
auch Java, CIL oder aber einen Interpreter unterstuetzen kann.

Das Ganze ist eine F# Bibliothek und kann daher problemlos ueber Mono auf anderen
verwendet werden. Da aber der Code sehr einfach ist sollte es keine Problem sein hier
auch direkt in eine andere Sprache zu Portieren.

Der Tokenizer

Das Tool benutzt eine einzige Funktion “tokenize” um eine Sequenz von Char in eine
Sequenz von Strings umzuwandeln. Man bekommt in diesen Schritt also keine Objekte, wie
etwa bei Yacc, sondern halt nur den zerlegten String. Hierbei kommt ausschliesslich das
Patternmatching von F# zum Einsatz. Fuer diejenigen die sich darunter nichts vorstellen
koennen. Patternmatching in F# ist eine bessere Form vom “Switch”-Statement. Hier
kann man seinen “Case” fuer Sequenzen, Typen, Member usw. machen. Beim Tokenizer
sieht das in etwa wie folgt aus:

Code:
  1.  
  2.     let rec  tokid acc = function
  3.             | c :: t when Char.IsLetter(c) -> tokid(acc + (c.ToString())) t
  4.             | '_' :: t -> tokid(acc + "_") t
  5.             | c :: t when Char.IsDigit(c) -> tokid(acc + (c.ToString())) t
  6.             | t -> acc, t
  7.     let rec tokenize (acc : string list) = function
  8.             | c :: t when Char.IsWhiteSpace(c) -> tokenize acc t  //ignore whitespace
  9.             | c :: t when Char.IsLetter(c) ->  //starts with a letter so it’s keyword or name
  10.                 let s,t' = tokid "" t  //read the full string
  11.                 match (c.ToString() + s) with
  12.                     | "sizeof" -> tokenize ("sizeof" :: acc) t' //is sizeof keyword
  13.                     | t -> tokenize (t :: "$id" :: acc) t' //is
  14.             | '.' :: '.' :: '.' :: t -> tokenize ("..." :: acc) t
  15.             | '<' :: '<' :: '=' :: t -> tokenize ("<<=" :: acc) t
  16.             | '>' :: '>' :: '=' :: t -> tokenize (">>=" :: acc) t
  17.             | [] -> List.rev acc
  18.             | t -> failwith ("Invalid token near " + (seqstr t)  )
  19.  



Die gesamte Funktion ist in etwa 150 Zeilen um alle Tokens in der Sprache zu erkennen.

Der Lexer

Der Lexer ist eine Funktion welche eine Sequenz von Strings nimmt und uns eine Sequenz
von AST (Abstract Syntax Tree) Deklarationen liefert. Allerdings werden die Sachen da schon
etwas komplexer. Schaut euch einfach mal am besten den Baum an der Dort abgearbeitet wird
und ihr bekommt eine gute Vorstellung davon was wir hier fuer eine Monsterfunktion haben :)

Code:
  1.  
  2.  
  3. type Identifier = string
  4. type Constant = string
  5. type StringLiteral = string
  6. type PrimaryExpression =
  7.     | Constant          of Constant
  8.     | StringLiteral     of StringLiteral
  9.     | Identifier        of Name
  10.     | Expression        of Expression
  11. and Name = Identifier
  12. and PostfixExpression =
  13.     | None
  14.     | ArrayExpression   of PrimaryExpression * Expression list
  15.     | CallExpression    of PrimaryExpression * Expression list
  16.     | MemberExpression  of PrimaryExpression * Name list
  17.     | PostIncrement     of PrimaryExpression
  18.     | PostDecrement     of PrimaryExpression
  19. and UnaryExpression =
  20.     | None
  21.     | Increment         of PrimaryExpression
  22.     | Decrement         of PrimaryExpression
  23.     | Dereference       of PrimaryExpression
  24.     | ReferTo           of PrimaryExpression
  25.     | SizeOf            of PrimaryExpression
  26.     | SizeOfB           of TypeName
  27.     | TypeOf            of PrimaryExpression
  28.     | TypeOfB           of TypeName
  29.     | Minus             of PrimaryExpression
  30.     | Not               of PrimaryExpression
  31.     | Invert            of PrimaryExpression
  32. and BinaryExpression =
  33.     | None
  34.     | Multiply          of Expression * Expression
  35.     | Divide            of Expression * Expression
  36.     | Modulo            of Expression * Expression
  37.     | Add               of Expression * Expression
  38.     | Sub               of Expression * Expression
  39.     | Left              of Expression * Expression
  40.     | Right             of Expression * Expression
  41.     | Less              of Expression * Expression
  42.     | Greater           of Expression * Expression
  43.     | LEqual            of Expression * Expression
  44.     | GEqual            of Expression * Expression
  45.     | Equal             of Expression * Expression
  46.     | NEqual            of Expression * Expression
  47.     | And               of Expression * Expression
  48.     | Xor               of Expression * Expression
  49.     | Or                of Expression * Expression
  50.     | LogicalAnd        of Expression * Expression
  51.     | LogicalOr         of Expression * Expression
  52.     | Cast              of Expression * TypeName
  53. and Expression =
  54.     | Noop
  55.     | PrimaryExpression of PrimaryExpression
  56.     | UnaryExpression   of UnaryExpression
  57.     | PostfixExpression of PostfixExpression
  58.     | BinaryExpression  of BinaryExpression
  59. and PrimaryType =
  60.     | Void
  61.     | Char
  62.     | UChar
  63.     | Short
  64.     | UShort
  65.     | Int
  66.     | UInt
  67.     | Long
  68.     | ULong
  69.     | LongLong
  70.     | ULongLong
  71.     | Float
  72.     | Double
  73.     | LongDouble
  74.     | Bool
  75.     | Struct            of Parameter list
  76.     | Union             of Parameter list
  77.     | Name              of Name
  78.     | Typename          of TypeName
  79. and UnaryType =
  80.     | None
  81.     | Const             of TypeName
  82.     | Volatile          of TypeName
  83.     | Reference         of TypeName
  84.     | Array             of Expression list * TypeName
  85.     | Functor           of Parameter list * TypeName
  86. and Parameter =
  87.     | NamedParameter    of Name * TypeName
  88.     | UnnamedParameter  of TypeName
  89.     | Ellipsis
  90. and TypeName =
  91.     | PrimaryType       of PrimaryType
  92.     | UnaryType         of UnaryType
  93. and DeclarationSpecifier =
  94.     | Type                  
  95.     | Static            
  96.     | Shared            
  97.     | None              
  98. and Declaration =
  99.     | Import            of DeclarationSpecifier * Name * TypeName * Initializer
  100.     | Using             of Name
  101.     | Declaration       of DeclarationSpecifier * Name * TypeName * Initializer
  102.     | Inferred          of DeclarationSpecifier * Name * Initializer
  103.     | None
  104. and Initializer =
  105.     | None
  106.     | Assignment        of Expression
  107.     | Complex           of Compound list
  108. and Statement =
  109.     | Noop
  110.     | Compound          of Compound list
  111.     | Jump              of Jump
  112.     | Selection         of Selection
  113.     | Iteration         of Iteration
  114.     | Assignment        of Assignment
  115. and Assignment =
  116.     | Unary             of Expression
  117.     | Normal            of Expression * AssignmentOp * Expression    
  118. and AssignmentOp =
  119.     | None
  120.     | Normal        
  121.     | MulAssign
  122.     | DivAssign
  123.     | ModAssign
  124.     | AddAssign
  125.     | SubAssign
  126.     | LeftAssign
  127.     | RightAssign
  128.     | AndAssign
  129.     | OrAssign
  130.     | XorAssign
  131. and Compound =          
  132.     | Statement         of Statement
  133.     | Declaration       of Declaration
  134. and Jump =
  135.     | Continue          
  136.     | Break
  137.     | Return            
  138.     | ReturnExpression  of Expression
  139. and Selection =
  140.     | If                of Expression * Statement
  141.     | IfElse            of Expression * Statement * Statement
  142.     | Switch            of Expression * Cases list
  143. and Cases =
  144.     | Case              of Expression * Statement
  145.     | Default           of Statement
  146.     | BreakCase         of Expression * Statement
  147.     | BreakDefault      of Statement
  148. and Iteration =
  149.     | While             of Expression * Statement
  150.     | DoWhile           of Expression * Statement
  151.     | For               of ForParams * ForParams * ForParams * Statement
  152. and ForParams =
  153.     | Declaration       of Declaration
  154.     | Assignment        of Assignment
  155.     | None
  156.     | Expression        of Expression
  157.  


Semantische Analyse
Die Semantische Analyse ist jetzt noch der einzige offene Punkt. Hier wird dann die Bedeutung des
Codes ermittelt und wir erhalten die eigentlichen Objekte die dann nachher vom Programm in den Zielcode
umgewandelt werden. Ein Beispiel:
Eine Variante fuer Deklarationen ist “Inferred”. Hier ist kein Typ angegeben, also muss dieser aus dem
Initializer hergeleitet werden.

Diesen beiden Teile (Code Generation und Semantik) moechte ich dann hier genauer Beleuchten da diese
einfach interessanter sind :)


Testprogramm
Und hier einmal mein kleines Testbeispiel:
Code:
  1.  
  2.  import printf: (str: ptr const char,...) -> void; //import von C Funktionen
  3.  using Test.Textb; //Laden von weiteren Quellcode Dateien, funktioniert aehnlich wie bei D
  4.  
  5. testb : const int { //komplexe Initializer
  6.     printf("hallo world");
  7.     return 12;
  8. }
  9.  
  10. test : (int x,int y) -> void { //eine einfache Funktion
  11.     printf("\"x\" is %i \"y\" is %i",x,y );
  12. }
  13.  
  14. type myStruct : struct {
  15.    x: int;
  16.    y: int;
  17. } { //dies koennte ein konstruktor sein ... sieht aber haesslich aus oder?
  18.  //den Typ an sich finde ich aber schon cool :)
  19. }
  20.  
  21. //die gute alte "main" aus C
  22. static main : (argc : int, argv : ptr ptr char) -> int {
  23.     static makefive : (i: int) -> int = i + argc + 5; //eine Lambda
  24.     for(x := makefive(12); x < 10; x++) { //For Schleifen (waren ein echter Alptraum) ausserdem ist X eine Inferred-Deklaration
  25.     }
  26.     do { //do while Schleifen
  27.         test : ptr const char = "hallo world";
  28.         testb := test;
  29.         if(testb) {
  30.             switch(test) {
  31.                 case retain(testb): //Ein fall-through case
  32.                     printf("retain works");
  33.                 case testb:
  34.                     printf("%s equals %s",test,testb);
  35.                     return 1;
  36.                 default:
  37.                     printf("%s does not equal %s",test,testb);
  38.                     break;
  39.             }
  40.             break;
  41.         } else {
  42.             continue;
  43.         }
  44.     } while(false);
  45.     return 0;
  46. }          
  47.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mo Jun 29, 2015 09:19 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Ok Zeit fuer ein kurzes Update.

Wie bereits im Meinungsthread erwaehnt benoetige ich fuer den naechsten Meilenstein noch die Analyse der Initializer. Am Wochenende bin ich
in diesem Punkt einen grossen Schritt weitergekommen. Und zwar habe ich mir eine Funktion gebastelt welche mir aus einer Expression eine
Liste fuer die intermediate representation und den aktuellen Typen liefert. Man kann jetzt also schon einmal den Typen aller Deklarationen
ermitteln. Am besten sieht man das aber an einen konkreten Beispiel:
Code:
  1.  
  2. x := (fun(12))[3]; //wir wissen das x ein integer ist
  3.  
  4. fun : (x : int) -> [4] int { //denn fun wird aufgerufen und wir greifen auf ein Element des Array zu
  5.     .... //ich weiss allerdings noch nicht ob der Body auch ein Integer-Array liefert
  6. }
  7.  
  8.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mo Jun 29, 2015 20:45 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Zeit für etwas Syntax Sugar!!
Code:
  1.  
  2. fun : (x : int) -> {
  3.     return x,x+1,x+2,[1,2,3]
  4. }
  5.  


Diese kleine Funktion ist ein wahres Magic-Monster, denn sie zeigt einige Neuerungen im Syntax. Denn
das Tool kann jetzt erkennen das es sich hierbei um eine Funktion handelt welche eine Struct zurückgibt!
Das Komma ist jetzt nämlich ein binärer Operator der zwei Expressions in einen Struct umwandelt. Über
eine einfache Funktion kann man dieses gute Stück dann zu einer Liste von Expressions expandieren. Das
wird dann zum Beispiel zum Aufrufen von Funktionen und für den Array-Constructor genommen.

Das Ganze funktioniert super gut da ich jetzt den Shunting-Yard Algorithmus im Parser eingebaut habe. Für
diejenigen die das gute Stück noch nicht kennen: Shunting-Yard erlaubt es sehr schnell Operator-Reihenfolge
zu erkennen. Man bekommt jetzt also auch gleich die richtige Reihenfolge geliefert.

Des Weiteren habe ich noch zwei kleine Neuerungen eingebaut. Zum einen gibt es jetzt Zeilennummern für
Fehlermeldungen und zum anderen gibt es jetzt die Wildcard-Expression "_".

Erinnert ihr euch jetzt noch an die Case-Statements und das Komma? Hier eine kleine Hilfe:
Code:
  1.  
  2. switch(test) {
  3.   case _,12:
  4.       printf("second struct member is 12!");
  5.       return;
  6.    case 12:
  7.       printf("it's just 12!");
  8.       return;
  9. }
  10.  


:mrgreen:

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Do Jul 02, 2015 13:48 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
So lieber Leute ich habe jetzt auch den Typenparser aufgeraeumt. Dort gibt es nun Unterstützung fuer ein einfacheres Typename System, welches dann
besser in Switches usw. genutzt werden kann. Schaut euch einfach mal folgendes Beispiel an:
Code:
  1.  
  2. type fun : struct {sfun1: int->int,member1: int,int->int,sfun2: (arg1:int,arg2:int->int)->int} -> union{ int->int,int->void } -> int;
  3. //oder
  4. type funp : struct {int->int,int,int->int,(int,int->int)->int} -> union{ int->int,int->void };
  5. type funpp : funp -> int;
  6.  

Die Regeln sind eigentlich ganz einfach. :
Ein Typename ist eine Liste von Typennamen die nur einen Eintrag enthält.
Struct bzw. Union ist ein Typename der eine Liste von Typenamen speichern kann
Funktionen nehmen einen Typenamen oder, falls Klammern verwendet wurden, eine Typenamen-Liste als Parameter.
Funktionen haben max. einen Rueckgabewert.
Bei mehreren Typenamen können Elemente einen Namen erhalten
Der Typename fuer Funktionen ist rechtsassoziativ.

Das bedeutet zum Beispiel:
Code:
  1.  
  2. int,int -> int  //Fehler (Type und Funktion)
  3. (int,int) -> int //Funktion
  4. (a:int,b:int) -> int //Funktion(a,b)
  5. struct { a: int->int} //struct{a = Funktion}
  6. a: b: int -> int //Fehler
  7. int -> int,int //Fehler (Funktion und Type)
  8.  
  9.  



[edit]

Achja bei Union gibt es uebrigens einen Sonderfall:
Code:
  1.  
  2. union {
  3.    A,B,C
  4. }
  5.  

sind nur Namen und damit im Prinzip das gleiche wie ein Enum...

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mi Jul 08, 2015 08:34 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
kurzes Update,

ich habe jetzt eine ganze Reihe von "Fehler" behoben und die Module-Klasse fast fertig. Bei den Fehlern ging es hauptsaechlich um solche Probleme die durch meine kurzen
Typenamen entstanden sind. Grob gesagt gibt es jetzt zwei verschiedene Arten Structs und Unions zu definieren. Die erste Variante sollte eigentlich jeder aus C, Java und co.
kennen. Halt normal mit geschweiften Klammern und Name + Type + Semikolon. Die zweite Variante ist die kurze Schreibweise mit normalen Klammern:
Code:
  1.  
  2. struct { //normal
  3.   a : int;
  4.   b : float;
  5. };
  6. struct (int,float); //kurz
  7. struct (a:int;float);
  8.  


Wobei Unions sich hier etwas anders verhalten, denn hier wird der Name und nicht der Typ bevorzugt:
Code:
  1.  
  2. union(a,b); //a und b sind Namen fuer member ... also ein enum
  3. struct(a,b); //a und b sind Typenamen
  4. union {
  5.    a : int;
  6.    b;
  7.    c;
  8. };
  9.  


Daraus ergibt sich auch eine Aenderung bei Typlisten und Funktion. Funktionen benoetigen jetzt immer die Typeliste in Klammern und wenn eine Typenliste nur einen Member enthaelt kann Sie implizit zu einen normalen Typenamen.
Code:
  1.  
  2. int->int; //falsch
  3. (int)->int; //richtig
  4. a : (int); //a ist int
  5.  


So gesehen gibt es jetzt also 3 verschiedene Listenversionen fuer Member und Parameter.


Bei den Modulen, also den eigentlichen Output gibt es auch grosse Fortschritte. Hier gibt es nun die Klassenfamilie Scope (Scope, Exectuable, Module, Loop, Conditional, etc.) welche unter anderen die Dictionaries fuer Variablen, Parameter, Funktionen und Typen liefern. Zum auslesen und verarbeiten gibt es hier die beiden Methoden "ReadNext" und
"BuildNext" welche sich im Prinzip wie das "MoveNext" von IEnumerable verhalten. Sprich man kann Parser und Build wie wild untereinander mixen. Der Idee hierfür kam mir als
ich die Using-Direktiven eingebaut habe. Man will ja schliesslich nicht fuer jede einzelne Datei das Ganze Projekt durchgehen, sondern nur das was man auch wirklich braucht.

"Funktionskoerper" (es ist also ein Ende in sicht :)).

Der Aufruf in C# sieht dann in etwa wie folgt aus:
Code:
  1.  
  2. //Module nimmt Name und Quellcode als Parameter
  3. Scope.Module m = new Scope.Module("main",@"
  4.  
  5. import printf(** const char,...) -> void;
  6.  
  7. main : (argc: int, argv: ** char) -> {
  8.    printf("" hallo world \n"");
  9.    return EXIT_SUCCESS;
  10. }");
  11. while(m.ReadNext()) { //Deklarationen parsen
  12.    
  13. }
  14. if(m.Usings.IsChanged) { //wir koennten jetzt Parallel weitere Datein laden...
  15. }
  16.  
  17. while(m.BuildNext()) { //Deklarationen bauen
  18. }
  19.  
  20. m.GetLastError(); //letzten Fehler
  21.  
  22. foreach(var t in m.Types) {
  23.    if (t.IsFunctor) {
  24.        foreach(var p in t.Parameters) { //gilt fuer Functor und Funktion
  25.        }
  26.        var r = t.Returns;
  27.    } else if (t.IsStructOrUnion) {
  28.        foreach(var m in t.Member) {
  29.        }
  30.    }
  31.  
  32. foreach(var if in m.ImportFunctions) {
  33.  
  34. }
  35.  
  36. foreach(var iv in m.ImportVariables) {
  37. }
  38.  
  39. //hier fehlt das ASM fuer Initializer
  40. foreach(var sv in m.StaticVariables) {
  41. }
  42.  
  43. foreach(var v in m.Variables) {
  44. }
  45.  
  46. //hier fehlt das ASM fuer den Body
  47. foreach(var sf in m.StaticFunctions) {
  48. }
  49.  
  50. foreach(var f in m.Functions) {
  51. }
  52.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Fr Aug 14, 2015 17:01 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hallo liebe Leute,

es hat nach dem Urlaub etwas länger gedauert wieder einen Start zu finden. Aber jetzt bin ich wieder voll drinne und ich habe auch gleich ein paar
tolle neue Features mitgebracht. Als erstes habe ich das System für Typenamen umgebaut so das es jetzt im Großen und Ganzen dem von Java gleicht:
Code:
  1.  
  2. TypeSpecifier =
  3.    | Scalar of BaseType //int,void,name usw.
  4.    | Array of TypeSpecifier //int[]
  5.    | Func of TypeSpecifier * Typespecifier list //int[](int,int)[][] :-)
  6.  


Außerdem habe ich jetzt auch angefangen Klassen zu definieren. Dabei handelt es sich um eine Mischung aus Caml, Java und Smalltalk:

Code:
  1.  
  2.  
  3. struct foo_t : foobar_t {
  4.     {Member und Klassenvariablen}
  5.     {Member und Klassenmethoden}
  6. }
  7. struct bar_t : foobar_t {
  8.      int x;
  9.      int[] ys;
  10. }
  11.  
  12. interface foobar_t { //Reihenfolge spielt keine Rolle :)
  13.     static self alloc();  //siehe "self" weiter unten.
  14.     self init();
  15. }
  16.  
  17. union uberfoobar_t {
  18.     foo_t foo;
  19.     bar_t bar;
  20.     nothing = 0;
  21.     {Member und Klassenmethoden}
  22.     void print() {
  23.        switch(self) { //unions erlauben einen switch über typen
  24.           case foo_t:
  25.           case bar_t:
  26.                  printf("something");
  27.                  break;
  28.           default:
  29.                   printf("nothing");
  30.                   break;
  31.        }
  32.     }
  33. }
  34.  


Self ist hierbei übrigens eine Art besseres "this" das zusätzlich in statischen Methoden die Klasse und in Declaration
den aktuellen Namen der Klasse liefert. Es ist also Vererbung wie bei Objective-C nur halt stark typisiert weil man
kein "id" oder "object" Typen braucht. Kontruktoren sind daher also komplett überflüssig, da Factories in diesen Fall
einfacher und mächtiger sind.

Unions entsprechen zum Großteil der Caml Union und sind eher eine Art Enum auf Steroide. Neu ist allerdings das
Sie auch noch die Eigenschaften eines Interface besitzen, also Methoden definieren. Keine Ahnung ob das
sinnvoll ist, aber ich fand es eine coole Idee um die starre Klassenhierarchie zu umgehen :)

Natürlich gibt es auch weiterhin komplett externe Methoden und Variablen. Man muss also nicht alles wie bei
Java in Klassen packen. Und man kann die Implementierung einer Klasse auf mehrere Source Files auslagern.


Das Ganze hat natürlich den Nachteil das ich dadurch erst einmal Typenableitung auf Eis gelegt habe. Aber ich
sowieso festgestellt das es eine dumme Idee war damit zu beginnen. Stellt euch einfach mal folgendes Beispiel
vor:
Code:
  1.  
  2. static val:=foo();
  3.  
  4. foo: () -> bar();
  5. bar: () -> switch(val) ....  //val benötigt val um aufgelöst zu werden
  6.  

So etwas macht dann natürlichen keinen Spaß :-)

Kurz: die Sprache ist jetzt stark und statisch Typisiert.

Möglich wird das alles durch eine einzige kleine Klasse im Compiler welche die Architektur grundlegend ändert:
Code:
  1.  
  2. Deferred<'a> = {
  3.      Value : 'a
  4.      Tokens : Token list
  5. }
  6.  


Auf diese Weise kann zum Beispiel ein Block von geschweiften Klammern zu einen späteren Zeitpunkt Compeliert werden und man spart sich die
Probleme durch forward Declaration. Außerdem werden dann auch größere Projekte noch schnell Verarbeitet da alles dann sozusagen Compile-By-Need ist :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mo Aug 24, 2015 17:44 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
So liebe Leute, das erste Projekt ist hierfür letzte Woche angelaufen. Das Ganze ist eine Webanwendung welche die Bibliothek als eine Art Template-Engine
zur Generierung von Server und Clientseitigen Code benutzt. Mal schauen wie gut das läuft :)

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mo Nov 30, 2015 18:42 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hallo liebe Leute,

die oben genannte Webanwendung ist nun fertig und es wird Zeit einmal darüber zu diskutieren
wie gut sich der BTCC geschlagen hat. Die gute Nachricht ist das er funktioniert und man tatsächlich
brauchbare Sachen damit bauen kann die auch Geld bringen (jedenfalls mir :)). Die schlechte ist
allerdings das der Code zur Zeit etwas chaotisch ist. Daher ist es natürlich auch sehr aufwendig
Fehler in der erzeugten Sprache zu korrigieren.

Passend zur Adventszeit muss man aber nur 4 Dinge tun um das zu beheben. Diese will ich euch
nun einmal in Art kleinen Tutorial näher bringen. Weihnachten seid ihr dann hoffentlich in der Lage
eure eigenen Compiler zu bauen :mrgreen:

Also hier nun, mit etwas Verspätung, der erste Teil:

Um etwas Ordnung in chaotischen Code zu bekommen bieten einige funktionale Sprache die
Möglichkeit ein Verhalten von mehreren Funktionen in *Trommelwirbel* eine andere Funktion
auszulagern. Diese abstrakten Helfer-Funktionen können dann allerhand lustiger Dinge
vollbringen wenn man Funktionen der gleichen Kategorie kombiniert.

Bei einigen von euch klingeln da natürlich gleich wieder die Alarmglocken, denn Kategorie ist ja
mal wieder so ein böses Wort in unseren Bereich. Zumindest dann wenn man an der Uni zu viel
Haskell gelernt hat und nicht weiß das andere Sprachen sich die Sache etwas einfacher machen :)

Nehmen wir einfach mal folgendes Problem: Ihr habt einen Webservice der euch ein JSON Array mit
den Urls von Bilder liefert. Ihr sollt nun einfach die alle Urls der Bilder ausgeben. In einer
perfekten Welt würde man nun einfach den Webservice aufrufen, den String parsen und für jeden
Eintrag einfach den Wert in die Konsole schreiben.

Da die Welt aber nicht perfekt ist, wisst ihr natürlich das man erst prüfen muss ob der Webservice
eine Antwort gegeben hat, ob die Anwort überhaupt JSON ist und ob das JSON überhaupt die Urls
enthält. Das sind dann wieder eine ganze Reihe von If und Else, oder aber eine Exception die ihr
vermutlich erst abfangt wenn es zu spät ist. Was also tun? Nun ganz einfach, man baut einen Typen
der dieses Fehlverhalten kapselt und eine Factory für diesen Typen:
Code:
  1.  
  2. type Maybe<'a> =
  3.     | Something of 'a //alle in Ordnung
  4.     | Nothing //ein Fehler ist passiert    
  5. type MaybeBuilder() =
  6.     member self.Return(x) = Something(x) //diese Funktion wird aufgerufen wenn wir ein Ergebniss haben
  7.     member self.Zero() = Nothing
  8.     member self.Bind(m,f) =  //diese Funktion kombiniert m mit der Funktion f
  9.         match m with //F# kann jetzt implizit herleiten das m vom Typ Maybe ist
  10.         | Something(x) -> f x
  11.         | Nothing -> Nothing //F# kann jetzt implizit herleiten das f einen Maybe zurückliefern muss
  12.         //also: m ist Maybe<a> und f nimmt ein (a) und liefert Maybe<b>
  13.  


Soweit so gut, nur was bringt das jetzt? Ganz einfach wie F# verfügt über eine besondere Art von
Syntax-Sugar. Und zwar kann man Typen die ein bestimmtes Interface benutzen in sog. Compute-Expression
benutzen (daher auch die seltsamen Namen). :
Code:
  1.  
  2. let random = System.Random()
  3. let maybe50() = MaybeBuilder() {
  4.     if(random.Next(100) = 50) then return "hallo " //.Return
  5.     //Zero()
  6. }
  7. let withMaybe50() = maybe {
  8.     let! x = maybe50
  9.     return x + "world" //.Bind auf x -> .Return()
  10. }
  11.  


Natürlich gibt es nicht nur diese 3 Funktionen im Interface. Man kann auf diese Weise so ziemlich jeden
Sprachelement ein neues Verhalten erteilen.

Für einen Compiler kann man genau das gleichen machen. Das ist dann zwar etwas komplexer aber der Sprung
ist nicht so gigantisch wie man nun glauben könnte. Fragt euch einfach mal warum ich von 4 offenen Punkten
geredet habe :)

Mein Compiler ist im Prinzip eine Funktion die einen Text nimmt und einen umgewandelten Text ausgibt. Dazu
zerlege ich erst den Text in kleine Stücke die zusammengehören. Aus diesen Stücken baue ich dann ein Objekt
welches meinen Quellcode darstellt. Diese Objekt prüfe ich dann auf Fehler und wenn alles korrekt ist gebe
ich den fertigen C-Code zurück. Macht also 4 verschiedene Arten von Funktion die man zu einer 5. Funktion,
den Compiler selbst, zusammenschustert.

Beginnen wir also damit den Text in kleinere Stücke zu zerlegen. Hier sollen die ganzen Operatoren, Keywords
und Literals ausgelesen werden. Viele nehmen hierfür einfach Reguläre Ausdrücke und gut ist. Das bringt aber
auch eine ganze Reihe von Mehraufwand mit sich:
- Eine Regex generiert euch keine Information die Ihr für die Fehlerausgabe braucht. Ihr müsst also wieder
zusätzliche Arbeit investieren um zum Beispiel die Zeilennummer rauszubekommen.
- Bestimmte Tokens sind sehr schwer mit Regex zu bauen. Versucht einfach mal einen String-Literal mit einer
Regex zu parsen. Wenn ihr nicht gerade eine Monster-Regex bauen wollt, dann müsst ihr hier wieder drübergehen
um zum Beispiel die ganzen Escape-Sequenzen zu checken.
- Regex lassen sich sehr schwer kombinieren und man muss daher vieles doppelt machen.
- Ihr könntet auch gleich Yacc und Co benutzen wenn ihr vorgefertigte Tools benutzen wollt :P

Also bau ich mir hier meine eigenen Builder der Funktionen zum Textzerlegen generiert. Dazu gehe
ich immer erst von einer einfachen Funktion aus und arbeite mich dann hoch zu einer etwas komplexe
Code:
  1.  
  2. Text -> Token list //meine Funktion nimmt Text und liefert Tokens.
  3. Text -> Token list * Text //Für Fehler brauche ich noch den Text der keine Tokens enthält.
  4. Text -> Token * Text //Mein Builder kann ganz leicht komplexere Geschichten bauen also fliegt die Liste raus.
  5. Text -> Token option * Text //Damit mein Builder Schleifen bauen kann, muss ich gleich hier schon Fehler erkennen.
  6. int * Text -> Token option * int * Text //Mein Token nicht nur den Textwert enthalten sondern auch die Zeilennummer.
  7. string * int * Text -> Token option * string * int * Text //Außerdem wäre ein Name nicht schlecht.
  8.  


Nun habe ich also den Kopf für eine sehr flexible Funktion. Ich kann damit natürlich nicht nur Listen bauen
sondern das Ganze auch in von den anderen Funktionen aus Aufrufen. Stichwort Call-By-Need. Jetzt sieht das
natürlich noch etwas dreckig aus. Also baue ich mir erst einmal ein paar Helfer-Typen, die ich dann auch
noch einmal später erweitern kann:
Code:
  1.  
  2. type TextStream = {
  3.     Line : int //Zeilen
  4.     Chars : char list  //Listen machen sich besser in F# als string für "dynamische" Daten
  5. } with
  6.     member self.IsEmpty = self.Chars.IsEmpty //ich bin etwas faul :-)
  7.     static member FromString s = {Line = 1; Chars = [for c in s -> c]}
  8. //mein Token ist natürlich
  9. type Token = {
  10.     Name : string //dieser Wert kommt ja bereits aus der Funktion und ist "statisch"
  11.     Line : int
  12.     Value : char list
  13. } with
  14.     //und ein kleiner Helper um temporäre Tokens zu erstellen
  15.     static member JustValue s = {Name = ""; Line = 0; Value = s}
  16.  
  17. type TokenizerFunc = (TextStream -> Token option * TextStream)
  18. type Tokenizer = { //den Namen hole ich mir aus einen Extra Typen
  19.     Name : Token -> string //ihr werdet mir später noch Dankbar sein ;)
  20.     Eval : TokenizerFunc
  21. }
  22.  


Soweit so gut. Jetzt brauchen wir natürlich noch einen Builder der uns das Ganze hübsch
verpacken lässt. Neben unseren Standard "bind","return" und "zero" Funktionen gibt es ja
wie gesagt noch viel mehr Möglichkeiten. Also schauen wir uns erst einmal an wie wir das
Ganze denn nun verwenden wollen:
Für die Keywords möchte ich ganz gerne einfach nur den Text eintragen und gut ist. Also
wäre es nicht schlecht wenn der Builder mit IEnumerable<char> arbeiten könnte. Dieses
Interface wird gleich von einer ganzen Reihe Standard-Geschichten (auch string) unterstützt
und sollte uns daher eine Flexibilität geben.

Bei komplexeren Geschichten wie etwa einen Namen oder Literals reicht das aber natürlich
nicht aus. Da nehme ich einfach eine Funktion die mir für einen Char einen Boolean gibt.
Dadurch kann ich dann ganz leicht solche Sachen wie das TakeWhile von Linq bauen und diese
Sachen wie wild kombinieren. Außerdem gibt es ja schon im .NET diese tollen Funktion wie
Char.IsDigit :-)

Außerdem möchte ich gerne in unseren Expressions die Token-Werte als String haben. Dann wird
die Arbeit noch ein wenig leichter. Alles in allen soll es dann in etwa wie folgt ausschauen:

Code:
  1.  
  2. let keyword str = token(str) { return! str }
  3. let tNull = keyword "null"
  4.  
  5. let tUnicodeChar =
  6.     let hd = ['A'..'F'] @ ['a'..'f'] @ ['0'..'9'] |> Set.ofList
  7.     token("unichar") {
  8.         let! _ = "\\u"
  9.         let! d1 = hd.Contains
  10.         let! d2 = hd.Contains
  11.         let! d3 = hd.Contains
  12.         let! d4 = hd.Contains
  13.         let r =
  14.             Byte.Parse(d1+d2+d3+d4, Globalization.NumberStyles.HexNumber)
  15.             |> char
  16.         return [r]
  17.     }
  18. let tNullOrUniChar = tNull <|> tUnicodeChar
  19.  


Ziemlich cool oder? Dann auf ans Werk:
Code:
  1.  
  2. //wir wollen ja dem Tokenizer Objekt einen Namen geben. Damit wir
  3. //da so wenig Arbeit wie möglich haben bietet sich ein Parameter im
  4. //Builder an.
  5. type TokenBuilder(name) =
  6.     //ReturnFrom ist die implementierung für das "return!" und gibt
  7.     //überlicherweise an das man den Wert als Builder-Ergebniss haben
  8.     //will. Da mein Builder immer wieder neue ToknizerFunc erzeugt kann
  9.     //kann ich das auch gleich für diese Funktionen implementieren und
  10.     //in meinen Builder immer wieder verwenden.
  11.     member self.ReturnFrom(x : TokenizerFunc) = {
  12.         //wir ignorieren den Wert des Token und geben immer
  13.         //den aktuellen Namen des Builder.
  14.         Name = fun _ -> name;
  15.         //Eval ist natürlich unsere TokenizerFunc
  16.         Eval = fun cs ->
  17.             match x cs with
  18.             | Some(r),rs -> Some({r with Name = name}),rs //nur ändern wir den Namen vom Token
  19.             | _ -> None,cs
  20.     }
  21.     //Am Zweihäufigsten braucht man natürlich den Standard-Bind. Dieser
  22.     //sorgt genau wie beim Maybe dafür das wir unseren Tokenizer in
  23.     //Expressions verwenden können.
  24.     member self.Bind(m: Tokenizer, f) = self.ReturnFrom(fun cs -> //den Namen übergeben
  25.         match m.Eval cs with //wir führen den aktuellen Tokenizer aus
  26.         | Some(r),rs ->  //Genau wie bei Maybe prüfen ob ein Ergebniss vorliegt
  27.             //danach wandeln wir das Ergebniss in einen String um damit wir in
  28.             //in unseren Expressions halt den String verwenden können
  29.             let s = new string[|for c in r.Value -> c|]
  30.             let t2 = f(s) //den nächsten Teil der Expression ausführen
  31.             //welcher uns auch einen Tokenizer liefert :-)
  32.             match t2.Eval rs with //Den errechneten Tokenizer ausführen
  33.             | Some(r2),r2s -> //Nur wenn alles gut gegangen ist liefern wir einen Token
  34.                 Some(Token.JustValue(r2.Value)),r2s //Temporären Token zurückliefern
  35.             | _ -> None,cs
  36.         | _ -> None,cs
  37.     )
  38.     //Als nächstes gibt dann noch das "return!" für unsere char->bool
  39.     //Funktionen. Diesen verwenden wir zum Beispiel auch für unsere Strings.
  40.     member self.ReturnFrom(p : char -> bool) = self.ReturnFrom(fun cs ->
  41.         match cs.Chars with //den aktuellen Stream matchen
  42.         //wenn der Stream Inhalt hat, dann prüfe mit der Funktion p
  43.         //ob man den ersten char nehmen will.
  44.         | r::rs when p r ->
  45.             //wenn ja dann geben wir nicht nur den Token zurück, sondern
  46.             //prüfen auch gleich auf '\n' und erhöhen die Zeilennummer.
  47.             if(r = '\n') then  
  48.                 Some(Token.JustValue([r])),{cs with Line = cs.Line + 1; Chars = rs}
  49.             else Some(Token.JustValue([r])),{cs with Chars = rs}
  50.         | _ -> None,cs
  51.     )
  52.     //Jetzt arbeiten wir erst einmal unsere normalen "return" Expression ab
  53.     //Zuerst nehmen wir eine Char-Liste damit wir leichter mit den Wert eines
  54.     //Token arbeiten können.
  55.     member self.Return(c : char list) = self.ReturnFrom(fun cs -> Some(Token.JustValue(c)),cs)
  56.     //Dann gibt es natürlich noch ein "return" für IEnumerable<char>, also
  57.     //z.B. strings die wir in unserer Expression bauen
  58.     member self.Return(s : char seq) = self.Return([for c in s -> c])
  59.     //Dann erlauben wir Expressions die mit unserer char->bool Funktion beginnen
  60.     member self.Bind(m : char->bool, f) =
  61.         let t1 = self.ReturnFrom(m)
  62.         self.Bind(t1,f)
  63.     //Und zum Schluss bauen wir noch eine kleine "Bibliothek" mit Expressions für
  64.     //normale Strings. Als erstes natürlich dann wieder das "return!"-string
  65.     member self.ReturnFrom(txt: char seq) =
  66.         let rec text = function  //rekursive Helfer-Funktion zum bauen unserer Expression
  67.             | [] -> self.Return([]) //wenn wir am string-ende sind dann mach nichts
  68.             | x::xs -> TokenBuilder(name) { //ansonsten baue einen neuen Tokenizer
  69.                 let! _ = (=) x //char->bool Funktion die auf gleichheit mit dem ersten char prüft
  70.                 let! _ = text xs //Wiederhole text mit den restlichen Char-Werten
  71.                 return x::xs //Zurückgeben tun wir dann unseren "string"
  72.             }
  73.         //String in Char-Liste umwandeln und text aufrufen um den
  74.         //Tokenizer für den String zu erstellen.
  75.         text [for c in txt -> c]
  76.     //Jetzt erlauben wir noch den Expressions mit einen string anzufangen.
  77.     member self.Bind(m : char seq,f) =
  78.         let t1 = self.ReturnFrom(m)
  79.         self.Bind(t1,f)
  80. //Dann geben wir dem Builder einen hübschen Alias
  81. let token(name) = TokenBuilder(name)       
  82.  


Uff, geschafft! Jetzt können wir schon ziemlich viel mit unseren Tokenizern machen.
Allerdings brauchen wir noch ein paar kleine Helferlein um komplexere Sachen mit
dem Tokenizer selbst zu bauen. Dafür brauchen wir nur einen Or-Operator:
Code:
  1.  
  2. let (<|>) p q = { //Bauen einen neuen Record
  3.     Eval = fun cs -> //Im Eval
  4.         match p.Eval cs with //lassen wir erst einmal p durchlaufen
  5.         | None,_ -> q.Eval cs //gibt es kein Ergebniss lassen wir Q laufen
  6.         | r,rs -> r,rs //ansonsten nehmen wir das Ergebniss
  7.     Name = fun (t) -> t.Name; //Wer Aufgepast hat weiß das wir jetzt den Namen von p oder q erhalten :-)
  8. } //Record mit Name und Eval ergibt einen Tokenizer :-)
  9.  


Sieht nicht nach besonders viel aus oder? Nun ja so ein "oder" kann ganz tolle Helferlein
bauen die wir jetzt im Nachhinein noch an den Tokenizer hängen können:
Code:
  1.  
  2. type Tokenizer with
  3.     member self.Maybe =  //Für kleine Helferlein die optional sein sollen z.B. der Suffix bei Zahlen
  4.         let t2 = token("") { return [] }
  5.         self <|> {t2 with Name = self.Name}
  6.     member self.Repeat = //Für kleine Helferlein die Wiederholt werden z.B. Ziffern von Zahlen
  7.         let rec many1 (p:Tokenizer) : Tokenizer = (token("") {
  8.             let! r = p
  9.             let! rs = many p
  10.             return r+rs
  11.         } )
  12.         and many p : Tokenizer = (many1 p) <|> token("") {return []}
  13.         {(many1 self) with Name = self.Name}
  14.  


Also dann viel Spaß beim Text zerlegen und bis nächste Woche :-)

[edit]
Hier noch kleines Beispiel.
Die Test-Datei:
Code:
  1.  
  2.  
  3.  
  4. wherenullnullnull
  5.  
  6. hallo world
  7.  

Test Programm
Code:
  1.  
  2. open System
  3. open System.IO
  4. open Tokenizer
  5.  
  6. let isSpace = ['\n';'\r';'\t';' '] |> Set.ofList
  7. let space = token("space") {
  8.     let! s = isSpace.Contains
  9.     return s
  10. }
  11. let keyword str = token(str) {
  12.     return! str
  13. }
  14. let Null = keyword "null" <|> keyword "where"
  15.  
  16. [<EntryPoint>]
  17. let main argv =
  18.     let tmp = File.ReadAllText "TestSource.txt"
  19.     let _,r = space.Repeat.Maybe.RunWithText(tmp)
  20.     printfn "%A" (Null.RunWithStream(r))
  21.     0 // return an integer exit code
  22.  
  23.  
  24.  


Ausgabe:
Code:
  1.  
  2. (Some {Name = "where";
  3.        Line = 3;
  4.        Value = ['w'; 'h'; 'e'; 'r'; 'e'];},
  5.  {Line = 3;
  6.   Chars =
  7.    ['n'; 'u'; 'l'; 'l'; 'n'; 'u'; 'l'; 'l'; 'n'; 'u'; 'l'; 'l'; '\013'; '\010';
  8.     '\013'; '\010'; 'h'; 'a'; 'l'; 'l'; 'o'; ' '; 'w'; 'o'; 'r'; 'l'; 'd';
  9.     '\013'; '\010'];})
  10.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Di Dez 08, 2015 19:15 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Argh, sorry für die Verspätung. Weihnachtsstress usw..

Im ersten Teil habe ich euch ein bisschen in das Builder-Pattern von F# eingeführt und euch gezeigt
wie man damit ganz leicht seinen Text in sinnvolle Teile zerlegen kann. Für einen richtigen Parser
müssen jetzt diese Teile nehmen und daraus richtige Objekte bauen. Daraus entsteht dann logischer
Weise eine Funktion die Text nimmt und uns vielleicht irgendetwas liefert...

Da stellt sich doch gleich erst einmal die Frage aller Fragen. Ist ein Token nicht auch irgendetwas?
Ja, natürlich, unser Tokenizer ist bereits ein Parser. Der Unterschied ist halt nur das man den
Tokenizer spezialisieren um besser mit Texten zu arbeiten. Wer also ganz viel lange Weile hat kann
gerne Überlegen wie man die generische Variante und Tokenizer vereinen kann :)

Nun ja nicht lang gesabbelt hier nun unsere Basistypen:
Code:
  1.  
  2. //Das Parser Ergebniss ist etwas anders als ein Token
  3. type ParserResult<'t> =
  4. //Wenn es etwas gibt geben wir einfach nur den Wert ohne Metadaten
  5.    | Result of 't
  6. //Wenn es nichts gibt holen wir uns die Metadaten um später Fehler auszugeben
  7.     | Error of int * string list
  8. //der Rest ist im Prinzip genau wie beim Tokenizer
  9. type ParserFunc<'t> = Text -> ParserResult<'t> * Text
  10. type Parser<'t> = { Names : string list ; Eval : ParserFunc<'t> }
  11.  


Unser Builder selbst ist dieses auch etwas leichter:
Code:
  1.  
  2. type ParserBuilder(name) =
  3.     //der Rückgabewert wird dieses mal einfach durchgereicht
  4.     member self.Return(x) = {Names = [name]; Eval = fun cs -> Result(x),cs}
  5.     //Parser können mit "return!" einfach weitergereicht werden
  6.     member self.ReturnFrom(x) = {Names = [name]; Eval = x.Eval}
  7.     //unser Parser kann aus mehreren Tokenizer bestehen. Jeder Tokenizer
  8.     //wird mit Zeile und String-Wert verarbeitet. Dann kann der Benutzer noch
  9.     //die Zeile in sein Objekt einbauen.
  10.     member self.Bind(m : Tokenizer,f : (int*string) -> Parser<'a>) = {
  11.        Names = [name]
  12.        Eval = fun cs ->
  13.            match m.RunWithText cs with //Tokenizer ausführen
  14.            | Some(r),rs ->
  15. //Wenn es etwas gibt dann erstelle den nächsten Parser
  16. //Und führe diesen auch gleich aus.
  17.                match (f (r.Line,new string[|for c in r.Value -> c|])).Eval rs with
  18.                | Result(x),xs -> Result(x),xs //wenn es etwas gibt, dann reichen wir das durch
  19. //das gleiche beim Fehler. Nur müssen wir einmal neubauen damit der Rückgabewert generisch
  20. //bleibt. Ggf. kann man hier auch noch weitere Details hinzufügen. Ich packe hier noch den Namen
  21. //des aktuellen Parser dazu, damit man so eine Stacktrace bekommt.
  22.                | Error(el,es),_ -> Error(el,name::es),cs
  23. //Wenn der Tokenizer nicht funktioniert dann geben wir den Namen des Tokenizer
  24. //zurück. Dann weiß der Benutzer was hier erwartet wurde.
  25.            | _ -> Error(cs.Line,m.Names),cs
  26.    }
  27.    //Bei Parsenr ist es genau das gleiche wie beim Tokenizer. Nur dieses mal
  28.    //verarbeiten wir einfach nur den Wert ohne Zeilennummer.
  29.    member self.Bind(p : Parser<'a>,f : 'a -> Parser<'b>) = {
  30.         Names = [name]
  31.         Eval = fun cs ->
  32.             match p.Eval cs with //ersten Parser ausführen
  33.             | Result(r),rs -> //wenn es etwas gibt
  34.                 match (f r).Eval rs with //dann baue den zweiten Parser und führe diesen aus.
  35.                 | Result(x),xs -> Result(x),xs //auch hier reichen wir wieder durch
  36.                 | Error(el,es),_ -> Error(el,name::es),cs //und bauen unseren "Trace"
  37. //auch die Fehler des ersten Parser müssen neugebaut werden damit wir ParserResult<'a> nach
  38. //ParserResult<'b> umwandeln.
  39.             | Error(el,es),_ -> Error(el,es),cs
  40.     }
  41.  


Na, geht doch locker fluffig von der Hand oder? Dann wollen wir mal noch ein paar Funktionen
zum Kombinieren von Parsern definieren:
Code:
  1.  
  2. let parser(name) = ParserBuilder(name)
  3. type Parser with
  4.     static member (<|>) (p: Parser<'t>,q : Parser<'t>) = { //Der 'Or'-Operator
  5.         Names = (p.Names) @ (q.Names)
  6.         Eval = fun cs -> match p.Eval cs with
  7.                          | Result(r),rs -> Result(r),rs
  8.                          | _,_ -> q.Eval cs
  9.     }
  10.     member self.Repeat = //einfache Listen von Ergebnissen
  11.         let rec many1 (p:Parser<_>) : Parser<_> = (parser("") {
  12.             let! r = p //führe p aus
  13.             let! rs = many p //baue einen Parser mit many und führe diesen aus
  14.             return r::rs //und pack das Ergebniss von den anderen Ergebnissen
  15.         })
  16.         and many p : Parser<_> = (many1 p) <|> ((parser("") { return [] })) //many ist many1 oder nichts
  17.         {(many1 self) with Names = self.Names} //wir starten mit many1 damit es immer ein Ergebniss gibt
  18.     //Genau das gleiche wie Repeat, nur dieses mal erwarten wir einen Token zwischen den Elementen
  19.     member self.SeparatedBy (x:Tokenizer) =  
  20.         let rec many1 (p:Parser<_>) : Parser<_> = (parser("") {
  21.             let! r = p
  22.             let! _ = x //unser Trennzeichen zwischen die Elemente legen
  23.             let! rs = many p
  24.             return r::rs
  25.         })
  26.         and many p : Parser<_> = (many1 p) <|> ((parser("") { return [] }))
  27.         let p = {(many self) with Names = self.Names} //dieses mal starten wir mit many, damit es auch leere Listen gibt
  28.         let p2 = parser("") {
  29.             let! xs = p //zuerst führen wir daher die Liste mit Trennzeichen aus
  30.             let! x = self //und abschließen tun wir mit dem normalen Parser
  31.             return xs @ [x]
  32.         }
  33.         {p2 with Names = self.Names}
  34.     //zum Schluss noch ein paar Helferlein zum ausführen.
  35.     member self.RunWithText s = self.Eval s
  36.     member self.RunWithString s = self.RunWithText(Text.FromString s)
  37.    
  38.  


Zum Abschluss noch ein kleines Beispiel:
Code:
  1.  
  2. let isSpace = ['\n';'\r';'\t';' '] |> Set.ofList
  3. let space = token("space") {
  4.     let! s = isSpace.Contains
  5.     return s
  6. }
  7. let keyword str = token(str) {
  8.     return! str
  9. }
  10. let oneBoolean = parser("boolean") {
  11.     let! _ = space.Repeat.OrNothing
  12.     let! l,t = keyword "true" <|> keyword "false"
  13.     return l,bool.Parse t
  14. }
  15. let manyBooleans =
  16.     let comma = keyword ","
  17.     oneBoolean.SeparatedBy(comma)
  18. [<EntryPoint>]
  19. let main argv =
  20.     let tmp = File.ReadAllText "TestSource.txt"
  21.     printfn "%A" (manyBooleans.RunWithString tmp)
  22.     0 // return an integer exit code
  23.  


Mit folgenden Testcode:
Code:
  1.  
  2.  
  3. true,
  4. true,
  5. false,true,true,
  6. false,
  7. true,true
  8.  
  9. hallo world
  10.  
  11.  


Liefert uns:

Code:
  1.  
  2. (Result
  3.    [(3, true); (4, true); (5, false); (5, true); (5, true); (6, false);
  4.     (7, true); (7, true)],
  5.  {Line = 7;
  6.   Chars =
  7.    ['\013'; '\010'; '\013'; '\010'; 'h'; 'a'; 'l'; 'l'; 'o'; ' '; 'w'; 'o'; 'r';
  8.     'l'; 'd'; '\013'; '\010'];})
  9.  
  10.  
  11.  
  12.  
  13.  


Nehmen wir aber folgenden Code:
Code:
  1.  
  2.  
  3.  
  4. hallo world
  5.  


Dann bekommen wir:
Code:
  1.  
  2. (Error (4,["boolean"; "true"; "false"]),
  3.  {Line = 1;
  4.   Chars =
  5.    ['\013'; '\010'; '\013'; '\010'; '\013'; '\010'; 'h'; 'a'; 'l'; 'l'; 'o'; ' ';
  6.     'w'; 'o'; 'r'; 'l'; 'd'; '\013'; '\010'];})
  7.  
  8.  
  9.  
  10.  
  11.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Mi Dez 16, 2015 12:59 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hallo liebe Leute,

ich wollte ja eigentlich mit euch die Validierung durchgehen, als ich das am Wochenende gemacht hatte, habe ich aber festgestellt das es ja
quatsch ist diesen Teil noch einmal in einen Builder zu verpacken. Mit eigenen Funktionen geht das schneller und flexibler. Von daher lasst uns
heute einfach mal einen kleinen Beispiel Parser und dessen Validierung durchgehen. Dann habt ihr auch gleich ein Beispiel wie man die Bibliothek
dann nun eigentlich verwendet.

Damit ihr auch wirklich viel seht, zeige ich euch mal wie man Ausdrücke ausliest und überprüft. Hierfür braucht man als erstes mal zwei kleine Typen. Der eine spiegelt das Typen-System der Ausdrücke wieder und der andere den Ausdruck selbst:
Code:
  1.  
  2. type MyBasetype =
  3.     | Integer //Erst einmal die einfach Basis-Typen
  4.     | Double
  5.     | String
  6.     | Boolean
  7.     | Object    of Map<string,MyBasetype> //"Structs"
  8.     | Tuple     of MyBasetype list //Ich finde jede Sprache sollte mehrere Rückgabewerte unterstützen
  9.     | Array     of MyBasetype //Ein kleines Attribute für Arrays... Const usw. kann man genauso bauen
  10.     | Functor   of MyBasetype * MyBasetype list //Funktionen mit Rückgabewert * Argumente
  11.     | Typename  of string  //Für Lookups auf unsere Funktionen
  12.     | Unkown  //Unbekannter Type
  13.     | Void
  14. type MyExpression =
  15.     | Integer       of uint64 //Literals
  16.     | Float         of double
  17.     | String        of string
  18.     | Boolean       of bool
  19.     | Identity      of string
  20.     | Null          
  21.     | Object        of Map<string,MyExpression> //Objekt-Aufbau wie bei JS
  22.     | Unary         of MyUnaryOperator * MyExpression //Die ganzen Operationen
  23.     | Postfix       of MyPostfixOperator * MyExpression
  24.     | Binary        of MyExpression * MyBinaryOperator * MyExpression
  25.     | Tuple         of MyExpression list //Tuple-Aufbau
  26.     | Array         of MyExpression list //Array-Aufbau
  27. and MyUnaryOperator =
  28.     | Not
  29.     | Minus
  30.     | Parent
  31. and MyPostfixOperator =
  32.     | Array         of MyExpression
  33.     | Member        of string
  34.     | Call          of MyExpression list
  35. and MyBinaryOperator =
  36.     | Mul | Div | Mod
  37.     | Add | Sub
  38.     | Less | Greater | LEqual | GEqual
  39.     | Equal | NEqual
  40.     | BitAnd
  41.     | BitXOr
  42.     | BitOr
  43.     | And
  44.     | Or
  45.  


Soweit so gut, nun brauchen wir noch eine Funktion zum Prüfen von "MyExpression". Dazu braucht man einfach nur eine Funktion die den Typen ermittelt und eine welche diese auf Kompatibilität prüft.

Code:
  1.  
  2. //Eine kleine Helfer-Variable die unseren Scope simuliert. Für komplexere Geschichten baut man sich
  3. //ganz einfach ein Stack-Objekt das die Typen für den Scope liefert. Zum Testen reicht könnt ihr
  4. //hier aber einfach eine kleine Standard-Bibliothek bauen :)
  5. let scope : Map<string,MyBasetype> =
  6.     ["a",MyBasetype.Integer; //der Identifier a ist ein integer
  7.      "b",MyBasetype.Double;] |> Map.ofList //und b ist ein double
  8.  
  9. let rec testType = function
  10.     | MyBasetype.Unkown,_ -> false //Unbekannt ist immer Inkompatibel
  11.     | _,MyBasetype.Unkown -> false
  12.     | MyBasetype.Void,_ -> false //Void darf nicht kombiniert werden
  13.     | _,MyBasetype.Void -> false
  14.     | MyBasetype.Integer,MyBasetype.Double -> true //Zahlen können wir ohne Probleme hin und her casten
  15.     | MyBasetype.Double,MyBasetype.Integer -> true
  16.     | MyBasetype.Tuple(x),MyBasetype.Tuple(y) -> //Tuple müssen wir Speziell behandeln, da ja auch die einzelnen Member gecastet werden
  17.         testTuple(x,y)
  18.     | x,y -> x = y //Den Rest können wir einfach mit dem Struct-Vergleich prüfen
  19. and testTuple = function //Beim Tuple gehen wir einfach die Liste durch
  20.     | x::xs,y::ys ->
  21.         let t = MyBasetype.Tuple([for x in xs -> testExpression x])
  22.         if testType(t,t) then t //Prüfen ob ein Element "Unknown" ist
  23.         else MyBasetype.Unkown
  24.     | _ -> true
  25. let rec testExpression = function
  26.     | MyExpression.Binary(a,o,b) -> //Für Binäre Ausdrücke
  27.         let ax = testExpression a  //bauen wir erst den Typen vom ersten Operanden
  28.         let bx = testExpression b //dann den Typen des zweiten Operanden
  29.         if(testType(ax,bx)) then //Wenn beide Kompatibel sind
  30.             match o with //Prüfen wir den Operator
  31.             | Less | Greater | LEqual | GEqual //Bei Vergleichen gibt es immer einen Boolean
  32.             | And | Or -> MyBasetype.Boolean
  33.             | _ -> bx //Ansonsten den Typen des zweiten Operanden
  34.         else MyBasetype.Unkown //Falls unsere Typen nicht kompatibel sind geben wir Unbekannt
  35.     | MyExpression.Integer(_) -> MyBasetype.Integer //Jetzt mal kurz die einfachen Literals...
  36.     | MyExpression.Float(_) -> MyBasetype.Double
  37.     | MyExpression.Boolean(_) -> MyBasetype.Boolean
  38.     | MyExpression.String(_) -> MyBasetype.String
  39.     | MyExpression.Null(_) -> MyBasetype.Object(Map.empty) //Eigentlich müssten wir hier einen speziellen Typen bauen
  40.     | MyExpression.Unary(o,x) ->
  41.         match o,(testExpression x) with //Bei Vorzeichen-Operatoren matche ich den Operator zusammen mit den Typen
  42.         | MyUnaryOperator.Minus,MyBasetype.Integer -> MyBasetype.Integer //Minus kann nur mit Zahlen
  43.         | MyUnaryOperator.Minus,MyBasetype.Double -> MyBasetype.Double
  44.         | MyUnaryOperator.Not,_ -> MyBasetype.Boolean //Not nur mit Boolean
  45.         | MyUnaryOperator.Parent,tx -> tx //Klammern lösen wir einfach auf
  46.         | _ -> MyBasetype.Unkown //Der Rest ist nicht definiert
  47.     | MyExpression.Tuple(xs) -> MyBasetype.Tuple([for x in xs -> testExpression x]) //Tuple ergibt einen Tuple :)
  48.     | MyExpression.Array(xs) -> //Beim Array-Constructor holen wir uns den Typen des ersten Elements
  49.         if xs.Length = 0 then MyBasetype.Array(MyBasetype.Unkown)
  50.         else
  51.             let x = testExpression xs.Head
  52.             let mutable bx = true
  53.             for x' in xs do //und prüfen ob dieser Kompatibel mit den anderen Typen im Array ist
  54.                 bx <- bx && (testType (x,testExpression x'))
  55.             if bx then MyBasetype.Array(x)
  56.             else MyBasetype.Array(MyBasetype.Unkown)
  57.     | MyExpression.Postfix(o,x) ->
  58.         let tx = testExpression x
  59.         match o,tx with
  60.         | MyPostfixOperator.Array(i),MyBasetype.Array(y) -> //beim Indexer holen wir uns den Element-Typen des Array
  61.             let it = testExpression i
  62.             if testType(MyBasetype.Integer,it) then y
  63.             else MyBasetype.Unkown
  64.         | MyPostfixOperator.Member(s),MyBasetype.Object(y) -> //bei Member-Ausdrücken holen wir uns den Typen aus der Map des Objekt
  65.             if y.ContainsKey s then y.Item s
  66.             else MyBasetype.Unkown
  67.         | MyPostfixOperator.Call(args),MyBasetype.Functor(f,fargs)  -> //Funktionsaufrüfe
  68.             let targs = [for a in args -> testExpression a] //Erst wandeln wir die Argument in Typen um
  69.             if testTuple(targs,fargs) then f //Danach prüfen wir beide Listen
  70.             else MyBasetype.Unkown
  71.         | _ -> MyBasetype.Unkown
  72.     | MyExpression.Object(xs) -> //Objekt müssen wir einfach Stupide in ein Objekt umwandeln :-)
  73.         let txs = [for x in xs -> x.Key, testExpression x.Value]
  74.         MyBasetype.Object (Map.ofList txs)
  75.     | MyExpression.Identity(m) -> //Bei einen Namen holen wir uns die Sache aus dem Scope
  76.         if scope.ContainsKey m then scope.Item m
  77.         else MyBasetype.Unkown
  78.  


Jetzt braucht man nur einen Parser der uns ein Objekt zum Prüfen liefert. Dafür baue ich mir erst einmal ein paar kleine Helferlein:
Code:
  1.  
  2. open Parser
  3. open AST
  4. open Tokenizer
  5. open System
  6. open System.Globalization
  7.  
  8. let isSpace = (['\n';'\r';'\t';' '] |> Set.ofList).Contains
  9. let isDigit = (['0'..'9'] |> Set.ofList).Contains
  10. let isHexDigit = ((['a'..'f'] @ ['A'..'F'] @ ['0'..'9']) |> Set.ofList).Contains
  11. let isStrChar c = (c <> '\"') && (c <> '\\')
  12. let isEscChar = (['\"';'\\';'/';'b';'f';'n';'r';'t'] |> Set.ofList).Contains
  13. let space = (token("space") { return! isSpace }).Repeat
  14. let letters = (token("letter") { return! Char.IsLetter }).Repeat
  15. let digits = (token("digit") { return! isDigit }).Repeat
  16. let underscores = (token("_") {return! (=) '='}).Repeat
  17. let hexDigits = (token("hexdigit") { return! isHexDigit }).Repeat
  18. let opCode x = token(x) {
  19.     let! _ = space.OrNothing
  20.     let! _ = x
  21.     let! _ = space.OrNothing
  22.     return x
  23. }
  24. let opEnd x = token(x) {
  25.     let! _ = space.OrNothing
  26.     let! _ = x
  27.     return x
  28. }
  29.  
  30. let keyword str = token(str) { return! str }
  31. let expparser = parser("expression")
  32.  
  33. let pIdentifier =
  34.     let pa = parser("identifier") {
  35.         let! l,s1 = underscores
  36.         let! _,s2 = (letters <|> digits).Repeat
  37.         let! _,s3 = (letters <|> digits <|> underscores).Repeat.OrNothing
  38.         return s1 + s2 + s3
  39.     }
  40.     let pb = parser("identifier") {
  41.         let! l,s1 = letters
  42.         let! _,s2 = (letters <|> digits <|> underscores).Repeat.OrNothing
  43.         return s1 + s2
  44.     }
  45.     pa <|> pb
  46.  
  47.  
  48. //helper function to create a parser for operators
  49. let private makeOp x y =
  50.     expparser {
  51.         let! _ = opCode x
  52.         return y
  53.     }
  54. //create parsers for our binary operatores
  55. let private pBinOps =
  56.     makeOp "*"   MyBinaryOperator.Mul <|>
  57.     makeOp "/"   MyBinaryOperator.Div <|>
  58.     makeOp "%"   MyBinaryOperator.Mod <|>
  59.     makeOp "+"   MyBinaryOperator.Add <|>
  60.     makeOp "-"   MyBinaryOperator.Sub <|>
  61.     makeOp "<="  MyBinaryOperator.LEqual <|>
  62.     makeOp "<"   MyBinaryOperator.Less <|>
  63.     makeOp ">="  MyBinaryOperator.GEqual <|>
  64.     makeOp ">"   MyBinaryOperator.Greater <|>
  65.     makeOp "=="  MyBinaryOperator.Equal <|>
  66.     makeOp "!="  MyBinaryOperator.NEqual <|>
  67.     makeOp "&&"  MyBinaryOperator.And <|>
  68.     makeOp "||"  MyBinaryOperator.Or <|>
  69.     makeOp "&"   MyBinaryOperator.BitAnd <|>
  70.     makeOp "^"   MyBinaryOperator.BitXOr <|>
  71.     makeOp "|"   MyBinaryOperator.BitOr
  72. //get the weight of a binary operator
  73. //lower values have a higher precedence
  74. let private wBinOps = function
  75.     | MyBinaryOperator.Mul      -> 1000
  76.     | MyBinaryOperator.Div      -> 1000
  77.     | MyBinaryOperator.Mod      -> 1000
  78.     | MyBinaryOperator.Add      -> 2000
  79.     | MyBinaryOperator.Sub      -> 2000
  80.     | MyBinaryOperator.Less     -> 3000
  81.     | MyBinaryOperator.Greater  -> 3000
  82.     | MyBinaryOperator.LEqual   -> 3000
  83.     | MyBinaryOperator.GEqual   -> 3000
  84.     | MyBinaryOperator.Equal    -> 4000
  85.     | MyBinaryOperator.NEqual   -> 4000
  86.     | MyBinaryOperator.BitAnd   -> 5000
  87.     | MyBinaryOperator.BitXOr   -> 6000
  88.     | MyBinaryOperator.BitOr    -> 7000
  89.     | MyBinaryOperator.And      -> 8000
  90.     | MyBinaryOperator.Or       -> 9000
  91. //shunt our binary expression into form that
  92. //can easily be transformed to asm
  93. let rec private sBinOps op a = function
  94.     | MyExpression.Binary(xb,xop,xc) as b ->
  95.         if((wBinOps op) < (wBinOps xop)) then
  96.             let c = MyExpression.Binary(a,op,xb)
  97.             sBinOps xop c xc
  98.         else
  99.             MyExpression.Binary(a,op,b)
  100.     | b -> MyExpression.Binary(a,op,b)
  101. //helper parser for escape sequences in strings.
  102. let private escChar =
  103.     let replaceEscChar = function 'b' -> '\b' | 'f' -> '\f' | 'n' -> '\n'
  104.                                     | 'r' -> '\r'| 't' -> '\t' | other -> other
  105.     let simple = token("char"){
  106.         let! _ = (=) '\\'
  107.         let! c = isEscChar
  108.         return new string [|for x in c -> replaceEscChar x |]
  109.     }
  110.     let unicode = token("char") {
  111.         let! _ = "\\u"
  112.         let! d1 = isHexDigit
  113.         let! d2 = isHexDigit
  114.         let! d3 = isHexDigit
  115.         let! d4 = isHexDigit
  116.         let r =
  117.             let s = d1 + d2 + d3 + d4
  118.             Byte.Parse(s, Globalization.NumberStyles.HexNumber)
  119.             |> char
  120.         return r.ToString()
  121.     }
  122.     expparser {
  123.         let! l,c = unicode <|> simple <|> token("char") { return! isStrChar }
  124.         return c.Chars 0
  125.     }
  126.  
  127.  
  128. let rec pExpression : Parser<MyExpression> =
  129.     let p = //parse unary expressions, note that this will give unary expression higher precedence than post-fix
  130.         expparser {
  131.             let! _ = opCode "(" //parenthesis
  132.             let! x = pExpression
  133.             let! _ = opCode ")"
  134.             return MyExpression.Unary(MyUnaryOperator.Parent,x)
  135.         } <|> expparser {
  136.             let! _ = opCode "!" //not operator
  137.             let! x = pExpression
  138.             return MyExpression.Unary(MyUnaryOperator.Not,x)
  139.         } <|> expparser {
  140.             let! _ = opCode "-" //unary minus operator for negative values
  141.             let! x = pExpression
  142.             return MyExpression.Unary(MyUnaryOperator.Minus,x)
  143.         }
  144.     //parse integer constants
  145.     let i =
  146.         let x = expparser { //integers are a sequence of digits
  147.             let! l,i = digits
  148.             let b,x = UInt64.TryParse(i)
  149.             if b then return MyExpression.Integer x
  150.         }
  151.         let y = expparser { //or a sequence of hex-digits after "0x" or "0X"
  152.             let! _ = keyword "0x" <|> keyword "0X"
  153.             let! l,h = hexDigits
  154.             let b,x = UInt64.TryParse(h,NumberStyles.HexNumber,CultureInfo.InvariantCulture)
  155.             if b then return MyExpression.Integer x
  156.         }
  157.         x <|> y
  158.     //parse float constants
  159.     let f =
  160.         let frac = token("frac") { //a sequence of digits with "." and another sequence of digits
  161.             let! x = digits
  162.             let! y = "."
  163.             let! z = digits
  164.             return x+y + z
  165.         }
  166.         let exp = token("exp") { //the exponent part of a float
  167.             let! e = keyword("e") <|> keyword("E")
  168.             let! s = (keyword("+") <|> keyword("-")).OrNothing
  169.             let! d = digits
  170.             return e+s+d
  171.         }
  172.         expparser {
  173.             let! _,f = frac //must either be a frac number with optional exponent
  174.             let! _,e = exp.OrNothing
  175.             let b,x = Double.TryParse(f+e)
  176.             if b then return MyExpression.Float x
  177.         } <|> expparser { //or a normal integral with an exponent
  178.             let! _,d = digits
  179.             let! _,e = exp
  180.             let b,x = Double.TryParse(d+e)
  181.             if b then return MyExpression.Float x
  182.         }
  183.     //parse string constants
  184.     let s =
  185.         expparser {
  186.             let! _ = keyword("\"")
  187.             let! s = escChar.Repeat
  188.             let! _ = keyword("\"")
  189.             return MyExpression.String(new string (Array.ofList s))
  190.         }
  191.     //parse boolean constants
  192.     let b =
  193.         expparser {
  194.             let! _ = keyword "true"
  195.             return MyExpression.Boolean true
  196.         } <|> expparser {
  197.             let! _ = keyword "false"
  198.             return MyExpression.Boolean false
  199.         }
  200.     //parse identifier constants (identity)
  201.     let v = expparser {
  202.         let! id = pIdentifier
  203.         return MyExpression.Identity id
  204.     }
  205.     //parse null-constants
  206.     let n = expparser {
  207.         let! _ = keyword "null"
  208.         return MyExpression.Null
  209.     }
  210.     //helper function to handle ambigeous syntax for tuple, call and array-literal
  211.     let expand = function
  212.         | MyExpression.Tuple(args) -> args //if previous expression was tuple, convert to list
  213.         | arg -> [arg] //otherwise create a list with just the argument
  214.     //parse postfix expression
  215.     let rec postfix (exp:MyExpression) : Parser<MyExpression> =
  216.         expparser {
  217.             let! _ = opCode "[" //array indexer; must have just 1 argument
  218.             let! i = pExpression
  219.             let! _ = opEnd "]"
  220.             return! postfix(MyExpression.Postfix(MyPostfixOperator.Array i,exp))
  221.         } <|> expparser {
  222.             let! _ = opCode "(" //call without arguments
  223.             let! _ = opEnd ")"
  224.             return! postfix(MyExpression.Postfix(MyPostfixOperator.Call [],exp))
  225.         } <|> expparser {
  226.             let! _ = opCode "(" //call with arguments
  227.             let! xa = pExpression //check for tuple to get multiple arguments
  228.             let! _ = opEnd ")"
  229.             return! postfix(MyExpression.Postfix(MyPostfixOperator.Call(expand xa),exp))
  230.         } <|> expparser {
  231.             let! _ = opCode "." //member expression
  232.             let! s = pIdentifier
  233.             return! postfix(MyExpression.Postfix(MyPostfixOperator.Member s,exp))
  234.         } <|> expparser { return exp }
  235.     //member assigment for object literal
  236.     let m = typeparser { // <identifier> : <typename>
  237.         let! _ = space.OrNothing
  238.         let! n = pIdentifier
  239.         let! _ = opCode ":"
  240.         let! t = pExpression
  241.         let! _,eol = space <|> opCode ";"
  242.         if eol = ";"    then return n,t
  243.         else if eol.Contains "\n" then return n,t
  244.     }
  245.     //parse object literal
  246.     let o =
  247.         typeparser {
  248.             let! _ = opCode "{" //empty objects
  249.             let! _ = opEnd "}"
  250.             return MyExpression.Object(Map.empty)
  251.         } <|> typeparser {
  252.             let! _ = opCode "{" //object with many assignments
  253.             let! ms = m.Repeat
  254.             let! _ = opEnd "}"
  255.             return MyExpression.Object(Map.ofList ms)
  256.         }
  257.     //parse array literal
  258.     let a =
  259.         typeparser {
  260.             let! _ = opCode "[" //empty array
  261.             let! _ = opEnd "]"
  262.             return MyExpression.Array([])
  263.         } <|> typeparser {
  264.             let! _ = opCode "[" //array with values
  265.             let! xa = pExpression //check for tuple to get multiple values
  266.             let! _ = opCode "]"
  267.             return MyExpression.Array(expand xa)
  268.         }
  269.     //loop-parse binary expression
  270.     let rec binary (exp:MyExpression) : Parser<MyExpression> =
  271.         expparser {
  272.             let! o = pBinOps //get one binary operator
  273.             let! other = pExpression //right-hand expression
  274.             return! binary(sBinOps o exp other) //shunt operator and get next expression
  275.         } <|> expparser { return exp } //or return the current expression
  276.     //primary expressions are constants, identifier, literals or unary expressions
  277.     let primary = expparser {
  278.         let! x = f <|> i <|> s <|> p <|> v <|> n <|> o <|> a
  279.         return! postfix x //wrap result into post-fix expressions
  280.     }
  281.     let px = expparser { //wrap result into binary expressions
  282.         let! x = primary
  283.         return! binary x
  284.     }
  285.     expparser { //finally try to create a tuple, so this one always has the highest precedence
  286.         let! xs = px.SeparatedBy(opCode ",")
  287.         if xs.Length > 1 then return MyExpression.Tuple xs
  288.         else if xs.Length = 1 then return xs.Head
  289.     }
  290.  


Zum Testen nehme ich einfach mal folgendes kleine TestProgramm
Code:
  1.  
  2. ({ x : 5; y : 10; }.x + a + b), a*b
  3.  

und bekomme
Code:
  1.  
  2. Tuple [Double; Double]
  3.  

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: [Tool] BTCC
BeitragVerfasst: Di Mär 15, 2016 10:10 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Nov 08, 2010 18:41
Beiträge: 769
Programmiersprache: Gestern
Hab jetzt den Parser + Beispiel auf GitHub geladen. Den Link findet ihr in meiner Sig.

_________________
Meine Homepage


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 11 Beiträge ] 
Foren-Übersicht » Sonstiges » Projekte


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.048s | 19 Queries | GZIP : On ]