Shift/Réduire le conflit dans CUP

Question

J'essaye d'écrire un analyseur pour un langage javascript avec JFlex et Cup, mais j'ai quelques problèmes avec ces changements mortels/réduire les problèmes et réduire/réduire les problèmes.

J'ai fait des recherches approfondies et j'ai trouvé des tonnes d'exemples, mais je ne suis pas en mesure d'extrapoler ceux-ci à ma grammaire. Ma compréhension jusqu'à présent est que ces problèmes sont parce que l'analyseur ne peut pas décider de quelle manière il devrait prendre parce qu'il ne peut pas distinguer. La grammaire est la suivante: début avec INPUT;

INPUT::= PROGRAM; 

PROGRAM::= FUNCTION NEWLINE PROGRAM 
| NEWLINE PROGRAM; 

FUNCTION ::= function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der; 

    OPTIONAL ::= 
    | TYPE; 


    TYPE::= integer 
    | boolean 

    ARG ::= 
    | TYPE id MORE_ARGS; 

    MORE_ARGS ::= 
    | colon TYPE id MORE_ARGS; 


    NEWLINE ::= salto NEWLINE 
    | ; 

    BODY ::= ; 

Je reçois plusieurs conflits, mais ces deux sont un simple exemple:

Warning : *** Shift/Reduce conflict found in state #5 
between NEWLINE ::= (*) 
and  NEWLINE ::= (*) salto NEWLINE 
under symbol salto 
Resolved in favor of shifting. 

Warning : *** Shift/Reduce conflict found in state #0 
between NEWLINE ::= (*) 
and  FUNCTION ::= (*) function OPTIONAL id p_izq ARG p_der NEWLINE l_izq NEWLINE BODY l_der 
under symbol function 
Resolved in favor of shifting. 

PS: La grammaire est beaucoup plus complexe, mais je pense que si je vois comment ces changement/réduire les problèmes sont résolus, je serai en mesure de réparer le reste.

Merci pour vos réponses.

Answer 1

PROGRAM est inutile (in the technical sense). C'est, il ne peut pas produire une phrase parce que dans

PROGRAM::= FUNCTION NEWLINE PROGRAM 
     | NEWLINE PROGRAM; 

les deux productions pour PROGRAM sont récursives. Pour qu'un non-terminal soit utile, il doit être capable de produire éventuellement une chaîne de terminaux, et pour ce faire, il doit avoir au moins une production non récursive; sinon, la récursivité ne peut jamais se terminer. Je suis surpris que CUP ne vous ait pas mentionné cela. Ou peut-être que c'était le cas, et vous avez choisi d'ignorer l'avertissement. C'est un problème - les non-terminaux inutiles ne peuvent jamais correspondre à quoi que ce soit, donc ils finiront par aboutir à une erreur d'analyse - mais ce n'est pas le conflit d'analyse que vous signalez. Les conflits proviennent d'une autre caractéristique de la même production, qui est liée au fait que vous ne pouvez pas diviser par 0.

La chose à propos de rien est que tout nombre de rien ne sont toujours rien. Donc, si vous aviez plein de choses et que quelqu'un vous demandait exactement combien vous n'aviez pas, vous auriez un peu de problème, car pour obtenir "beaucoup" de "0 * beaucoup", vous auriez à calculer "0/0", et ce n'est pas une valeur bien définie. (Si vous aviez plein de deux, et que quelqu'un vous demandait combien de deux vous aviez, ce ne serait pas un problème: supposons que l'abondance de deux soit de 40, vous pourriez facilement calculer 40/2 = 20, ce qui fonctionne parfaitement parce que 20 * 2 = 40.)

Donc, ici, nous n'avons pas d'arithmétique, nous avons des chaînes de symboles. Et malheureusement la chaîne ne contenant aucun symbole est vraiment invisible, comme 0 l'a été pendant tous ces millénaires jusqu'à ce qu'un mathématicien arabe ait remarqué la valeur de ne pouvoir rien écrire.

Où tout cela est à venir autour de est que vous avez

PROGRAM::= ... something ... 
     | NEWLINE PROGRAM; 

Mais NEWLINE est autorisé à produire rien.

NEWLINE ::= salto NEWLINE 
     | ; 

Ainsi, la deuxième production récursive de PROGRAM peut rien ajouter. Et cela n'ajouterait peut-être pas beaucoup de temps, car la production est récursive.Mais l'analyseur doit être déterministe: il doit savoir exactement combien de rien ne sont pas présents, de sorte qu'il puisse réduire chaque rien à un terminal non-terminal et ensuite réduire un nouveau terminal non-terminal NEWLINE. Et il ne sait vraiment pas combien de choses à ajouter.

En résumé, les éléments facultatifs et les éléments répétés sont ambigus. Si vous voulez insérer un rien dans votre langage, vous devez vous assurer qu'il y a un nombre fini fixe de rien, parce que c'est la seule façon dont l'analyseur peut disséquer sans ambiguïté le néant. Maintenant, puisque le seul point de cette récursion particulière (pour autant que je puisse le voir) est de permettre des instructions terminées à la fin de la ligne vides (qui sont visibles à cause du retour à la ligne, mais ne font rien). Et vous pouvez le faire en changeant la récursion pour éviter rien:

PROGRAM ::= ... 
     | salto PROGRAM; 

---

Bien qu'il soit pas pertinent à votre problème actuel, je me sens obligé de mentionner que CUP est un générateur d'analyseur LALR et tout ce genre de choses que vous pourriez avoir appris ou lu sur Internet sur les analyseurs de descente récursifs ne pas être en mesure de gérer la récursivité gauche ne s'applique pas. (J'ai supprimé une diatribe sur la façon dont la technique d'analyse est enseignée, donc vous devrez essayer de le récupérer à partir des indications que j'ai laissées.) Générateurs d'analyseur bottom-up comme CUP et yacc/bison love left récursion. Ils peuvent gérer la récursivité droite, bien sûr, mais à contrecoeur, car ils doivent gaspiller de l'espace de pile pour chaque récursivité autre que la récursivité gauche. Il n'y a donc pas besoin de déformer votre grammaire pour faire face à la déficience; il suffit d'écrire la grammaire naturellement et être heureux. (Vous avez besoin rarement, voire jamais non terminaux représentant « le reste » quelque chose.)

---

PD: Beaucoup de rien est une référence culturelle spécifique à une chanson de l'opéra 1934 Porgy and Bess.