Discussion :

[jalam]

Bonjour et bonne année à tt le monde!

Il parait qu'on a besoin d'éliminer la récursivité à gauche et de factoriser à gauche la grammaire d'un langage avant de pouvoir écrire un analyseur syntaxique descendant. J'aimerais bien savoir pourquoi? est ce que quelqu'un pourrait m'aider?
merci

[gorgonite]

regardes de plus près l'algorithme du packrat...

[GrandFather]

Bonjour,

Il parait qu'on a besoin d'éliminer la récursivité à gauche et de factoriser à gauche la grammaire d'un langage avant de pouvoir écrire un analyseur syntaxique descendant.

L'analyse descendante récursive est la plus facile à coder, mais elle exige effectivement que la grammaire ne soit pas récursive à gauche, ceci pour éviter que l'analyseur ne rentre dans une boucle récursive infinie (enfin, infinie, jusqu'au débordement de pile plutôt ).

[gorgonite]

L'analyse descendante récursive est la plus facile à coder, mais elle exige effectivement que la grammaire ne soit pas récursive à gauche, ceci pour éviter que l'analyseur ne rentre dans une récursion infinie (enfin, infinie, jusqu'au débordement de pile plutôt ).

justement, pas forcemment mais cela reporte une partie du coût temporel vers la mémoire...

[Jean-Marc.Bourguet]

justement, pas forcemment mais cela reporte une partie du coût temporel vers la mémoire...

Je ne comprends pas ce que tu veux dire. La descente récursive est un algo prédictif: on regarde les symboles de look-ahead et on choisi la production qu'ils commencent. Si le non-terminal est récursif à gauche, on va partir en récursion infinie.

[gorgonite]

Je ne comprends pas ce que tu veux dire. La descente récursive est un algo prédictif: on regarde les symboles de look-ahead et on choisi la production qu'ils commencent. Si le non-terminal est récursif à gauche, on va partir en récursion infinie.

http://pdos.csail.mit.edu/~baford/packrat/thesis/

[Jean-Marc.Bourguet]

http://pdos.csail.mit.edu/~baford/packrat/thesis/

* Ok, des algo non deterministes (poursuivant plusieurs analyses en paralleles) ou avec backtrack peuvent etre descendants et parser des grammaires ayant de la recursivite a gauche.

* Je ne vois pas l'interet d'un algo qui utilise une autre description des langages que des CFGs comme reponse a une question sur les grammaires... mais il faudrait que je lise la these plus loin que la presentatio - ah, dans celle-ci il parle de grammaire TDPL mais c'est la premiere fois que je vois le mot grammaire associe avec une description TDPL; une description TDPL est plus proche d'un programme prolog ou on utilise beaucoup de cut que d'une grammaire.

(Edit) Citation de ton document: "In TDPL, while right recursion works in much the same way as it does in a CFG, a left-recursive definition is considered erroneous, because its interpretation under TDPL rules leads to a degenerate self-reference."