Warum getrennt lexen und analysieren?

15

Es ist möglich, ein Dokument mit einem einzigen Durchgang von einem Zustandsautomaten aus zu analysieren. Was ist der Vorteil von zwei Durchgängen, dh. Haben Sie einen Lexer zum Konvertieren von Text in Token und einen Parser zum Testen der Produktionsregeln für diese Token? Warum nicht einen einzigen Durchgang haben, der die Produktionsregeln direkt auf den Text anwendet?

compilers parsers Brent
quelle
2
Siehe auch: programmers.stackexchange.com/questions/128888/…
User
2
Dies wurde bereits auf CS, stackexchange, mit vielen sehr technischen Kommentaren als Antwort auf die Ausdruckskraft von lexer + parser diskutiert . Möglicherweise ist dort jedoch Platz für weitere Antworten.
Babou
Ich frage mich, ob Parallelität im Pipeline-Stil (wenn auch stark unausgeglichene Phasen) ein Nebeneffekt sein könnte. Auch das Verhalten des Befehls und des Datencaches kann interessant sein. Um wie viel (wenn überhaupt) sich die Kompilierzeit verkürzen würde, hängt von der jeweiligen Hardware ab.
Paul A. Clayton
Ein ziemlich offensichtlicher (zumindest für mich) Grund ist, dass Sie das Scanner-Tool dann separat verwenden können. In der Praxis verwende ich häufig Flex, um Eingaben zu scannen, aber ich brauche selten die volle Leistung von Yacc.
Jamesqf

Antworten:

13

Sie müssen sie nicht trennen. Die Leute kombinieren sie zu scannerlosen Parsern .

Der Hauptnachteil von scannerlosen Parsern scheint zu sein, dass die resultierenden Grammatiken ziemlich kompliziert sind - komplizierter als die entsprechende Kombination eines regulären Ausdrucks, der Lexing ausführt, und einer kontextfreien Grammatik, die Parsing für den Token-Stream ausführt. Insbesondere Grammatiken für das scannerlose Parsen neigen zur Mehrdeutigkeit. Es ist einfacher, Mehrdeutigkeiten für Grammatiken zu beseitigen, die an einem Token-Stream arbeiten.

Ein pragmatischer Vorteil der Verwendung einer dedizierten Vorab-Lexing-Phase besteht darin, dass Sie den nachfolgenden Parser nicht mit lexikalischen Details koppeln. Dies ist nützlich während der frühen Entwicklung von Programmiersprachen, wenn sich die lexikalischen und syntaktischen Details immer noch häufig ändern.

Martin Berger
quelle
1
TPPPT
@babou Ja das ist richtig. Ich kenne keine formalen Ergebnisse der mit LL (k) zusammengesetzten Form regulärer Ausdruck, die von LL (k) oder ähnlichem ausgeht. Darüber hinaus wird Lexing normalerweise nicht mit regulären Sprachen durchgeführt, sondern mit etwas Stärkerem, nämlich regulären Sprachen, die mit den Prioritäten "Längste Übereinstimmung" und "Erstes Schlüsselwort" erweitert wurden. Ich bin mir nicht sicher, was genau das für eine Sprachklasse ist und welche Abschlusseigenschaften sie hat.
Martin Berger
2
Wenn Ihre Vorausschau das Lesen eines Bezeichners umfasst, erfordert die Komposition eine uneingeschränkte Vorausschau, da die Länge der Bezeichner (im Prinzip) nicht beschränkt ist.
Babou
@babou Ich bin mir nicht sicher. Wenn das längste Schlüsselwort 17 Zeichen lang ist, muss eine längere Zeichenfolge ein Bezeichner oder lexikalisch ungültig sein.
Martin Berger
Ihr Bezeichner oder möglicherweise eine Zeichenfolge, eine Zahl oder ein anderes Literal ist eine Folge von mehr als 17 einzelnen Symbolen, die möglicherweise vor dem Token stehen, das Sie tatsächlich benötigen. Das ist eine große Vorausschau, unbegrenzt. Möglicherweise haben Sie eine nicht deterministische Sprache.
Babou