Quelle est la meilleure façon de dire si une grammaire BNF est ambiguë ou non?

Question

A savoir, est-il un outil là-bas qui montrera automatiquement la langue complète pour une grammaire donnée, y compris les ambiguïtés mettant en évidence (le cas échéant)?

Answer 1

Il est peut-être une particularité au sujet de style BNF grammaires, mais en général, de décider si une grammaire sans contexte donné (par exemple BNF) est ambiguë est impossible.

En bref, il n'existe pas un outil, car en général, cet outil est mathématiquement impossible. Il pourrait y avoir des cas particuliers qui pourraient travailler pour vous, bien.

Answer 2

En général, non.

Mais comme une approche pratique, ce que vous pouvez faire, est donné une grammaire, est pour chaque règle, d'énumérer les chaînes possibles de terminaux valides / non-terminaux, pour voir si une règle a deux ou plusieurs équivalents dérivations (ce qui serait un ambiguïté).

est un système de transformation de programme pour langauges informatiques arbitraires , tirée par les descriptions de grammaire explicites. DMS utilise un générateur d'analyseur syntaxique pour entraîner le moteur d'analyse syntaxique de GLR.

générateur d'analyseur de DMS en option le contrôle d'ambiguïté esquissée ci-dessus, en lançant une recherche itérative approfondissement dans toutes les règles de grammaire. Ceci est pratique car il a les tables parse pour guider efficacement l'énumération des choix. Vous pouvez lui dire d'exécuter cette vérification jusqu'à une profondeur choisie. Il peut prendre beaucoup de temps si vous choisissez une profondeur de toute taille intéressante, mais en fait une profondeur de 3 ou 4 est suffisante pour trouver de nombreuses ambiguïtés stupides introduites dans une grande grammaire. Nous faisons généralement lors de nos débogage de grammaire initiale, et au point où nous pensons avoir à peu près droit.