TODO 11 KB
Newer Older
POTTIER Francois's avatar
POTTIER Francois committed
1
* Set up continuous integration (ci.inria.fr)...
POTTIER Francois's avatar
POTTIER Francois committed
2 3
  Check that Menhir builds (and the test pass)
  with multiple versions of OCaml.
POTTIER Francois's avatar
POTTIER Francois committed
4

POTTIER Francois's avatar
POTTIER Francois committed
5 6 7
* Add a command line option to control how "MenhirLib" should be named in the
  generated code. (Suggested by Gabriel Scherer.)

POTTIER Francois's avatar
POTTIER Francois committed
8 9
* Incremental API: expose a function `lookahead` of type `'a env -> token option`.

POTTIER Francois's avatar
POTTIER Francois committed
10 11 12
* Think about implementing Adams and Might's technique for intersecting
  a grammar with a tree automaton. (As a preprocessing step. Think about
  the interaction with parameterized symbols and with %inline.)
POTTIER Francois's avatar
POTTIER Francois committed
13
  See also de Souza Amorim, Steindorfer & Visser.
POTTIER Francois's avatar
POTTIER Francois committed
14

15
* Update the dune demos to work with a recent dune.
POTTIER Francois's avatar
POTTIER Francois committed
16

POTTIER Francois's avatar
POTTIER Francois committed
17 18 19 20 21 22 23 24 25 26 27 28 29
* Work of Frédéric on concrete syntax trees.
  - Produce a definition of the specific type of CSTs for this grammar.
    (Before expansion.)
  - Produce a grammar where the semantic actions build CSTs.
  - Define a generic (internal) type of CSTs and
    produce a function that maps generic CSTs to specific CSTs.
  - "Uninliner" : map CSTs for the expanded grammar
    back to CSTs for the source grammar?
  - "Unparsing" : map an arbitrary CST to one that can be printed
    and re-parsed identically, while inserting a minimal number of
    "parentheses". Ideally, with a static guarantee of success,
    and in linear time.

POTTIER Francois's avatar
POTTIER Francois committed
30 31
* allow a rule of the form "foo == bar" as sugar for "foo: bar { $1 }"?
  (Allow parameters. Allow several alternatives on the right-hand side,
POTTIER Francois's avatar
POTTIER Francois committed
32 33
  as long as each alternative has length 1.) (Frédéric Bour.)
  (Gabriel Scherer, "A suggestion for a more expressive production syntax.")
POTTIER Francois's avatar
POTTIER Francois committed
34
    https://sympa.inria.fr/sympa/arc/menhir/2017-05/msg00003.html
POTTIER Francois's avatar
POTTIER Francois committed
35
  (Always parenthesize production groups that share a semantic action?)
POTTIER Francois's avatar
POTTIER Francois committed
36
  (Or just disallow them?)
POTTIER Francois's avatar
POTTIER Francois committed
37

POTTIER Francois's avatar
POTTIER Francois committed
38 39 40
* Allow the generated types (token, etc.) to be annotated with OCaml
  attributes such as [@@deriving show].

POTTIER Francois's avatar
POTTIER Francois committed
41 42
* Send CompCert pull request using the new API (current_state_number)
  and MenhirLib.ErrorReports where possible.
POTTIER Francois's avatar
POTTIER Francois committed
43

POTTIER Francois's avatar
POTTIER Francois committed
44 45
* Menhir's Web page should be folded back into the git repo's README.

POTTIER Francois's avatar
POTTIER Francois committed
46
* Move more of ErrorReports from CompCert to MenhirLib.
POTTIER Francois's avatar
POTTIER Francois committed
47
  In [show], might want to apply [shorten] to the output of [f].
POTTIER Francois's avatar
POTTIER Francois committed
48

POTTIER Francois's avatar
POTTIER Francois committed
49 50 51
* Clean up the calc-inspection demo, which uses an undocumented/unfinished
  approach to error reporting.

POTTIER Francois's avatar
POTTIER Francois committed
52
* clean up this TODO file! and use gitlab issues for known bugs?
POTTIER Francois's avatar
POTTIER Francois committed
53

POTTIER Francois's avatar
POTTIER Francois committed
54
* Contribute ocamlbuild or dune rules for dealing with .messages files.
POTTIER Francois's avatar
POTTIER Francois committed
55

POTTIER Francois's avatar
POTTIER Francois committed
56 57 58
* Does ocamlbuild have support for --only-tokens and --external-tokens?
  If not, contribute it (demos/calc-param).

POTTIER Francois's avatar
POTTIER Francois committed
59 60
* Complete the implementation of --only-preprocess-for-ocamlyacc.
  Currently, the position keywords ($startpos, etc.) are not supported.
POTTIER Francois's avatar
POTTIER Francois committed
61 62
  Translate them to calls to the Parsing module.
  Document this command.
POTTIER Francois's avatar
POTTIER Francois committed
63

POTTIER Francois's avatar
POTTIER Francois committed
64 65 66 67 68
* The documentation says not to use _i,
  but --only-preprocess produces it.
  Should we avoid producing it?
  Should we check that it is not used?

POTTIER Francois's avatar
POTTIER Francois committed
69
* Possible extensions to the inspection API:
POTTIER Francois's avatar
POTTIER Francois committed
70
  - offer a way of mapping an initial state (number) back to its nonterminal symbol
POTTIER Francois's avatar
POTTIER Francois committed
71 72 73
  - expose the number of states (useful for memoisation).
  - expose the number of productions.
  - expose an isomorphism between token and xtoken = exists 'a. ('a terminal * 'a)
POTTIER Francois's avatar
POTTIER Francois committed
74
      T.token2terminal, T.token2value offer one direction (token -> xtoken)
POTTIER Francois's avatar
POTTIER Francois committed
75
      the other direction would have to be generated
POTTIER Francois's avatar
POTTIER Francois committed
76

POTTIER Francois's avatar
POTTIER Francois committed
77 78 79
* explain how to simulate inherited attributes in the manual
  (cf. post by David Chemouil on mailing list)

80 81 82
* Look for "artificial dependency" and remove them.
  Make sure every module is explicitly called.

POTTIER Francois's avatar
POTTIER Francois committed
83 84 85 86 87
* 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.)
POTTIER Francois's avatar
POTTIER Francois committed
88 89
  Currently we warn about nonterminals that generate the empty language.
  Maybe we need a %void annotation when this is intended?
POTTIER Francois's avatar
POTTIER Francois committed
90 91 92 93
  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
94

95 96 97
* --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
98 99
* Implement --copy-errors to copy error messages from one .messages
  file to another (for those states that exist in both files).
POTTIER Francois's avatar
POTTIER Francois committed
100 101
  Or --merge-errors which merges two .messages file,
  recognizing the default message as irrelevant.
POTTIER Francois's avatar
POTTIER Francois committed
102 103
  (Gabriel Scherer.)

POTTIER Francois's avatar
POTTIER Francois committed
104 105 106 107
* Add a facility to produce a set of *valid* sentences that reach *every*
  (reachable) state of the automaton. Also, a set of valid sentences that
  exercise *every* production. This could be useful in regression testing,
  says Frédéric Bour.
POTTIER Francois's avatar
POTTIER Francois committed
108

POTTIER Francois's avatar
POTTIER Francois committed
109 110
* 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
111
  et l'API d'inspection, les règles anonymes, la gestion fine des
POTTIER Francois's avatar
POTTIER Francois committed
112 113 114
  erreurs de syntaxe... Indiquer qu'avec %inline+symboles paramétrés+règles anonymes
  on va en fait beaucoup plus loin que LR(1), à condition que la grammaire
  après macro-expansion soit encore LR(1).
POTTIER Francois's avatar
POTTIER Francois committed
115

POTTIER Francois's avatar
POTTIER Francois committed
116 117 118 119 120 121 122
* Document the fact that (ocaml)yacc and Menhir do not have the same
  behavior concerning default reductions (one performs the default
  reduction *before* calling the lexer, the other does it the other
  way around). The difference is observable only when the semantic
  action has a side effect which influences the lexer (i.e., only
  when there is a "lexer hack").

123
* Pénible que l'API d'inspection ne donne pas accès
124 125
  à 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
126
  devrait alors produire une option. Et le cas Nil du type
127
  stream devrait contenir l'état initial...
POTTIER Francois's avatar
POTTIER Francois committed
128
  attention, car si on lui applique la fonction items, on va
129 130
  obtenir un item spécial S' -> S # qui va poser problème.
  Exposer l'état initial avec un type différent lr1initial?
POTTIER Francois's avatar
POTTIER Francois committed
131 132
  Ou alors, exposer juste le symbole de départ correspondant?
  Mais comment le retrouver?
POTTIER Francois's avatar
POTTIER Francois committed
133

POTTIER Francois's avatar
POTTIER Francois committed
134 135 136 137 138 139 140
* Allow %token PLUS "+"
  as a definition of "+" as syntactic sugar for PLUS
  (Check what Bison allows, and follow it.)
  This could be desugared on the fly in the fancy parser
  (although it would then be impossible to print the sugared grammar).
  (Suggested by Perry Metzger.)

POTTIER Francois's avatar
POTTIER Francois committed
141
* autoriser %token FOO [@unused]
142
  équivalent à --unused-token FOO sur la ligne de commande.
POTTIER Francois's avatar
POTTIER Francois committed
143 144
  Add an analogous mechanism for nonterminals that are known
  to be unreachable.
POTTIER Francois's avatar
POTTIER Francois committed
145

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

148 149
* Standard library: add more list forms (left-recursive lists,
  flexible lists, etc.)
POTTIER Francois's avatar
POTTIER Francois committed
150

POTTIER Francois's avatar
POTTIER Francois committed
151
* Define [print_checkpoint].
152
  Define a printer that shows the states in the stack.
POTTIER Francois's avatar
POTTIER Francois committed
153

POTTIER Francois's avatar
POTTIER Francois committed
154 155 156
* Documenter la différence de philosophie avec Denny & Malloy à propos
  des conflits (cf. email à Laurence Tratt).

POTTIER Francois's avatar
POTTIER Francois committed
157
* Add demos/calc-coq to show how the Coq back-end is used.
POTTIER Francois's avatar
POTTIER Francois committed
158 159 160

* Simplify the demos by assuming that Menhir is already installed.
  Remove find-menhir.sh.
POTTIER Francois's avatar
POTTIER Francois committed
161
  Update [make check].
POTTIER Francois's avatar
POTTIER Francois committed
162

POTTIER Francois's avatar
POTTIER Francois committed
163 164 165 166
* allow the user to choose the type of "source code intervals" that are stored
  in the stack (instead of imposing a pair of locations, $startpos and $endpos)
  and to choose how intervals are combined.

POTTIER Francois's avatar
POTTIER Francois committed
167 168 169
* write a specialized version of PackedIntArray.get to the .ml file,
  for added performance. (Suggested by Frédéric Bour.)

170 171 172
* 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
173 174
  non-terminaux), non? (Jacques-Henri.)

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

178 179 180 181 182
* 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?

183 184 185
* 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
186
  production A -> alpha B beta avec alpha et beta nullables, et regarder
187
  ensuite s'il existe un cycle de productions unité.
188

POTTIER Francois's avatar
POTTIER Francois committed
189
* Permettre une trace avec autre chose que fprintf stderr. Cela permettrait
190 191 192
  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.
193

POTTIER Francois's avatar
POTTIER Francois committed
194 195 196 197
* Offer a way of annotating the generated type definitions ([token],
  ['a terminal], ['a nonterminal], etc.) with OCaml attributes, such
  as [@@deriving show]. (Suggested by Perry Metzger.)

198
* (petit) BUG: --follow-construction n'affiche pas le contenu des états
199 200
  initiaux (r0)

201
* Préserver dirname/ dans les directives #line émises.
202

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

206 207
* é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
208 209
  les deux points ne commence pas par un nombre.

210 211
* si une variable est inutilisée dans une action sémantique, le
  warning est affiché dans le code produit.
212 213 214

* 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
215
  (see e.g. belloeil.mly) (et le reduced_parser.mly d'Adrien Guatto)
POTTIER Francois's avatar
POTTIER Francois committed
216
  (also check the parser.mly sent by Andrej Bauer on 2016/01/21)
POTTIER Francois's avatar
POTTIER Francois committed
217
  Or just give up on explaining the conflict in this case.
218

219 220
* BUG: cutdown.mly

221
* dans le dump de l'automate, rajouter les transitions qui ont
POTTIER Francois's avatar
POTTIER Francois committed
222
  ete supprimees par resolution de conflits. Afficher aussi les
223
  réductions par défaut?
POTTIER Francois's avatar
POTTIER Francois committed
224

POTTIER Francois's avatar
POTTIER Francois committed
225 226
* Ideally, [PartialGrammar] should avoid renaming the parameters of
  a rule, when there is no need to do so. The renamed parameter is
227 228
  visible in sort unification error messages and in messages about
  duplicate formal parameters (test/bad/duplicate-formal.mly).
POTTIER Francois's avatar
POTTIER Francois committed
229 230 231 232 233 234 235 236 237 238 239

* Create a clean functor out of LRijkstra.
  - Must use Cmly_api instead of Grammar
    (or must cleanly document its minimum requirements)
  - Must not perform any side effects
  - Must produce reachability information about pairs (s, z)
  On top of that, implement a GRAMMAR -> GRAMMAR transformation
  that removes all "don't care" entries in the reduction table.
  Then, implement partition refinement for a union of n GRAMMARs (?)
  as a way of testing whether two LR(1) automata (whose LR(0) skeleta
  are identical) are equivalent.
POTTIER Francois's avatar
POTTIER Francois committed
240 241 242 243 244 245 246

* Quand on est dans un état d'erreur et qu'on tente une réduction
  (car elle est activée dans l'état courant), si l'action sémantique
  fait $syntaxerror, on va apparemment boucler (on rattrape l'exception
  et on se retrouve en mode gestion d'erreur dans le même état; cf. bug
  rapporté par Gabriel Scherer sur la grammaire d'OCaml, OCaml 0007847).
  On pourrait détecter ce cas et le traiter spécialement?