Kann man C++ mit einem LL(k) oder LR(k) Parser parsen?
-
Hi,
Frage steht eigentlich schon im Topic: ist es möglich C++ mit einem LL(k) oder LR(k) Parser zu parsen? Bei Google bekomme ich nichts sinnvolles raus, dass es nicht mit k=1 geht weiß ich auch so schon...
-
-
DeepCopy schrieb:
Das ist doch ein LL(k) Parser-Framework für C++ wie lex und yacc und kein LL(k) Parser der C++ parst.
Google mal: c++ parser (k)
Dutzende von Hits
Bei dem Link ist mein Thread inzwischen auf Platz 1, das sieht ja nicht vielversprechend aus. Konnte aber immerhin das hier finden: http://www.jguru.com/faq/view.jsp?EID=531848
Leider existiert der Link zu dem genannten Paper nicht mehr und per Google finde ich es auch nicht
-
Zwei Möglichkeiten:
Die Harte: Du siehst dir den Quelltext vom gcc-Parser an.
Die Sanfte: Du fragst den Entwickler des C++ Parser-Frameworks in meinem ersten Post einfach mal.Mehr fällt mir jetzt auch nicht ein.
-
Ich hab's nie ausprobiert und kenne mich mit Compilerbau auch nicht richtig aus. Aber vielleicht sind diese Links hilfreich: Ich hatte da mal etwas von einem angeblich sehr tollen und modernen C++ Code Parser gehört: Elsa (passender Google Tech Talk dazu). Dann scheint LLVM noch recht modular aufgebaut zu sein, wobei die Unterstützung für C++ aber noch nicht 100% fertig ist, soweit ich weiß.
Gruß,
SP
-
Laut http://eli-project.sourceforge.net/elionline/faq_5.html#SEC19 geht es wohl nicht:
Compounding the problem is the fact that C++ has a number of essential ambiguities that make it very difficult to specify formally. For example, if something looks like both a declaration and an expression then it's a declaration. How do you express that formally?
-
C++-Parser schrieb:
Frage steht eigentlich schon im Topic: ist es möglich C++ mit einem LL(k) oder LR(k) Parser zu parsen? Bei Google bekomme ich nichts sinnvolles raus, dass es nicht mit k=1 geht weiß ich auch so schon...
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig. Ansonsten verstehe ich nicht, wieso googeln nach C++ LR(k) nicht helfen soll, das hier:
http://stackoverflow.com/questions/243383/why-c-cannot-be-parsed-with-a-lr1-parser
sieht doch sehr gut aus?
-
Bashar schrieb:
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig.
Laut http://ag-kastens.upb.de/lehre/material/plac/folien/Folie321.html nicht
-
Bashar schrieb:
C++-Parser schrieb:
Frage steht eigentlich schon im Topic: ist es möglich C++ mit einem LL(k) oder LR(k) Parser zu parsen? Bei Google bekomme ich nichts sinnvolles raus, dass es nicht mit k=1 geht weiß ich auch so schon...
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig. Ansonsten verstehe ich nicht, wieso googeln nach C++ LR(k) nicht helfen soll, das hier:
http://stackoverflow.com/questions/243383/why-c-cannot-be-parsed-with-a-lr1-parser
sieht doch sehr gut aus?Danke, der Link hat mir wirklich weitergeholfen
-
life schrieb:
Bashar schrieb:
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig.
Laut http://ag-kastens.upb.de/lehre/material/plac/folien/Folie321.html nicht
So ganz sicher bist du dir aber nicht, wenn ich den Smiley richtig interpretiere? Tipp: In der Folie geht es um Grammatiken, ich rede von Sprachen.
-
Bashar schrieb:
life schrieb:
Bashar schrieb:
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig.
Laut http://ag-kastens.upb.de/lehre/material/plac/folien/Folie321.html nicht
So ganz sicher bist du dir aber nicht, wenn ich den Smiley richtig interpretiere?
Ich kenne den Beweis dafür nicht, vertraue dem Prof. aber mehr als dir. Aber deinem "Tipp" entnehme ich mal, dass deine Aussage eh anders gemeint war?
Tipp: In der Folie geht es um Grammatiken, ich rede von Sprachen.
D.h., du willst eigentlich sagen, dass jede LR(k) parsebare Grammatik sich auch in eine äquivalente LR(1) parsebare Grammatik umformen lässt?
-
Ich hatte 1 Semester Compilerbau, aber gerafft hab ich das ganze LL, LR Zeugs etc. nie richtig. Ich könnte auch niemals ansatzweise einen echten Compiler für C oder sowas schreiben.
Es beruhigt mich zu sehen, dass offenbar die meisten anderen auch wenig Plan von Compilerbau haben.
-
life schrieb:
Bashar schrieb:
life schrieb:
Bashar schrieb:
Meines Wissens sind LR(k)-Parser für endliches k>=1 gleich mächtig.
Laut http://ag-kastens.upb.de/lehre/material/plac/folien/Folie321.html nicht
So ganz sicher bist du dir aber nicht, wenn ich den Smiley richtig interpretiere?
Ich kenne den Beweis dafür nicht, vertraue dem Prof. aber mehr als dir. Aber deinem "Tipp" entnehme ich mal, dass deine Aussage eh anders gemeint war?
Tipp: In der Folie geht es um Grammatiken, ich rede von Sprachen.
D.h., du willst eigentlich sagen, dass jede LR(k) parsebare Grammatik sich auch in eine äquivalente LR(1) parsebare Grammatik umformen lässt?
Was er sagen will ist, dass jede Sprache die von einer LR(k) (k>1) Grammatik beschrieben/erzeugt wird auch durch eine LR(1) Grammatik beschrieben/erzeugt werden kann. Weiß jetzt nicht ob du das mit Äquivalenz gemeint hast, aber ich gehe mal davon aus, dass du mit Äquivalenz zweier Grammatiken meinst, dass sie die selbe Sprache erzeugen.
-
C++-Parser schrieb:
D.h., du willst eigentlich sagen, dass jede LR(k) parsebare Grammatik sich auch in eine äquivalente LR(1) parsebare Grammatik umformen lässt?
Was er sagen will ist, dass jede Sprache die von einer LR(k) (k>1) Grammatik beschrieben/erzeugt wird auch durch eine LR(1) Grammatik beschrieben/erzeugt werden kann. Weiß jetzt nicht ob du das mit Äquivalenz gemeint hast, aber ich gehe mal davon aus, dass du mit Äquivalenz zweier Grammatiken meinst, dass sie die selbe Sprache erzeugen.
Ja das habe ich mit Äquivalenz gemeint. Damit sind dann meine Aussage und deine Aussage auch "äquivalent" ;).
-
life schrieb:
Ich kenne den Beweis dafür nicht, vertraue dem Prof. aber mehr als dir.
Da wird er sich aber freuen. Nicht darüber, dass dir der Beweis nicht einfällt, natürlich.
D.h., du willst eigentlich sagen, dass jede LR(k) parsebare Grammatik sich auch in eine äquivalente LR(1) parsebare Grammatik umformen lässt?
Das wäre eine äquivalente Formulierung, ja. Die Frage war, ob C++ von einem LR(k)-Parser erkannt werden kann, d.h. ob die Sprache C++ LR(k) ist. Wenn wir aber wissen, dass C++ nicht LR(1) ist, wissen wir aufgrund dieser Umformbarkeit auch, dass C++ nicht LR(k) ist.
-
Bashar schrieb:
Das wäre eine äquivalente Formulierung, ja.
Ja, ich habe jetzt verstanden, dass du die "Mächtigkeit" auf die Menge der akzeptierten Sprachen und nicht auf die Menge der parsebaren Grammatiken bezogen hast. Trotzdem wundere ich mich etwas über deine Unfreundlichkeit. Ich will es aber mal nicht persönlich nehmen ;).
-
life schrieb:
Trotzdem wundere ich mich etwas über deine Unfreundlichkeit.
Das wundert mich, dass dich das wundert. Lies doch mal mein und dein erstes Posting mit dem Wissen, das du jetzt hast.