Hand-Codierung einen Parser
https://stackoverflow.com/questions/2632641
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Für alle Compiler-Gurus, Ich will einen rekursiven Abstieg Parser schreiben, und ich will es nur mit Code zu tun. Keine Erzeugungs lexers und Parser aus einer anderen Grammatik und erzählen Sie mir nicht den Drachen Buch zu lesen, ich werde schließlich dazu kommen um.
Ich will in die gritty Details erhalten über einen Lexer und Parser für eine vernünftige einfache Sprache Implementierung sagen CSS. Und ich will dieses Recht tun.
Dies wird wahrscheinlich eine Reihe von Fragen am Ende wird aber jetzt mit einem Lexer Ich fange an. Tokenisierung Regeln für CSS können hier .
ich mich selbst das Schreiben von Code wie diese finden (hoffentlich können Sie den Rest dieser Schnipsel ableiten):
public CssToken ReadNext()
{
int val;
while ((val = _reader.Read()) != -1)
{
var c = (char)val;
switch (_stack.Top)
{
case ParserState.Init:
if (c == ' ')
{
continue; // ignore
}
else if (c == '.')
{
_stack.Transition(ParserState.SubIdent, ParserState.Init);
}
break;
case ParserState.SubIdent:
if (c == '-')
{
_token.Append(c);
}
_stack.Transition(ParserState.SubNMBegin);
break;
Was heißt das? und wie weit weg bin ich von etwas Vernünftiges gut verstanden? Ich bin zum Ausgleich etwas versuchen, was in Bezug auf die Effizienz ist fair und einfach zu arbeiten mit, mit einem Stapel eine Art Zustandsmaschine zu implementieren ist recht gut funktioniert, aber ich bin nicht sicher, wie so weitermachen.
Was ich habe, ist ein Eingangsstrom, von dem ich ein Zeichen in einer Zeit lesen kann. Ich mache keinen Blick einen Kopf gerade jetzt, ich habe gerade gelesen das Zeichen dann auf dem aktuellen Stand try je etwas damit zu tun.
Ich möchte wirklich in den Kopf gesetzt des Schreibens wieder verwendbaren Code-Schnipsel erhalten. Diese Transition Methode bedeutet derzeit, dass zu tun, wird es den aktuellen Status des Stapels Pop und drücken Sie dann die Argumente in umgekehrter Reihenfolge. Auf diese Weise, wenn ich schreibe Transition(ParserState.SubIdent, ParserState.Init) es „Anruf“ eine Unterroutine SubIdent wird die wird, wenn Sie fertig sind, Rückkehr in den Init Zustand.
Der Parser wird auf die gleiche Weise in viel umgesetzt werden, zur Zeit, mit allem in einer einzigen großen Methode, wie dies ermöglicht es mir leicht einen Token zurück, wenn ich einen gefunden, aber es Kräfte auch mir alles in einer einzigen großer Methode zu halten . Gibt es eine schöne Möglichkeit, diese tokenization Regeln in einzelne Methoden aufgeteilt?
Lösung
Was Sie schreiben ein Kellerautomat genannt wird. Dies ist in der Regel mehr Energie, als Sie einen Lexer schreiben müssen, ist es sicherlich übertrieben, wenn Sie einen Lexer für eine moderne Sprache wie CSS zu schreiben. Ein Rekursiver Abstieg ist nah an der Macht zu einem Kellerautomaten, aber Rekursiver Abstieg ist viel einfacher zu schreiben und zu verstehen. Die meisten Parser-Generatoren erzeugen Pushdown- Automate.
lexers sind fast immer als endliche Automaten geschrieben, das heißt, wie Sie Ihren Code mit Ausnahme des „Stack“ Objekt loszuwerden. Finite-State-Maschinen sind eng mit regulären Ausdrücken verwandt (tatsächlich sind sie beweisbar zueinander äquivalent). Wenn solch ein Parser entwerfen, man in der Regel beginnt mit den regulären Ausdrücken und verwendet sie einen deterministischen endlichen Automaten zu schaffen, mit einigen zusätzlichen Code in den Übergängen den Anfang und das Ende jedes Token aufzuzeichnen.
Es gibt Werkzeuge, dies zu tun. Das lex Werkzeug und seine Nachkommen sind gut bekannt und wurden in viele Sprachen übersetzt worden. Die ANTLR Werkzeugkette hat auch eine Lexer-Komponente. Mein bevorzugtes Werkzeug ist ragel auf Plattformen, die sie unterstützen. Es gibt kaum einen Nutzen ein Lexer von Hand zu schreiben die meisten der Zeit, und der Code von diesen Tools erzeugt wird wahrscheinlich schneller und zuverlässiger.
Wenn Sie möchten, dass Ihre eigene Lexer von Hand schreiben, oft gute etwa wie folgt aussehen:
function readToken() // note: returns only one token each time
while !eof
c = peekChar()
if c in A-Za-z
return readIdentifier()
else if c in 0-9
return readInteger()
else if c in ' \n\r\t\v\f'
nextChar()
...
return EOF
function readIdentifier()
ident = ""
while !eof
c = nextChar()
if c in A-Za-z0-9
ident.append(c)
else
return Token(Identifier, ident)
// or maybe...
return Identifier(ident)
Dann können Sie Ihre Parser als Rekursiver Abstieg schreiben. Versuchen Sie nicht, Lexer / Parser Stufen in einem, es führt zu einem Gesamtdurcheinander von Code zu kombinieren. (Nach dem Parsec Autor, es ist langsamer, auch).
Andere Tipps
Wenn Sie Hand-Code alles von Grund gehen würde ich auf jeden Fall überlegen mit einem rekursiven anständigen Parser gehen. In Ihrem Beitrag sagen Sie nicht wirklich, was Sie mit dem Token-Stream tun, wenn Sie die Quelle analysiert haben.
Einige Dinge, die ich würde empfehlen, den Griff bekommen
1. Gutes Design für den Scanner / Lexer, ist es das, was Ihren Quellcode für Ihren Parser werden Zeichenüber.
2. Das nächste, was ist der Parser, wenn Sie eine gute EBNF für die Quellsprache der Parser haben in der Regel recht gut in eine rekursive anständigen Parser übersetzen kann.
3. Eine weitere Datenstruktur Sie wirklich den Kopf bekommen müssen um die Symboltabelle. Dies kann so einfach sein wie eine Hash-Tabelle oder so komplex wie eine Baumstruktur, die komplexe Satzstrukturen usw. Ich denke, für CSS darstellen können Sie vielleicht irgendwo zwischen den beiden sein.
4. Und schließlich wollen Sie mit Code-Generierung beschäftigen. Sie haben hier viele Möglichkeiten. Für einen Dolmetscher, können Sie einfach im Fluge interpretieren, wie Sie den Code analysieren. Ein besserer Ansatz könnte sein, ein zu generieren für i-Code, den Sie dann eine iterpreter für und später sogar einen Compiler schreiben kann. Natürlich für die .NET-Plattform können Sie direkt IL erzeugen (wahrscheinlich nicht für CSS :))
Für Hinweise, entnehme ich Ihnen nicht schwer in die Tiefe Theorie und ich mache Ihnen keine Vorwürfe. Ein wirklich guter Ausgangspunkt für die Grundlagen erhalten, ohne komplexen Code, wenn Sie nicht über den Pascal dagegen, das heißt, ist Jack Crenshaw ‚Sie baut ein Compiler‘
http://compilers.iecc.com/crenshaw/
Viel Glück Ich bin sicher, Sie werden dieses Projekt genießen.
Sie müssen Ihren eigenen Rekursiver Abstieg von Ihrem BNF / EBNF schreiben. Ich hatte mein eigenes kürzlich zu schreiben und dieser Seite war eine große Hilfe. Ich bin nicht sicher, was Sie unter „nur mit Code“ bedeuten. Meinen Sie damit Sie wissen wollen, wie Sie Ihre eigenen rekursive Parser schreiben?
Wenn Sie das tun wollen, müssen Sie zuerst Ihre Grammatik an seinem Platz haben. Sobald Sie Ihre EBNF haben / BNF vorhanden, kann der Parser ganz von ihm leicht geschrieben werden.
Das erste, was ich tat, als ich meine Parser schrieb, war alles, was in und dann tokenize den Text zu lesen. So beendete I im wesentlichen mit einer Reihe von Tokens, dass ich als ein Stapel behandelt. Zur Verringerung der Ausführlichkeit / Aufwand für einen Wert aus einem Stapel ziehen und dann wieder auf dem Druck, wenn Sie benötigen es nicht, können Sie eine peek Methode, die einfach gibt den oberen Wert auf dem Stapel, ohne es zu knallen.
UPDATE
Basierend auf Ihren Kommentar hatte ich von Grund auf eine rekursive-Abstiegs-Parser in Javascript zu schreiben. Sie können an dem Parser einen Blick hier . Suchen Sie einfach nach der constraints Funktion. Ich schrieb meine eigene tokenize Funktion die Eingabe als auch tokenize. Ich schrieb auch eine andere Komfortfunktion (peek, dass ich bereits erwähnt). Der Parser parst nach dem EBNF hier .
Das hat mich eine Weile, um herauszufinden, weil es Jahre her, seit ich einen Parser geschrieben (letzte Mal, als ich schrieb, es war in der Schule!), Aber glauben Sie mir, sobald Sie es erhalten, Sie get es. Ich hoffe, mein Beispiel bekommt Ihr weiter auf Ihrem Weg.
ANOTHER UPDATE
Ich erkannte auch, dass mein Beispiel sein kann, nicht, was Sie wollen, weil Sie einen shift-reduce zu verwenden Parser gehen könnten. Sie haben erwähnt, dass gerade jetzt versuchen Sie einen tokenizer zu schreiben. In meinem Fall habe ich meine eigenen tokenizer in Javascript schreiben. Es ist wahrscheinlich nicht robust, aber es war für meine Bedürfnisse ausreichend.
function tokenize(options) {
var str = options.str;
var delimiters = options.delimiters.split("");
var returnDelimiters = options.returnDelimiters || false;
var returnEmptyTokens = options.returnEmptyTokens || false;
var tokens = new Array();
var lastTokenIndex = 0;
for(var i = 0; i < str.length; i++) {
if(exists(delimiters, str[i])) {
var token = str.substring(lastTokenIndex, i);
if(token.length == 0) {
if(returnEmptyTokens) {
tokens.push(token);
}
}
else {
tokens.push(token);
}
if(returnDelimiters) {
tokens.push(str[i]);
}
lastTokenIndex = i + 1;
}
}
if(lastTokenIndex < str.length) {
var token = str.substring(lastTokenIndex, str.length);
token = token.replace(/^\s+/, "").replace(/\s+$/, "");
if(token.length == 0) {
if(returnEmptyTokens) {
tokens.push(token);
}
}
else {
tokens.push(token);
}
}
return tokens;
}
Basierend auf Ihren Code, es sieht aus wie Sie lesen, Zeichenüber und zugleich Parsen - Ich gehe davon aus, dass das, was ein shift-reduce-Parser tut? Die Strömung für das, was ich habe, ist tokenize zuerst den Stapel von Tokens zu bauen, und dann die Token durch die rekursiven Abstieg Parser senden.
Es sieht aus wie Sie eine "shift-reduce" Parser implementieren möchten, wo Sie explizit einen Token-Stack aufzubauen. Die übliche Alternative ist es, einen „rekursiven Abstieg“ Parser, in der Tiefe von Prozeduraufrufen den gleichen Token-Stack mit ihren eigenen lokalen Variablen bauen, auf dem tatsächlichen Hardware-Stack.
In shift-reduce, der Begriff "reduzieren" bezieht sich auf die Operation auf dem explizit gepflegt Token Stapel ausgeführt. Zum Beispiel, wenn die Spitze des Stapels Term, Operator, Term dann eine Kürzungsregelung resultierende als Ersatz in Expression für das Muster werden kann werden angewandt. Die Reduktionsregeln werden explizit in einer Datenstruktur von der Schalt reduzieren Parser verwendet codiert; als Ergebnis können alle Reduktionsregeln an der gleichen Stelle des Quellcodes gefunden werden.
Der shift-reduce Ansatz bringt einige Vorteile im Vergleich zu rekursiven Abstieg. Auf der subjektiven Ebene meiner Meinung nach ist, dass shift-reduce ist leichter zu lesen und warten als rekursiven Abstieg. Objektive, shift-reduce für informative Fehlermeldungen aus dem Parser erlaubt, wenn ein unerwartetes Token auftritt.
Insbesondere weil der shift-reduce-Parser eine explizite Codierung von Regeln für die Herstellung hat „Kürzungen“, der Parser ist leicht zu artikulieren erweitert, welche Art von Token rechtlich verfolgt haben könnte. (Z.B. "; erwartet"). Eine rekursive Abstieg Implementierung kann nicht einfach die gleiche Sache zu tun erweitert werden.
Ein großes Buch auf beiden Arten von Parser und die Trade-offs in den verschiedenen Arten der Umsetzung shift-reduce ist "Introduction In dem Compiler Construction“, von Thomas W. Parsons .
shift-reduce wird manchmal als "bottom-up" genannt Parsen und rekursiven Abstieg wird manchmal als "top-down" Parsing bezeichnet. In Analogie verwendet, mit der höchsten Priorität zusammensetzt Knoten (z.B. „Factors“ in Vervielfachung Ausdruck) werden als „unten“ sein, der Parsing. Dies steht im Einklang mit der gleichen Analogie, die in „Abstieg“ von „rekursiven Abstieg“.
Wenn Sie die Parser verwenden mögen auch nicht-wohlgeformte Ausdrücke zu handhaben, wollen Sie wirklich einen Rekursiver Abstieg. Viel einfacher ist die Fehlerbehandlung und Reporting nutzbar zu erhalten.
Für Literatur, würde ich einige der alten Arbeit von Niklaus Wirth empfehlen. Er weiß, wie man schreibt. Algorithmen + Datenstrukturen = Programme ist, was ich verwendet, aber man kann seine Compiler Construction online.
