regulärer Ausdruck: ^ $

[diggaa1984]

hiho,

ich bau mir grad nen Scanner für kontextfreie Grammatiken .. der einigermaßen universal zumindest unterscheiden soll ob es sich um Terminale, Kommentare oder diverse Spezialdaten handelt, welche dynamisch im Scanner eingebracht werden können.

Nach den der Scanner Token nur Anhand von definierten Trennzeichen erkennen kann ergibt sich also das bspw solche Strings enstehen:

1234.5678E-5 .. sowas soll bspw. bei meinem Editor als Float erlaubt sein. Dezimalzahlen sind ebenfalls erlaubt .. und werden nicht als Teil der Grammatik formuliert sondern per Platzhalter eingebunden, sprich eine Regel in der Grammatik könnte so aussehen:

Number = INT | FLOAT

wenn man Dezimalzahlen und Gleitkommazahlen in der Grammatik verwenden möchte.
Diese kann ich selbstverständlich nur mittels regulärer Ausdrücke definieren.

INT = \\d+
FLOAT = (\\d+\\.\\d+([eE]?[-+]?\\d+)?)

nun passiert im Scanner folgendes: ich splitte den Eingabestring gemäß der Trennzeichen die eingestellt sind, erhalte also zum Beispiel einen Teilstring der Form

1234.567e+10

Der Scanner prüft nun seine bekannten Daten und kommt nun zu den Dezimalzahlen. Diese matchen 3x auf diesen String. Das ist natürlich verkehrt, denn es handelt sich um eine Gleitkommazahl. Nun habe ich mal folgendes in einem TestApplet für reguläre Ausdrücke probiert:

^\\d+$

: das würde nicht mehr auf diesen String matchen, die Frage die ich mir Stelle ob das eine sichere Option wäre im Scanner, um den definierten regulären Ausdrücke herum jeweils diese Zeichen zu setzen und dann zu prüfen ob auch wirklich der komplette String als übereinstimmend erkannt wird.

Kann man dabei auf die Nase fallen, wenn man das implizit bei allen regulären Ausdrücken macht, die NICHT zeilenübergreifend sind.
Zeilenübergreifend wäre zB ein Blockkommentar, da würde das natürlich nicht klappen (da der Scanner den Text des Kommentars ja auch per Delimiter trennt)

 

[xorm]

Hm eigentlich würde ich sogar sagen, dass du ^ und $ hinzufügen solltest. Sonst wäre es möglich, dass dir irgendwelche Daten untergeschoben werden, in denen das Muster zwar enthalten ist, drumrum aber noch haufenweise andere Dinges stehen können.
Abhängig davon, wie du mit Leerzeichen umgehst würde dir jedoch noch empfehlen am Anfang und am Ende des regulären Ausdruck eine optionale Zahl von Leerzeichen hinzuzufügen. Sonst wird deine Zahl unter Umständen nicht als Zahl erkannt wenn am Anfang oder am Ende ein Leerzeichen steht.

Das hat jetzt zwar nicht direkt etwas mit deiner Frage zu tun aber unter Umständen solltest du auch daran denken das bei \\d+ auch führende Nullen möglich sind. Abhängig davon, was du mit den Daten machst könnte das eventuell von Bedeutung sein.

 

[pexx]

Hi.

hab auch ma nen lexer gebaut. beim scannen wird sofort der erste akzeptierende DFA (oder in deinem fall regex) genommen. seine priorität (also index in der liste) entscheidet welcher Matcher vorzug bekommt. du müsstest dein FLOAT also einfach vor INT definieren (und den ersten regex der anspringt akzeptieren).

da du den eingabestring aber schon zu beginn an separatoren teilst, könntest du im regex auch ^bla$ nehmen. das würde aber zu problemen führen wenn die sprache so formuliert wird, dass trennzeichen(space,tab,newline?) eine bedeutung bekommen (bsp. python) oder wenn ein freizeichen in nem string auftaucht (überhaupt fand ich das korrekte matchen von strings mit maskier-zeichen und so am schwierigsten).

und mit den zeilenübergreifenden Regeln (ausser strings) solltest du den lexer glaub nicht belasten. das ist schon arbeit des kellerautomaten.


mfg

 

[diggaa1984]

an diese Reihenfolge des matchens dachte ich auch erst, finde ich aber zu wage, daher kam die Idee mit den ^...$

Es ist zwar möglich diese Annahme anzugeben und es dem Programmierer zu überlassen die richtige Reihenfolge zu beachten, dennoch macht es die Fehlersuche extrem schwierig wenn man dabei schusselt. Ich persönlich kenne ja nun das Programm von der 1. Zeile an, aber wenn später die Leute vom Lehrstuhl mal darin rummehren wollen dann kann sowas schnell mal schief gehen, denke ich.

Da das ganze ja dynamisch funktionieren soll, dachte ich zunächst an die Variante Trennezeichen programmatisch vorzuschreiben und dann noch einmal dynamisch zu testen, welche Trennzeichen explizit in der Grammatik selbst auftauchen als Terminal der Länge >= 2 .. Wichtig hierbei, Trennzeichen können durchaus noch vom Scanner als Token erkannt werden!!

Wenn ich bspw ( und ) als Trennzeichen nutze (im Editor ja durchaus brauchbar) .. dann macht es nix, wenn diese auch alleinstehend in der Grammatik vorkommen, denn sie werden ja dennoch erkannt. Wenn es aber ein Terminal in der Grammatik gibt wie zB:
)? .. dann würde das natürlich mit der Klammer als Trennzeichen schief gehen, das kann ich vorher ohne Probleme erkennen und dann die Klammer als Trennzeichen entfernen.

Die Sache ist eben, das der Editor für alle kontextfreien Grammatiken funktioniert und der Parser, welcher selbigen Scanner nutzt damit die Token erhält. Quasi ein Universalscanner auf oberer Ebene. Er erkennt Terminale, Kommentare, Unbekannte Strings und Wildcards (die sind hard codiert, biser PLACE, INT, FLOAT) je nach aktivierter Grammatik (zur Laufzeit wechselbar).

Der ebenfalls universale Parser (CYK-Algorithmus) müsste sich bei Terminalen noch die entsprechende Regel suchen, bei Unbekannten kann er gleich abbrechen etc.

und mit den zeilenübergreifenden Regeln (ausser strings) solltest du den lexer glaub nicht belasten. das ist schon arbeit des kellerautomaten.

Zeilenübergreifende Regeln? .. nene nur zeilenübergreifende "Terminale" in dem Sinn .. also Blockkommentar wäre soetwas .. da kann ich locker mit bisher 3 States im Scanner auskommen (NONE, SINGLELINE, MULTILINE) .. SingleLine = Zeilenkommentar --- Multiline = Blockkommentar ... eventuell finden sich da mal noch später weitere Anwendungen für, aber das wäre was ich mit dem Editor auch können muss!

 

[pexx]

nene nur zeilenübergreifende "Terminale" in dem Sinn .. also Blockkommentar wäre soetwas ..

ok an mehrzeilige kommentare hab ich nicht gedacht. das is definitiv aufgabe des scanners

nochma zum eigentlichen problem.. wenn dein splitten nach trennzeichen klappt seh ich keinen grund die Regex-Grenz-Operatoren nich zu verwenden.

aber trotzdem, was ist daran verkehrt die priorität entscheiden zu lassen? ich meine jemand der dein programm nutzt um ne sprache oder ein compiler zu basteln sollte schon wissen was er tut oder

 

[diggaa1984]

hm das mit den trennzeichen ist vielleicht doch ne dumme idee, wenn ich davon ausgehen darf, das ja beliebige kontextfreie grammatiken gescannt werden müssen .. irgendwas könnte also definitiv schief gehen.

momentan bin ich wieder auf dem dampfer des ... "ich such alles was ab dem 1. Zeichen matcht, und nehme davon den längsten Match sozusagen .. token basteln, string kürzen, wiederholen" ... hier allerdings das problem, das ich meine pattern für kommentare ändern können muss!?

so ein: /* foo */ ... die begrenzer können ja durchaus auch mal teil der grammatik sein ^^

 

[pexx]

ok, dann war das splitten wohl doch nicht sone gute idee.

hab mal meinen source raus gesucht, der funktioniert bis jetzt ganz gut läuft halt so, dass der offset immer um die anzahl der gefundenen zeichen des akzeptierenden matchers erhöht wird, bis das string-ende erreicht is.

public void tokenize (String source, int flags) throws LexerException {
	tokens = new ArrayList <Token> ();		
	int sLen = source.length();
	int lexPos = 0, t;				
	...				
	Acceptor e;				
	/*	Acceptor'en sind Objekte, welche einen String, beginnend
		ab einer Startposition, akzeptieren oder eben nicht.
		wenn der akzeptiert gibt der den neuen offset zurück, sonst
		Acceptor.NOT_ACCEPTED */
	
	// lese bis ende (lexPos == sLen-1)
	while (lexPos < sLen) {			
		accepted = false;	
		
		tokenizing:		
		for (int i = 0; i < reader.length; i++) {				
			// durch alle acceptor'en iterieren	
			
			e = reader[i];				
			if ( (t = e.read(source, lexPos)) != Acceptor.NOT_ACCEPTED ) { 
				// akzeptiert		
				
				lexPos = t;
				accepted = true;						
				tokens.add(
					new Token(e.getType(), e.getOutput())
				);						
				break tokenizing;
			} 				
		}			
		... // keiner hat akzeptiert --> exception
	}				
	...
}

public interface Acceptor {
	public static final int NOT_ACCEPTED = -1;

	public int read(String in, int startAt);

	/**
	 * resets dfa
	 */
	public void reset();

	/**
	 * get lexem or generated output
	 * @return output
	 */
	public String getOutput();

	/**
	 * get type of acceptor
	 * @return type
	 */
	public String getType();

}

Die oben verwendeten Acceptor-Objekte hab ich aus didaktischen Gründen als Endliche Automaten oder Mealymachines implementiert. Man könnte aber genauso Regexe benutzen.

Ein Kommentar wäre dann einfach einer dieser Acceptoren, der später (je nach bedarf) aus der resultierenden ArrayList entfernt wird.

hoffe das hilft ein bisschen,
ciao