Forum de Ti-Gen.org, le site francophone des TI

Bienvenue Invité ! Se connecter Mes sujets	Administrer
Utilisateurs actifs : Aucun membre + 1 visiteur

Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.

:: Index » Forum Ti68K » Programmation C » rendre une grammaire LL(1) (5 réponse(s))

./POST DE DEPART (post n°0) Marquer comme non lu.

Invité

Ecrit le: Samedi 3 avril 2004 à 15:59

bonjour,
est-il toujours possible de transformer une grammaire pour la rendre finalement exploitable avec un parser LL(1)?
Si ce n'est pas le cas, y a-t-il des regles precises pour tenter de s'en rapprocher au maximum?
merci.

./Post n°1 Marquer comme non lu.

Kevin Kofler

Ecrit le: Samedi 3 avril 2004 à 18:16

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

Il y a des méthodes de transformations de grammaires, mais elles n'élargissent pas beaucoup le nombre de grammaires exploitables. Il faut donc recourir à des astuces.

L'astuce utilisée habituellement est d'utiliser les productions (le code utilisateur qui est mis dans les grammaires de style yacc/Bison) pour sauvegarder du contexte supplémentaire. Donc:
* La grammaire accepte un ensemble de programmes plus large, et c'est aux productions de virer ceux qui ne sont pas conformes à la grammaire non-LL stricte.
* Souvent, la grammaire LL ne peut faire qu'une partie de l'interprétation sémantique, la vraie interprétation sémantique est faite par les productions et/ou par des passes successives au parsing.

Dans tout ceci, LL peut être remplacé par d'autres catégories de grammaires parsables systématiquement: LR, LALR etc. (Par exemple yacc/Bison utilisent du LALR.)

Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!

./Post n°2 Marquer comme non lu.

Invité

Ecrit le: Samedi 3 avril 2004 à 18:25

justement, je me trouve confronte a une grammaire qui demande pour certaines productions (peut etre meme pour la plupart) au moins deux ou trois tokens de look-ahead (les ensembles fisrt et follow de certains non-terminaux sont loins d'etre disjoints). Pourtant j'ai l'intuition qu'elle peut etre rendue LL(1) [je reste sur la technique LL(1), puisque je voudrais ecrire l'analyseur a la main], mais je ne connais aucune technique pour ce faire (a part la factorisation a gauche qui me parait inutile ici).
pour info, la grammaire en question de trouve ici : http://www.prism.uvsq.fr/~bad/Enseignement/Compil/Projet/2002/miniC.html
merci d'avance