TODO 13 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
* Discussion with Frédéric Bour.
  - clean up tabs -> spaces, remove trailing spaces. (use emacs in batch mode, or sed)
    check that my .emacs produces only spaces
  - annotations/attributes in .mly files
  - SDK, exposing a dump of Grammar/Lr0/Lr1
  - Engine: offer richer API
      new stack inspection API, without streams
        stack_next pourrait renvoyer une somme (stack + initial)
        allows comparing stacks
        allows exposing current state even when it is an initial state?
        meta-initial state with transition to the real initial states?
      remonter aussi la fonction element: 'a checkpoint -> int -> element de CompCert
      parameterize the type 'a env again
      and offer val input_needed : 'a env -> 'a checkpoint
                val pop: 'a env -> 'a env option
                val feed_symbol: 'a symbol -> -> 'a -> pos -> pos -> 'b env -> 'b env (* peut échouer si la transition n'existe pas *)
                val force_reduction: production -> 'a env -> 'a env (* unsafe actuellement; need a bitmap of which productions can safely be reduced in each state *)
                val default_reduction: _ lr1state -> production option
                bijection entre production et int
  - incompatibility avec ocamlyacc: Menhir discards the token when entering
    error mode, ocamlyacc doesn't.
  - allow splitting a nonterminal symbol (in a file or over multiple files).
    with an explicit keyword?

POTTIER Francois's avatar
POTTIER Francois committed
25 26 27
* Look into the format of bison's tables, and see if we could produce
  them.

POTTIER Francois's avatar
POTTIER Francois committed
28 29 30
* standard library: define "%public %inline epsilon: {}", which allows using
  "epsilon" as a marker for an empty right-hand side.

POTTIER Francois's avatar
POTTIER Francois committed
31
* Implement $0, $-1, etc.
POTTIER Francois's avatar
POTTIER Francois committed
32 33
    with named syntax along the lines of <x> foo: ...
    with and without --infer, must be type-safe (analyse left context)
POTTIER Francois's avatar
POTTIER Francois committed
34 35 36 37
    in the code and table back-ends
  On top of that, it is easy to implement mid-rule actions (à la Bison).
  On top of that, it should be easy to implement inherited attributes (à la BtYacc).
    again, should be type-safe
POTTIER Francois's avatar
POTTIER Francois committed
38

POTTIER Francois's avatar
POTTIER Francois committed
39 40 41 42
* Installation problems.
  - put menhirLib.{ml,mli} in a different directory;
  - avoid using "share/" for architecture-dependent files

POTTIER Francois's avatar
POTTIER Francois committed
43 44 45 46
* Add a flag to ignore all semantic actions, replacing them with unit,
  and replace all %type declarations with unit. Use it to build a more
  serious test suite in bench/good.

47 48 49
* Look for "artificial dependency" and remove them.
  Make sure every module is explicitly called.

POTTIER Francois's avatar
POTTIER Francois committed
50 51 52
* Develop an alternate src/Makefile that does not require ocamlbuild?
  Could use OCamlMakefile instead, for instance.

53 54 55 56
* A %type declaration with parameters is not properly checked;
  it could be useless or even ill-typed.
  Same for %on_error_reduce.

POTTIER Francois's avatar
POTTIER Francois committed
57 58 59 60 61 62 63
* Is it true that the warning "this production is never reduced" is
  sound but incomplete? i.e. certain states could be unreachable and
  we do not know it (but LRijkstra can tell us).
  Take never_reduced.mly and see if we can have a production that is
  never reduced *and no warning about it*. (Just place it behind
  another production that is never reduced.) Document this fact.

POTTIER Francois's avatar
POTTIER Francois committed
64 65 66 67 68 69 70 71 72
* If the right-hand side of a production provably generates the empty
  language, remove this production. (Must remove it explicitly, otherwise
  we lose the property that errors are detected as early as possible.
  Also, this avoids triggering the detection of epsilon-cycles, which
  assumes that all symbols are inhabited.)
  Document this trick: the empty language can be defined by "void: void"
  and can be used as an actual parameter in parameterized definitions.
  This allows making extensible definitions and instantiating them with
  "no extension".
POTTIER Francois's avatar
POTTIER Francois committed
73

74 75 76
* --compile-errors could warn about messages wider than 80 columns
                   could also warn statically about out-of-range $i?

POTTIER Francois's avatar
POTTIER Francois committed
77 78
* Dans les avantages de Menhir versus ocamlyacc (dans la doc et
  sur la page Web), ajouter le back-end Coq, l'API incrémentale
POTTIER Francois's avatar
POTTIER Francois committed
79 80
  et l'API d'inspection, les règles anonymes, la gestion fine des
  erreurs de syntaxe...
POTTIER Francois's avatar
POTTIER Francois committed
81

82
* Pénible que l'API d'inspection ne donne pas accès
83 84
  à l'état courant lorsque la pile est vide (état initial donc).
  Pourrait-on exposer cet état? Polymorphe? incoming_symbol
POTTIER Francois's avatar
POTTIER Francois committed
85
  devrait alors produit une option. Et le cas Nil du type
86
  stream devrait contenir l'état initial...
POTTIER Francois's avatar
POTTIER Francois committed
87
  attention, car si on lui applique la fonction items, on va
88 89 90 91
  obtenir un item spécial S' -> S # qui va poser problème.
  Exposer l'état initial avec un type différent lr1initial?
  De toute façon il faudra compliquer la notion de explanation
  qui ne pourra plus toujours être basée sur un item...
POTTIER Francois's avatar
POTTIER Francois committed
92

93 94 95
* gros BUG à corriger: il ne faut pas exiger le prochain token
  AVANT une réduction par défaut. Il faut suivre ocamlyacc et
  bison. Réfléchir... et corriger les deux back-ends. Attention
96 97
  toutefois, c'est un changement incompatible. Option de ligne
  de commande?
POTTIER Francois's avatar
POTTIER Francois committed
98
  (voir aussi messages de Tiphaine Turpin à partir du 30/08/2011)
POTTIER Francois's avatar
POTTIER Francois committed
99 100
  Idée de F. Bour: on pourrait annoter une production %default
  pour indiquer qu'elle doit toujours être réduite par défaut.
POTTIER Francois's avatar
POTTIER Francois committed
101
  Il faut aussi revisiter la notion de conflit end-of-stream.
102 103 104 105
  - si réduction par défaut, alors pas de conflit possible!
  - si conflit, alors pourquoi on le résoud en éliminant la
    réduction sur #? on pourrait faire aussi le choix opposé,
    à savoir éliminer toutes les autres actions. Que fait
POTTIER Francois's avatar
POTTIER Francois committed
106
    ocamlyacc?
107

POTTIER Francois's avatar
POTTIER Francois committed
108 109
* autoriser %token FOO "foo"
  pour pouvoir afficher les tokens sous forme plus lisible
110
  et auto-générer une fonction (ou une table) print_terminal
POTTIER Francois's avatar
POTTIER Francois committed
111

POTTIER Francois's avatar
POTTIER Francois committed
112
* autoriser %token FOO (unused)
113 114
  (syntaxe concrète à déterminer)
  équivalent à --unused-token FOO sur la ligne de commande.
POTTIER Francois's avatar
POTTIER Francois committed
115

116
* Produce well-chosen (predictable) names for anonymous rules?
POTTIER Francois's avatar
POTTIER Francois committed
117

POTTIER Francois's avatar
POTTIER Francois committed
118 119 120
* The construction of an anonymous rule should work also when the
  body has parameters (should produce a parameterized rule).

121 122
* In the standard library, possibly rename "anonymous" and "embedded" and
  document them. The non-inline version allows embedding an action in the
123
  middle of a rule.
124

POTTIER Francois's avatar
POTTIER Francois committed
125 126
* Add left-recursive lists to the standard library.

POTTIER Francois's avatar
POTTIER Francois committed
127 128 129 130
* Define [print_result].
  Define a printer that shows the states in the stack.
  Try computing a set of expected symbols in the current state.

POTTIER Francois's avatar
POTTIER Francois committed
131
* Generate default printers for terminal and nonterminal.
POTTIER Francois's avatar
POTTIER Francois committed
132 133
  Using modular implicits, generate terminal2token and
  nonterminal2value.
POTTIER Francois's avatar
POTTIER Francois committed
134

POTTIER Francois's avatar
POTTIER Francois committed
135 136 137 138
* document that --depend may produce inaccurate dependencies
  for parser.cmi and that it is recommended to use --raw-depend
  --ocamldep "ocamldep -modules" and work from there (which is
  what ocamlbuild does).
139

140 141
* Suite des patchs de Frédéric Bour.
    API d'inspection complète.
POTTIER Francois's avatar
POTTIER Francois committed
142
      Documenter loop_handle_undo, loop_test, acceptable.
143
      Exposer le nombre d'états (pour la mémoisation).
POTTIER Francois's avatar
POTTIER Francois committed
144
      Idem pour les productions.
POTTIER Francois's avatar
POTTIER Francois committed
145 146
      Fonctions d'affichage pour les types terminal, nonterminal, etc.?
      Fonctions d'isomorphisme entre token et 'a terminal * 'a?
POTTIER Francois's avatar
POTTIER Francois committed
147
    Librairie(s) pour la gestion des erreurs.
148
    Librairie pour la complétion du parsing.
POTTIER Francois's avatar
POTTIER Francois committed
149
      Need a way of feeding the parser a nonterminal symbol.
POTTIER Francois's avatar
POTTIER Francois committed
150
      Or a way of applying a semantic action to a vector of semantic values.
151

POTTIER Francois's avatar
POTTIER Francois committed
152 153 154
* Test and document --lalr (maybe). Explain that it is (probably)
  incompatible in principle with --explain. Modify the code to fail
  gracefully when the problem arises.
POTTIER Francois's avatar
POTTIER Francois committed
155

POTTIER Francois's avatar
POTTIER Francois committed
156 157 158
* BUG: --only-preprocess imprime des actions sémantiques où les $ ont
  été remplacés par _, ce qui rend la grammaire invalide.

POTTIER Francois's avatar
POTTIER Francois committed
159 160
* Tenter une minimisation a posteriori de l'automate. Sur la grammaire
  OCaml on devrait retrouver l'automate LALR, non?
161 162 163
  Faire cette minimisation *après* la résolution des conflits afin que
  la minimisation n'affecte pas le comportement de l'automate, même en
  présence de directives de priorité. Du coup si on combine --canonical
POTTIER Francois's avatar
POTTIER Francois committed
164 165 166 167 168
  et --minimize alors on devrait obtenir un automate correct, proche de
  IELR, voir Denny et Malloy. Confirmer.

* Pourquoi --canonical --table ne marche pas sur une grosse grammaire?
  (3m57 pour ocaml.mly versus 16s sans --table)
169
  Afficher combien de temps est passé à comprimer les tables.
POTTIER Francois's avatar
POTTIER Francois committed
170 171

* TableBackend en principe ne devrait pas avoir besoin de Invariant?
172
  Gain de temps/simplicité possible.
POTTIER Francois's avatar
POTTIER Francois committed
173

POTTIER Francois's avatar
POTTIER Francois committed
174 175 176
* bundle the Coq library with menhir, and add demos/calc-coq
  to show how it is used

POTTIER Francois's avatar
POTTIER Francois committed
177 178
* Clarifier si ocamlbuild doit recevoir -use-ocamlfind, -no-ocamlfind,
  ou rien; tester en particulier sous Windows?
POTTIER Francois's avatar
POTTIER Francois committed
179
  Modifier la doc pour recommander ocamlfind.
POTTIER Francois's avatar
POTTIER Francois committed
180

181 182
* ajouter une possibilité de désactiver certains warnings (utile pour
  le cours de compilation où on démarre avec une grammaire à trous),
fpottier's avatar
fpottier committed
183 184
  par exemple les non-terminaux inaccessibles

fpottier's avatar
fpottier committed
185
* move to a new license (GPL V2?), as per Hongbo Zhang's request.
186
* Les fichiers dans demos/ ne devraient pas être sous QPL mais libres...
fpottier's avatar
fpottier committed
187

188
* BUG: la directive $type<...> nt donne lieu à un message d'erreur bizarre
189 190
  si le non-terminal nt n'existe pas. (Jacques-Henri.)

191 192 193
* On pourrait rendre moins restrictif le critère qui garantit la terminaison
  de l'expansion des non-terminaux paramétrés. Il suffirait de vérifier que
  les paramètres effectifs sont toujours des atomes (symboles terminaux ou
194 195
  non-terminaux), non? (Jacques-Henri.)

196
* Reconnaître les directives # n "foo" dans le fichier .mly et en tenir
POTTIER Francois's avatar
POTTIER Francois committed
197 198
  compte dans les locations.

199 200 201 202 203
* BUG: message de Valentin Gatien-Baron du 09/01/2010: le bug de --explain
  est-il bien le bug connu? peut-on le corriger? ne suffirait-il pas de
  passer sous silence les conflits qui ont lieu dans une partie inaccessible
  de l'automate?

204 205 206
* Implémenter un test de détection de boucles. Si la grammaire contient une
  boucle, elle est infiniment ambiguë. Pour le test, calculer tous les
  nullables, ajouter une production unité A -> B dès qu'il existe une
207
  production A -> alpha B beta avec alpha et beta nullables, et regarder
208
  ensuite s'il existe un cycle de productions unité.
209

POTTIER Francois's avatar
POTTIER Francois committed
210
* Permettre une trace avec autre chose que fprintf stderr. Cela permettrait
211 212 213
  au programmeur (par exemple) de décider à runtime s'il veut afficher ou
  non la trace. (En mode --trace.) Et si possible, donner accès depuis
  l'extérieur à la fonction print_token qui est engendrée.
214

215
* (petit) BUG: --follow-construction n'affiche pas le contenu des états
216 217 218
  initiaux (r0)

* relire la preuve de Pager et comprendre si ce que fait Lr1.grow est correct
219
  ou pas; faut-il faire grossir les états existants, ou bien (par exemple) les
220 221 222 223
  supprimer et recommencer leur construction?

* que fait/que doit faire la combinaison --tokens-only --depend?

224
* Préserver dirname/ dans les directives #line émises.
225

226 227
* BUG: Boris (1.- bouclage parser sur une entrée erronée 2.- une lecture
  trop loin dans le stream, également liée à error).
228

229 230
* éviter "Warning: 22 conflicts ..." car emacs prend "Warning" pour un
  nom de fichier; d'après Damien, il devrait suffire que la phrase après
231 232
  les deux points ne commence pas par un nombre.

233
* ajouter une option -q pour désactiver tous les warnings
234

235 236
* si une variable est inutilisée dans une action sémantique, le
  warning est affiché dans le code produit.
237

238 239 240 241
* si une parenthèse est mal fermée dans une action sémantique,
  l'erreur de syntaxe peut être détectée par OCaml en dehors
  des actions sémantiques. Bétonner en mettant une séquence
  improbable de begin/end/parenthèseses autour de l'action?
242 243 244

* BUG: solving a shift/reduce conflict in favor of reduction can
  cut a path that was required in order to explain another conflict.
POTTIER Francois's avatar
POTTIER Francois committed
245
  (see e.g. belloeil.mly) (et le reduced_parser.mly d'Adrien Guatto)
POTTIER Francois's avatar
POTTIER Francois committed
246
  (also check the parser.mly sent by Andrej Bauer on 2016/01/21)
POTTIER Francois's avatar
POTTIER Francois committed
247
  Or just give up on explaining the conflict in this case.
248 249 250
  Take priorities into account *during* the construction of the
  automaton? Is it feasible? Compatible with Pager?

251 252
* BUG: cutdown.mly

253 254 255 256
* le fichier .conflicts devrait etre supprime par --explain s'il
  n'y a aucun conflit

* dans le dump de l'automate, rajouter les transitions qui ont
POTTIER Francois's avatar
POTTIER Francois committed
257
  ete supprimees par resolution de conflits. Afficher aussi les
258
  réductions par défaut?
259 260 261

* expliquer aussi les conflits end-of-stream

262
* Documenter l'emploi d'ocamlbuild.
263

264
* Lorsqu'on crée un pseudo-lexème pour utiliser dans les
265
  directives %prec, la question de savoir s'il est associatif
266
  à gauche ou à droite ou pas du tout ne se posera jamais. Donc,
267
  pour faire propre, on ne devrait pas autoriser l'emploi de
268 269
  %left, %right, %nonassoc (sauf pour compatibilité arrière,
  avec warning) mais introduire un nouveau mot-clé %fictitious
270 271
  ou %pseudo ou whatever.

272 273 274 275
* Autre remarque du même tonneau, si on souhaite choisir un
  niveau mais pas un statut d'associativité (parce qu'on pense
  qu'il est inutile), il faudrait pouvoir déclarer %neutral
  (whatever) et obtenir un niveau au statut non-spécifié (d'où
276 277
  erreur si on tente de consulter ce statut).

278 279 280
* Prévoir une sortie --ocamlyacc qui affiche la grammaire sans
  les liaisons des valeurs sémantiques et sans les actions
  sémantiques?
281

282 283 284 285 286
* Faire le nécessaire pour empêcher les warnings d'ocaml 3.09
  sur les valeurs sémantiques nommées et non utilisées? Le
  problème est que l'erreur est forcément rapportée dans le
  fichier .ml engendré. Et ça résoudrait le problème du cas
  où on n'utilise que $startpos(v) et pas v.