Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.compilers > #1265 > unrolled thread
| Started by | Seima Rao <seimarao@gmail.com> |
|---|---|
| First post | 2014-06-17 16:54 +0530 |
| Last post | 2014-08-01 14:58 -0700 |
| Articles | 1 on this page of 41 — 17 participants |
Back to article view | Back to comp.compilers
Formatting of Language LRMs Seima Rao <seimarao@gmail.com> - 2014-06-17 16:54 +0530
Re: Formatting of Language LRMs "lpsantil@gmail.com" <lpsantil@gmail.com> - 2014-06-20 10:10 -0700
Re: Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-08-03 04:37 +0000
Re: Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-20 12:09 -0700
Re: Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-06-21 02:27 +0000
Re: Formatting of Language LRMs Kaz Kylheku <kaz@kylheku.com> - 2014-06-21 03:09 +0000
Re: Formatting of Language LRMs Joshua Cranmer 🐧 <Pidgeot18@verizon.net.invalid> - 2014-06-22 21:12 -0500
Re: VWG and K, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-22 21:47 -0700
RE: Formatting of Language LRMs "Costello, Roger L." <costello@mitre.org> - 2014-07-03 09:06 +0000
Re: Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-07-03 22:30 -0700
Re: syntax checkers, was Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 17:35 +0000
Re: executable semantics, was Formatting of Language LRMs wclodius@earthlink.net (William Clodius) - 2014-07-04 15:53 -0600
Re: specifying semantics, was Formatting of Language LRMs seimarao@gmail.com - 2014-06-24 02:19 -0700
Re: specifying semantics, was Formatting of Language LRMs "lpsantil@gmail.com" <lpsantil@gmail.com> - 2014-06-24 13:12 -0700
Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-26 00:54 -0400
Re: specifying semantics, was Formatting of Language LRMs Andy Walker <news@cuboid.co.uk> - 2014-06-28 20:10 +0100
Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-28 22:43 -0400
Re: BNF, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-06-30 22:00 -0600
Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-28 12:25 -0700
Re: specifying semantics, was Formatting of Language LRMs Andy Walker <news@cuboid.co.uk> - 2014-06-29 11:19 +0100
Re: specifying semantics, was Formatting of Language LRMs George Neuner <gneuner2@comcast.net> - 2014-06-29 07:56 -0400
Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-29 11:49 -0700
Re: specifying semantics, was Formatting of Language LRMs Gene Wirchenko <genew@telus.net> - 2014-06-30 18:09 -0700
Re: specifying semantics, was Formatting of Language LRMs Ivan Godard <ivan@ootbcomp.com> - 2014-06-30 20:53 -0700
Re: Algol history, was specifying semantics anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 11:51 +0000
Re: Algol history, was specifying semantics Ivan Godard <ivan@ootbcomp.com> - 2014-07-03 22:20 -0700
Re: Algol history, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-07-04 15:52 -0600
Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 05:49 +0000
Re: Algol history, was specifying semantics Ivan Godard <ivan@ootbcomp.com> - 2014-07-07 10:48 -0700
Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 19:49 +0000
Re: Algol history, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-07 19:43 +0000
Re: specifying semantics, was Formatting of Language LRMs Gene Wirchenko <genew@telus.net> - 2014-07-03 21:44 -0700
Re: specifying semantics, was Formatting of Language LRMs anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-02 09:51 +0000
Re: specifying semantics, was Formatting of Language LRMs Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-03 10:15 -0400
Re: specifying semantics, was Formatting of Language LRMs glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 06:08 +0000
Re: specifying semantics, was Formatting of Language LRMs Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-07-04 08:51 +0200
Re: Parsing Fortran, was specifying semantics glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-07-04 17:53 +0000
Re: Parsing Fortran, was specifying semantics wclodius@earthlink.net (William Clodius) - 2014-07-04 15:57 -0600
Re: Formatting of Language LRMs mertesthomas@gmail.com - 2014-06-30 12:04 -0700
Re: Formatting of Language LRMs federation2005@netzero.com - 2014-07-28 17:55 -0700
Re: Formatting of Language LRMs federation2005@netzero.com - 2014-08-01 14:58 -0700
Page 3 of 3 — ← Prev page 1 2 [3]
| From | federation2005@netzero.com |
|---|---|
| Date | 2014-08-01 14:58 -0700 |
| Message-ID | <14-08-002@comp.compilers> |
| In reply to | #1354 |
On Monday, July 28, 2014 7:55:12 PM UTC-5, federat...@netzero.com wrote:
> ... publication of algebraic frameworks for level 2 in the Chomsky
> Hierarchy. An algebra was defined in LNCS 4988 ("The Algebraic
> Approach I, II")
A framework for 2nd order formalisms (expressed as Eilenberg-Moore algebras)
that does the analogue to what the Peano Axioms do for arithmetic.
I put some notes that expand on 4988 up on Scribd under
The Algebraic Approach II - V
http://www.scribd.com/doc/235317956/The-Algebraic-Approach-II-V
This is still a work in progress.
> An equivalent formalism was devised by Kozen a couple years ago
http://arxiv.org/abs/1309.0893
Actually Grathwohl is the lead author.
> 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 "older formalism" is the one which has been in place since the
1970's developed by Gruska, McWhirter and Yntema. The key elements are
the substitution operator (which I denote here (x = A, B)), and the
least fixed point operator (mu x.A). This may be grafted on top of the
Kleene algebra of regular expressions. The star A* B becomes (mu x.B |
Ax), for instance.
> The newer notation permits "bra" and "ket" operators in expressions on the
> RHS.
... and is the one I've spoken of here and elsewhere in the past. It is a
direct outgrowth of the Chomsky-Schutzenberger Theorem, and incorporates an
algebra (that would be very familiar to people in DSP who work with
multiresolution analysis)
bd = 1 = pq, bq = 0 = pd, db + qd = 1
and the {b,d,p,q} commute with the {x,y}'s.
So, the Dyck language, D(x,y) = mu S.(1 | xSy | SS) would simply become
b(xp | yq)* d.
Such an expression -- minus the algebra -- comes straight out of the
Chomsky-Schutzenberger Theorem, in which one obtains the language D(x,y) by
(1) expanding the alphabet X = {x,y} to X' = {x,y,b,d,p,q},
(2) devising a regular expression (which I term the "Chomsky-Schutzenberger
Kernel") b (xp | yq)* d over that alphabet
(3) taking the intersection of this with the interleave
(x | y)* interleave D(b,p;d,q)
where the 2-bracket Dyck language is D(b,p;d,q) = mu S.(1 | bSd | pSq | SS)
(4) mapping {b,p,d,q} to the empty word 1.
This can be extended to a more general algbera in which multiple bracket
symbols are permitted b0,b1,b2,... d0,d1,d2,.... The corresponding algebra
then assumes a form reminiscent of the "bra" and "ket" notation used in
Hilbert spaces:
b0, b1, b2, ... become the "bras" <0|, <1|, <2|, ...
d0, d1, d2, ... become the "kets" |0>, |1>, |2>, ...
and the underlying algebra generalizes to one which has the identities
If you are encoding context-free transductions with input alphabet X and
output alphabet Y, the very same framework applies, with the additional
element that the X's and Y's commute. The commutativity rule yx -> xy
corresponds to what in parsing theory is called a "look ahead".
The tricky part about incorporating these extensions is devising a syntax for
an extended BNF notation that allows all these elements to cohabit with one
another.
The result is a 3 level framework that has BNF (plus the fixed point and
substitution operators) at level 1, regular expression operators A*, A?, A+
(i.e. EBNF) at level 2, and the bra-ket algebra at level 3.
Thus, a syntax for D(x,y) (z D(x,y))* could be written as the substitution
expression ("Chomsky-Schuetzenberger" form)
S = <0|(<1|x)*(y|1>)*|0>, S(zS)*
or as the grammar expression ("Gruska-McWhirter-Yntema" form)
S -> SS, S -> xSy, S -> 1, S(zS)*
or in a wide variety of other ways.
[toc] | [prev] | [standalone]
Page 3 of 3 — ← Prev page 1 2 [3]
Back to top | Article view | comp.compilers
csiph-web