Was macht Java leichter zu parsen als C?

Lesezeit: 7 Minuten

Benutzer-Avatar
Daniel Shaper

Ich bin mit der Tatsache vertraut, dass die Grammatiken von C und C++ kontextsensitiv sind und Sie insbesondere einen “Lexer-Hack” in C benötigen. Andererseits habe ich den Eindruck, dass Sie Java nur mit parsen können 2 Zeichen der Vorausschau, trotz beträchtlicher Ähnlichkeit zwischen den beiden Sprachen.

Was müssten Sie an C ändern, damit es einfacher zu analysieren ist?

Ich frage, weil alle Beispiele, die ich für die Kontextsensitivität von C gesehen habe, technisch zulässig, aber schrecklich seltsam sind. Zum Beispiel,

foo (a);

könnte die Funktion void aufrufen foo mit argument a. Oder es könnte erklären a ein Objekt des Typs sein foo, aber Sie könnten die Klammern genauso gut loswerden. Teilweise tritt diese Verrücktheit auf, weil die Produktionsregel “direkter Deklarator” für die C-Grammatik erfüllt den doppelten Zweck, sowohl Funktionen als auch Variablen zu deklarieren.

Andererseits ist die Java-Grammatik hat separate Produktionsregeln für Variablendeklaration und Funktionsdeklaration. Wenn du schreibst

foo a;

dann wissen Sie, dass es sich um eine Variablendeklaration handelt und foo kann eindeutig als Typname geparst werden. Dies ist möglicherweise kein gültiger Code, wenn die Klasse foo wurde im aktuellen Geltungsbereich noch nicht definiert, aber das ist eine Aufgabe für die semantische Analyse, die in einem späteren Compilerdurchlauf durchgeführt werden kann.

Ich habe gesehen, dass C aufgrund von Typedef schwer zu analysieren ist, aber Sie können auch Ihre eigenen Typen in Java deklarieren. Welche C-Grammatikregeln außerdem direct_declaratorsind schuld?

  • Coole Frage. Wahrscheinlich viel zu breit oder in erster Linie rechthaberisch.

    – Sternchen

    12. Oktober 2014 um 22:01 Uhr

  • Dies ist eine gültige Frage zu Parsern, und das einzige, was breit oder auf Meinungen basiert, sind die letzten paar Sätze (die wahrscheinlich fallen gelassen oder geändert werden sollten). Hör auf mit den knappen Abstimmungen.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    12. Oktober 2014 um 22:10 Uhr


  • Ich habe die Frage entsprechend bearbeitet, danke für @R .. für das Feedback.

    – Daniel Shapero

    12. Oktober 2014 um 22:17 Uhr

  • Virtuell jeder (Standard-)Computersprache ist kontextsensitiv; Sie können eine Variable eines Typs nicht deklarieren und sie am häufigsten missbrauchen Sprachen. Das ist anders als „alle Grammatiken für die Sprache” sind kontextsensitiv; die meisten Leute, die Parser bauen, bauen einen kontextfreien (oder noch restriktiveren) Parser und verwenden dann Hacks außerhalb des Parsers, um die kontextfreien Eigenschaften zu überprüfen.

    – Ira Baxter

    12. Oktober 2014 um 22:43 Uhr


  • @IraBaxter Ich würde das nicht “Hacks” nennen. Das Problem in zwei Teile aufzuteilen, scheint vernünftig zu sein, da das Parsen kontextsensitiver Sprachen nicht effizient durchgeführt werden kann (und tatsächlich ist sogar das Parsen kontextfreier Sprachen nicht effizient, und deshalb beschränken wir uns im Allgemeinen auf Teilmengen von kontextfreien Sprachen) . Eine kontextfreie Analyse + statische Analyse, um nur kontextsensitive Eigenschaften über den AST zu überprüfen, ist eine vernünftige Sache.

    – Bakuriu

    13. Oktober 2014 um 5:32 Uhr

Benutzer-Avatar
Ira Baxter

Das Parsen von C++ wird immer schwieriger. Das Parsen von Java wird genauso schwierig.

Sehen Sie sich diese SO-Antwort an, in der erläutert wird, warum C (und C++) “schwer” zu analysieren ist. Die kurze Zusammenfassung ist, dass C und C++ Grammatiken sind von Natur aus mehrdeutig; Sie geben Ihnen mehrere Parses und Sie muss Verwenden Sie den Kontext, um die Mehrdeutigkeiten aufzulösen. Die Leute machen dann den Fehler anzunehmen, dass Sie beim Analysieren Mehrdeutigkeiten auflösen müssen; nicht so, siehe unten. Wenn Sie beim Parsen darauf bestehen, Mehrdeutigkeiten aufzulösen, wird Ihr Parser komplizierter und umso schwieriger zu erstellen. aber diese Komplexität ist eine selbst zugefügte Wunde.

Die „offensichtliche“ LALR(1)-Grammatik von IIRC, Java 1.4, war nicht mehrdeutig, sodass sie „einfach“ zu analysieren war. Ich bin mir nicht sicher, ob das moderne Java nicht zumindest lokale Mehrdeutigkeiten über große Entfernungen aufweist. Es gibt immer das Problem zu entscheiden, ob “…>>” zwei Vorlagen abschließt oder ein “Rechtsverschiebungsoperator” ist. Ich vermute, dass modernes Java nicht mehr mit LALR (1) analysiert.

Aber man kann das Parsing-Problem umgehen, indem man starke Parser (oder schwache Parser und Kontextsammlungs-Hacks, wie es C- und C++-Frontends jetzt meistens tun) für beide Sprachen verwendet. C und C++ haben die zusätzliche Komplikation, einen Präprozessor zu haben; diese sind in der Praxis komplizierter als sie aussehen. Eine Behauptung ist, dass die C- und C++-Parser so schwer sind, dass sie von Hand geschrieben werden müssen. Es ist nicht wahr; Mit GLR-Parsergeneratoren können Sie Java- und C++-Parser problemlos erstellen.

Aber das Parsen ist nicht wirklich das Problem.

Sobald Sie geparst haben, werden Sie etwas mit dem AST/Parse-Baum machen wollen. In der Praxis müssen Sie für jeden Bezeichner wissen, was seine Definition ist und wo er verwendet wird (“Namens- und Typauflösung”, schlampig, Symboltabellen erstellen). Dies stellt sich als viel mehr Arbeit heraus, als den Parser richtig hinzubekommen, was durch Vererbung, Schnittstellen, Überladung und Vorlagen noch verstärkt wird, und die Verwirrung durch die Tatsache, dass die Semantik für all dies in informeller natürlicher Sprache geschrieben ist, die sich über Dutzende bis Hunderte von Seiten erstreckt des Sprachstandards. C++ ist hier wirklich schlecht. Java 7 und 8 werden aus dieser Sicht ziemlich schrecklich. (Und Symboltabellen sind nicht alles, was Sie brauchen; einen längeren Aufsatz über “Life After Parsing” finden Sie in meiner Biografie).

Die meisten Leute kämpfen mit dem reinen Parsing-Teil (werden oft nie fertig; überprüfen Sie SO selbst auf die vielen, vielen Fragen zum Erstellen funktionierender Parser für echte Sprachen), sodass sie nie ein Leben nach dem Parsing sehen. Und dann bekommen wir Volkstheoreme darüber, was schwer zu analysieren ist, und kein Signal darüber, was nach dieser Phase passiert.

Das Korrigieren der C++-Syntax bringt Sie nicht weiter.

In Bezug auf die Änderung der C++-Syntax: Sie werden feststellen, dass Sie viele Stellen patchen müssen, um sich um die Vielfalt lokaler und realer Mehrdeutigkeiten in jeder C++-Grammatik zu kümmern. Wenn Sie darauf bestehen, könnte die folgende Liste ein guter Ausgangspunkt sein. Ich behaupte, dass es keinen Sinn macht, dies zu tun, wenn Sie nicht das C++-Standardkomitee sind; Wenn Sie dies tun und damit einen Compiler erstellen würden, würde ihn niemand mit Verstand verwenden. Es wird zu viel in bestehende C++-Anwendungen investiert, um den Leuten, die Parser erstellen, aus Bequemlichkeit zu wechseln; Außerdem ist ihr Schmerz vorbei und vorhandene Parser funktionieren gut.

Vielleicht möchten Sie Ihren eigenen Parser schreiben. OK das passt; Erwarten Sie nur nicht, dass der Rest der Community Sie die Sprache ändern lässt, die sie verwenden müssen, um es Ihnen einfacher zu machen. Sie alle wollen es einfacher haben, und das heißt, die Sprache so zu verwenden, wie sie dokumentiert und implementiert ist.

  • Gute Antwort. Siehe auch D und C+, die versuchen, einige dieser Probleme zu lösen. s/inhalt/streit/

    – david.pfx

    12. Oktober 2014 um 23:02 Uhr

  • Ich habe Life After Parsing schon früher gelesen und fand, dass es ein echter Augenöffner ist; Mir wurde klar, dass in der semantischen Analyse (Namens-/Typauflösung, …) viel mehr Arbeit steckt als im Parsen. Ich bin nicht versuchen, die Syntax einer beliebigen Sprache zu ändern. ich tun verstehen möchten, was die Eigenschaften einer Sprache sind, in der Sie zuerst die syntaktische Analyse und dann die semantische Analyse durchführen können. C ist keine solche Sprache (benötigt Lexer-Hack); Ich dachte immer, dass Java das ist, und ich möchte wissen, warum.

    – Daniel Shapero

    12. Oktober 2014 um 23:52 Uhr


  • @Korrok: Lesen Sie meine Antwort zum Erstellen von Java/C++ mit GLR-Parsern. Sie brauchen keinen Lexer-Hack. Die Unterscheidung liegt also im Kopf der Leute, die die falsche Parsing-Technologie verwenden. … Zugegeben, das Erstellen eines vollständigen C++-Frontends (insbesondere C++14, das wir getan haben) ist schwieriger als das Erstellen von Java8, aber beides ist schwierig (in Bezug auf Aufwand und Aufmerksamkeit für Details) und Parsing ist das einfachste Stück.

    – Ira Baxter

    13. Oktober 2014 um 0:00 Uhr


  • Ich stimme Ihrem “Leben nach dem Parsing” zu: zB kann die Überlastungsauflösung in C # jedes 3-SAT-Problem codieren und ist daher NP-schwer.

    – Jörg W Mittag

    13. Oktober 2014 um 11:22 Uhr

  • blogs.msdn.com/b/ericlippert/archive/2007/03/28/…

    – Jörg W Mittag

    13. Oktober 2014 um 12:57 Uhr

1254860cookie-checkWas macht Java leichter zu parsen als C?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy