Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1265 > unrolled thread

Formatting of Language LRMs

Back to article view | Back to comp.compilers

Contents

  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 2 of 3 — ← Prev page 1 [2] 3  Next page →

#1285 — Re: specifying semantics, was Formatting of Language LRMs

Hi Ivan,


On Sat, 28 Jun 2014 12:25:18 -0700, Ivan Godard <ivan@ootbcomp.com>
wrote:

>Where would you place VWG on the operational/denotational/axiomatic
>spectrum?

Denotational.

Technically any grammar formalism is a denotational description of the
syntax of the accepted/generated language.  But I think what you
really may be asking is whether a vW-grammar also is a semantic
description of the language it describes.

The only place I have seen a 2 level grammar used was in the original
Algol68 report.  Despite the inclusion of semantically meaningful
terms like "inseparable" and "strongly", etc., in actuality the vW
grammar in the report was used only for syntax specification. Language
semantics were not described *using* the formalism but rather were
given by accompanying text and only were *referenced* by the
formalism.

[Quickly reviewing the reports I noticed that the revised report
adopted a different (though equally dense) 2 level grammar "to make
its study easier for the uninitiated reader".  Honestly, I don't see
how the "NEST" grammar was any improvement on the vW.]


At the most basic, any grammar imparts some (very limited) semantics
to the described language by constraining[*] the symbolic alphabet and
the set of strings that are to be considered valid.  However, the
meaning of those strings is knowable only to an observer/manipulator at
a level higher than the grammar that describes them.

[*] Even though the set of valid strings may, in fact, be infinite,
owing to constraints the set must be countably infinite and therefore
(theoretically) enumerable. 8-)


Of course, 2-level grammars like vW can be shown to be Turing Complete
- so in theory one could describe Yet Another Grammar which, in turn,
could be used to describe both the syntax and denotation semantics of
Yet Another Language.  I can imagine that the YAG is some sort of a
declarative programming language in its own right and the YAL is a
program "written" in YAG which is (or generates) the compiler for YAL.

Ouch!  I've just gotten a meta-circular headache!
George

[toc] | [prev] | [next] | [standalone]

#1286 — Re: specifying semantics, was Formatting of Language LRMs

On 6/29/2014 4:56 AM, George Neuner wrote:

> Technically any grammar formalism is a denotational description of the
> syntax of the accepted/generated language.  But I think what you
> really may be asking is whether a vW-grammar also is a semantic
> description of the language it describes.
>
> The only place I have seen a 2 level grammar used was in the original
> Algol68 report.  Despite the inclusion of semantically meaningful
> terms like "inseparable" and "strongly", etc., in actuality the vW
> grammar in the report was used only for syntax specification. Language
> semantics were not described *using* the formalism but rather were
> given by accompanying text and only were *referenced* by the
> formalism.

Well, conventionally the type system of a language is considered
semantics, yet the whole Algol68 type system, including checking all
expressions for type validity, is present in the VWG. So while one can
say that any language definition mechanism is syntactic by definition,
that doesn't seem to be a useful definition to me.

BTW, I'm talking about the VWG in the *Revised* Report, which different
somewhat from that in the original report before the Great Schism.

[toc] | [prev] | [next] | [standalone]

#1290 — Re: specifying semantics, was Formatting of Language LRMs

On Sun, 29 Jun 2014 11:49:00 -0700, Ivan Godard <ivan@ootbcomp.com>
wrote:

[snip]

>BTW, I'm talking about the VWG in the *Revised* Report, which different
>somewhat from that in the original report before the Great Schism.
                                                      ^^^^^^^^^^^^
     What was this, please?

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#1291 — Re: specifying semantics, was Formatting of Language LRMs

On 6/30/2014 6:09 PM, Gene Wirchenko wrote:
> On Sun, 29 Jun 2014 11:49:00 -0700, Ivan Godard <ivan@ootbcomp.com>
> wrote:
>
> [snip]
>
>> BTW, I'm talking about the VWG in the *Revised* Report, which different
>> somewhat from that in the original report before the Great Schism.
>                                                        ^^^^^^^^^^^^
>       What was this, please?

When Algol68 was revised, there was a major split in the committee as
to the merits of the proposed changes, and even more about the use of
VWG as a language notation. The majority accepted the proposal, and
their work became the Revised Report and their spiritual descendant
populate IFIPS WG2.1 (Algol) to this day.

The minority, which included a number of luminaries such as Wirth and
Dijkstra, resigned from WG2.1, wrote scathingly about the Algol68
language, and formed a rump group that became WG2.3, which also
survives. Philosophically they wished to return to (a slightly cleaned
up) Algol 60; the linguistic descendants include Pascal and Ada.

These events, known as the Great Schism, occurred slightly before I
arrived. I attended a few meetings of both WG2.1 and WG2.3 and found
the character of the two groups very different: WG2.1 had a youthful
enthusiastic, and creative feel to it, while WG2.3 seemed to be
sourpuss, political, and puffed-up: an air of offense that someone
should enter the rarefied academe without proper obeisance. That was
my feeling; others no doubt would have felt differently, and in
fairness there were many of the participants who were every bit as
welcoming as any in WG2.1. BTAIM, I quit going to WG2.3, and
eventually was honored with my name in the Revised Report.

I went on to be a founder of the next Working Group in sequence
(WG2.4, then titled Machine-Oriented Languages). Despite staying
mostly in industry, I have since encountered that WG2.3 priesthood
"feel" in some (but mercifully few) other contexts, even as recently
as this year. I suspect readers have encountered the like.

[toc] | [prev] | [next] | [standalone]

#1295 — Re: Algol history, was specifying semantics

Ivan Godard <ivan@ootbcomp.com> writes:
>When Algol68 was revised, there was a major split in the committee as
>to the merits of the proposed changes, and even more about the use of
>VWG as a language notation. The majority accepted the proposal, and
>their work became the Revised Report and their spiritual descendant
>populate IFIPS WG2.1 (Algol) to this day.
>
>The minority, which included a number of luminaries such as Wirth and
>Dijkstra, resigned from WG2.1, wrote scathingly about the Algol68
>language, and formed a rump group that became WG2.3, which also
>survives. Philosophically they wished to return to (a slightly cleaned
>up) Algol 60; the linguistic descendants include Pascal and Ada.

The story I read (IIRC in the HOPL paper on Algol 68 was that this
split happened in 1965 or so, leading to Wirth and Hoare publishing a
paper on Algol W in 1966.  So that was not when Algol68 was revised,
but when Algol 60 was revised.  Wirth and Hoare wanted a relatively
conservative revision, while the other wanted a revolutionary
revision.

Interestingly, wrt the original topic, Wikipedia says:

  The Algol W Language Description defines Algol W in an affix grammar
  that resembles BNF. This grammar was a precursor of the Van
  Wijngaarden grammar.

  Much of Algol W's semantics is defined grammatically:

    * Identifiers are distinguished by their definition within the
      current scope. For example, a <procedure identifier> is an
      identifier that has been defined by a procedure declaration, a
      <label identifier> is an identifier that is being used as a goto
      label.

    * The types of variables and expressions are represented by
      affixes. For example <T function identifier> is the syntactic
      entity for a function that returns a value of type T, if an
      identifier has been declared as an integer function in the
      current scope then that is expanded to <integer function
      identifier>.

    * Type errors are grammatical errors. For example "<integer
      expression> / <integer expression>" and "<real expression> /
      <real expression>" are valid but distinct syntactic entities
      that represent expressions, but "<real expression> DIV <integer
      expression>" (i.e. integer division performed on a
      floating-point value) is an invalid syntactic entity.

And already the Algol 60 grammar (in BNF) does a number of things in
the grammar that are done in the type system in, say, Pascal.  So it
seems to me that we explored the power of grammar formalisms in the
1960s, but eventually came to the conclusion that going beyond
context-free grammars is not practically useful, and type systems are
best not expressed in the grammar (they also became more complex
later, so expressing them as grammars probably would have been a
burden).

And no other generally-used formalism for expressing type systems has
appeared, either, although that seems to be an area where a formalism
can be helpful.  But apparently the type systems always need new
features that would require extending the formalism, and people have
not learned how to divide stuff between a common type system formalism
that does not cover everything on the one side and stuff that does not
fit into the formalism on the other side.  Given that, it's surprising
that we have learned how to do that with context-free grammars/(E)BNF,
and to accept the limitations of that formalism.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1298 — Re: Algol history, was specifying semantics

On 7/3/2014 4:51 AM, Anton Ertl wrote:

>
> The story I read (IIRC in the HOPL paper on Algol 68 was that this
> split happened in 1965 or so, leading to Wirth and Hoare publishing a
> paper on Algol W in 1966.  So that was not when Algol68 was revised,
> but when Algol 60 was revised.  Wirth and Hoare wanted a relatively
> conservative revision, while the other wanted a revolutionary
> revision.

<snip history>

Thank you for the update. It was before my day, and I wasn't interested
in the politics, and so never quite got it straight.

I think one reason why formal semantics (and VWG) never became more
popular was that the minority, largely academics, controlled important
university posts and journal boards while the more industrial majority
did not. I know Klaus Wirth personally prevented publication of papers
that differed from the philosophical positions of the minority or that
reported work in the majority tradition or from industry. Academic
infighting can be quite vicious, and not just in the language world;
such politics led to the founding of SP&E, among other things.

Ivan

[toc] | [prev] | [next] | [standalone]

#1305 — Re: Algol history, was specifying semantics

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:

> Ivan Godard <ivan@ootbcomp.com> writes:
> >When Algol68 was revised, there was a major split in the committee as
> >to the merits of the proposed changes, and even more about the use of
> >VWG as a language notation. The majority accepted the proposal, and
> >their work became the Revised Report and their spiritual descendant
> >populate IFIPS WG2.1 (Algol) to this day.
> >
> >The minority, which included a number of luminaries such as Wirth and
> >Dijkstra, resigned from WG2.1, wrote scathingly about the Algol68
> >language, and formed a rump group that became WG2.3, which also
> >survives. Philosophically they wished to return to (a slightly cleaned
> >up) Algol 60; the linguistic descendants include Pascal and Ada.
>
> The story I read (IIRC in the HOPL paper on Algol 68 was that this
> split happened in 1965 or so, leading to Wirth and Hoare publishing a
> paper on Algol W in 1966.  So that was not when Algol68 was revised,
> but when Algol 60 was revised.  Wirth and Hoare wanted a relatively
> conservative revision, while the other wanted a revolutionary
> revision.

Not quite.  More easily accessible than the HOPL papers are de Beer's
papers

<http://heerdebeer.org/ALGOL/The_History_of_ALGOL.pdf>
<http://datamuseum.dk/site_dk/20100213/Huub_de_Beer-ALGOL_anniversary.pdf>

What became as Algol 68 started off with the proposed name Algol 66,
with three original goals to be embodied in separate reports: one
describing a language to be used in the semantic definition of
programming languages; a small revision of Algol 60 addressing the most
obvious problems, but described using the language of the other paper;
and what I think of as a user guide for Algol '66'.

As is often the case arriving at a consensus was difficult. From the
begining there was strong disagreement about what was meant by a small
revision of Algol 60. At one extreme some took it as a requirement to
fix only the ambiguities and contradictions in the semantics of the
revised Algol 60 report. However a significant fraction also wanted to
replace call by name with a different argument passing mechanism.
Another significant fraction wanted to add features such as case
selection and record data types. It was hard to reach a concensus on how
ambiguities and contradictions would be resolved, while call by name
could not be implemented efficientlyin descibing algorithm's in papers
it had a minor impact and alternative mechanisms were harder to
describe, and while time passed arguing those two issues more small
additions appeared on the table. It is common in this situation for
people to say, in effect "The proposal is too large and must be
simplified, but it is essential that it also have these additons that
are still not accepted." and when push comes to shove make more of a
deal oabout the lack of the additions than about the complexity of other
people's additions.

(Van Wijngaarden appears to have been ambivalent about the proposed
additions. He is reported to, at least a couple of times, have strongly
resisted proposals on their first suggestion with the objection that
they would complicate the language too much and impose too much of a
delay, and then the next day change his mind and note that with a few
minor changes in the current draft the proposal could be made to work.
With him having done the most obvious groundwork it was easy for
proposals to slip from Algol Y into Algol X.)

As time went it became obvious by that the 1966 deadline would not be
met so the effort was renamed Algol X, with features not currently
accepted for Algol X documented as planned for a followon language Algol
Y. Wirth and Hoare's report that served as the basis of Algol W was
their idea of a minimal Algol X that could meet the 1966 deadline, if
accepted by the comittee. But Algol W kept call by name, while adding
record data types and Hoare's select case, so it was too large revision
for the minimalists, and was not as efficient in implementation as the
majority of revisionists wanted. Wirth and Hoare remained in the
comittee until the first draft was published for comment hoping that
something would happen to change Algol 68 back to Algol W.

Van Wijngaarden was the only researcher far enough along to provide a
semantics language on the desired time scale so he soon came to play a
major role in all three efforts. From the beginning, there were
complaints from prominant participants that two level grammars were too
complicated to understand. I suspect that this reflects less a problem
with two level grammars per se than that: semantics in general are hard
to understand; there was no existing concensus on the description of
semantics so all participants had poor groundwork for learning two-level
grammars; and most participants (other than van Wijngaarden and the
editors) were involved part time which made it even more difficult for
them to fully follow the details of the semantics descriptions.


(Note the above makes it tempting for language definitions to be lazy
about defining semantics. It is tempting to write an implementation that
does the most obvious desired things and take that as the definition,
written up as a fifty page or so report. But that fifty page report will
typically have serious ambiguities, or limited functionality. To that
end I am reminded of Richard A. O'Keefe's comment in comp.lang.misc:

"The essential ideas of Algol 68 were that the whole language should be
precisely defined and that all the pieces should fit together smoothly.
The basic idea behind Pascal was that it didn't matter how vague the
language specification was (it took *years* to clarify) or how many
rough edges there were, as long as the CDC Pascal compiler was fast."

I am also reminded of Fortran 77, which had a rather long appendix
listing potential incompatibilities with Fortran 66 compilers, with the
vast majority of the incompatibilities being ambiguities in the Fortran
66 standard that were defined in the Fortran 77 standard.)


> <snip>
>
> And already the Algol 60 grammar (in BNF) does a number of things in
> the grammar that are done in the type system in, say, Pascal.  So it
> seems to me that we explored the power of grammar formalisms in the
> 1960s, but eventually came to the conclusion that going beyond
> context-free grammars is not practically useful, and type systems are
> best not expressed in the grammar (they also became more complex
> later, so expressing them as grammars probably would have been a
> burden).
>
> And no other generally-used formalism for expressing type systems has
> appeared, either, although that seems to be an area where a formalism
> can be helpful.  But apparently the type systems always need new
> features that would require extending the formalism, and people have
> not learned how to divide stuff between a common type system formalism
> that does not cover everything on the one side and stuff that does not
> fit into the formalism on the other side.  Given that, it's surprising
> that we have learned how to do that with context-free grammars/(E)BNF,
> and to accept the limitations of that formalism.

Part of the problem is the variety of formalisms available for
describing semantics. In addition to vWgs, there is the Vienna
Definition Method (and its predecessor the Vienna Definition Language),
atribute grammars, Scott/Strachley, etc. all of which come with minor
variants in notation. It is easy for the experts to wind up in detailed
arguments about minor features, and the majority of non-experts to
decide that if the experts cann't agree on what tool to use, lets see
what we can do without using the tools.

Another part of the problem is there is not a good consensus on how to
use semantic formalisms in language definitions: i.e., use it to guide
the desing as in vWgs in Algol 68 or the Vienna Definition Method in the
Modula II standard, or use it to describe a design as was attempted with
the Vienna Definition Language and PL/I.

<https://cs.uwaterloo.ca/research/tr/1979/CS-79-01.pdf>

[toc] | [prev] | [next] | [standalone]

#1308 — Re: Algol history, was specifying semantics

William Clodius <wclodius@earthlink.net> wrote:

(snip)
> As time went it became obvious by that the 1966 deadline would not be
> met so the effort was renamed Algol X, with features not currently
> accepted for Algol X documented as planned for a followon language Algol
> Y. Wirth and Hoare's report that served as the basis of Algol W was
> their idea of a minimal Algol X that could meet the 1966 deadline, if
> accepted by the comittee. But Algol W kept call by name, while adding
> record data types and Hoare's select case, so it was too large revision
> for the minimalists, and was not as efficient in implementation as the
> majority of revisionists wanted. Wirth and Hoare remained in the
> comittee until the first draft was published for comment hoping that
> something would happen to change Algol 68 back to Algol W.

Reminds me, I am still intersted in finding the OS/360 Algol W
compiler.  Source or load module.

There is a not-yet-debugged source listing on bitsavers, and I
(or someone) could type it in, but it would still need to be
debugged. At least that is how I understand it.

-- glen
[As far as I know, the machine readable source was lost.  Even with a copy
of the source, you'll need a copy of PL360, the Algol-flavored assembler it
was written in. -John]

[toc] | [prev] | [next] | [standalone]

#1309 — Re: Algol history, was specifying semantics

> [As far as I know, the machine readable source was lost.
> Even with a copy of the source, you'll need a copy of PL360, the
> Algol-flavored assembler it was written in. -John]

IMO, PL360 was the best language work that Wirth ever did. It was an
expression assembler, as opposed to a conventional statement
assembler, and was representative of a family of such languages with
different target machines done by different people.

The key idea was the absence of operator precedence; expressions were
executed in strict left-to-right order, with operations for each machine
op and explicit register names for operands:

	r5 := r3 + r2 * r1;  	(PL360)

The target register served as the accumulator for the expression.
[Agreed.  Tight, clearly defined, efficient little language.
Princeton let you run small PL360 and AlgolW programs on their
mainframe without having an account when I was in high school. -John]

[toc] | [prev] | [next] | [standalone]

#1312 — Re: Algol history, was specifying semantics

Ivan Godard <ivan@ootbcomp.com> wrote:
>> [As far as I know, the machine readable source was lost.
>> Even with a copy of the source, you'll need a copy of PL360, the
>> Algol-flavored assembler it was written in. -John]

> IMO, PL360 was the best language work that Wirth ever did.

(snip)

> The key idea was the absence of operator precedence; expressions were
> executed in strict left-to-right order, with operations for each machine
> op and explicit register names for operands:

>        r5 := r3 + r2 * r1;     (PL360)

> The target register served as the accumulator for the expression.

It gets even more interesting, as I remember it, if the left side
register is also on the right. Consider:

   r1:= r1 + r1 + r1;

which, in effect, multiplies r1 by four. As you note, r1 is the
accumulator for the expression, and also changes as it is being
evaluated:

    LR R1,R1
    AR R1,R1
    AR R1,R1

Remembering from 40 years ago, I believe that one is in the manual.

-- glen

[toc] | [prev] | [next] | [standalone]

#1311 — Re: Algol history, was specifying semantics

(snip, I wrote)

> Reminds me, I am still intersted in finding the OS/360 Algol W
> compiler.  Source or load module.

(snip)

> [As far as I know, the machine readable source was lost.  Even with a copy
> of the source, you'll need a copy of PL360, the Algol-flavored assembler it
> was written in. -John]

I wouldn't mind a load module that I could just run. It could also
be disassembled, which, along with the available source listing might
be enough to put together an actual source.

PL/360 is available, I believe both source and load module.

I had the ALGOL W manual about the time (1972) that I was first
learning Fortran. I don't remember by now actually using it.

The thing I do remember is that it allows variable names up to 255
characters long! Compared to six for Fortran IV, that was pretty
surprising.

That, and that my first programs were in B5500 Algol has kept
me interested, besides any historical interest of others.

I did even once ask Wirth, who seems not to have any copies.

(Writing a PL/360 decompiler could also be interesting.)

-- glen
[I found AlgolW source online at the computer history museum, but it was apparently
OCR'ed from listings so who knows how many typo bugs it has. -John]

[toc] | [prev] | [next] | [standalone]

#1297 — Re: specifying semantics, was Formatting of Language LRMs

On Mon, 30 Jun 2014 20:53:21 -0700, Ivan Godard <ivan@ootbcomp.com>
wrote:

>On 6/30/2014 6:09 PM, Gene Wirchenko wrote:
>> On Sun, 29 Jun 2014 11:49:00 -0700, Ivan Godard <ivan@ootbcomp.com>
>> wrote:
>>
>> [snip]
>>
>>> BTW, I'm talking about the VWG in the *Revised* Report, which different
>>> somewhat from that in the original report before the Great Schism.
>>                                                        ^^^^^^^^^^^^
>>       What was this, please?

     Thank you.

>These events, known as the Great Schism, occurred slightly before I
>arrived. I attended a few meetings of both WG2.1 and WG2.3 and found
>the character of the two groups very different: WG2.1 had a youthful
>enthusiastic, and creative feel to it, while WG2.3 seemed to be
>sourpuss, political, and puffed-up: an air of offense that someone
>should enter the rarefied academe without proper obeisance. That was

     Interesting.  I always got a similar feeling about Wirth's
languages.

     Context is everything folks.  Just try searching for the Great
Schism when you do not know what it is.  There has been more than one.

[snip]

Sincerely,

Gene Wirchekno

[toc] | [prev] | [next] | [standalone]

#1293 — Re: specifying semantics, was Formatting of Language LRMs

Ivan Godard <ivan@ootbcomp.com> writes:
>Well, conventionally the type system of a language is considered
>semantics, yet the whole Algol68 type system, including checking all
>expressions for type validity, is present in the VWG.

What is conventionally called "syntax" is an artifact of the compiler
technology (or maybe of specification technology, see below): Parsers
are based on context-free grammars, and anything that is not groked by
the parser is a syntax error, and what the parser accepts is
considered the syntax; and everything else is called the semantics.

And programming language specifications also follow that division:
most of them provide a context-free grammar, and provide everything
else in natural language.

However, "everything else" is a very wide category, and if you look
closer, you make further distinctions: There is static stuff and
run-time stuff; typically name lookups are done statically (you get an
error even if the code is not executed).  One may consider the static
stuff "syntax", but I think a more usual term is "static semantics".
I think the vW stuff in Algol 68 is also static stuff.

There is also the run-time semantics.

There have been some ways to specify static stuff.  vW grammars have
not caught on; attribute grammars are more successful, but for
compiler writers, not for language specifications; and even in
compilers attribute grammars are not very widely used.  It's mostly
just code in the compiler implementation language.

For the dynamic stuff, there has been quite a bit of academic work
(operational semantics, denotational semantics (although I think they
make little difference between static and dynamic stuff), but few uses
in language specifications or compilers.  I think Modula-3 used a
formal specification, but don't know about the type.

Generally, the problem of formal specifications is that, while they
may be precise, doing a complete formal specification is hard and they
are hard to understand (so it's easy to miss specification bugs).
Doing partial formal specifications for areas that are easier to
formally specify, and where the specifications are relatively easy to
understand has been much more successful (context-free grammars are to
most obvious example).  And the rest is filled in with natural
language.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1296 — Re: specifying semantics, was Formatting of Language LRMs

> What is conventionally called "syntax" is an artifact of the compiler
> technology (or maybe of specification technology, see below):

I disagree here.  It is no accident.  Same as the split between
lexical and syntactic analysis, the division between syntax and
(static) semantics is an engineering issue: specifying a language is a
fairly large amount of work, so you want to split it into simpler
parts.


        Stefan

[toc] | [prev] | [next] | [standalone]

#1300 — Re: specifying semantics, was Formatting of Language LRMs

Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> What is conventionally called "syntax" is an artifact of the compiler
>> technology (or maybe of specification technology, see below):

> I disagree here.  It is no accident.

Doesn't seem to me that it says it is an accident.

> Same as the split between
> lexical and syntactic analysis, the division between syntax and
> (static) semantics is an engineering issue: specifying a language is a
> fairly large amount of work, so you want to split it into simpler
> parts.

And for that reason, both specification and compiler want to divide
up the problem. There aren't so many convenient places to divide
the work.

Also, I have always thought that BNF didn't distinguish lexical and
syntactical sides of the problem.

When I first learned about BNF, and without any actual compiler
books, I started to figure out how a recursive descent algorithm
would work, but hadn't thought about a separate lexical analyzer.

But I think many languages are designed to separate syntax and
semantics, not only to make the description easier, but intentionally
to make compilers easier to write.

-- glen

[The split makes the code easier to write and easier to read.  You
could since LALR or LL(1) are more powerful than the regex that lex
and its ilk use, you could glom everything in the lexer into the BNF
of the grammar, but it would be huge and unreadable, since every token
definition would be encrusted with all of the optional whitespace and
comments that a lexer has already thrown away.  In the other
direction, you could write many semantic rules in the BNF like what
types can combine with what operators, but ugh. In practice, even
operator precedence BNF rules are ugly enough that we use hacks in
yacc/bison to fake them. -John]

[toc] | [prev] | [next] | [standalone]

#1301 — Re: specifying semantics, was Formatting of Language LRMs

Stefan Monnier schrieb:
>> What is conventionally called "syntax" is an artifact of the compiler
>> technology (or maybe of specification technology, see below):
>
> I disagree here.  It is no accident.  Same as the split between
> lexical and syntactic analysis, the division between syntax and
> (static) semantics is an engineering issue: specifying a language is a
> fairly large amount of work, so you want to split it into simpler
> parts.

I don't know of any *general* formal description of lexical analysis,
that would allow to e.g. describe Fortran and Algol (or C) lexing at the
same time. In an experiment with an scannerless parser a problem with
whitespace popped up, where whitespace sometimes is required to separate
keywords from identifiers, sometimes is optional:

Fortran: D O I = ...
Pascal:  if  x ...
C:       int i ...

Just in the Fortran example neither a longest nor a shortest match lexer
is a solution. Do we have to exclude Fortran (and C) as context
sensitive languages then? But what would be the benefit of an
description formalism, that only is applicable to new languages, whose
syntax and semantics can (must!) be described using just that formalims?

In the case of the scannerless parser experiment the grammar size
exploded, when the handling of whitespace was added. Also the well known
"dangling else" problem can be solved only at the expense of a bigger
grammar, which then may still be readable by a compiler generator, but
not by humans any more.


Such problems suggest to me that the design of a language starts with
the design of an appropriate description formalism. But which formalism
could be used to describe *that* formalism?

DoDi

[You can scan Fortran with longest match, but the things you're
matching for are very context dependent.  I've done it. I agree that
it's unlikely we'll find a general model for different languages. -John]

[toc] | [prev] | [next] | [standalone]

#1303 — Re: Parsing Fortran, was specifying semantics

Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:

(snip)

> whitespace popped up, where whitespace sometimes is required to separate
> keywords from identifiers, sometimes is optional:

> Fortran: D O I = ...
> Pascal:  if  x ...
> C:       int i ...

(snip)

> [You can scan Fortran with longest match, but the things you're
> matching for are very context dependent.  I've done it. I agree that
> it's unlikely we'll find a general model for different languages. -John]


The two favorite ones that I always remember for Fortran are:

      DO1I=1,2

and

      DO 1 I=1.2

(and with no IMPLICIT NONE in effect, or with DO1I already declared).

To avoid these kinds of problems, WATFIV disallows "FORMAT(" as the
first seven characters of a statement that isn't a FORMAT statement.

Doesn't seem like it is overly restrictive, but when using variable
format, I always called my array (it had to be an array back then)
FORMAT.

-- glen
[To parse a Fortran statement you first have to decide whether it's an
assignment or something else, after which you can use a simple
contnext sensitive longest match to find the tokens.  To see if it's
an assignment, you look for an = sign that is not followed by a comma
that is not inside parens, being sure to skip over 'literal' and
9hHollerith strings and noting that in typical dialects the statement
REAL*4HFOO does not contain a Hollerith string.. It wasn't as hard as
it sounds. -John]

[toc] | [prev] | [next] | [standalone]

#1306 — Re: Parsing Fortran, was specifying semantics

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

> <snip>
> -- glen
> [To parse a Fortran statement you first have to decide whether it's an
> assignment or something else, after which you can use a simple
> contnext sensitive longest match to find the tokens.  To see if it's
> an assignment, you look for an = sign that is not followed by a comma
> that is not inside parens, being sure to skip over 'literal' and
> 9hHollerith strings and noting that in typical dialects the statement
> REAL*4HFOO does not contain a Hollerith string.. It wasn't as hard as
> it sounds. -John]

WIth the proviso that what is termed an assignment in the initial
analysis may be further qualified as a statement function definiton in
the semantic analysis.
[Right.  You have to look up the symbol and see if it's defined as an
array. -John]

[toc] | [prev] | [next] | [standalone]

#1288

At tuesday, 17. Juni 2014 13:24:12 UTC+2 wrote Seima Rao:
>    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 no Seed7 standard, but Seed7 uses, at least partly, other
ways than BNF for syntax and english for semantic descriptions.

Seed7 describes syntax with the Seed7 Structured Syntax Description
(S7SSD). See http://seed7.sourceforge.net/manual/syntax.htm S7SSD
describes the syntax based on typeless operators. The operators can be
prefix, infix and postfix. There are also operators which contain
several keywords. Only the syntax of literals is described with BNF.

For the semantic description normal functions are used.  E.g.:
http://seed7.sourceforge.net/manual/stats.htm#while-statement
Call-by-name parameters are used for condition parameters and loop
bodies. Just some semantic descriptions still rely on english.


Greetings Thomas Mertes

--
Seed7 Homepage:  http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.compilers

csiph-web