Re: implementing ShEx recursive shapes

Yes, I implemented the Regular Expression derivatives algorithm inspired
from RelaxNG. The origins of the algorithm come from Janusz Brozozowski
(1964). A re-examination of the algorithm can be found in [2].

I am planning to write a paper explaining the implementation in a near
future. Let me know if you are interested and I can send you a draft as
soon as it is available.

Meanwhile, you can see the Scala source code which is available here:

https://github.com/labra/ShExcala/blob/master/src/main/scala/es/weso/shex/ShapeValidatorWithDeriv.scala

My first implementation followed the inference rules that I wrote in the
ShEx wiki and used backtracking (which had exponential growth). It can be
found here:

https://github.com/labra/ShExcala/blob/master/src/main/scala/es/weso/shex/ShapeValidatorBacktracking.scala

[1] Brzozowski, Janusz A. (1964). Derivatives of regular expressions.
Journal of the ACM, 11(4), 481– 494.
[2] Scott Owens, John Reppy, and Aaron Turon. 2009. Regular-expression
derivatives re-examined.
Journal of Functional Programming 19, 2 (March 2009), 173-190.
http://dx.doi.org/10.1017/S0956796808007090

Best regards, Jose Labra

On Sun, Jul 27, 2014 at 10:04 AM, Eric Prud'hommeaux <eric@w3.org> wrote:

> * Peter F. Patel-Schneider <pfpschneider@gmail.com> [2014-07-26
> 14:59-0700]
> > I came across a comment on how to implement recursive ShEx shapes
> > using a technique used elsewhere (in RelaxNG, I think).  Of course,
> > now that I want to look up this technique, I can't find the comment.
> >
> > Does anyone know which technique is being used?
>
> Jose Labra Gayo told me that he implemented James Clark's RelaxNG
> algorithm <http://www.thaiopensource.com/relaxng/derivative.html>.
>
> I haven't looked at what he did, but I expect he took the subset of
> the algorithm required for 'interleave'd contents. He may also have
> exteneded it to handle reverse arcs and negative arc assertions
> (both excluded from the Submission, but bantied about as potential
> requirements).
>
>
> > peter
> >
>
> --
> -ericP
>
> office: +1.617.599.3509
> mobile: +33.6.80.80.35.59
>
> (eric@w3.org)
> Feel free to forward this message to any list for any purpose other than
> email address distribution.
>
> There are subtle nuances encoded in font variation and clever layout
> which can only be seen by printing this message on high-clay paper.
>
>


-- 
Saludos, Labra