Regex mit RDP-Parser parsen

Antoras

Hallo,

ich möchte gerne einen Regex-Parser schreiben, der zu Beginn nur mit dem Eingabealphabet A={(,),|,*,sign} klarkommen soll. Zum Parsen des Ausdrucks habe ich mich für einen Recursive-Descent-Parser entschieden.
Ich glaube aber gerade festgestellt zu haben, dass man mit diesen gar keine Regex parsen kann, da diese Linksrekursiv sind.

Ich habe folgende EBNF entworfen:

star = union ["*"]
union = concat {"|" concat}
concat = paren {paren}
paren = "(" star ")" | sign
sign = "a-zA-z0-9_"

Das würde für Eingaben $A^*=\{a,ab,ab*,a|b,(ab)*,(a|b)*\}$ super funktionieren, aber z.B. nicht für $A^*=\{a*b\}$ .

Damit das funktioniert müsste der Aufruf vor den Aufruf von sign in paren ein star eingefügt werden. Dann hätte ich aber keine Möglichkeit mehr ein sign zu parsen.

Liege ich richtig in der Annahme, dass es nicht möglich ist mit einem RD-Parser einen Regex zu parsen? Wenn ja, was für einen Parser sollte ich stattdessen verwenden?

Bashar

Wo ist denn deine Grammatik linksrekursiv? Vielleicht überseh ich ja was ... Nichtsdestotrotz sind linksrekursive Grammatiken weder ungewöhnlich noch ein Beinbruch, du musst sie dann halt in eine nicht linksrekursive Grammatik umwandeln. Google: linksrekursion beseitigen.

BTW kommt mir deine Grammatik falsch vor. Ist star das Startsymbol? Hast du nicht angegeben, aber es sieht so aus. Damit würdest du a*b natürlich nicht parsen können.

Und ich mag mich ja irren, aber soweit ich weiß hat * eine höhere Präzedenz als |. Das heißt a|b* würde ich immer als a|(b*) verstehen und nicht, wie bei dir, (a|b)*.

Mein Vorschlag:

regex ::= concat { "|" concat }
concat ::= rep { rep }
rep ::= core { "*" }
core ::= "(" regex ")" | char
char ::= "a-zA-Z0-9_"

(Ich bin BTW nicht so firm in EBNF, mehr yacc, d.h. BNF, gewöhnt, also kann es sein, dass da noch Fehler drin sind.)

Antoras

Bashar schrieb:

Und ich mag mich ja irren, aber soweit ich weiß hat * eine höhere Präzedenz als |. Das heißt a|b* würde ich immer als a|(b*) verstehen und nicht, wie bei dir, (a|b)*.

Stimmt, das bin ich total übergangen. Das Ändern der Prioritäten hat schon Abhilfe geschafft. Jetzt funktioniert der Parser.

Bashar schrieb:

Wo ist denn deine Grammatik linksrekursiv?

Sie ist es eben gerade nicht. Ich hab angenommen, dass Regex es immer sind. Vielleicht war ich deshalb so verwirrt was dazu geführt hat, dass mir die falschen Prioritäten nicht aufgefallen sind.

Bashar

Antoras schrieb:

Bashar schrieb:

Wo ist denn deine Grammatik linksrekursiv?

Sie ist es eben gerade nicht. Ich hab angenommen, dass Regex es immer sind. Vielleicht war ich deshalb so verwirrt was dazu geführt hat, dass mir die falschen Prioritäten nicht aufgefallen sind.

Achso. IMHO ergibt die Aussage überhaupt keinen Sinn. Sprachen können nicht linksrekursiv sein, das ist eine Eigenschaft von Grammatiken.