Puis-je convertir n'importe quelle grammaire en une grammaire de priorité d'opérateur?

Question

Toute grammaire peut-elle être implémentée par l'opérateur de précédence de l'opérateur?

Answer 1

Si vous demandez si vous pouvez changer la priorité de l'opérateur d'une langue à travers la grammaire, alors la réponse est: oui, bien sûr.

Si vous demandez si vous pouvez analyser une grammaire contextuelle «typique» en utilisant la méthode Pratt de l'analyse descendante de l'opérateur, alors la réponse est non. MAIS vous pouvez mélanger les deux. Un bon article couvrant l'analyse Pratt qui devrait vous donner quelques informations sur l'application de ceci à un analyseur de descente récursif: http://effbot.org/zone/simple-top-down-parsing.htm

Answer 2

Ceci est une excellente question, pour laquelle la réponse est: oui. Il apparaît comme un problème doublement étoilé (# 4.21) dans le chapitre 4 du texte Hopcroft & Ullman sur la Computabilité et les langages formels. La réponse (une preuve résumée par construction) est également fournie. Très brièvement, il suppose une pré-conversion en GNF réduit, à partir de laquelle la construction finale est effectuée pour enlever les non-terminaux adjacents. Pas la construction la plus efficace, mais cela fonctionne (si vous pouvez suivre le traitement similaire pour la conversion en CNF et GNF plus tôt). J'espère que cela aide!