Not possible to set priority on rules

[martian-a]

The spec doesn't mention prioritisation of rules or how precedence is to be determined. This means that when I have rules that are ambiguous:

1. I can't predict or influence which rule will take precedence over another
2. Results are inconsistent across parsers

To illustrate point 2, see karaoke_ixml.zip which contains:

• an iXML grammar
• a sample input file
• the XML generated by several iXML processors using those two inputs

The processors compared are:

• Markup Blitz 1.9
• NineML via XML Calabash 3.0.20
• Agence XML's Invisible XML Tester
• jωIXML
• ixampl

No two processors returned the matching results.

Even if implementations were to continue implementing their own logic for precedence, as a grammar author it would be helpful to be able to specify which rule I expect take priority over another. So that, for example, to disambiguate the following grammar:

   song-list: group+ .
       group: (artists, songs) .
       songs: song+ .
     artists: text, line-ending .
        song: text, multiplex?, code, line-ending .
   @multiplex: -" (Multiplex)", +"true" .
       @code: -" ", [Lu], [Lu], [Nd], [Nd], [Nd], [Nd], [Nd] .

        -text: (word, " ")*, word .
        -word: [L; N; P; Sc]* .
 -line-ending: (-#a; -#d) .

I could specify that:

• the song rule is a higher priority than the artists rule
• the code and multiplex rules are a higher priority than the text rule

Because although Exhale (Shoop Shoop) (Multiplex) MH04561 matches both the artists and song rules, if a processor isn't going to attempt to disambiguate them by, for example, giving precedence to the rule that has the most factors, then I would like it to choose song over artists because of the priorities I specified. In the example I've provided above, that first priority rule would probably make the second redundant but extra layers of priority might be relevant in a more complex grammar.

[spemberton]

Sorry, but I completely disagree with this analysis. Precedence can easily be specified by grammar rules, and is a normal use of grammar. I tried three ixml implementations on a sample input I created, and I got the same result from all three. On the supplied input, the complaint is that the input is ambiguous: <!-- AMBIGUOUS The input from line.pos 1.1 to 14.1 can be interpreted as 'group+' in 3 different ways: 1: group+[1.1:]: group[:3.1] group+[:14.1] 2: group+[1.1:]: group[:4.1] group+[:14.1] 3: group+[1.1:]: group[:6.1] group+[:14.1] --> and that is because "text" is all encompassing. I just checked and "Exhale (Shoop Shoop) (Multiplex) MH04561" matches 'artists' as well as 'song', so the poor parser doesn't know what to match it against. It's not a problem of precedence but of an ambiguous grammar. Steven On Wednesday 08 October 2025 21:13:15 (+02:00), martian-a wrote: [Unlabeled Image] martian-a created an issue (invisibleXML/ixml#310) <#310> The spec doesn't mention prioritisation of rules or how precedence is to be determined. This means that when I have rules that are ambiguous: I can't predict or influence which rule will take precedence over another Results are inconsistent across parsers To illustrate point 2, I've attached karaoke_ixml.zip <https://github.com/user-attachments/files/22784370/karaoke_ixml.zip> that contains: an iXML grammar a sample input file the XML generated by several iXML processors using those two inputs The processors compared are: Markup Blitz 1.9 <https://github.com/GuntherRademacher/markup-blitz> NineML via XML Calabash 3.0.20 <https://codeberg.org/xmlcalabash/xmlcalabash3> Agence XML's Invisible XML Tester <https://www.agencexml.com/ixml/tester.xml> jωIXML <https://johnlumley.github.io/jwiXML.xhtml> ixampl <https://www.cwi.nl/~steven/ixml/tutorial/run.html> No two processors returned the matching results. Even if implementations were to continue implementing their own logic for precedence, as a grammar author it would be helpful to be able to specify which rule I expect take priority over another. So that, for example, to disambiguate the following grammar: song-list: group+ . group: (artists, songs) . songs: song+ . artists: text, line-ending . song: text, multiplex?, code, line-ending . @multiplex: -" (Multiplex)", +"true" . @code: -" ", [Lu], [Lu], [Nd], [Nd], [Nd], [Nd], [Nd] . -text: (word, " ")*, word . -word: [L; N; P; Sc]* . -line-ending: (-#a; -#d) . I could specify that: the song rule is a higher priority than the artists rule the code and multiplex rules are a higher priority than the text rule Because although Exhale (Shoop Shoop) (Multiplex) MH04561 matches both the artists and song rules, if a processor isn't going to attempt to disambiguate them by, for example, giving precedence to the rule that has the most factors, then I would like it to choose song over artists because of the priorities I specified. In the example I've provided above, that first priority rule would probably make the second redundant but extra layers of priority might be relevant in a more complex grammar. — Reply to this email directly, view it on GitHub <#310> , or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNIXLZ2SYK42LYIL5M6IZL3WVO4XAVCNFSM6AAAAACIVA6HVSVHI2DSMVQWIX3LMV43ASLTON2WKOZTGQ4TMNJYGYZTOMY> . You are receiving this because you are subscribed to this thread.

[spemberton]

I should also mention if the input is ambiguous (as in this case), implementations are expressly allowed to produce a different result; they are required to produce one of the ambiguous parses, without further specification of how that parse is chosen. All implementations produce ixml:state="ambiguous" on the root element as they are required to do, so there is no problem in this case. The problem is the grammar. Steven On Wednesday 08 October 2025 21:13:15 (+02:00), martian-a wrote: [Unlabeled Image] martian-a created an issue (invisibleXML/ixml#310) <#310> The spec doesn't mention prioritisation of rules or how precedence is to be determined. This means that when I have rules that are ambiguous: I can't predict or influence which rule will take precedence over another Results are inconsistent across parsers To illustrate point 2, I've attached karaoke_ixml.zip <https://github.com/user-attachments/files/22784370/karaoke_ixml.zip> that contains: an iXML grammar a sample input file the XML generated by several iXML processors using those two inputs The processors compared are: Markup Blitz 1.9 <https://github.com/GuntherRademacher/markup-blitz> NineML via XML Calabash 3.0.20 <https://codeberg.org/xmlcalabash/xmlcalabash3> Agence XML's Invisible XML Tester <https://www.agencexml.com/ixml/tester.xml> jωIXML <https://johnlumley.github.io/jwiXML.xhtml> ixampl <https://www.cwi.nl/~steven/ixml/tutorial/run.html> No two processors returned the matching results. Even if implementations were to continue implementing their own logic for precedence, as a grammar author it would be helpful to be able to specify which rule I expect take priority over another. So that, for example, to disambiguate the following grammar: song-list: group+ . group: (artists, songs) . songs: song+ . artists: text, line-ending . song: text, multiplex?, code, line-ending . @multiplex: -" (Multiplex)", +"true" . @code: -" ", [Lu], [Lu], [Nd], [Nd], [Nd], [Nd], [Nd] . -text: (word, " ")*, word . -word: [L; N; P; Sc]* . -line-ending: (-#a; -#d) . I could specify that: the song rule is a higher priority than the artists rule the code and multiplex rules are a higher priority than the text rule Because although Exhale (Shoop Shoop) (Multiplex) MH04561 matches both the artists and song rules, if a processor isn't going to attempt to disambiguate them by, for example, giving precedence to the rule that has the most factors, then I would like it to choose song over artists because of the priorities I specified. In the example I've provided above, that first priority rule would probably make the second redundant but extra layers of priority might be relevant in a more complex grammar. — Reply to this email directly, view it on GitHub <#310> , or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNIXLZ2SYK42LYIL5M6IZL3WVO4XAVCNFSM6AAAAACIVA6HVSVHI2DSMVQWIX3LMV43ASLTON2WKOZTGQ4TMNJYGYZTOMY> . You are receiving this because you are subscribed to this thread.

[martian-a]

Thanks for your feedback Steven.

The input I provided is an extract from a much larger text file. The only reliable difference between a line that represents a list of artists and a line that represents a song is that the penultimate factor in a song is always a code.

I think that code and text will currently always overlap because text needs to also match uppercase letters and 0-9, and there's no way yet to exclude code from text. Although I plan to try John Lumley's experimental support for that ASAP.

Precedence can easily be specified by grammar rules

Where is this defined in the spec? Apologies if I've missed it.

[LinguaCelta]

I think what Steven means is that it is often possible to write a grammar in such a way that rule precedence would be clear from the grammar itself.

But it isn't currently possible within iXML for an author to specify precedence explicitly.

As things stand, if the input permits more than one interpretation, a conformant iXML processor is only required to do two things:

• Specify that the grammar/input combo is ambiguous;
• Produce one of the possible parses.

There's nothing in the spec to say which parse you'll get. An implementer might decide on a way to choose a parse (so you'd only ever get one parse of the possible parses), or they might leave it to chance and potentially give you a different parse each time.

@ndw I think has implemented some ways to ask for specific parses, or all parses, in CoffeePot. Not sure whether he has a pragma to do precedence, though I know he was discussing it at some stage.

[ndw]

CoffeePot attempts to enumerate all the parses, and they are identified deterministically, so if you don't like parse 1, you can ask for parse 2, etc. Or ask for all the parses. (Not recommended for infinitely ambiguous grammars.)

There is a priority pragma if you want to influence the serializer.

[martian-a]

If the grammar writer has no explicit method for specifying priority and parsers can use different algorithms to apply the rules, it seems to me that the grammar writer would need to a) know which algorithm the processor is using and b) be sufficiently familiar with the algorithm to know how that will impact precedence. The spec doesn't require iXML processors to share what algorithm(s) is/are used and several don't include this information in their documentation (which is likely to also make it more "interesting" should a grammar writer/maintainer/user need to switch processors).

[LinguaCelta]

According to the iXML specification, the grammar author has to expect that any valid parse might be the result of using an iXML processor. There's no requirement that a processor should have a predictable way of selecting a specific parse when the result is ambiguous. The process might be predictable ("always select the leftmost path through the parse forest") but it might equally be essentially random ("get a random number between 1 and the number of different parses, and return the parse with that index").

I think it's really important to emphasize this: being able to get a specific parse from an ambiguous result is totally unsupported by the current version of iXML.

Processors may make it possible for you to narrow down an ambiguous result to get your preferred parse, but that behaviour is implementation-specific and has nothing to do with the iXML spec.

I do think it would be worth discussing whether a precedence operator could be added to the language, but I suspect it might be better implemented as a pragma (if we can agree on a proposal for adding pragmas!).

[spemberton]

On Saturday 11 October 2025 17:44:30 (+02:00), martian-a wrote: [Unlabeled Image] martian-a left a comment (invisibleXML/ixml#310) <#310 (comment)> If the grammar writer has no explicit method for specifying priority and parsers can use different algorithms to apply the rules, it seems to me that the grammar writer would need to a) know which algorithm the processor is using and b) be sufficiently familiar with the algorithm to know how that will impact precedence. The spec doesn't require iXML processors to share what algorithm(s) is/are used and several don't include this information in their documentation (which is likely to also make it more "interesting" should a grammar writer/maintainer/user need to switch processors). I'm not clear if we are talking about the same priority, but it is standard grammar practice to specify priority/precedence. For non-ambiguous grammars all processors are required to operate in the same way, there's no worry about that. They may not use different algorithms to apply the rules. For ambiguous grammars, they are required to produce one serialisation, and they may choose which, which may cause different results. Steven

[LinguaCelta]

For non-ambiguous grammars all processors are required to operate in the same way, there's no worry about that. They may not use different algorithms to apply the rules.

I think that's a bit misleading. From the spec:

Different processors may vary in whether input is detected as ambiguous or not.

Since the spec (rightly) doesn't prescribe a specific parsing algorithm, there will be cases where processors using different algorithms will disagree on whether or not a given combination of grammar and input is ambiguous. For very simple grammars, it may be possible to be confident that there is no ambiguity, of course. But I don't think it's quite true to say that "all processors are required to operate in the same way" - it's just that there are some simple grammars where it is clear that no known algorithm will identify any ambiguity, so differences in how the processors operate will not make any difference to the output of an iXML parse.

[ndw]

@spemberton , what do you mean by

I'm not clear if we are talking about the same priority, but it is standard grammar practice to specify priority/precedence.

Consider:

S : X | Y .
X : "a" .
Y : "a" .

How do I specify that I would like the X rule to have higher precedence or priority? What "standard grammar practice" are we talking about?

[spemberton]

On Monday 13 October 2025 13:57:58 (+02:00), Bethan Tovey-Walsh wrote: [Unlabeled Image] LinguaCelta left a comment (invisibleXML/ixml#310) <#310 (comment)> For non-ambiguous grammars all processors are required to operate in the same way, there's no worry about that. They may not use different algorithms to apply the rules. I think that's a bit misleading. From the spec: Different processors may vary in whether input is detected as ambiguous or not. This describes a case like a: "a"*; "b"*. that some parsers may find ambiguous, and some not. That notwithstanding, the resulting serialisation will be the same. Since the spec (rightly) doesn't prescribe a specific parsing algorithm, there will be cases where processors using different algorithms will disagree on whether or not a given combination of grammar and input is ambiguous. For very simple grammars, it may be possible to be confident that there is no ambiguity, of course. But I don't think it's quite true to say that "all processors are required to operate in the same way" - it's just that there are some simple grammars where it is clear that no known algorithm will identify any ambiguity, so differences in how the processors operate will not make any difference to the output of an iXML parse. For non ambiguous grammars, all parsers are required to operate in the same way. Steven

[spemberton]

The standard practice I am talking about is the one that is used to say that × has higher priority than +. In the particular example given you can write: S: X. X: "a". since if X is to have priority, then Y has no purpose. Steven On Monday 13 October 2025 14:55:11 (+02:00), Norman Walsh wrote: [Unlabeled Image] ndw left a comment (invisibleXML/ixml#310) <#310 (comment)> @spemberton <https://github.com/spemberton> , what do you mean by I'm not clear if we are talking about the same priority, but it is standard grammar practice to specify priority/precedence. Consider: S : X | Y . X : "a" . Y : "a" . How do I specify that I would like the X rule to have higher precedence or priority? What "standard grammar practice" are we talking about? — Reply to this email directly, view it on GitHub <#310 (comment)> , or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNIXL5PI5DGJXFYEIMWD2T3XOOK7AVCNFSM6AAAAACIVA6HVSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGOJXGQYTQNZWHE> . You are receiving this because you were mentioned.

[ndw]

That seems slightly disingenous, Steven. It was clearly a trivial example to demonstrate the issue in the simplest possible terms. In the real world, there are inherently ambigous data sets and sometimes uses want to be able to say "yes, I know both match, but just prefer this one". I'm not prepared to say that it is impossible in all cases to rewrite the grammar to avoid that ambiguity, but neither am I prepared to say that it's always possible, and I'm confident that it would sometimes be very difficult.