Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end
From: federation2005@netzero.com
Newsgroups: comp.compilers
Subject: Re: Formatting of Language LRMs
Date: Mon, 28 Jul 2014 17:55:12 -0700 (PDT)
Organization: Compilers Central
Lines: 38
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <14-07-064@comp.compilers>
References: <14-06-010@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: miucha.iecc.com 1406605315 49945 2001:470:1f07:1126:0:676f:7373:6970 (29 Jul 2014 03:41:55 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Tue, 29 Jul 2014 03:41:55 +0000 (UTC)
Keywords: syntax
Posted-Date: 28 Jul 2014 23:41:55 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1354

On Tuesday, June 17, 2014 6:24:12 AM UTC-5, Seima Rao wrote:
>    Therefore I am curious to know if there are other interesting formatting
>    of language standards or language definitions such that the
>    pattern is different?

There is one that I've been in the process of developing that
incorporates a unified algebraic framework (actually: a calculus) for
context-free expressions and translation expressions (i.e. upward
revisions of "regular expressions" powerful enough to incorporate
context-free languages and context-free transductions).

There has been much activity as of late in the development and
publication of algebraic frameworks for level 2 in the Chomsky
Hierarchy. An algebra was defined in LNCS 4988 ("The Algebraic
Approach I, II") suitably powerful enough to handle all context-free
subsets of all monoids (even non-free monoids). An equivalent
formalism was devised by Kozen a couple years ago (I believe he calls
them "Continuous Chomsky Algebras"). There is activity underway by an
affiliate in Germany to actually flesh out the equivalence proof.

I'll post more on this or a pointer to an article discussing this,
hopefully in the near future. But here are the basics of what I've
developed:

BNF allows sequences on the RHS of a rule.
EBNF allows regular expressions on the RHS of a rule.
(???) allows full-fledged context-free expressions (CFE) on the RHS.

There are a couple ways one can specify a CFE. One, which harkens to the older
formalism (predating 2008) is the "grammar expressions", consisting of a
series of rules followed by an expression (much like GCC's "statement
expression"). (Even in subexpressions).

The newer notation permits "bra" and "ket" operators in expressions on the
RHS.

It gets interesting past this point ... but again, another time and another
venue.