Ich habe einen C-Parser (wie) mit PEG in Ruby geschrieben

Es ist ein Artikel, den ich so etwas wie einen C-Parser in Ruby geschrieben habe. Obwohl ich einen C-Parser geschrieben habe, handelt es sich nicht um einen strengen und sehr vollständigen C-Parser wie den in Python implementierten Pycparser, sondern um eine verschiedene Implementierung, deren Implementierung etwa drei Tage dauerte.

Repository: github.com/hsssnow23/Captain

Stichprobe input:

typedef struct {
    unsigned int id;
    float x;
    float y;
} Actor;

output:

#<CTypedef:0x000000037809a8
 @from=
  #<CStruct:0x0000000376a068
   @body=
    [#<CVariable:0x000000034f0350
      @name="id",
      @type=
       #<CType:0x000000034f3780
        @const=false,
        @name="int",
        @pointer=false,
        @prefix="unsigned">,
      @value=nil>,
     #<CVariable:0x000000035b6ca8
      @name="x",
      @type=
       #<CType:0x000000035ad950
        @const=false,
        @name="float",
        @pointer=false,
        @prefix=nil>,
      @value=nil>,
     #<CVariable:0x000000036a0df8
      @name="y",
      @type=
       #<CType:0x000000036a3a30
        @const=false,
        @name="float",
        @pointer=false,
        @prefix=nil>,
      @value=nil>],
   @name=nil>,
 @to="Actor">

Ursprünglich war es ein Parser, der für ein Tool erstellt wurde, das automatisch Code generiert, indem es C zusätzliche Informationen mit Anmerkungen hinzufügt, aber es ist sehr langsam. Wahrscheinlich liegt der Hauptgrund darin, dass der für die Implementierung verwendete PEG-Parser in meiner Implementierung nicht Packrat Parsing ist. In diesem Artikel möchte ich darüber schreiben, wie es war, als ich den PEG-Parser tatsächlich verwendet habe.

Zuerst grob zusammengefasst

Vorteile von PEG

• In einer Sprache wie Ruby, die eine Überlastung des Bedieners ermöglicht, ist es leicht zu verstehen, da es wie DSL geschrieben werden kann. (Parser-Generatoren wie Lex Yacc haben viele Tricks, daher denke ich, dass es etwas schwierig ist, damit auszukommen.) ――Es ist einfach, den PEG-Parser selbst zu implementieren, wenn es sich um einen einfachen Parser handelt, der die Geschwindigkeit ignoriert. (Schließlich umfasst die Implementierung des PEG-Parsers selbst 269 Zeilen.)
• Da Phrasenanalyse und Syntaxanalyse gleichzeitig durchgeführt werden können, spart dies Zeit und Mühe. Daher kann es so einfach wie ein regulärer Ausdruck verwendet werden.
• Im Gegensatz zu regulären Ausdrücken können Sie Klammern analysieren.

Nachteile von PEG

• Eine einfache Implementierung kann nicht mit O (n) ausgeführt werden.
• Kann sich nicht nach links zurückziehen.

Impressionen

einfach. Es ist überwältigend einfach. Ich denke, der große Vorteil gegenüber anderen Parsern ist, dass Sie mit dem Schreiben beginnen können, sobald Sie denken, was einfach ist. Da Sie die Phrasenanalyse überspringen und den Parser schreiben und einen Syntaxbaum erstellen können, ist er meiner Meinung nach am besten geeignet, wenn Sie ihn umfangreicher als reguläre Ausdrücke ausführen möchten, obwohl es sich um einen einfachen Parser handelt. Ich dachte jedoch, es wäre etwas schwierig, einen Parser in PEG zu schreiben, obwohl es sich bereits um eine Spezifikation wie den C-Parser handelt. Viele vorhandene Programmiersprachen werden mit Parser-Generatoren wie Lex und Yacc erstellt, und es ist schwierig, die Konsistenz mit ihnen sicherzustellen. PEG ist noch jung und es ist sehr klar, wie weit es analysiert werden kann. Es scheint, dass es nicht ist. (Ehrlich gesagt bin ich nicht sicher, ob ich es analysieren kann, wenn es sich um eine C-Sprachquelle handelt, die in die Ecke stößt)

Ich hatte jedoch das Gefühl, dass es einfacher sein würde, einen Parser zu schreiben, dessen Parser sich je nach Inhalt der Analyse ändert. (Ich denke, es gibt nur wenige Situationen, in denen es benötigt wird)

Zusammenfassung

Meine letzte Schlussfolgerung ist, dass PEG der am meisten empfohlene Parser ist. Obwohl ich sicher bin, dass ein kleinformatiger Parser, den Sie selbst angeben können, eine gute Wahl ist, dachte ich, dass es subtil sein könnte, ihn an anderer Stelle zu verwenden.

Referenzartikel: http://kmizu.hatenablog.com/entry/20100203/1265183754