Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Problem mit LL1-Grammatik für JavaCC

Werbeanzeige

Phil_GDM

Alter Hase

  • »Phil_GDM« ist der Autor dieses Themas

Beiträge: 443

Wohnort: Graz

Beruf: Student-Softwareentwicklung u. Wissensmanagement

  • Private Nachricht senden

1

21.04.2006, 14:52

Problem mit LL1-Grammatik für JavaCC

Also ich hab die Aufgabenstellung, mit JavaCC einen Parser zu erstellen, der die Sprache E parsen kann.
Voraussetzung ist: es muss sich um einen LL1 Parser handeln.

Die Sprache ist ursprünglich definiert als:

Quellcode

 
1
2
3
4
5
6
7
8

S->E | epsilon
E->id | num | if P then E else E | (E) | E E op | E op
P->E E rop

id: Variablenname
num: Zahl
op: Operator [plus, minus, inc, dec]
rop: Vergleichsoperator [isequal, isgreater]

(Arithmetische Postfixausdrücke)


Da diese Sprachdefinition natürlich auf keinen Fall LL1 sein kann, bringe ich zuerst mal die Linksrekursion weg, dann sieht die Grammatik so aus

Quellcode

 
1
2
3
4

S->E | epsilon
E->(E) R | if P then E else E R | num R | id R
R->E op R | op R | epsilon
P->E E op


Meiner Meinung nach, ist diese Grammatik jetzt eigentlich LL1-Fähig (es sind keine Linkrekursionen drinnen, keine Zyklen, und auch keine Produktionen mit gleichem Präfix.

Dennoch ist JavaCC nicht in der Lage, eine Term wie z.b. 100 100 plus aufzulösen.

Der Grund:
JavaCC parst das ganze auf folgende Art u. Weise
S -> E -> 100 R -> 100 E (op R) -> 100 100 R (op R) -> 100 100 op R (op R) -> 100 100 op epsilon (op R).

Das Problem besteht also darin, dass JavaCC zuerst die E-Produktion vor dem op in R->E op R auflöst, und währen der Auflösung einen Operator konsumiert, der aber erst nach der Auflösung von E konsumiert werden dürfte.

Weiß jemand von euch, wie man die Gramatik so umformen könnte, das JavaCC richtig parst?

mfg Philipp