Qual è il modo più semplice per dire se una grammatica BNF è ambigua o no?

Question

Vale a dire, c'è uno strumento là fuori che mostrerà automaticamente la lingua completa per una determinata grammatica, incluse le ambiguità di evidenziazione (se presenti)?

Answer 1

Potrebbe esserci qualche particolarità sulle grammatiche in stile BNF, ma in generale, decidere se una data grammatica libera dal contesto (come BNF) è ambigua non è possibile.

In breve, non esiste uno strumento perché, in generale, questo strumento è matematicamente impossibile. Potrebbero esserci alcuni casi speciali che potrebbero funzionare per te, comunque.

Answer 2

In generale, n.

Ma come approccio pratico, ciò che si può fare, viene data una grammatica, è per ogni regola, per elencare possibili stringhe di terminali/non terminali validi, per vedere se una regola ha due o più derivazioni equivalenti (che sarebbe un'ambiguità).

Il nostro DMS Software Reengineering Toolkit è un sistema di trasformazione del programma per langaugari di computer arbitrari, guidato da descrizioni grammaticali esplicite. DMS utilizza un generatore di parser per pilotare il suo motore di analisi GLR.

Il generatore di parser di DMS opzionalmente il controllo dell'ambiguità tracciato sopra, eseguendo una ricerca iterativa di approfondimento su tutte le regole di grammatica. Questo è pratico perché ha le tabelle di analisi per guidare in modo efficiente l'enumerazione delle scelte. Puoi dirlo per eseguire questo controllo fino a una profondità scelta. Può richiedere molto tempo se si sceglie una profondità di qualsiasi dimensione interessante, ma in realtà una profondità di 3 o 4 è sufficiente per trovare molte stupide ambiguità introdotte in una grande grammatica. Generalmente lo facciamo durante il nostro debugging iniziale della grammatica, e nel punto in cui pensiamo di averlo più o meno giusto.