Rewrite règle récursive BNF avec itération

Question

Regardez la règle BNF récursive suivante

(1) X = Xa | b 

Ce produit des phrases comme

X = b 
X = ba 
X = baa 
X = baaa 
... 

Cela peut être écrit comme

(2) X = b a* 

où la main droite le côté n'est pas récursif

Maintenant, jetez un oeil à la règle BNF récursive suivante

(3) X = { X } | b 

Cela produit des phrases comme

X = b 
X = {b} 
X = {{b}} 
X = {{{b}}} 
... 

est d'une manière non récurrente, il possible de réécrire la règle (3) analogue à celle que nous avons fait quand nous avons réécrit la règle (1) à la règle (2).

Observez que X = {* b} * n'est pas bon puisque les parenthèses doivent être équilibrées.

Answer 1

Je ne sais pas si la question ci-dessus est possible de répondre. La raison de la question ci-dessus était que je voulais éviter une boucle infinie dans mon analyseur (écrit en Java). Une façon était de s'assurer que les règles BNF ne sont pas récursives, d'où ma question. Mais une autre façon est d'utiliser la règle récursive, mais évitez la boucle infinie dans mon programme (Java). Il s'avère que vous pouvez éviter les boucles par instanciation paresseuse.

Par exemple regarder les règles suivantes:

expression = term ('+' term)*; 
term  = factor ('*' factor)*; 
factor  = '(' expression ')' | Num; 

expression

() appelle terme(), qui appelle le facteur(), qui appelle l'expression(), on peut ainsi se retrouver avec boucle infinie. Pour éviter que l'on peut utiliser instanciation paresseux, donc au lieu d'écrire quelque chose comme:

public Parser expression() { 
    expression = new ... 
    return expression; 
} 

nous écrire à la place:

public Parser expression() { 
    if (expression == null) { 
     expression = new ... 
    } 
    return expression; 
} 

Observons que vous devez déclarer l'expression comme une variable d'instance pour obtenir ce travail.