J'ai écrit un analyseur C (comme) en utilisant PEG dans Ruby

C'est un article que j'ai écrit quelque chose comme un analyseur C en Ruby. Même si j'ai écrit un analyseur C, ce n'est pas un analyseur C strict et très complet comme pycparser implémenté en Python, mais c'est une implémentation diverse qui a pris environ 3 jours à implémenter.

Dépôt: github.com/hsssnow23/Captain

échantillon 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">

À l'origine, il s'agissait d'un analyseur créé pour un outil qui génère automatiquement du code en ajoutant des informations supplémentaires en C avec des annotations, mais c'est vraiment lent. La raison principale est probablement que l'analyseur PEG utilisé pour l'implémentation n'est pas Packrat Parsing dans mon implémentation. Donc, dans cet article, j'aimerais écrire sur la façon dont j'ai utilisé l'analyseur PEG.

En gros résumé en premier

Avantages du PEG

• Dans un langage comme Ruby qui permet la surcharge d'opérateurs, il est facile à comprendre car il peut être écrit comme DSL. (Les générateurs d'analyseurs tels que lex yacc ont beaucoup d'astuces, donc je pense que c'est un peu difficile de s'entendre.) ――Il est facile d'implémenter l'analyseur PEG lui-même s'il s'agit d'un analyseur simple qui ignore la vitesse. (Enfin, l'implémentation de l'analyseur PEG lui-même fait 269 lignes.)
• Puisque l'analyse de phrase et l'analyse syntaxique peuvent être effectuées en même temps, cela économise du temps et des efforts. Par conséquent, il peut être utilisé aussi facilement qu'une expression régulière.
• Contrairement aux expressions régulières, vous pouvez analyser les parenthèses.

Inconvénients du PEG

• Une implémentation simple ne peut pas être exécutée avec O (n).
• Impossible de battre en retraite vers la gauche.

Impressions

facile. C'est extrêmement facile. Je pense que c'est un gros avantage par rapport aux autres analyseurs que vous pouvez commencer à écrire dès que vous pensez à ce qui est facile. Puisque vous pouvez ignorer l'analyse de phrase et écrire l'analyseur et créer un arbre de syntaxe, je pense que c'est plus approprié lorsque vous voulez le faire plus riche que les expressions régulières même s'il s'agit d'un simple analyseur. Cependant, j'ai pensé que ce serait un peu difficile d'écrire un analyseur en PEG, bien qu'il s'agisse déjà d'une spécification comme l'analyseur C. De nombreux langages de programmation existants sont créés avec des générateurs d'analyseurs tels que lex et yacc, et il est difficile d'assurer la cohérence avec eux, et PEG est encore jeune et il est très clair dans quelle mesure il peut être analysé. Il semble que ce ne soit pas le cas. (Honnêtement, je ne suis pas sûr de pouvoir l'analyser si c'est une source en langage C qui pousse le coin)

Cependant, j'ai senti qu'il serait plus facile d'écrire un analyseur dont l'analyseur lui-même change en fonction du contenu de l'analyse. (Je pense qu'il y a peu de situations où cela est nécessaire)

Résumé

Ma conclusion finale est que PEG est l'analyseur le plus recommandé. Cependant, je pense qu'un analyseur avec un petit format qui vous permet de décider vous-même des spécifications convient parfaitement, mais j'ai pensé qu'il pourrait être subtil à utiliser à d'autres fins.

Article de référence: http://kmizu.hatenablog.com/entry/20100203/1265183754