Quand une grammaire ambiguë ou règle de production OK? (Décalage bison / réduire avertissements)

Question

Il y a certainement beaucoup de documents et guides pratiques sur la résolution de changement / réduire les erreurs. Les bisons docs suggèrent que la bonne solution est généralement juste% pensent eux et y faire face.

Quand vous avez des choses comme ceci:

S: S 'b' S | 't'

Vous pouvez facilement les résoudre comme ceci:

S: S 'b' T | T
T: 't'

Ma question est la suivante: Est-il préférable de laisser la grammaire et une touche ambiguë% pensent déplacer / réduire les problèmes ou est-il préférable d'essayer d'ajuster la grammaire pour les éviter? Je pense qu'il ya un équilibre et il est basé sur les besoins de l'auteur, mais je ne sais pas vraiment.

Answer 1

Comme je l'ai lu, votre question est « Quand une grammaire ambiguë ou règle de production OK? »

Considérons d'abord la langue que vous décrivez. Quelle serait la conséquence de permettre une règle de production ambiguë dans la langue.

Votre exemple décrit une langue qui pourrait inclure une expression comme: t b t b t b t

L'expression résolue comme dans votre deuxième exemple serait (((( t ) b t) b t ) b t ) mais dans une Grammer ambiguë, il pourrait aussi devenir ( t b ( t b ( t b ( t)))) ou même ( t b t ) b ( t b t ). Ce qui pourrait être valide peut dépendre de la langue. Si la soustraction des modèles d'opérateur b, il ne devrait vraiment pas être ambiguë, mais si elle était plus, il pourrait être ok. Cela dépend vraiment de la langue.

La deuxième question à considérer est ce que le fichier source de grammaire résultant finit par ressembler à, après les conflits sont résolus. Comme avec tout autre code source, une grammaire est destiné à être lu par les humains, et secondairement aussi par des ordinateurs. Préférez une notation qui donne une explication plus claire de ce que l'analyseur essaie de faire de la grammaire. Autrement dit, si l'analyseur exécute un comportement non défini peut-être, par exemple, ordre d'évaluation des arguments d'une fonction dans une langue avide, faire la grammaire regarder ambigu.

Answer 2

Vous pouvez guider la résolution des conflits avec la priorité des opérateurs. Déclarer 'b' comme un opérateur gauche ou à droite associative et vous avez couvert au moins ce cas.

Pour des modèles plus complexes, tant que l'analyseur finale produit le résultat correct dans tous les cas, les avertissements ne sont pas grand-chose à craindre. Bien que si vous ne pouvez pas l'obtenir pour donner le résultat correct en utilisant des déclarations que vous auriez à réécrire la grammaire.

Answer 3

Dans mon cours du compilateur dernier semestre, nous avons utilisé le bison, et construit un compilateur pour un sous-ensemble de pascals.

Si la langue est assez complexe, vous aurez des erreurs. Tant que vous comprenez pourquoi ils sont là, et ce que vous devez faire pour les enlever, nous l'avons trouvé bien se passer. Si quelque chose était là, mais en raison du comportement fonctionnerait comme nous le voulions, et nécessiterait beaucoup à beaucoup de réflexion et de travail pour qu'il vaille la peine (et ce qui complique aussi la grammaire), nous l'avons laissé seul. Assurez-vous de bien comprendre l'erreur et le document quelque part (même pour vous-même), de sorte que vous savez toujours ce qui se passe avec elle.

Il est une analyse coûts / bénéfices une fois les choses deviennent vraiment impliqués, mais à mon humble avis, la fixation devrait prendre en considération d'abord, puis comprendre en fait ce que le travail serait (et si ce travail casse quelque chose, ou fait autre chose plus difficile) et aller de là. Ne jamais les passer en commun.

Answer 4

Quand je dois prouver qu'une grammaire est sans ambiguïté, je tends à écrire d'abord comme Parsing Expression grammaire , puis le convertir à la main à ce que la grammaire de type l'ensemble d'outils que je utilise pour les besoins du projet. Dans mon expérience, la nécessité de ce niveau de preuve est très rare, cependant, puisque la plupart quart de travail / réduire les conflits que j'ai rencontré ont été les assez insignifiants pour montrer l'exactitude (de l'ordre de votre exemple).