Existe-t-il une bonne ressource en ligne avec une collection de grammaires pour certains des principaux algorithmes d’parsing (LL (1), LR (1), LR (0), LALR (1))? J’ai trouvé beaucoup de grammaires individuelles qui appartiennent à ces familles, mais je ne connais aucune ressource utile où quelqu’un a écrit un grand nombre d’exemples de grammaires.
Est-ce que quelqu’un connaît une telle ressource?
Techniques d’parsing – Un guide pratique contient plusieurs exemples (c’est-à-dire probablement une demi-douzaine par type) de presque tous les types de grammaire. Vous pouvez acheter le livre de la 2e édition, bien que la 1ère édition soit disponible gratuitement sur le site Web de l’auteur au format PDF (près du bas du lien).
L’auteur a également des grammaires de test qu’il regroupe avec ses exemples de code de la deuxième édition, disponibles ici .
Note: toutes ces grammaires sont petites (moins de deux douzaines de règles), car elles sont évidemment publiées.
Exemples de wikipedia
grammaire
S -> F S -> ( S + F ) F -> a consortingbution
( a + a )
étapes d’parsing
S -> "(" S "+" F ")" -> ( "F" + F ) -> ( "a" + F ) -> ( a + "a" )
grammaire
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1
consortingbution
1 + 1
étapes d’parsing
need to build a parser table and traverse through states.
grammaire
S' -> SSS -> CCC -> c C | d
consortingbution
cd
étapes d’parsing
large table
grammaire
A -> C x A | ε B -> x C y | x C C -> x B x | z
consortingbution
xxzxx
étapes d’parsing
traverse large parser table
Vous pouvez également vouloir regarder
Je ne m’attendrais pas à ce que vous trouviez délibérément une grande collection de grammaires organisées de cette manière. Que gagnerait l’organisateur en retour?
Ce que vous pourriez avoir une chance de faire, c’est de trouver des générateurs d’parsingurs correspondant à chaque famille (par exemple, LL (1)), et chercher des instances d’entrées pour ce générateur d’parsingur, qui seront toutes LL (1) par définition. Par exemple, les grammaires d’ANTLR sont toutes des versions différentes de LL (k) en fonction de la version d’ANTLR que vous choisissez (la description de la version d’ANTLR indiquera ce qu’elle accepte); Les grammaires de bisons sont toutes des LALR (1) [ignorant l’option GLR récente]. Si vous allez sur mon site (voir bio), vous voyez une liste de grammaires qui sont toutes à peu près dépourvues de contexte (c’est-à-dire pas dans les classes que vous décrivez).
EDIT: Notez la précision de @Bart Kier que ANTLR peut explicitement marquer une grammaire comme LL (k) pour k spécifique.