[relaxng-user] reversed derivative?

[David Tolpin]

Hi,

I am implementing an authoring tool for structured documents. The
key feature of this tool is that the user enters just text, consisting
of paragraphs. The editor offers feasible tags  for the paragraphs,
based on the structural features of the paragraph and on the context,
and then offers alternative tag sequences between the current and
the previous paragraph.

That is,  for grammar

start = element book { title, chapter* }
title = element title { text }
section = element section { title, block* }
chapter = element chapter { title, block*, section* }
block =
  element para { text }
  | element list {
      element item { text }+
    }

  - if something looking as a <title> is entered inside a <list>,
    and if user confirms that it is indeed a <title>,
  - the <list> will be closed, a new <section> or <chapter> will be opened
  - optionally, the current <section> (and <chapter>) will be closed.

A preliminary version was implemented and appears to be useful. However,
the algorithms used are not appropriate for unrestricted grammars.

I have been able to re-implement the algorithms using the validation
algorithm as described at
http://www.thaiopensource.com/relaxng/derivative.html, with obvious
extensions needed to compute all possible paths between the current
and the previous paragraphs.

However, the straightforward extension requires that decisions are
made in the document order, that is, first elements are closed,
then opened top-down. It appears to be more convenient and natural,
however (the previous version had an option which allowed to choose
the order) to
  - first open new group tags, bottom-up (that is,
    term->varlistentry->variablelist)
  - then offer to close, again bottom-up currently open tags which can
    optionally be closed.
  (open elements which are to be closed in all alternatives are closed as soon
  as possible).

I would be grateful for a hint or a pointer to a source which can
help me implement this behaviour.

I am trying to build the ascending parts suitable for reverse
reduction by traversing the schema from right to left and precomputing
the derivatives for all block-level elements, but am not sure that
I am moving in the right direction.

Sincerely,
David Tolpin
http://davidashen.net/