Generality in both parsing and generating, should the json library technique be emulated?

[jjtolton]

I've noticed when writing DCG parsers, especially when things like whitespace are involved, it becomes really difficult to write a parser that also generates with fair enumeration. I've asked about this before with fair tree enumeration, but I haven't been able to generalize this to a full parser. I noticed an interesting technique in the json library. There is a parsing//0 rule used like this to detect parsing vs generating.

Is this a good approach to copy for general generative monotonic DCG parsers?

[hurufu]

I also find handling white spaces troublesome when I work with DCGs. You might consider 2 passes: first "lexer" that normalizes spaces and new lines, and then second pass with an actual grammar. Also consider to relax your grammar a little to be able to handle errors more gracefully.

[aarroyoc]

Same thing. As a side effect, it also improves the performance.

[jjtolton]

I'll give that a try! Do you have any issues regarding fair enumeration with that, or does it seem to work well?

[hurufu]

Yes, if you will reduce search space then enumeration will be better, but IMHO fair enumeration is overrated ;) In my experience if you need some sort of enumeration it should be constrained in one way or another (for example all json files that match a certain template).

Or we can put it another way. Let's say you have a DCG that describes real numbers, can you fairly enumerate all of them? – No, because there are uncountably many reals. You can always try to do something, but in the end it all depends on the use case.

[hurufu]

Regarding parsing//0 i don't know what to say, on one hand it is smart, but on the other it looses some generality, for example when your string contains holes: X = ['{','"',f,o,o,'"',:,_A,_B|"}"].

[UWN]

See this too.

[hurufu]

I found a somewhat relevant paper where they describe some DCG rules that can deal with spaces and allows "greedy rules" which isn't necessarily the most trivial thing to do in DCG.

Also they have full implementation for SWI and it can probably be easily ported to Scryer.