Struktur-Problem, Scriptsprachen-Parser

[Badestrand]

Hi!

Ich bin seit 2 Monaten dabei, eine Skriptsprache und einen Parser dafür zu entwickeln. Dieser Satz war extra provokant gewählt, ich möchte deshalb ein paar Anmerkungen machen (bevor zu viele doofe Kommentare kommen):
- Ich schätze mich als Realist ein und denke nicht, dass ich das Projekt fertig bekomme
- Selbst wenn ich es fertig bekomme, wird es niemand außer mir (und ich vielleicht auch nicht lange) benutzen
- Ich will also keine Konkurrenz-Produkt zu Python oder anderen Sprachen schreiben
- Ich mache das natürlich nur, weil es mir Spaß macht und der Weg ist das Ziel

So, ich will nämlich keine Sachen hören wie "schaffst du eh nicht" oder "was soll das bringen?", alles klar?

Aaaaaalso, ich stelle erstmal vor, wie weit ich bin, was mir noch vorschwebt, und wo mein (ernsthaftes) Problem ist. Ich stecke in diesem Projekt nämlich gerade in einer Art kein-Bock-mehr-weil-ich-nicht-weiterkomme-Phase. Und wenn ich nicht bald weitermache, bin ich aus dem Source draußen und hab keine Lust mehr

Da das recht viel Text wird (glaube ich), danke ich schon mal jedem, der sich das überhaupt durchliest - Zu jeder konstruktiven Kritik bezüglich Design und/oder Code bin ich natürlich offen.

Die Test-Datei:

singleton class XmlNode
	int i
	int j
	Point pt

	bool DoSomething( str s )
		if ( s = "Hallo" )
			return true
		return false

	public str Attribute [ str s ]
		if i=1 and s="blub"
			return "eine kleine Maus"
		elif s = "Harald"
			return ""
		return "nix"

	public int hummer.Get()
		return 0

	public void hummer.Set( int value, val2, double x )
		i = value

	public bool operatorif= (XmlNode node2)
		for z=0 -> 20
			j = hummer

class Point
	int x
	int y

int GlobalFunc( double x, y, int a, str z )
	a = 7
	return a+4

Der Code basiert auf Einrückungen und kennt keine Semikola. Der Rest dürfte ja vertraut aussehen oder selbsterklärend sein Arrays oder ähnliche Strukturen sind übrigens (noch) nicht drin.

Die Datenstrukturen

Als erstes werden die einzelnen Zeilen in LineInfo-Strukturen eingepackt, die sehen so aus:

struct LineInfo
{
	string  file;    // Der Pfad der Datei, also "C:\blabla\bla.txt"
	string  line;    // Die Zeile als ganzer String
	int     linenr;  // Die Zeilennummer... :)
	int     spaces;  // Die Anzahl der Einrückungen, Tabs werden in Leerzeichen umgerechnet
};

Die LineInfo-Strukturen werden dann in Nodes, also Knoten gepackt. Die Knoten repräsentieren die Verschachtelung. Die Datei ist quasi der Root-Knoten, singleton class XmlNode, class Point und int GlobalFunc( double x, y, int a, str z ) sind die Kinderknoten, die wiederum Kinderknoten in der Form von Variablen, Funktionen oder Code beinhalten.
Jede Zeile wird dabei wieder in "Expression"s zerlegt, Ausdrücke also. Ein Ausdruck kann
- irgendein unbekannter String sein, z.B. XmlNode
- ein in Anführungszeichen gesetzter Text sein, z.B. "Heinrich ist stolz"
- ein Keyword wie if, for, class, singleton usw
- eine Zahl, 123 oder 456
- ein Operator, also '+=', '*', '-' usw.
- oder Klammern. Wird in einer Zeile eine Klammer entdeckt, ist der Expression dafür "()" bzw "[]" und das darin-stehende wird als sub-expressions gehandhabt, wie in einem Baum.

class Node
{
	public:
		struct Expression
		{
			enum Type
			{
				STRING,     // XmlNode
				QUOTE,      // "Heinrich ist stolz"
				KEYWORD,    // if / for
				NUMBER,     // 98172
				OPERATOR,   // += % *
				BRACES      // () oder []
			};

			string              text;
			Type                type;
			vector<Expression>  expr;
		};

		LineInfo           line;        // Und Informationen über die Zeile, für Fehlerausgaben
		vector<Expression> expressions; // Die einzelnen Ausdrücke in der Zeile
		vector<Node>       nodes;       // Die Kinderknoten
};

Soweit so gut, das funktioniert soweit.

Was kommen soll:
Jetzt will ich die Nodes parsen. Dazu will ich für jede Ebene bzw jeden Container einen Kontext implementieren, der wie folgt aussehen soll:

struct Context
{
	const Context*         parent;
	vector<Class>          classes;
	vector<Struct>         structs;
	vector<Function>       funcs;
	vector<Variable>       vars;
	vector<Context>        children;
};

Ein Kontext repräsentiert die Sichtbarkeit in seinem Bereich. So gibt es einen globalen Kontext, in dem die globalen Klassen, Variablen, Funktionen usw eingetragen sind. Dieser Kontext hat Kind-Kontexte, wie z.B. Klassen, die dann wiederum eigene Variablen, Funktionen usw haben. In einer (nicht-statischen) Klassen-Funktion sind so z.B. globale Variablen, Klassen-Variablen und die Parameter-Variablen bekannt.

Funktionen sollen zusätzlich zu ihren Eigenschaften und ihrem Kontext noch Code beherbergen können. Da lass ich mir aber noch was einfallen, jetzt kommt erst einmal das nächste Kapitel

Wo es hapert:
Ich weiß einfach nicht, wie ich das Parsen der Nodes implementieren soll Dabei hab ich mit 2 Möglichkeiten angefangen und weiß weder, welche ich nehmen soll, noch ob ich überhaupt eine der beiden nehmen soll

Ich hatte erst alles hard-codiert, wenn ein Knoten geparst werden sollte, wurden nacheinander alle Möglichkeiten durchgegangen: Ist es eine Klasse (das Keyword "class" kommt drin vor), ist es eine Funktion usw. Das hat mich aber irgendwie nicht zufriedengestellt und hat mich stattdessen auf eine zweite Möglichkeit gebracht:

Ich dachte, ich könne das ganze einfach auch flexibel machen. Also hab ich mir eine Datei gebastelt, aus der sogenannte Container geladen werden. Ein Container ist dabei z.B. eine Klasse oder eine Funktion.
Hier ein Auszug der Datei:

name = class
possible_containers = GLOBAL
container = FORCE
preparse = "['singleton'] 'class' STRING [ ':' STRING { ',' STRING } ]"
parse = "['singleton'] 'class' STRING { ':' container.class.name/container.struct.name }"

name = function
possible_containers = class GLOBAL
container = FORCE
preparse = "STRING STRING '(' [ STRING STRING { ',' [STRING] STRING } ] ')'
parse = "GLOBAL.class.name/GLOBAL.struct.name STRING '(' [ GLOBAL.class.name/GLOBAL.struct.name STRING { ',' [ GLOBAL.class.name/GLOBAL.struct.name ] STRING } ] ')'"

Ist nicht nicht ganz ausgereift, vor allem das Element "parse". Die Idee war, diese Container-Typen zu laden und dementsprechend die Nodes zu parsen. Der Container "function" z.B. darf in einem Container mit dem Namen "class" oder dem globalen Container enthalten sein, "function" muss auch selber ein Container sein und der PreParse-String dient zum Parsen, ob eine Node nun ein "function"-Container ist oder nicht.
Das Pre-Parsen funktioniert auch, nur wird es schwierig, weiterzumachen. Wie soll ich so z.B. spezifizieren, dass ein "elif" (sowas wie "else if") nur nach einem "if" kommen darf? Und wie soll ich so Warnungen bzw Fehler rausschmeißen, wenn zwei gleich-priorisierte Operatoren ohne Klammern verwendet werden?
Außerdem müsste beim Pre-Parsen der Klasse ihr gleich schon Eigenschaften zugewiesen werden, damit diese beim richtigen Parsen dann abgefragt werden können, müsste dann etwa so aussehen:

preparse = "['singleton'] 'class' STRING [ ':' STRING { ',' STRING } ]"
->
preparse = "['singleton'->stand_alone] 'class' STRING->name [ ':' STRING->parent_class { ',' STRING->parent_class } ]"

Bei komplexeren Containern wird das ein unüberschaubares Wirr-Warr, das das Konzept des einfachen und flexiblen Containers zunichte macht.

Und genau hier weiß ich nicht weiter. Ich weiß nicht, wie ich die Knoten in Klassen und Funktionen unterteilen soll, ich weiß nicht, wie genau ich die Operatoren spezifizieren soll - ich bin mir unsicher, ob ich schon einmal soviel wie möglich parsen soll oder erst ein paar Elemente integrieren und den Rest dazunehmen soll, ich brauche einfach Hilfe

Wenn jemand eine gute oder konkrete Ideen hat, immer her damit! Sonst verzweifele ich noch oder werfe das Projekt hin, wäre ja auch doof

Und an die Mods: Bitte nicht in "Rund um die Programmierung" verschieben Da tummeln sich auch die ganzen Javaianer, Assembler-Freaks, Webleute und was weiß ich wer... Ich fühl mich so gut aufgehoben im cpp-Forum und will hier auch bleiben..

Ach, und noch was: Ich kann die nächsten Tage nicht sooo viel Online sein, also bitte nicht wundern, wenn ich nicht sofort antworte Am Samstag fahr ich dann auch in den Urlaub, ab da (ich hoffe da habt ihr mir dann schon geholfen :)) werd ich dann auch ne Woche nicht mehr schreiben..

[Willy Wonker]

Also prinzipiell geht es ja darum den ursprungstext in typisierte strukturen zu bringen, und die grammatik irgendwie abzubilden.
Das parsen an sich kann man noch in einige unterpunkte aufbrechen:
- das einlesen des datenstroms
- das tokenisieren (also das herstellen der beziehung zu den atomischen bestandteilen einer expression) (if -> keyword)
- die klassifizierung des tokens (if -> keyword -> IF_STATEMENT)

wenn du also das IF_STATEMENT als bestandteil der menge der keywords siehst dann kannst du leicht diese dinge abstrahieren. (enum)

Zu deinem anderen problem, wie du es schaffst ein elif einem if zuzuordnen.
Welche art von parser schreibst du denn? is er rekursiv absteigend oder tabellengesteuert? In jedem fall geht es aber darum die information das es ein "if" (oder generell ein block) ist mitzuliefern bzw./oder die information einer block-terminierung zurückzuliefern.

Ich empfehle: The Dragon book, Alfred V Aho, (Compilerbau, Niklaus Wirth is auch ok)

[Basingstoke]

vielleicht solltest du dich mal mit boost::spirit beschäftigen.
so wie ich das verstanden hab haben die da ein Parser Framework
entwickelt mit dem du auch deine eigene Grammatik zusammen-zaubern
kannst.

[Badestrand]

Willy Wonker schrieb:

Also prinzipiell geht es ja darum den ursprungstext in typisierte strukturen zu bringen, und die grammatik irgendwie abzubilden.
Das parsen an sich kann man noch in einige unterpunkte aufbrechen:
- das einlesen des datenstroms
- das tokenisieren (also das herstellen der beziehung zu den atomischen bestandteilen einer expression) (if -> keyword)
- die klassifizierung des tokens (if -> keyword -> IF_STATEMENT)

wenn du also das IF_STATEMENT als bestandteil der menge der keywords siehst dann kannst du leicht diese dinge abstrahieren. (enum)

Ja, so in etwa hatte ich mir das auch gedacht. Also einfach hardcoden? Mein Problem war ja unter anderem, dass ich nicht weiß, ob ich solche Schlüsselwörter hardcoden soll oder nicht - aber du hast wahrscheinlich recht, ich sollte es erstmal im Code implementieren!

Willy Wonker schrieb:

Zu deinem anderen problem, wie du es schaffst ein elif einem if zuzuordnen.
Welche art von parser schreibst du denn? is er rekursiv absteigend oder tabellengesteuert? In jedem fall geht es aber darum die information das es ein "if" (oder generell ein block) ist mitzuliefern bzw./oder die information einer block-terminierung zurückzuliefern.

Ich weiß ehrlich gesagt nicht, wie man die Parser-Art nennt, ich kenne mich da überhaupt nicht aus...

Willy Wonker schrieb:

Ich empfehle: The Dragon book, Alfred V Aho, (Compilerbau, Niklaus Wirth is auch ok)

Hole ich mir, danke!
edit: Oha, 84€... Muss ich mir überlegen

Basingstoke schrieb:

vielleicht solltest du dich mal mit boost::spirit beschäftigen. so wie ich das verstanden hab haben die da ein Parser Framework entwickelt mit dem du auch deine eigene Grammatik zusammen-zaubern kannst.

Gucke ich mir gerade an, danke auch dir!

[WeaponX2007]

Badestrand schrieb:

Willy Wonker schrieb:

Also prinzipiell geht es ja darum den ursprungstext in typisierte strukturen zu bringen, und die grammatik irgendwie abzubilden.
Das parsen an sich kann man noch in einige unterpunkte aufbrechen:
- das einlesen des datenstroms
- das tokenisieren (also das herstellen der beziehung zu den atomischen bestandteilen einer expression) (if -> keyword)
- die klassifizierung des tokens (if -> keyword -> IF_STATEMENT)

wenn du also das IF_STATEMENT als bestandteil der menge der keywords siehst dann kannst du leicht diese dinge abstrahieren. (enum)

Ja, so in etwa hatte ich mir das auch gedacht. Also einfach hardcoden? Mein Problem war ja unter anderem, dass ich nicht weiß, ob ich solche Schlüsselwörter hardcoden soll oder nicht - aber du hast wahrscheinlich recht, ich sollte es erstmal im Code implementieren!

Im ersten Schritt finde ich die Überlegung sinnlos, da das Ding erstmal laufen soll. Auch wenn im Design Goal vielleicht was anderes steht.
Die Schritte zum vollwertigen Compiler oder Interpreter bergen weitaus gröbere Probleme als die Frage ob keywords hardcoded sein sollen oder nicht
Bauen mal den Parser auf. Schau zu das du einfache arithmetische operationen durchführen kannst. Achte auf operator präzedenz und distributiv gesetz.
Bilde Bedingungen ab und erstelle das Framework für loops.

Du kannst auch mal versuchen deine Sprache in BNF abzubilden und dir dann über die implementation der einzelnen Punkte angefangen wieder bei den expressions gedanken machen.

Willy Wonker schrieb:

Zu deinem anderen problem, wie du es schaffst ein elif einem if zuzuordnen.
Welche art von parser schreibst du denn? is er rekursiv absteigend oder tabellengesteuert? In jedem fall geht es aber darum die information das es ein "if" (oder generell ein block) ist mitzuliefern bzw./oder die information einer block-terminierung zurückzuliefern.
Ich weiß ehrlich gesagt nicht, wie man die Parser-Art nennt, ich kenne mich da überhaupt nicht aus...

Bring mal ein Beispiel, dann kann ich dir da helfen.

Willy Wonker schrieb:

Ich empfehle: The Dragon book, Alfred V Aho, (Compilerbau, Niklaus Wirth is auch ok)

Hole ich mir, danke!
edit: Oha, 84€... Muss ich mir überlegen

Basingstoke schrieb:

vielleicht solltest du dich mal mit boost::spirit beschäftigen. so wie ich das verstanden hab haben die da ein Parser Framework entwickelt mit dem du auch deine eigene Grammatik zusammen-zaubern kannst.

Gucke ich mir gerade an, danke auch dir! [/quote]

Funktioniert, ist aber sehr hässlich!!

WX, Gestern Willy Wonker

[phlox81]

Also fürs parsen ist boost::spirit sicher einen Blick wert.
Insbesondere spirit2.0 dürfte dich da dann unterstützen. Es bietet die Möglichkeit vor den Parser einen Lexer zu schalten, und auch während des Parsens entsprechende Lexerstates setzen zu können. Mit Spirit definierst du dir einfach in einer bestimmten Syntax deine Regeln die du parsen willst, und kannst dann entsprechend darauf reagieren. In den Examples ist übrigens schon eine kleine Skriptsprache dabei, die nicht ganz so komplex ist, wie was du da vor hast, aber ist für dich sicher interessant da mal einen Blick reinzuwerfen. Im Magazin ist schon ein Artikel zu boost::spirit, und es müsste bald ein weiterer erscheinen.

phlox