Exemples de grammaires LL (1), LR (1), LR (0), LALR (1)?

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

LL (1)

grammaire

S -> F S -> ( S + F ) F -> a 

consortingbution

 ( a + a ) 

étapes d’parsing

 S -> "(" S "+" F ")" -> ( "F" + F ) -> ( "a" + F ) -> ( a + "a" ) 

LR (0)

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. 

LR (1)

grammaire

 S' -> SSS -> CCC -> c C | d 

consortingbution

 cd 

étapes d’parsing

 large table 

LALR

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

  • Outil d’parsing du simulateur
  • antlr works – > télécharger <
  • Génération de tables d’parsingurs depuis ocw mit
  • De l’parsing à la génération de code ocw mit
  • exemples supplémentaires

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.