Transformation d'une régle de la grammaire

**javalhoussain** · 26/12/2010, 21h22

Bonjour ,
J'ai une règle qui provoque de récursivité j'essaye de la transformer mais toujours y a de boucle si vous pouvez m'aider à la reformuler :

Code autre :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
INSTR        :  'if' EXPR 'then do 'INSTR SUITE 
				| 'while' EXPR' do' INSTR 
				| LVALUE' :='EXPR 
				| 'return' EXPR
                                | 'return'
				| 'ident ('EXPRLIST')'
				| 'begin' SEQUENCE 'end' 
				| 'begin end'; 
SUITE	     :EOF|' else' INSTR ;

**regwb** · 27/12/2010, 05h03

Ton but c'est quoi, enlever l'INSTR qui apparait à droite de la règle INSTR?

Je suis pas sûr de voir le problème, si le but c'est de parser cette grammaire je pense que la forme actuel va très bien. Le genre de problème avec la récursivité vient de la "left recursion" en général:
http://en.wikipedia.org/wiki/Left_recursion

Mais ici ça n'est pas le cas. Sinon je ne suis pas sûr d'avoir bien compris ce que tu veux dire par enlever la récursivité, mais je suis pas sûr qu'on puisse aller beaucoup plus loin que ça.

**TropMDR** · 27/12/2010, 08h40

Envoyé par javalhoussain

Bonjour ,
J'ai une règle qui provoque de récursivité j'essaye de la transformer mais toujours y a de boucle si vous pouvez m'aider à la reformuler :

De toute évidence, le langage que tu décris est infini (prendre tout terme de la forme while true do while true do while true..... do return, avec profondeur n, pour tout n). Donc une grammaire finie le décrivant aura forcément une forme de "récursivité". Ton problème est donc mal posé

**javalhoussain** · 28/12/2010, 23h36

Bonjour,

Envoyé par TropMDR

De toute évidence, le langage que tu décris est infini (prendre tout terme de la forme while true do while true do while true..... do return, avec profondeur n, pour tout n). Donc une grammaire finie le décrivant aura forcément une forme de "récursivité". Ton problème est donc mal posé

Merci bien pour l'aider à éclairer le problème mais question qui se pose comment éviter ce genre de compléxité pour simplifier l'analyse descendent.