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

Est-il une bonne ressource en ligne avec une collection de grammaires pour certains des principaux l'analyse des algorithmes (LL(1), LR(1), LR(0), LALR(1))? J'ai trouvé de nombreuses grammaires qui tombent dans ces familles, mais je ne connais pas la bonne ressource d'où quelqu'un a écrit un grand nombre d'exemple les grammaires.

Quelqu'un sait-il de la ressource?

Ce sont l'analyse des algorithmes de ne pas grammaires. Entendez-vous des exemples de syntaxe qui nécessite un type de l'analyseur ou d'une autre?
J' pense techniquement parlant, LL(1), etc. sont en fait des familles de grammaires. L'analyse des algorithmes nommée d'après eux sont des algorithmes qui peuvent analyser toute la grammaire qui se trouve être dans la famille des langues.
Je vous suggère de prendre un coup d'oeil à la ANTLR site web. Il a quelques bonnes grammaires de langages 😉
Si vous avez eu une telle liste, ce qui sur terre feriez-vous avec elle? La liste des noms dans chaque catégorie ne semble pas très intéressant en lui-même; vous ne voulez sûrement pas à réellement traiter le contenu de toutes ces grammaires?
Baxter - je suis en train de l'enseignement d'une compilateurs cours et continuer de se faire voler exemple les grammaires à partir d'autres sources, quand je veux montrer les différentes analyse des algorithmes. Il est difficile (mais faisable) pour créer des grammaires non trivial dans ces catégories, et très difficile de faire des grammaires qui sont LR(1), mais pas LALR(1) ou LALR(1), mais pas SLR(1). J'espérais trouver des exemples du monde réel les grammaires qui correspondent à ces descriptions de sorte que je puisse me concentrer sur la présentation, il a le matériel plutôt que de peaufiner les grammaires.
Haïssent, peut-être qu'il a disparu parce que vous avez voulu trop en faire.
Le livre dans ma réponse ci-dessous semble avoir de bons exemples qui serait un bon ajustement pour un compilateur de classe.
Le suivant lien vers mon dépôt GitHub contient 4 LL(1) les grammaires, un LR(0) grammaire n'est PAS LL(1), un SLR(1) qui n'est PAS LR(0) et un LR(1) qui n'est PAS SLR(1). TOUS les exemples peut être compilé et exécuté en écrivant simplement "make" dans le terminal de tout *.nix comme OS.

InformationsquelleAutor templatetypedef | 2011-06-25

grammar lalr ll lr parsing

19

Techniques D'Analyse - Un Guide Pratique a plusieurs exemples (c'est à dire probablement une demi-douzaine par type) de presque tous les types de grammaire. Vous pouvez acheter de la 2ème édition livre, bien que la 1ère édition est disponible gratuitement sur l'auteur site web au format PDF (près de bas de lien).

L'auteur a aussi quelques test grammaires qu'il bundles avec ses exemples de code à partir de la deuxième édition, qui peut être trouvé ici.

Remarque: tous ces grammaires sont de petite taille (moins d'une douzaine de règles), car évidemment d'un livre.

InformationsquelleAutor Jason Moore
36

Exemples de wikipedia

LL(1)

grammaire
```
S -> F
S -> ( S + F )
F -> a
```
entrée
```
( a + a )
```
l'analyse des mesures
```
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 
```
entrée
```
1 + 1
```
l'analyse des mesures
```
need to build a parser table and traverse through states.
```
LR(1)

grammaire
```
S’ -> S S 
S  -> C C 
C  -> c C | d
```
entrée
```
cd
```
l'analyse des mesures
```
large table
```
LALR

grammaire
```
A -> C x A | ε
B -> x C y | x C
C -> x B x | z
```
entrée
```
xxzxx
```
l'analyse des mesures
```
traverse large parser table
```
Vous pouvez également avoir un coup d'oeil à
- pouvez-vous s'il vous plaît dites-moi comment prouver une grammaire à LR(0) ou SLR(1)?
- Vous voudrez peut-être consulter cs143.stanford.edu, Stanford compilateurs sûr, qui a tout un tas de conférence de diapositives et de documents détaillant la façon dont vous le ferais. Le deuxième problème, et à mi-parcours (et leurs solutions) entrer dans quelques détails à ce sujet.
- Je ne crois pas que la grammaire est LR(0). Dans l'état: [S -> E .], [E -> Adresse . + B] nous avons un décaler/réduire les conflits. Nous avons besoin d'utiliser un jeton de prospection afin de déterminer s'il faut réduire, S -> Adresse . sur $ d'anticipation, ou de continuer de changer. Le conflit est résolu en utilisant le générique de SUIVRE l'ensemble de S, faire de la grammaire SLR pas LR(0).
- Je suis d'accord avec @ChrisSmowton
InformationsquelleAutor Prashant Bhate
2

Je ne voudrais pas vous attendre à trouver une grande collections de grammaires organisée de cette façon sur le but. Ce serait l'organisateur de gain en retour?

Ce que vous pourriez avoir une chance de le faire, c'est de trouver un analyseur de générateurs qui correspondent à chaque famille (par exemple, LL(1)), et aller chercher les instances d'entrées pour que l'analyseur générateur, qui seront tous LL(1) par définition. Par exemple, ANTLR de grammaires sont toutes différentes versions de LL(k) en fonction de la version de ANTLR vous chercher (la description de la ANTLR version dira ce k il accepte); Bison grammaires sont tous LALR(1) [en ignorant la récente GLR option]. Si vous allez sur mon site (voir bio), vous verrez une liste de grammaires qui sont toutes à peu près libre de tout contexte (qui est, non pas dans les catégories que vous décrivez).

EDIT: Remarque @Bart Kier a précisé que les ANTLR peut marquer explicitement une grammaire LL(k) pour k.
- Bonne suggestion pour essayer de parser des générateurs. À l'aide de ANTLR, vous pouvez définir le style à l'avance manuellement comme ceci: options { k=1; } pour LL(1), ou, par défaut options { k=*; } pour LL(k).
- Kiers: j'étais sous l'impression que les anciennes versions de ANTLR ne pouvais pas faire k>1 et k=* diversement. Faire toutes les versions d'accepter une déclaration explicite? Toujours intéressant de savoir. Je pensais que le plus récent ANTLR utilisé grammmar-règle spécifique lookaheads à comprendre ce que la prospection a été automatiquement. Mais je ne suis pas un ANTLR expert.
- Je crois que le délié d'anticipation, k=*, a été ajoutée dans le ANTLR v3. ANTLR v2.x a toujours eu un fixe k. C'est hors de ma tête, je vais jeter un oeil à ma copie de la ANTLR de référence à l'avenir et si je ne me trompe, je vais rectifier. Mais je suis sûr que c'est correct.
InformationsquelleAutor Ira Baxter

Vous devez vous connecter pour publier un commentaire.