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

Groups > comp.compilers > #1040 > unrolled thread

Re: Programming language and IDE design

Back to article view | Back to comp.compilers

Contents

  Re: Programming language and IDE design Martin Ward <martin@gkc.org.uk> - 2013-11-16 15:55 +0000
    Re: Programming language and IDE design Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2013-11-16 19:48 +0100
    Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2013-11-18 19:02 -0500
      Re: Programming language and IDE design "Steven G. Kargl" <sgk@REMOVEtroutmask.apl.washington.edu> - 2013-11-19 15:36 +0000
      Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2013-11-19 12:41 -0500
        Re: Parsing Fortran, was Programming language and IDE design glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-11-19 20:18 +0000
          Re: Parsing Fortran, was Programming language and IDE design glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-11-21 21:22 +0000
      Re: Programming language and IDE design wclodius@earthlink.net (William Clodius) - 2013-11-22 18:27 -0700
      Re: Programming language and IDE design "robin" <robin51@dodo.com.au> - 2013-11-25 10:33 +1100
        Re: Programming language and IDE design Martin Ward <martin@gkc.org.uk> - 2013-12-03 15:15 +0000
          Re: Programming language and IDE design Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2013-12-05 03:35 +0100
      Re: Programming language and IDE design hu47121@usenet.kitty.sub.org (Hannah) - 2014-03-02 00:03 +0000
        Re: LL vs LR, was Programming language and IDE design Ivan Godard <ivan@ootbcomp.com> - 2014-03-01 20:31 -0800
          Re: LL vs LR, was Programming language and IDE design Kaz Kylheku <kaz@kylheku.com> - 2014-03-02 18:41 +0000
        Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2014-03-02 12:21 -0500
    Re: Programming language and IDE design Jonathan Thornburg <jonathan@cobalt.astro.indiana.edu> - 2013-11-19 19:39 +0000

#1040 — Re: Programming language and IDE design

On Friday 08 Nov 2013 at 05:21, glen herrmannsfeldt <gah@ugcs.caltech.edu>
wrote:
> Much "implementation dependence" comes from dependence on the host
> processor.  Maybe sometimes too much, but it is nice to be able to use
> the new features of newer processors.
>
> Many early machines were sign magnitude, but most now use twos
> complement, which mostly is an advantage.
>
> Different word sizes are also a common dependence, with 36 bit words
> and 6-bit characters common on the early scientific machines.

Avoiding dependence on the processor is a major reason for eliminating
implementation dependence.



On Friday 08 Nov 2013 at 05:45, "Hans-Peter Diettrich" <DrDiettrich1@aol.com>
wrote:
> > Similarly, a string data type
> > which can hold any size of string.
>
> While I strongly agree that a string type is an absolute must, string
> handling and text processing can be considered subject to a domain
> specific language.
>
>...
>
> > Hash tables should allow any type of key and value, and so on.
>
> I'd consider hash tables as domain specific, together with databases and
> other containers. As opposed to strings, such items should be part of
> libraries, be language specific or third-party.

It is hard to imagine a significant class of programs which would have
no need for strings. Even numeric analysis programs need to print out
results in a readable form! Similarly, once one has started using
hash tables extensively, they are essential for so many classes
of program that to describe them as "domain specific" is as absurd
as saying that arrays or lists are "domain specific".

My preference is to define the fundamental data type as a *sequence*:
with operators to extract the nth element of a sequence,
extract a subsequence, create a sequence and so on.
Arrays and lists are just two different implementations of sequences:
with different trade-offs between the efficiency of operations.
The declaration of a sequence can specify the implementation
(array or list) or leave it to the compiler to choose.

In this context, a string is simply a sequence of characters.

It seems to me absurd to have different notations for:
(1) Extracting the nth element of an array;
(2) Extracting the nth character in a string; and
(3) Extracting the nth item in a list.

To me, this is as bad as using a different notation for an "array
of integers" as for an "array of floats"!


On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:
> The majority of successful languages are LL(k) for small k.  It's hard
> to get much simpler than that for parsing.

C is not LL(K), neither is COBOL, nor C++, nor I think is Java.
That probably covers the majority of successful languages:
if "success" is defined as "total lines of code in production".

On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:
> >(2) Absolutely no behaviour should be "implementation dependent"
> >or "undefined". Every syntactically valid program should have
> >a single semantically valid meaning (even if that meaning
> >is "halt with an error message").
>
> It's impossible not to have implementation dependent behavior: e.g.,
> program execution time is a behavior that can't be specified.

In my opinion, execution time is not part of the semantics or meaning
of a program.

> Witness that there is not a single CPU that fully implements
> IEEE-754 arithmetic (old or new spec), and every implementation
> differs in what is lacking and in what needs to be corrected by
> software to yield compliant results.

This is the huge advantage of IEEE-754 arithmetic: the programmer
can know for certain what the result of a floating point operation
will be. The language abstracts from all the messy differences
between implementations: while also providing an incentive
to hardware designers to ensure that the time-critical components
of the specification can be implemented efficiently.

Early CPUs did not have a hardware stack:  your attitude would suggest
that *therefore* languages should define the behaviour of a recursive
subroutine to be "implementation dependent".  Fortunately, there were
language designers, such as the designers of Lisp and Algol,
who recognised the value of recursion and included it in their language.
As a result, hardware designers added stack operations to their CPUs.

If we had had more languages with hash tables built in,
we might by now have CPUs with content addressable memory:
allowing for constant time hash table implementations.

On Sunday 10 Nov 2013 at 04:41, "Jonathan Thornburg"
<jthorn@astro.indiana.edu> wrote:
> Martin Ward <martin@gkc.org.uk> wrote:
> > (2) Absolutely no behaviour should be "implementation dependent"
> > or "undefined". Every syntactically valid program should have
> > a single semantically valid meaning (even if that meaning
> > is "halt with an error message").
>
> This is really problematic in the area of floating-point arithmatic.
> For example, at what point should floating-point arithmetic overflow
> or underflow, and what should be the consequences of this happening?
> To be very precise, what "single semantically valid meaning" should we
> perscribe for trying to compute the square of 1.0e300?

These questions are precisely why the IEEE 754 floating point standard
was needed:  it specifies precise answers to all these questions
(without leaving anything "implementation dependent",
other than extra information encoded in a NaN).  See the paper
"What Every Computer Scientist Should Know About Floating Point":

http://www.validlab.com/goldberg/paper.ps

Alas, although the result of a = b + c is now precisely defined
in C and C++ for floating point variables b and c, the result can be
"undefined behaviour" for ordinary 32 bit signed integer values(!)
Other examples are integer divide by zero and "shift past bitwidth".

Programmers who want defined behaviour from their programs
(and who doesn't?) have to add extra code to integer operations:
even when running on hardware which implements two's
complement arithmetic. For example, CERT recommends:

  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    /* Handle error */
  } else {
    sum = si_a + si_b;
  }

> Java encountered all of these problems, and eventually chose to back
> off its "precise specification" to allow implementation-defined
> semantics for floating-point arithmetic.

That would be a disaster for Java if it were true, however
the current Java language specification (Java SE 7 Edition) states:

"The Java programming language requires that floating-point arithmetic
behave as if every floating-point operator rounded its floating-point
result to the result precision.  Inexact results must be rounded
to the representable value nearest to the infinitely precise result;
if the two nearest representable values are equally near,
the one with its least significant bit zero is chosen.
This is the IEEE 754 standard's default rounding mode known
as round to nearest."

The alternative floating point semantics (provide a result which is
a rough approximation to the rounded exact result) was implemented
in an early version of the Intel P5 Pentium, but was not well received:
with many users describing it as a "bug"! :-)
http://en.wikipedia.org/wiki/Pentium_FDIV_bug

--
			Martin

Dr Martin Ward STRL Principal Lecturer and Reader in Software Engineering
martin@gkc.org.uk  http://www.cse.dmu.ac.uk/~mward/  Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Mirrors:  http://www.gkc.org.uk  and  http://www.gkc.org.uk/gkc
[This discussion has gone into the weeds. It's over unless someone
wants to bring it back to compiler design and implementation. -John]

[toc] | [next] | [standalone]

#1041

Martin Ward schrieb:
> On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:
>> The majority of successful languages are LL(k) for small k.  It's hard
>> to get much simpler than that for parsing.
>
> C is not LL(K),

C is LL(1) with one exception, which makes it LL(2). See my ToPas
project on SourceForge.

DoDi

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

#1042

On Sat, 16 Nov 2013 15:55:10 +0000, Martin Ward <martin@gkc.org.uk>
wrote:

>On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:
>
>> The majority of successful languages are LL(k) for small k.  It's hard
>> to get much simpler than that for parsing.
>
>C is not LL(K), neither is COBOL, nor C++, nor I think is Java.
>That probably covers the majority of successful languages:
>if "success" is defined as "total lines of code in production".

They _all_ are LL(k).  More specifically, I believe all of your
examples are, at most, LL(2).

AFAIK, Fortran's DO loop requires the most lookahead of any of the
classic language features: LL(4) [if I'm counting correctly].

   10DOI=42
   10DOI=42,45

Card Fortran didn't require whitespace separation. You had to look
ahead to find [or not] the comma to distinguish DO "I = m,n" from the
assignment "DOI = n".


>> It's impossible not to have implementation dependent behavior: e.g.,
>> program execution time is a behavior that can't be specified.
>
>In my opinion, execution time is not part of the semantics or meaning
>of a program.

Then I hope never to encounter any devices you have programmed.


>Early CPUs did not have a hardware stack:  your attitude would suggest
>that *therefore* languages should define the behaviour of a recursive
>subroutine to be "implementation dependent".  Fortunately, there were
>language designers, such as the designers of Lisp and Algol,
>who recognised the value of recursion and included it in their language.
>As a result, hardware designers added stack operations to their CPUs.

I simply said that your assertion:

  (2) Absolutely no behaviour should be "implementation dependent"
      or "undefined". Every syntactically valid program should have
      a single semantically valid meaning (even if that meaning
      is "halt with an error message").

is not plausible.  I did not offer an alternative.


Since you brought up this ludicrous example, you ought to know that
the people who programmed those early CPUs - stack or no - were far
more aware of the program's runtime environment and of the tradeoffs
of using "equivalent" codings than you seem to want to be.

George
[Fortran through F77 potentially had to look arbitrarily far ahead to
tell FORMAT statements from an assignment to an array called FORMAT.
BTDT. But I would be surprised if any modern languages were that hard
to lex. -John]

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

#1044

> [Fortran through F77 potentially had to look arbitrarily far ahead to
> tell FORMAT statements from an assignment to an array called FORMAT.
> BTDT. But I would be surprised if any modern languages were that hard
> to lex. -John]

Fixed source form is supported by all Fortran standards (F77, F90, F95,
F2003, F2008) and it is still supported in the current draft of the next
revision to the Fortran standard.  So, I suppose you need to define
"modern langauges".

--
steve
["not Fortran" -John]

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

#1045

Our esteemed moderator wrote:

>[Fortran through F77 potentially had to look arbitrarily far ahead to
>tell FORMAT statements from an assignment to an array called FORMAT.
>BTDT. But I would be surprised if any modern languages were that hard
>to lex. -John]

You're right - I forgot that the FORMAT *statement* also could be
confused with an assignment [I only ever used format strings with READ
and WRITE].  That potentially could require a large lookahead.

But it's still LL(k).  8-)

George
[Oh, sure, once you know whether a statement is an assignment or
something else, parsing is trivial. -John]

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

#1048 — Re: Parsing Fortran, was Programming language and IDE design

George Neuner <gneuner2@comcast.net> wrote:
> Our esteemed moderator wrote:

>>[Fortran through F77 potentially had to look arbitrarily far ahead to
>>tell FORMAT statements from an assignment to an array called FORMAT.
>>BTDT. But I would be surprised if any modern languages were that hard
>>to lex. -John]

> You're right - I forgot that the FORMAT *statement* also could be
> confused with an assignment [I only ever used format strings with READ
> and WRITE].  That potentially could require a large lookahead.

It is the H format descriptor that complicates the parsing, and I
believe that has been removed by now from the standard. Even so, many
compilers still support it for back compatibility.

Because of this complication, WATFIV, at least the version I used,
disallowed 'FORMAT(' as the first seven characters of a statement that
wasn't a FORMAT statement. That is, no assignment to elements of an
array named FORMAT.  (I believe WATFIV allows multiple assignment, so
there would have been a way to get around it.)

One feature of Fortran 66 was that you could store the format data
into an array (had to be an array, not a scalar) and use that in place
of a FORMAT statement. It always seemed obvious to me that the array
be named FORMAT.

I believe a favorite example might have been similar to:

1     FORMAT(I2,5H)=X(1,I2)

(and gfortran seems to allow this one.)

> But it's still LL(k).  8-)

> [Oh, sure, once you know whether a statement is an assignment or
> something else, parsing is trivial. -John]

As previously noted, fixed form is still allowed in the current and
proposed next standard. That is, all additions to the language since
Fortran 77 can also be written in fixed form. Someone presumably checks
to be sure that there aren't any new ambiguities added with the new
features.

-- glen
[I found that H descriptors were easy to handle, just pull them out in a
prepass.  The problem was assignments that look like format statements:

      FORMAT(A5,I3,I5) = 42

WATFIV was a student compiler and probably concluded that any student
who wrote code like that deserved to fail. -John]

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

#1050 — Re: Parsing Fortran, was Programming language and IDE design

(snip, I wrote)

> Because of this complication, WATFIV, at least the version I used,
> disallowed 'FORMAT(' as the first seven characters of a statement that
> wasn't a FORMAT statement. That is, no assignment to elements of an
> array named FORMAT.  (I believe WATFIV allows multiple assignment, so
> there would have been a way to get around it.)

(snip)

> [I found that H descriptors were easy to handle, just pull them out in a
> prepass.  The problem was assignments that look like format statements:

>      FORMAT(A5,I3,I5) = 42

> WATFIV was a student compiler and probably concluded that any student
> who wrote code like that deserved to fail. -John]

But arrays named FORMAT are allowed everywhere else, except at the left
side of an assignment. Functions named FORMAT are also allowed.

And at least once, (not with WATFIV) I used it as the name of a run-time
format specified, which was required to be an array.

-- glen

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

#1051

George Neuner <gneuner2@comcast.net> wrote:

> On Sat, 16 Nov 2013 15:55:10 +0000, Martin Ward <martin@gkc.org.uk>
> wrote:
>
> >On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:
> >
> >> The majority of successful languages are LL(k) for small k.  It's hard
> >> to get much simpler than that for parsing.
> >
> >C is not LL(K), neither is COBOL, nor C++, nor I think is Java.
> >That probably covers the majority of successful languages:
> >if "success" is defined as "total lines of code in production".
>
> They _all_ are LL(k).  More specifically, I believe all of your
> examples are, at most, LL(2).
>
> AFAIK, Fortran's DO loop requires the most lookahead of any of the
> classic language features: LL(4) [if I'm counting correctly].
>
>    10DOI=42
>    10DOI=42,45
>
> Card Fortran didn't require whitespace separation. You had to look
> ahead to find [or not] the comma to distinguish DO "I = m,n" from the
> assignment "DOI = n".

In Fortran typically staement classification (and identification of
tokens in fixed form) was performed as an initial pass. Once the
statement is identified as to whether or not it is an assignment then
the syntactic interpretation of the first token is LL(1), and I suspect
all tokens including Holleriths.
[I wrote some F77 parsers 30 years ago, and there was some reason I
needed to deal with the Hollerith strings before the rest of the
pre-parse, but I don't remember offhand what it was. -John]

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

#1055

From: "George Neuner" <gneuner2@comcast.net>
Sent: Tuesday, November 19, 2013 11:02 AM

> AFAIK, Fortran's DO loop requires the most lookahead of any of the
> classic language features: LL(4) [if I'm counting correctly].
>
>   10DOI=42
>   10DOI=42,45

The statements are
    DO 10 I = 42
    DO 10 I = 42, 45

> Card Fortran didn't require whitespace separation.

Still doesn't, though since the advent of Fortran 90,
an alternative free source form requires a space between the syntactic elements,
so the difficulty doesn't arise.  Nor, can the "classic" (apocryphal?) error
DO10I=42.45
occur (assuming that declarations are made compulsory with the statement
IMPLICIT NONE).

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

#1058

On Sunday 24 Nov 2013 at 23:33, "robin" <robin51@dodo.com.au> wrote:
> > AFAIK, Fortran's DO loop requires the most lookahead of any of the
> > classic language features: LL(4) [if I'm counting correctly].
> >
> >   10DOI=42
> >   10DOI=42,45
>
> The statements are
>     DO 10 I = 42
>     DO 10 I = 42, 45

The difference is even smaller than this:

     DO 10 I = 42.45
     DO 10 I = 42,45

The first is an assignment of a floating point value to variable DO10I,
the second is a loop with I as the loop variable.

Fortran allows spaces in the middle of identifiers, so requiring
spaces around keywords does not help (unless you *also*
disallow spaces within identifiers).

The fact that the two statements can be distinguished with an LL(k)
parser does not necessarily mean that the language is easy to read.
Disallowing spaces within identifiers, insisting on spaces around keywords,
insisting on correct indentation and correct and distinct closing keywords
to block structures, and requiring all identifiers to be declared with an
appropriate type, all make the language harder to write:
but also easier for humans to read (even if they make no difference
to the language parser). Any, or all, of these restrictions would have
prevented the confusion between an assignment and a loop.

--
			Martin

Dr Martin Ward STRL Principal Lecturer and Reader in Software Engineering
martin@gkc.org.uk  http://www.cse.dmu.ac.uk/~mward/  Erdos number: 4
G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/
Mirrors:  http://www.gkc.org.uk  and  http://www.gkc.org.uk/gkc

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

#1059

Martin Ward schrieb:

> The difference is even smaller than this:
>
>      DO 10 I = 42.45
>      DO 10 I = 42,45
>
> The first is an assignment of a floating point value to variable DO10I,
> the second is a loop with I as the loop variable.
>
> Fortran allows spaces in the middle of identifiers, so requiring
> spaces around keywords does not help (unless you *also*
> disallow spaces within identifiers).
>
> The fact that the two statements can be distinguished with an LL(k)
> parser does not necessarily mean that the language is easy to read.

How would a LL grammar look like, when the lexer returns multiple tokens
for an identifier, here "DO","10" and "I"? With a traditional lexer I'd
suspect that such a language is *context sensitive*, with something else
for "LL(k)".

DoDi
[I suppose the prepass to tell whether it's an assignment is LL(1).  You definitely
need to preprocess the statement to tell whether it's an assignment or something
else.  After that, the parsing is very easy. -John]

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

#1125

George Neuner <gneuner2@comcast.net> wrote:
>On Sat, 16 Nov 2013 15:55:10 +0000, Martin Ward <martin@gkc.org.uk>
>wrote:

>>On Friday 08 Nov 2013 at 21:04, George Neuner <gneuner2@comcast.net> wrote:

>>> The majority of successful languages are LL(k) for small k.  It's hard
>>> to get much simpler than that for parsing.

>>C is not LL(K), neither is COBOL, nor C++, nor I think is Java.
>>That probably covers the majority of successful languages:
>>if "success" is defined as "total lines of code in production".

>They _all_ are LL(k).  More specifically, I believe all of your
>examples are, at most, LL(2).

I don't think C++ is LL(2).

Think e.g.

  T(a)++;
vs.
  T(a)[5];

(Example from n3485, page 131).

The former is a statement, while the latter is a declaration, and you
can decide this only very late. As the first four tokens are the same,
C++ can't be LL(4), at least.

As you can substitute '('^n x ')' ^n for a in this example (i.e. enclose
that identifier in any number of parentheses), C++ isn't LL(n) for any n.
(In the first case, "a" is a subexpression, that can be parenthesized,
while in the second case, it's the declarator-id that can also be
parenthesized).

Then, in C99, in function parameter declarations
(i.e. parameter-type-list, then in the single parameter-declaration,
after declaration-specifiers, even if you left-factor those), you have
to decide whether you're to descend into declarator or into
abstract-declarator_opt.

FIRST_k(declarator), however, includes "("^k, as does
FIRST_k(abstract-declarator_opt):

The former via k recursions of declarator -> direct-declarator -> ( declarator )
the latter via k recursions of
  abstract-declarator -> direct-abstract-declarator -> ( abstract-declarator )

So the C grammar is not LL(k) for any k, either. You can probably parse
that particular part of the C/C++ grammar easily using LR.

Hannah.

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

#1126 — Re: LL vs LR, was Programming language and IDE design

On 3/1/2014 4:03 PM, Hannah wrote:
<snip>

> So the C grammar is not LL(k) for any k, either. You can probably parse
> that particular part of the C/C++ grammar easily using LR.
>
> Hannah.

The standard way to handle this, and many such other cases where a
formal grammar is not LL, is to introduce a function (in recursive
descent) or rule (in parser generators) that recognizes "parenthesized
thingy" and then figure it out later. Yes, that amounts to LR, but you
only need it in a few specialized places. There's an equivalent trick
in "DOI=1," in Fortran, where you let the lexer resolve it so the
parser sees proper lexemes, not characters.

C and its descendants are well known for being inhumane (as well as
parser-unfriendly) in their excessive overloading of parens and braces.
More friendly (or less keystroke-obsessed) languages require all
syntactic regions to have both openers and closers, unique for each kind
of region, to avoid the canonical C bug of mismatched closers; Algol68
is an early example of doing it right.
[C++ is unusually bad, with some parts just plain ambiguous.  In the example
a few messages back, I gather that the rule is that if you can parse it as a
declaration, it's a declaration, otherwise it's something else. -John]

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

#1128 — Re: LL vs LR, was Programming language and IDE design

On 2014-03-02, Ivan Godard <ivan@ootbcomp.com> wrote:
> On 3/1/2014 4:03 PM, Hannah wrote:
><snip>
>
>> So the C grammar is not LL(k) for any k, either. You can probably parse
>> that particular part of the C/C++ grammar easily using LR.
>>
>> Hannah.
>
> The standard way to handle this, and many such other cases where a
> formal grammar is not LL, is to introduce a function (in recursive
> descent) or rule (in parser generators) that recognizes "parenthesized
> thingy" and then figure it out later. Yes, that amounts to LR, but you
> only need it in a few specialized places. There's an equivalent trick
> in "DOI=1," in Fortran, where you let the lexer resolve it so the
> parser sees proper lexemes, not characters.

You can parse "anything" with LL(k) with backtracking. What you do is
you try various different parses, in a carefully designed order, until
something matches, with backtracking.

> [C++ is unusually bad, with some parts just plain ambiguous.  In the example
> a few messages back, I gather that the rule is that if you can parse it as a
> declaration, it's a declaration, otherwise it's something else. -John]

Years ago (1999) I wrote a parser for C expression syntax (only the expression
syntax)  as part of a module which could diagnose, at run-time, unsafe uses of
a C macro that contains multiple evaluations:

The source code is here:

http://git.savannah.gnu.org/cgit/kazlib.git/tree/sfx.c

E.g. dumb example:

  #define INCR(A) (SFX_CHECK(A) = (A) + 1)

This SFX_CHECK (actually KAZLIB_SFX_CHECK, for hygiene) expands to code which
produces the value of (A), but also hands the expression "A" to a run-time
checker which answers the question, does the C expression "A" have side
effects?

The answer to the question is "yes, no, or possibly".

(Also, the expression "A" is put into a hash table which caches the
result for next time, so the checking is faster, when turned on.)

If the answer is other than no, then a diagnostic is printed, with the
expression "A", and file name and line number where that macro was
expanded. The diagnostic tells you whether there is a confirmed problem
in that line or just suspicion.

The parser has way to know how a symbol is declared, and so it uses
backtracking techniques.

In fact, an exception library based on setjmp/longjmp is used for some
backtracking returns.  There is logic like, "if parsing it this way throws a
syntax error, try it this way".

For instance, what is "(a)(b)"?  This could be that function a is being
called with argument b.  Or it could be that a is a type, and b is being
cast to that type.

I remember parts of this being somewhat tough to write, but it looks fairly
transparent to me today.  That was about a year before I discovered Lisp.

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

#1127

On Sun, 2 Mar 2014 00:03:18 +0000 (UTC), hu47121@usenet.kitty.sub.org
(Hannah) wrote:

>I don't think C++ is LL(2).
>
>Think e.g.
>
>  T(a)++;
>vs.
>  T(a)[5];
>
>(Example from n3485, page 131).
>
>The former is a statement, while the latter is a declaration, and you
>can decide this only very late. As the first four tokens are the same,
>C++ can't be LL(4), at least.
>
>As you can substitute '('^n x ')' ^n for a in this example (i.e. enclose
>that identifier in any number of parentheses), C++ isn't LL(n) for any n.
>(In the first case, "a" is a subexpression, that can be parenthesized,
>while in the second case, it's the declarator-id that can also be
>parenthesized).

I suppose that it depends on your definitions: a "syntax" token is
different from a "grammar" token ... a single grammar token can
represent an expression of any complexity.  I think the whole notion
of lookahead is ambiguously level dependent.

But I concede your point re: syntax.

>So the C grammar is not LL(k) for any k, either. You can probably parse
>that particular part of the C/C++ grammar easily using LR.

However, both C and C++ are LL(*).  LL(*) Antlr-3 grammars are
available for both http://www.antlr3.org/grammar/list.html

Also in that list you'll find an LL(k) Antlr-2 grammar for C/C++ which
at quick glance claims to be LL(2) ... but I haven't examined it to
know what tricks it may be employing.
http://hg.netbeans.org/main/file/tip/cnd.modelimpl/src/org/netbeans/modules/c
nd/modelimpl/parser/cppparser.g

George

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

#1047

I asked:
> at what point should floating-point arithmetic overflow
> or underflow, and what should be the consequences of this happening?
> To be very precise, what "single semantically valid meaning" should we
> perscribe for trying to compute the square of 1.0e300?

Martin Ward <martin@gkc.org.uk> wrote:
> These questions are precisely why the IEEE 754 floating point standard
> was needed:  it specifies precise answers to all these questions
> (without leaving anything "implementation dependent",
> other than extra information encoded in a NaN).  See the paper
> "What Every Computer Scientist Should Know About Floating Point":
>
> http://www.validlab.com/goldberg/paper.ps

The IEEE single-extended and double-extended formats define the
precision and exponent range as "implementation-dependent".  You can
see this in table D-1 of the validlab.com version of Goldberg's paper
[which we should note was originally published in ACM Computing Surveys
23(1), March 1991, pages 5-48], and the immediately following sentence
   "The IEEE standard only specifies a lower bound on how many
    extra bits extended precision provides."
This means that whether or not certain operations overflow is indeed
implementation-dependent.

--
-- "Jonathan Thornburg [remove -animal to reply]" <jthorn@astro.indiana-zebra.edu>
   Dept of Astronomy & IUCSS, Indiana University, Bloomington, Indiana, USA
   "There was of course no way of knowing whether you were being watched
    at any given moment.  How often, or on what system, the Thought Police
    plugged in on any individual wire was guesswork.  It was even conceivable
    that they watched everybody all the time."  -- George Orwell, "1984"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web