[langsec-discuss] How do i prove a Domain Specific Language is of particular formal grammar
jon at callas.org
Thu Sep 6 16:13:00 UTC 2012
On Sep 6, 2012, at 12:53 AM, Krishna Sashank O V (MS2011006) wrote:
> Hi ,
> I have come across this interesting paper on langsec, that talks about "Security applications of formal language theory" ,
> Now, we have a domain specific language that is XML based i.e SAML ( Secure Assertion Mark Up Language )
> I would like to analyze and prove the class of chomsky hierarchy of languages it falls under , like whether it is regular, deterministic context-free , etc ?
> How do I start about this exercise , are there any references of similar exercises ? any directions ?
Here's some guidance, which is not a proof. I might even be incomplete in this, which is what I mean by *guidance*.
If it has parentheses or equivalent, it's context-sensitive. Any SGML derivative is context-sensitive, as are S-expressions. (Think of *ML as S-expressions with colored parens.) If you need a stack to parse it, it's context-sensitive. Or worse, to any of those. It is highly likely that if you can't know an object's size in advance, then it's almost certainly context-sensitive. That's why TLV (tag-length-value) records are desirable; they simplify. Note however, that TLVs can be embedded in a complex language.
If it's got control structures, it's at least context sensitive. If it has backwards gotos in any form, it's Turing-complete. Loops, recursion, etc. are backwards gotos. If-then-else is a forward goto.
I am no longer a SAML expert, but my bet is that it's only context-sensitive because it's S-expressions, and I don't believe it has loops etc. Optional arguments are only context sensitive (they're equivalent to if-then-else or more fundamentally, a forward goto).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the langsec-discuss