[langsec-discuss] How do i prove a Domain Specific Language is of particular formal grammar

Alex Gantman agantman at qualcomm.com
Thu Sep 6 16:23:47 UTC 2012


I think you meant "context-free" when you said "context-sensitive."


At 09:13 AM 9/6/2012, Jon Callas wrote:

>On Sep 6, 2012, at 12:53 AM, Krishna Sashank O V (MS2011006) wrote:
>>Hi ,
>>I have come across this interesting 
>>on langsec, that talks about "Security applications of formal 
>>language theory" ,
>>At the page number 8 states that HTTP is context-sensitive , 
>>javascript is non deterministic context-free etc .
>>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).
>langsec-discuss mailing list
>langsec-discuss at lists.langsec.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.langsec.org/pipermail/langsec-discuss/attachments/20120906/a419eabb/attachment.html>

More information about the langsec-discuss mailing list