String verarbeiten und ausgeben

[JavaGamer]

Hallo,

ich habe mal wieder ein Problem. Ich bin gerade dabei einen kleinen Parser zu schreiben, nur dieser soll die Kommentare weglassen und überprüfen ob auch alles richtig ist und den Rest danach weiter bearbeiten. Nun zu meinem Problem:

1. Jedes mal wenn die Datei eingelesen wird kommt der Inhalt nacher in komischer Form wieder raus.
2. Wie überprüfe ich, ob es zu jeder geöffneten Klammer auch eine geschlossene gibt und ob hinter jeder Anweisung (alles was keine geöffnete Klammer besitzt und kein Kommentar ist) ein Semikolon ist? (Eine Anweisung kann auch mehrere Zeilen lang sein...)

Also hier mein bisheriger Code:

	public static void checkFile(File file) throws IOException
	{
		loadFile(file);
		
		List<String> contents = new ArrayList<String>();
		
		/*Files.lines(file.toPath())
			.map(s -> s.trim())
			.filter(s -> !s.isEmpty())
			.forEach(s -> lines.add(s));*/
		
	    List<String> lines = Files.lines(file.toPath())
	    	    .map(s -> s.trim())
	    	    .filter(s -> !s.isEmpty())
	    	    .collect(Collectors.toList());
		
		for(int i = 0; i < lines.size(); i++)
		{
			String check = lines.get(i);
			
			if(check.contains("//"))
			{
				int position = check.indexOf("//");
				
				//String result = check.substring(position, check.length());
				String result = check.substring(0, position);
				contents.add(result);
			}
			else
				contents.add(check);
		}
		
		for(int i = 0; i < contents.size(); i++)
		{
			System.out.println(contents.toString());
		}
	}

Die Datei selbst:

include <platformer_v1>

class story_level_1.shd
{
	init()
	{
		game:s_level=1; // the png and shd file of the level
		
		x:start = 1; // the start point to load from
		x:end = 49; // the end point to load
		x:spawn=3; // the spawn point
		x:portal=47; // the portal point
		
		y:start = 1;
		y:end = 22;
		y:spawn=3;
		y:portal=10;
	}
	
	tick()
	{
		if(player == portal)
			level++;
		
		if(player == from 'x:start' to 'x:end')
			level;
		
		if(player == from 'y:start' to 'y:end')
			level;
		
		if(player == (from 'y:end' & 'x:start' to 'y:end' & 'x:end'))
			level;
		
		if(player == (from 'x:end' & 'y:start' to 'x:end' & 'y:end'))
			level;
	}
	
	render()
	{
		game:color_dirt=255,0,0;
		game:color_bedrock=127,0,0;
		game:color_background=0,0,0;
	}
}

Und zum Schluss der momentanige output, der ein wenig falsch ist (so sieht jede Zeile vom output aus, darum hier nur eine Zeile):

[include <platformer_v1>, class story_level_1.shd, {, init(), {, game:s_level=1; , x:start = 1; , x:end = 49; , x:spawn=3; , x:portal=47; , y:start = 1;, y:end = 22;, y:spawn=3;, y:portal=10;, }, tick(), {, if(player == portal), level++;, if(player == from 'x:start' to 'x:end'), level;, if(player == from 'y:start' to 'y:end'), level;, if(player == (from 'y:end' & 'x:start' to 'y:end' & 'x:end')), level;, if(player == (from 'x:end' & 'y:start' to 'x:end' & 'y:end')), level;, }, render(), {, game:color_dirt=255,0,0;, game:color_bedrock=127,0,0;, game:color_background=0,0,0;, }, }]

Würde man jetzt den Output so haben wie er fast sein sollte:

[include <platformer_v1>, 
class story_level_1.shd, 
{, 
init(), 
{, 
game:s_level=1; 
, x:start = 1; 
, x:end = 49; 
, x:spawn=3;
 , x:portal=47; 
, y:start = 1;
, y:end = 22;
, y:spawn=3;
, y:portal=10;
,
 }, 
tick(), 
{,
 if(player == portal), 
level++;, 
if(player == from 'x:start' to 'x:end'),
 level;,
 if(player == from 'y:start' to 'y:end'),
 level;,
 if(player == (from 'y:end' & 'x:start' to 'y:end' & 'x:end')), 
level;,
 if(player == (from 'x:end' & 'y:start' to 'x:end' & 'y:end')), 
level;, 
},
render(), 
{, 
game:color_dirt=255,0,0;
, game:color_bedrock=127,0,0;
, game:color_background=0,0,0;
, }
, }]

Ich denke mal jedem ist aufgefallen das hier mehr Kommans als vorher drinnen sind und das die eckigen Klammern da auch nicht hingehören. Ob dort etwas fehlt habe ich jetzt aber nicht geprüft, da ich das dafür erstmal wieder so schön lesbar haben möchte wie vorher...

Und zudem soll ja Teil zwei des Problems überprüfen ob alles da ist und richtig ist. (Schade dass es hier im Forum anscheinend keine Spoiler mehr gibt...)

Ich hoffe jemand kann mir hierbei helfen.
JavaGamer

 

[daersc]

Hallo JavaGamer,


Ich hab auch schon mal versucht, einen kleinen Java-Parser zu implementiere. Mir war damals allerdings nur das Auffinden von String-Literalen wichtig und ich habe alles andere ignoriert. Die String-Literale habe ich mit ihrer Position in einer Map gespeichert.

1. Jedes mal wenn die Datei eingelesen wird kommt der Inhalt nacher in komischer Form wieder raus.

In deinem Fall liegt das nicht am Einlesen, sondern am Rausschreiben. In Zeile 36 iterierst du über den gesamten Inhalt (mit der Zählervariable i) und gibst jedes mal per

System.out.println(contents.toString());

den gesamten Inhalt der Liste aus (der eben standardmäßig mit den eckigen Klammern und Kommata zwischen allen Elementen der Liste dargestellt wird).

Versuche es stattdessen mit

System.out.println(contents.get(i));

Dafür hast du ja schließlich über die Liste iteriert.

2. Wie überprüfe ich, ob es zu jeder geöffneten Klammer auch eine geschlossene gibt und ob hinter jeder Anweisung (alles was keine geöffnete Klammer besitzt und kein Kommentar ist) ein Semikolon ist? (Eine Anweisung kann auch mehrere Zeilen lang sein...)

Das Zeilenweise Einlesen der Datei würde ich ehrlich gesagt nicht machen - Alleine aus dem Grund, dass einzelne Zeilen in Java in der Regel keine Bedeutung haben. Stattdessen würde ich eher einen Zeichenweisen Stream verwenden und auch die Zeilenumbrüche einlesen und manuell verarbeiten.


Um öffnende und schließende Klammern habe ich mich damals per Rekursion gekümmert: Jede öffnende Klammer ruft die eigene Methode (mit dem "Klammertyp" als Parameter) auf. Eine schließende Klammer vom entsprechenden Klammertyp beendet hingegen die Methode. Wenn das Dateiende zwischendurch erreicht ist, sind die Klammern unvollständig.

Edit: Natürlich sind die Klammern auch dann unvollständig, wenn eine schließende Klammer vom falschen Klammertyp gefunden wird.

Das gleiche sollte man aber auch mit Kommentaren machen! Also zum Beispiel "/*" oder "//" wird als Anfang einer Kommentar-Umgebung gesehen während "*/" oder ein Zeilenende den Kommentar beendet.

Auf ähnliche Weise könntest du auch überprüfen, ob ein Statement korrekt mit einem Semikolon geschlossen wurde - nur das Erkennen des Beginns eines Statements dürfte dann etwas schwerer ausfallen.


Viel Erfolg!

daersc

 

[Network]

Naja theoretisch kannst du auch einfach die Klammer-Auf und Klammer-Zu zählen.
Übersteigt die Klammer-Zu Zahl die Auf Zahl zu irgendeinem Punkt weißt du es gibt zu viele Klammer-Zu.
Übersteigt die Klammer-Auf Zahl die Klammer-Zu Zahl am Ende fehlen Klammer-Zu.

Wo die Klammern fehlen oder zu viel sind lässt sich logisch nicht ermitteln.


Ob ein Semikolon fehlt lässt sich feststellen (oder besser: vermuten) wenn am Ende einer Anweisung kein Semikolon oder kein Punkt steht oder keine Klammer-Auf/Zu oder ein Operator.

 

[daersc]

Naja theoretisch kannst du auch einfach die Klammer-Auf und Klammer-Zu zählen.

Da bin ich anderer Meinung. Nach dieser Methode wäre ein Konstrukt wie

{
    System.out.println("Hallo"
} )

in Ordnung, denn die Anzahl stimmt ja.

Hingegen wenn ich die Sache rekursiv löse, und in einer Variable gespeichert habe, welche Klammer als nächstes kommen muss, damit das syntatkisch in Ordnung ist, kann ich sofort ganz genau angeben, dass ein Klammerfehler existiert und sogar wo genau - nämlich dort, wo eine unerwartete schließende Klammer auftaucht.

 

[Network]

Wenn du es richtig machst geht das schon.
Noch eine kleine Zählerlogik mit einbauen und fertig, bitte nicht stupider hinstellen als es ist.

Hab auh nicht gesagt das deine Lösung falsch ist, habe einfach nur eine iterative Alternative gezeigt,
bin einfach kein Fan von Rekursion.
Rekursieren machen die Mathematiker, richtige Softwaretechniker iterieren.

Und deine rekursive Lösung weiß auch nicht immer wo die Klammer fehlt oder zuviel ist.
Bei deinem genannten Fehler sind zwei Klammern vertauscht, hat aber nichts mit dem eigentlichen Problem das eine Klammer fehlt oder zuviel ist.
Das kann man nur erahnen durch genaue Code Analyse wo wahrscheinlich die Klammer fehlt, aber das wäre auch nicht immer korrekt und ein großer Aufwand.

 

[daersc]

Sorry, so sollte das nicht rüber kommen.

Ich denke nur, es wäre iterativ recht schwierig sich zu merken, welche schließende Klammer als nächstes kommen sollte, und sich das auch über das Ende eines inneren Klammer-Paares hinaus zu merken. Dafür würde sich beispielsweise ein Stack eignen, der sich eben mehrere Zeichen merkt - aber dann kann man doch auch gleich den Methoden-Aufruf-Stack zunutze machen. Das macht das ganze übersichtlicher (in meinen Augen - die tatsächlich die eines Mathematikers sind 😉 )

Das kann man nur erahnen durch genaue Code Analyse wo wahrscheinlich die Klammer fehlt, aber das wäre auch nicht immer korrekt und ein großer Aufwand.

Ja das ist richtig. Der Aufwand ist wohl IMMER zu groß. Nützt ja nicht viel, wenn die Software so schlau ist, dass sie Fehler so genau erkennt, dass sie sie selbst beheben kann - dann bräuchte man ja kaum noch eine Syntax einzuhalten.

Auch die meisten Compiler geben ja nur solche Dinge wie "unerwartete Klammer" aus, wenn eine Klammer an früherer Stelle fehlt.

 

[JavaGamer]

Danke für eure Antworten, damit konnte ich das erste Problem lösen und beim zweiten scheint mir der von @daersc beschriebene Weg der bessere zu sein, jedoch habe ich keine Ahnung wie ich das umsetzten soll.
Und was ist eine Rekursion und was ist eigentlich der Unterschied zwischen Rekursion und iterativ?

 

[keddelzz]

Guten Abend,

eine Programmiersprache (auch wenn sie selbst ausgedacht ist) zu parsen ist je nachdem welche Konstrukte sie unterstützt nicht so einfach umzusetzen.

Lass mich dir grob erklären wie man (Bauer einer Programmiersprache) das macht:
1.) Man programmiert einen Scanner. - Ein Scanner ließt eine Quelltextdatei ein und fasst Zeichen zu sog. "Tokens zusammen". Ein Token ist ein "Wort" der Programmiersprache.
Der Code

variable = 3 + 7;

könnte zum Beispiel durch folgende Tokens repräsentiert werden:

IDENTIFIER("variable")
EQUALS
NUMBER(3)
PLUS
NUMBER(7)
SEMICOLON

Um einen Scanner zu programmieren, muss man jedoch nicht das Rad neu erfinden! Man kann auch sog. Scannergeneratoren zu Hilfe nehmen. (In meiner Uni nehmen wir JFlex - JFlex - The Fast Scanner Generator for Java)

Allerdings muss man sich erst ein bisschen in diesem Hilfswerkzeug einarbeiten.

2.) Nachdem man alle Tokens der Programmiersprache hat, kommt der schwierigere Teil: Das Parsen.
Das Parsen ist jedoch wesentlich komplexer als das Scannen, denn jetzt betrachtet man nicht nur die einzelnen Worte der Programmiersprache, sondern auch den Kontext in dem sie stehen (also z.B. Variablendefinition IN einer Methode, oder Methodendeklaration in einer Klasse).

Man definiert die Sprache mit einer sog. Kontextfreien Grammatik (Kontextfreie Grammatik) aus dieser Grammatik generiert man mit einem Pasergenerator (wie Java Cup CUP oder ANTLR ANTLR) dann den Parser.

Im Fach Compilerbau benutzen wir das Tool Java Cup. Die Bedienung des Tools zu verstehen war eine kleine Herausforderung, aber ich arbeite jetzt gerne damit.

Der Parser spuckt ein Java-Objekt aus, welches der sog. "Syntaxbaum" ist.
Durch den Baum kann man dann durchgehen und die gewünschten Aktionen durchführen. (zB. Codegenerierung beim Compilieren oder ausführen von Code beim Interpretieren)


Neben dem Studium beschäftige ich mich momentan viel mit der Programmiersprache Scala. Für die gibt es eine Bibliothek die meiner Meinung nach besser verständlich ist, als die Tools JFlex und Java Cup (https://github.com/scala/scala-parser-combinators). Allerdings will ich damit nicht sagen, dass du zwingend jetzt die Sprache Scala lernen musst, um erfolgreich einen Parser zu programmieren.


Man kann auch ohne die Tools einen Scanner / Parser bauen, allerdings frage ich mich auch: Warum das Rad neu erfinden?

Ich hoffe du kannst mit meiner Antwort etwas anfangen 😀

mfg - keddelzz

 

[JavaGamer]

Ok, danke. Ich werde es dann mal damit versuchen.