- From: C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com>
- Date: Mon, 14 Feb 2022 08:31:09 -0700
- To: Norm Tovey-Walsh <norm@saxonica.com>
- Cc: public-ixml@w3.org
Norm Tovey-Walsh writes: >> - I think that some ways of recording parsing results may make it easy >> to see whether there is more than one XML AST for a given sentence, >> but I'm not sure that's true for every possible approach. > FWIW, my implementation does a depth first search of the parse forest, > ignoring loops. At every node where it detects more than one possible > parse, it sets down a marker noting how many possible parses there are. > ... > I haven’t tried it yet, but I believe that if I tell the search to > ignore multiple parses on nodes that won’t be serialized in the XML, > I’ll get a result that amounts to enumerating all of the possible > different VXML results. In my toy grammar from before, I think there > would only be one such parse, and consequently no ambiguity. I agree about the example grammar: only one XML representation. Here's a grammar that tries to defeat an algorithm based only on vertical loops (derivation of N-from-to from N-from-to) by making horizontal loops. Of course, if this is translated from EBNF to BNF, the horizontal loops turn into vertical loops on newly introduced nonterminals, so I think your loop detection code should work. S = (A, B, C)*, D, (A, B, C)*. D = 'x'. A = . B = . C = . Michael -- C. M. Sperberg-McQueen Black Mesa Technologies LLC http://blackmesatech.com
Received on Monday, 14 February 2022 15:31:35 UTC