Cart
|
[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: Type-assignment
 K.Kawaguchi wrote: > > > It's not in general easy, unless you restrict the grammar. For example, > > > consider the following TREX pattern: > > > > Right. Kawaguchi-san's another algorithm determines if a RELAX module is > > already such a restricted grammar. > > I don't think so. It is true that a restricted grammar results in > FASTER algorithm, but it's also true that type-assignment is still > tractable and in fact quite simple even for unrestricted grammars. Well, this is a subjective issue. You modified my algorithm so as to record possible interpretations. You think the algorithm is "quite simple", and James thinks it is not easy. I do not think that it is difficult, but also do not think it is very easy. 1. Ambiguity If the grammar is guaranteed to be unambiguous, the algorithm does not become simpler but the type-assignment is always unique. Any ambiguous RELAX module can be disambiguated, I guess. At least, any tree regular language can be captured by an unambiguous tree regular grammar. (Hmm, subset construction certainly creates deterministic and thus unambiguous hedge automata. But are there any algorithms which do not significantly rewrite RELAX modules? Interesting but might not be really useful.) There are many ambiguity in computer science. For example, a regular expression a*a* is ambiguous. So is (a | a). Perl and other tools happily accept such regular expressions. They also have \1, \2 , etc. so as to reference to matches to sub exprssions. For example, if we compare "aab" against \(a*\)b, the value of \1 is "aa". What happens if we compare "aaa" against (\(a*\)*)? This expression is not complicated and different implementations probably behave the same. But if we create more complicated ambiguous regular expressions, different implementations choose different interpretations (i.e., type assignment) and behave differently. Hmm, do we have to care? 2. Effortless If the grammar is guaranteed to be "effortless" (in your terminology), the algorithm can be simplified and the type-assignment is always unique. I have called this algorithm "semi-deterministic top-down with one lookahead". Simply put, you can determine *the* non-terminal for a node when you visit the node by using the type and content model of the parent element. Some RELAX modules cannot be converted to "effortless" RELAX modules. Given two such modules, its intersection can be always captured by an "effortless" module but its union cannot be always captured. That is, this class is not closed under union (and difference). K.Kawaguchi wrote: > See my previous post to Norm, which describes it step by step. It works > with TREX. I could not find it. Which message are you talking about? But we have common understanding. Cheers, 
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! 
Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|
|||||||||
