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

Question

Existe-t-il une bonne ressource en ligne avec une collection de grammaires pour certains des principaux algorithmes d'analyse syntaxique (LL(1), LR(1), LR(0), LALR(1)) ? J'ai trouvé de nombreuses grammaires individuelles qui appartiennent à ces familles, mais je ne connais pas de bonne ressource où quelqu'un a écrit un grand ensemble de grammaires d'exemple.

Quelqu'un connaît-il une telle ressource ?

Answer 1

Exemples tirés de wikipedia

LL(1)

grammaire

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

entrada

( a + a )

étapes de l'analyse syntaxique

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 

entrada

1 + 1

étapes de l'analyse syntaxique

need to build a parser table and traverse through states.

LR(1)

grammaire

S’ -> S S 
S  -> C C 
C  -> c C | d

entrada

cd

étapes de l'analyse syntaxique

large table

LALR

grammaire

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

entrada

xxzxx

étapes de l'analyse syntaxique

traverse large parser table

Vous pouvez également jeter un coup d'œil à

• Outil de simulation d'analyse syntaxique
• travaux de fourmis - >téléchargement<
• Génération de tables d'analyse à partir d'ocw mit
• De l'analyse syntaxique à la génération de code ocw mit
• autres exemples

Answer 2

Techniques d'analyse syntaxique - Guide pratique comporte plusieurs exemples (c'est-à-dire probablement une demi-douzaine par type) de presque tous les types de grammaire. Vous pouvez acheter la 2e édition du livre, bien que la 1re édition soit disponible gratuitement sur le site de l'auteur. site web en format PDF (vers le bas du lien).

L'auteur dispose également de quelques grammaires de test qu'il associe à ses exemples de code de la deuxième édition, que vous trouverez à l'adresse suivante aquí .

Remarque : toutes ces grammaires sont de petite taille (moins de quelques dizaines de règles), car il s'agit évidemment d'un livre publié.

Answer 3

Je ne m'attends pas à ce que vous trouviez une grande collection de grammaires organisées de cette façon à dessein. Que gagnerait l'organisateur en retour ?

Ce que vous pourriez faire, c'est de trouver des générateurs d'analyseurs qui correspondent à chaque famille (par exemple, LL(1)), et de chercher des instances d'entrées pour ce générateur d'analyseur, qui seront toutes LL(1) par définition. Par exemple, les grammaires d'ANTLR sont toutes des versions différentes de LL(k) selon la version d'ANTLR que vous choisissez (la description de la version d'ANTLR indiquera quel k elle accepte) ; les grammaires de Bison sont toutes LALR(1) [ignorant la récente option GLR]. Si vous allez sur mon site web (voir bio), vous verrez une liste de grammaires qui sont toutes à peu près sans contexte (c'est-à-dire, pas dans l'une des classes que vous décrivez).

EDIT : Notez la clarification de @Bart Kier que ANTLR peut explicitement marquer une grammaire comme LL(k) pour un k spécifique.

Answer 4

La plupart des installations de yacc et de ses clones ou remplacements (comme btyacc, hyacc, bison) ont des suites de tests. Les grammaires de ces suites de test constituent ensemble une liste d'exemples. Je suppose qu'il en va de même pour les générateurs de parseurs LL, mais je n'en sais pas grand-chose. Puisque ANTLR a été mentionné, je peux également signaler qu'une recherche rapide révélera le grand dépôt d'exemples suivant sous ANTLR https://github.com/antlr/grammars-v4 Donc, je suppose que ça compte aussi comme une réponse.