PackCC - PackCC

PackCC est un générateur d'analyseur syntaxique pour C . Ses principales caractéristiques sont les suivantes:

• Génère un analyseur en C écrit à partir d'une grammaire décrite dans un PEG ,
• Donne une grande efficacité à un analyseur par analyse packrat ,
• Prend en charge les règles de grammaire récursives à gauche directes et indirectes ,
• Génère un analyseur thread-safe et réentrant ,
• Se compose d'un seul fichier source compact.

La grammaire d'un analyseur de sortie peut être décrite dans un PEG (Parsing Expression Grammar). Le PEG est un langage d'analyse descendante , similaire à la grammaire des expressions régulières . Comparé à un langage d'analyse ascendant, comme celui de Yacc , le PEG est beaucoup plus intuitif et ne peut pas être ambigu. Le PEG n'exige pas que la tokenisation soit une étape distincte, et les règles de tokenisation peuvent être écrites de la même manière que toutes les autres règles de grammaire.

L'analyseur généré peut analyser les entrées de manière très efficace par l'analyse packrat. L'analyse packrat est l' algorithme d' analyse de descente récursive qui est accéléré à l'aide de la mémorisation . En utilisant l'analyse packrat, toute entrée peut être analysée en temps linéaire. Sans cela, cependant, l'analyseur résultant pourrait présenter des performances temporelles exponentielles dans le pire des cas en raison de la capacité de prévision illimitée.

Contrairement aux analyseurs packrat courants, PackCC peut prendre en charge des règles de grammaire récursives à gauche directes et indirectes . Cela rend les règles de grammaire beaucoup plus intuitives.

Le code généré est embelli et aussi facile à comprendre que possible. En fait, il utilise de nombreuses instructions goto, mais les flux de contrôle sont beaucoup plus traçables que les tempêtes goto spaghetti générées par d'autres générateurs d'analyseurs.

PackCC lui-même est sous licence MIT, mais le code généré peut être distribué sous n'importe quelle licence ou peut être utilisé dans un logiciel propriétaire.

Exemple de fichier d'entrée

Une calculatrice de bureau. Notez que les règles de grammaire récursives à gauche sont incluses.

%prefix "calc"

statement <- _ e:expression _ EOL { printf("answer=%d\n", e); }
           / ( !EOL . )* EOL      { printf("error\n"); }

expression <- e:term { $$ = e; }

term <- l:term _ '+' _ r:factor { $$ = l + r; }
      / l:term _ '-' _ r:factor { $$ = l - r; }
      / e:factor                { $$ = e; }

factor <- l:factor _ '*' _ r:unary { $$ = l * r; }
        / l:factor _ '/' _ r:unary { $$ = l / r; }
        / e:unary                  { $$ = e; }

unary <- '+' _ e:unary { $$ = +e; }
       / '-' _ e:unary { $$ = -e; }
       / e:primary     { $$ = e; }

primary <- < [0-9]+ >               { $$ = atoi($1); }
         / '(' _ e:expression _ ')' { $$ = e; }

_      <- [ \t]*
EOL    <- '\n' / '\r\n' / '\r' / ';'

%%
int main() {
    calc_context_t *ctx = calc_create(NULL);
    while (calc_parse(ctx, NULL));
    calc_destroy(ctx);
    return 0;
}

Remarques

Liens externes

• PackCC
• "Les analyseurs Packrat peuvent prendre en charge la récursivité gauche "
• jambe de bois