RE: Concise Format for EXI Grammar

Hi Yusuke,

Here I am just providing a clarification below.

The grammar generation system written in the spec will lead you 
to a fully expanded automata that is reflexive to events, and it give 
you an immediate transition to the next state upon events. Such a 
system enjoys the benefit of speed at the cost of potential memory 
overuse caused by large maxOccurs numbers in the schema.
Nagasena's grammar format exhibits this characterstic.

Milinda uses counters for making switches to the subsequent
state. Milinda's grammar format contains lots of mini-automata
corresponding to particles and groups, and the switch between 
the automata is determined by a set of occurrence counters. 

Even though the final external "perception" of the state machines 
are the same, the unsercover structures they base its grammar delivery 
on are very different.

Sincerely,

-taki


-----Original Message-----
From: Yusuke DOI [mailto:yusuke.doi@toshiba.co.jp] 
Sent: Friday, March 09, 2012 5:04 AM
To: Takuki Kamiya
Cc: Carine Bournez; public-exi@w3.org
Subject: Re: Concise Format for EXI Grammar

Hi Takuki,

Thank you for the clarification. I think the state machines should be 'equivalent' even if there are many algorithms. Anyway I understand the situation.

OpenEXI grammar serialization will be very helpful, though Nagasena implementation is not yet released.

Thank you very much.

Yusuke

(2012/03/09 14:51), Takuki Kamiya wrote:
> Hi Yosuke,
>
> The EXI specification specifies abstract grammar for EXI, and how it binds to
> XML Schema.
>
> Although section 8.5.4 specifies a normative way to generate grammars given
> a schema, it is normative only in the sense that an implementations needs to
> produce encodings *as if* it was using the exact grammars generated by the
> method described in the spec. The paragraph that explains this is exerpted
> below from section 8.5.4:
>
> "The algorithms expressed in this section provide a concise and formal
>   description of the EXI grammars for a given set of XML Schema definitions.
>   More efficient algorithms likely exist for generating these EXI grammars and
>   EXI implementations are free to use any algorithm that produces grammars and
>   event codes that generate EXI encodings that match those produced by the
>   grammars described here."
>
> In other words, "EXI grammar" is just a denomination, a designation,
> a conceptual term that merely *depends* on the example "method"
> described in the spec.
>
> For example, OpenEXI [1] contains two EXI implementations (Milinda and Nagasena)
> each using fundamentally different way to compute and deliver grammars.
> Milinda uses a novel technique to generate schema-informed EXI grammars from
> schemas whereby the number of grammar state objects generated is roughly the
> same as that of schema constructs such as elements, types and groups regardless
> of minOccurs/maxOccurs constraint numbers given to particles in the schemas.
> Nagasena, on the other hand, uses the algorithm specified in the EXI
> specification to generate schema-informed EXI grammars. Unlike Milinda, the
> number of grammar state objects is additionally affected by minOccurs/maxOccurs
> numbers given to particles.
>
> Milinda and Nagasena were implemented by the same developer. They both have
> grammar serialization format. Nevertheless, it is technically not feasible
> to feed one serialized grammar into the other implementation. They are just
> fundamentally very different.
>
> The good news is that Nagasena's grammar format is independent of programming
> languages. EXI implementors who seek direct access to grammar knowledge
> without dealing with grammar's binding to W3C XML Schema can tap into
> Nagasena's serialized grammars.
>
> Sincerely,
>
> [1] http://openexi.sourceforge.net/
>
> taki
>
>
>
> -----Original Message-----
> From: Yusuke DOI [mailto:yusuke.doi@toshiba.co.jp]
> Sent: Wednesday, March 07, 2012 6:50 PM
> To: Carine Bournez; public-exi@w3.org
> Subject: Re: Concise Format for EXI Grammar
>
> Carie,
>
> Thanks for clarification. I don't find apparent interoperability problems so far. My concern is the learning cost before make things work. EXI spec is good and clear I think, but still needs certain amount of effort to understand correctly.
>
> When someone just want to make it work in some field, it's far better for him/her if s/he can start from a pre-compiled grammar. It can be implementation specific, but I don't find a reason to avoid some 'non-normative' reference serialization model. And I believe if we want to make more use of EXI in the world (my concern is on embedded systems), make it easy to start is very effective strategy.
>
> Regards,
>
> Yusuke
>
> (2012/03/08 3:36), Carine Bournez wrote:
>> Hi,
>>
>> On Thu, Feb 09, 2012 at 04:49:12AM +0900, Yusuke DOI wrote:
>>> Dear EXI gurus,
>>>
>>> Is there any intermediate format to describe EXI grammar?
>>>
>>> As I'm working for several EXI-related projects including SEP2, I'm
>>> feeling it's very convenient if we can share EXI grammar in well-defined
>>> format. The format used in EXI spec is very descriptive, but I guess
>>> that grammar notation is for humans.
>>>
>>> If there's machine-readable (e.g. in plain text or XML) intermediate
>>> format for EXI grammars, I believe we can reduce troubles on
>>> spec-understanding stage by sharing a good grammar between
>>> implementations. Then people can focus on implementations for various
>>> devices of their own.
>>
>>
>> The EXI 1.0 specification does not define a format to exchange grammars
>> between processors. It specifies how to build the grammars in a non-ambiguous
>> way, so that a grammar exchange is not needed. The grammar notation used in the
>> specification is for implementers of EXI processors and it has no
>> machine-readable serialization. In some applications it may be interesting
>> to define a serialized format of the grammars in use, but such a format
>> would be specific to each use case to suit best the application needs.
>>
>> If you encounter particular interoperability issues about grammars, we
>> welcome your feedback and will do our best to clarify the specification
>> wording.
>>
>>
>
>
>

Received on Friday, 9 March 2012 21:22:58 UTC