algorithme pour parser LALR

Bonjour,

J'ai un niveau moyen en math et c'est sans doute pour ça que j'ai du mal à comprendre les formules mathématiques présentées dans la plupart des cours sur les parseurs LR, SLR et LR(1) et LALR.

Mes difficultés viennent de la compréhension de la manière d'implémenter les méthodes premier et suivant dans les algorithmes LR(1) et LALR.

Pour LR et SLR j'ai compris comment ça marche, et je pense pouvoir les implémenter. Mais pour implémenter LALR, j'arrive pas à comprendre l'algorithme qui est derrière.

Avez-vous des exemples simples d'implémentations d'algorithme LALR.

Merci d'avance de vos réponses.

En fait l'exemple le plus connu de parser LaLR est sans doute bison.

Il construit la table First (premier) et Follow (suivant), puis construit un automate des items LR(0) pour en déduire l'automate LaLR correspondant (à quelques choses près ça se passe comme ça).

Pour construire First, c'est pas très compliqué, il suffit de connaitre les règles et la recherche est quasiment récursive.

Pour Follow, c'est presque pareil (il faut avoir calculé first avant tout ça).

Si ça peut t'aider :

http://www.cs.nuim.ie/~jpower/Course...ng/node48.html

merci pour ta réponse.

Cependant, dans la page que tu m'as indiqué, Il y a une implémentation pour une analyse descendante. Ce que je cherche c'est pour l'analyse ascendante LALR. J'ai bien vu les explications sur premier et suivant qui m'ont aidé.

Dans la pdf suivant:
http://www-verimag.imag.fr/PEOPLE/La...syntaxique.pdf

à la page 11, il y a un tableau sur LR(1). ce que je comprends pas c'est comment est calculé la colonne situations.

Merci de m'éclairer.

Le document que je t'ai donné n'était là que pour first et follow ;).

Concernant la construction de l'automate, c'est relativement simple,

prends la grammaire qui est donnée :

Z -> S $
S -> C C
C -> c C
C -> d

à l'état 0, tu mets l'axiome ainsi que toutes les règles qui peuvent être accessibles par l'axiome. Tu place un point pour indiquer là où tu es :

Z -> .S $
S -> .C C
C -> .c C
C -> .d

Ensuite, la construction des autres états se fait en avançant la lecture. Imaginons que tu ais lu la règle S, tu vas créer un état 1 avec le contenu suivant :

Z -> S. $

Tu ne mets que celle ci parce d'une part, à partir de 0 et en ayant lu S il n'y a que cette règle, ensuite tu n'en rajoutes pas parce qu'àprès le . il y a $

Maintenant, à partir de l'état 0 tu lis un C, ça te crée un état 2 :

S -> C. C

L'état n'est pas complet puisqu'il faut rajouter les règles que tu peux obtenir à partir de C (ie C -> c C et C -> d) l'état 2 devient donc :

S -> C. C
C -> .c C
C -> .d

Il suffit de répéter le processus jusqu'à ce que tous les cas aient été étudiés, ça n'est pas compliqué mais à faire à la main sur des gros automates on peut arriver à se planter, c'est pourquoi on utilise bison (qui ne fait quasiment que la même chose).

merci pour tes explications.

Ce que tu as expliqué je l'ai compris, c'était pour la grammaire LR(0) et SLR(1).

Mon problème de compréhension viens de 6 Construction d’un automate LR(1).
Je ne comprends pas comment sont calculer les valeurs entre accolade dans la colonne situation.

merci de ton aide.

Excuse moi, je n'avais pas suivi :aie:.

En fait, ce que tu as entre accolade, c'est ce qui peut arriver après la réduction de la règle.

Reprenons la grammaire :

Citation:

---

Z -> S $
S -> C C
C -> c C
C -> d

---

Dans l'état 0, tu y met tout ça et en plus tu rajoutes ce qui peux être lu après (les follow)

Z -> S $ { Epsilon }
S -> C C { $ }
C -> c C { c ; d }
C -> d { c ; d }

Ensuite, tout au long de la construction, tu gardes les valeurs pour la construction de tes états.

est-ce que les follows sont calculés pour chaque états ou une fois pour toutes. Ce que je comprends pas c'est pourquoi à l'étape 2 (q=2) les follows ne sont pas les mêmes qu'a l'état 0.

merci de ton aide

Après l'état 0, tu gardes les follow des règles que tu dérives :

Pour l'état 2, la règle que tu dérives c'est S -> c C { $ }, par conséquent, tu gardes le { $ } pour chacune des règles .

Il n'y a qu'à l'état 0 où tu as des follow différents par règle.

ok, merci beaucoup de ton aide.