Re: Formatting of Language LRMs

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.

Return to the comp.compilers page.
Search the comp.compilers archives again.