Parsen einer Aussagenlogischen Formel

[Tobias]

Hallo,

Vor einer weile habe ich schon einmal mein Problem mit der Lösung durch RegExp geschildert. Habe mich dann durch den netten Rat, ein wenig mit dem Thema Parsern beschäftigt und muss zugeben, dass mir das ganze recht fremd ist.
Nocheinmal zur erinnerung: So sieht eine Aussagenlogische Formel aus (latex)
(p\land q) \lor r

Ich formuliere diese Formel in Perl folgendermaßen:

(p1q)2r

Der Parser soll nun erstmal nur prüfen, ob es sich um eine korrekte Formel handelt. Ein weiterer Schritt wäre dann, auch eine Baumartige Struktur aus dem Parsingvorgang zu machen.

Eigentlich dürfte das doch nicht so schwehr sein. Denn der Umfang dieser Formeln ist z.B. im Gegensatz zu Mathematischen Formeln stark eingegrenzt.
ALLES muss geklammert sein. Nur die Äußeren Klammern dürfen weggelassen werden.
Es gibt nur einstellige Variablen von a-z

Es wäre toll, wenn mir einer für diesen konkreten Fall, die ersten Rechenschritte eines Parser aufzeigen könnte, denn das was ich im Internet gefunden habe, ist alles ziemlich komplex und abstrakt.

Schonmal sehr sehr vielen Dank im Vorraus
mit freundlichen Grüßen
Tobias

PS: Anbei noch der bisherige Code:

#!perl
use strict;

my $input = '((p \land q) \lor r)';
my @junctions = ('\land','\lor','\Rightarrow','\iff','\infty');
my @output;

sub rm_whitespaces { # Entfernt alle Leerzeichen
    my $handle = shift;
    $handle =~ s/\s+//g;
    return $handle;
}

sub convert_junctions { # Konvertiert die Junktoren in Zahlen
    my $handle = shift;
    my $i = 1;
    foreach (@junctions) {
        $handle =~ s/\\$_/$i/g;
        $i++;
    }
    return $handle;
}

sub build_array { # Erstellt ein Array von allen relevanten Zeichen
    my $handle = rm_whitespaces(convert_junctions(shift));
    my @letters = split(//, $handle);
    return @letters
}

print build_array($input);
print "\n";
print "\n";

[Markus]

Nabend.

also für mich hört sich das ganz noch einen Problem aus dem Compilerbau aus (anbei möchte ich erwähnen das ich diese Vorlesung gehasst habe). Also mit Latex kenne ich mich gar nicht aus. Allerdings wäre mein Ansatz beim Prüfen ob es sich um eine korrekte Formel handelt, das ich eine Kontextfreie Grammatik (http://de.wikipedia.org/wiki/Kontextfreie_Grammatik) erstelle, daraus mache einen Automaten (zB. http://de.wikipedia.org/wiki/Kellerautomat).
Das ist zwar sehr theoretisch dafür kann man einen solchen Automaten recht gut in einer Programmiersprache umsetzten. Die ersten Schritte einer konkreten Umsetzung kann ich dir nicht nennen da, ich Latex nicht benutze und desweitren macht es leider einiges an Arbeit.

Gruß

Markus