Linksrekursion entfernen

[Maik Görgens]

Hallo!

Ich will das Perl-Modul Parse::RecDescent verwenden. Der versteht aber keine Linksrekursion. Deshalb meine Frage. Wie kann ich aus folgendem Grammatik-Teil die Linksrekusion entfernen?

predicate:  '(' predicate ')'
          | predicate (/AND/i | /OR/i) predicate
          | expression ('=' | '<' | '<=' | '>' | '>=' | '<>')

Ich hab schon eine Reihe Beispiele gesehen, wie man das eigentlich macht, aber ich kriegs nicht auf meinen Fall übertragen.

Vielen Dank für Eure Hilfe!
Maik

[seth]

gudn tach Maik!

ist schon spaet, aber vielleicht isses ja richtig (ungetestet):

predicate: '(' predicate ')' | '(' predicate ')' andor predicate | expression symb andor predicate | expression symb
    andor: /AND/i | /OR/i
    symb: '=' | '<' | '<=' | '>' | '>=' | '<>'
    expression: 'foo'

ich habe also aus "predicate andor predicate" per fallunterscheidung "'(' predicate ')' andor predicate | expression symb andor predicate" gemacht.

prost
seth

[seth]

gudn tach!

ich habe jetzt mal bei mir Parse::RecDescent installiert und ein bissl damit rumgespielt. "top-down recursive-descent" heisst wohl, dass das ding nicht intelligent ist und backtracking betreibt, sondern stur von oben nach unten die grammatik abarbeitet und immer die erste passende regel nimmt. (in der doku steht auch was dazu)

deswegen ist symb: '=' | '<' | '<=' | '>' | '>=' | '<>' schlecht, weil im ausdruck '<=' das erste zeichen '<' zwar gefunden wuerde, aber das '=' dann nicht mehr.
kurz: die reihenfolge ist wichtig.

deine urspruengliche grammatik koennte also imho lauten:

predicate: '(' predicate ')' (op predicate)(?) | expression symb (op predicate)(?)
op: and | or
expression: 'foo'
symb: '<=' | '>=' | '<>' | '>' | '=' | '<'
and: /AND/i
or: /OR/i

dann sind z.b. folgenden ausdruecke in der sprache enthalten:
foo=
foo<=
foo>= and foo=
foo>= and foo= or (foo=)
foo>= and foo= or (foo>=)
(foo>=) and foo= or (foo>=)
foo>= and ((foo= or (foo>=)))
(foo>= and ((foo= or (foo>=)))) and foo=

nicht enthalten sind z.b.:
foo=foo
foo or foo
foo>= and foo=> or (foo>=)
(foo>= and ((foo= or (foo>=)))) and or

prost
seth