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

Groups > comp.lang.c > #67454 > unrolled thread

Labels

Back to article view | Back to comp.lang.c

Contents

  Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-15 09:46 -0700
    Re: Labels James Kuyper <jameskuyper@verizon.net> - 2015-08-15 14:49 -0400
      Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-15 18:48 -0700
    Re: Labels Bartc <bc@freeuk.com> - 2015-08-15 18:27 +0100
      Re: Labels Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-15 23:44 +0100
        Re: Labels James Kuyper <jameskuyper@verizon.net> - 2015-08-15 19:04 -0400
          Re: Labels Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-16 00:47 +0100
            Re: Labels James Kuyper <jameskuyper@verizon.net> - 2015-08-15 20:20 -0400
              Re: Labels Bartc <bc@freeuk.com> - 2015-08-16 01:56 +0100
                Re: Labels Keith Thompson <kst-u@mib.org> - 2015-08-15 19:47 -0700
                  Re: Labels James Kuyper <jameskuyper@verizon.net> - 2015-08-16 11:59 -0400
              Re: Labels Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-16 22:42 +0100
                Re: Labels James Kuyper <jameskuyper@verizon.net> - 2015-08-16 20:39 -0400
                  Re: Labels Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-17 03:16 +0100
          Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-15 19:01 -0700
        Re: Labels Bartc <bc@freeuk.com> - 2015-08-16 01:11 +0100
          Re: Labels Keith Thompson <kst-u@mib.org> - 2015-08-15 19:13 -0700
            Re: Labels Bartc <bc@freeuk.com> - 2015-08-16 10:34 +0100
              Re: Labels Keith Thompson <kst-u@mib.org> - 2015-08-16 13:58 -0700
              Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-16 20:42 -0700
                Re: Labels Keith Thompson <kst-u@mib.org> - 2015-08-16 21:24 -0700
                  Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-17 18:01 -0700
                Re: Labels Bartc <bc@freeuk.com> - 2015-08-17 11:04 +0100
          Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-15 19:04 -0700
          Re: Labels Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-16 23:55 +0100
      Re: Labels David Kleinecke <dkleinecke@gmail.com> - 2015-08-15 19:00 -0700

Page 2 of 2 — ← Prev page 1 [2]

#67560

David Kleinecke <dkleinecke@gmail.com> writes:
> On Sunday, August 16, 2015 at 2:34:31 AM UTC-7, Bart wrote:
>> On 16/08/2015 03:13, Keith Thompson wrote:
>> > Bartc <bc@freeuk.com> writes:
>> > [...]
>> >> But even knowing a starter symbol is a typedef name, then with 'T(' you
>> >> might still be a long way from knowing if this is a simple variable
>> >> declaration, or the start of a 1000-line function definition.
>> >
>> > At block scope, function definitions are not permitted.  At file scope,
>> > a function definition cannot start with 'T('; it requires at least a
>> > type name and an identifier.
>> 
>> The following seems to be legal:
>> 
>> #include <stdio.h>
>> 
>> typedef int T;
>> 
>> T(main)(void) {
>>     printf("Hello World\n");
>> }
>
> It is my understanding that typedefs are not actual types but rather 
> a kind of alsias for the type they are defined as. Hence
>    typedef int T;
> makes
>    T main ....
> compile eactly as if you had written
>    int main ...
>
> The compiler must maintain internally a table of what typedef names
> mean. The meaning part of that table is a (possibly very complicated)
> expression in non-typedef types and their decoration.  

Bart's point was that the parentheses around main are permitted
(something I initially didn't notice either).

I had incorrectly said that 'T(' cannot start a function definition.
Bart came up with a counterexample, using a typedef and extra
parentheses.

Yes, a typedef creates a new name for an existing type, not a
new type.  That's not the point here.  This:

    int(main)(void) { /* ... */ }

which is more commonly written as

    int main(void) { /* ... */ }

would have made the same point, except that my incorrect statement
involved an identifier T rather than the keyword int.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#67666

On Sunday, August 16, 2015 at 8:57:01 PM UTC-7, Keith Thompson wrote:
> David Kleinecke <dkleinecke@gmail.com> writes:
> > On Sunday, August 16, 2015 at 2:34:31 AM UTC-7, Bart wrote:
> >> On 16/08/2015 03:13, Keith Thompson wrote:
> >> > Bartc <bc@freeuk.com> writes:
> >> > [...]
> >> >> But even knowing a starter symbol is a typedef name, then with 'T(' you
> >> >> might still be a long way from knowing if this is a simple variable
> >> >> declaration, or the start of a 1000-line function definition.
> >> >
> >> > At block scope, function definitions are not permitted.  At file scope,
> >> > a function definition cannot start with 'T('; it requires at least a
> >> > type name and an identifier.
> >> 
> >> The following seems to be legal:
> >> 
> >> #include <stdio.h>
> >> 
> >> typedef int T;
> >> 
> >> T(main)(void) {
> >>     printf("Hello World\n");
> >> }
> >
> > It is my understanding that typedefs are not actual types but rather 
> > a kind of alsias for the type they are defined as. Hence
> >    typedef int T;
> > makes
> >    T main ....
> > compile eactly as if you had written
> >    int main ...
> >
> > The compiler must maintain internally a table of what typedef names
> > mean. The meaning part of that table is a (possibly very complicated)
> > expression in non-typedef types and their decoration.  
> 
> Bart's point was that the parentheses around main are permitted
> (something I initially didn't notice either).
> 
> I had incorrectly said that 'T(' cannot start a function definition.
> Bart came up with a counterexample, using a typedef and extra
> parentheses.
> 
> Yes, a typedef creates a new name for an existing type, not a
> new type.  That's not the point here.  This:
> 
>     int(main)(void) { /* ... */ }
> 
> which is more commonly written as
> 
>     int main(void) { /* ... */ }
> 
> would have made the same point, except that my incorrect statement
> involved an identifier T rather than the keyword int.
 
I missed the original point of the comment. I fear that the 
parentheses were allowed was too obvious to me. So I guessed.

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

#67573

On 17/08/2015 04:42, David Kleinecke wrote:
> On Sunday, August 16, 2015 at 2:34:31 AM UTC-7, Bart wrote:
>> On 16/08/2015 03:13, Keith Thompson wrote:
>>> Bartc <bc@freeuk.com> writes:
>>> [...]
>>>> But even knowing a starter symbol is a typedef name, then with 'T(' you
>>>> might still be a long way from knowing if this is a simple variable
>>>> declaration, or the start of a 1000-line function definition.
>>>
>>> At block scope, function definitions are not permitted.  At file scope,
>>> a function definition cannot start with 'T('; it requires at least a
>>> type name and an identifier.
>>
>> The following seems to be legal:
>>
>> #include <stdio.h>
>>
>> typedef int T;
>>
>> T(main)(void) {
>>      printf("Hello World\n");
>> }
>>
>> --
>> Bartc
>
> It is my understanding that typedefs are not actual types but rather
> a kind of alsias for the type they are defined as. Hence
>     typedef int T;
> makes
>     T main ....
> compile eactly as if you had written
>     int main ...

Possibly you're confusing the typedef T with a macro T. The translation 
from T to int can't be done automatically because it first has to be 
established exactly what T is at the point it is encountered.

It could be one of:

* A label name                        T:
* A function name                     T(10);
* A variable name                     T+U;
* An enum name                        T;
* A different typedef name
* Or the int typedef as defined above

> The compiler must maintain internally a table of what typedef names
> mean. The meaning part of that table is a (possibly very complicated)
> expression in non-typedef types and their decoration.

No more complicated than what is stored with each variable or parameter 
name. The difficulty here is (1) determining that this must be a typedef 
name; (2) finding out which typedef if there are several possibilities.

(The language I normally compile has a far simpler syntax to make life 
easier. At any point where a declaration might be expected, then if 
'<name> <name>...' is encountered, the first name is assumed to be a 
user type name. Then I just have to determine which type.

Even here, I have it easy because I only have one possible scope in each 
function, while C could potentially have hundreds, one per block, each 
containing a different version of 'typedef <type> T;'.)

-- 
Bartc

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

#67513

On Saturday, August 15, 2015 at 5:12:04 PM UTC-7, Bart wrote:
> On 15/08/2015 23:44, Ben Bacarisse wrote:
> > Bartc <bc@freeuk.com> writes:
> > <snip>
> >> Is 'A*B' an expression, or is it declaring a variable B of type
> >> pointer-to-A?
> >>
> >> Is 'F(G)' a function call to G with argument G, or is it declaring a
> >> variable G of type F, or is it the start of function declaration, or
> >> the start of function definition?
> >>
> >> I think you have your work cut out!
> >
> > This makes it sound as if C is particularly hard to parse, but it isn't,
> 
> I was making the point that if the OP thought detecting labels was 
> tricky, then other bits of syntax are worse. (I think labels are 
> straightforward because you only have to look one symbol ahead, and you 
> don't necessarily have to put back that symbol/token if it's not a colon.)
 
And I believe this is the only situation in C where even that much
machinery is needed.

> (FWIW I think C /is/ harder to parse compared with the syntaxes I come 
> up with. Perhaps more so for humans, with some bits of obscure syntax.)
> 
> > provided you know how to handle typedefs.  After reading a typedef, the
> > parser must mark the identifiers involved as referring to types.  This
> > can be as simple as a flag in the symbol table.  With that done, C can
> > be parsed using standard techniques to be found in any introductory text
> > on parsing.  New named types simply take on the same syntactic role as
> > type keywords like int.
> 
> With user-defined typedef names you can't rely on the 'shape' of the 
> syntax, but do need this bit of name resolution that otherwise could be 
> left until a later pass. (With F(G), F might appear as both a function 
> name and a typedef name, but in different scopes; this then forces your 
> hand in having the symbol table operate a certain way.)
> 
> But even knowing a starter symbol is a typedef name, then with 'T(' you 
> might still be a long way from knowing if this is a simple variable 
> declaration, or the start of a 1000-line function definition.
> 

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

#67548

Bartc <bc@freeuk.com> writes:

> On 15/08/2015 23:44, Ben Bacarisse wrote:
>> Bartc <bc@freeuk.com> writes:
>> <snip>
>>> Is 'A*B' an expression, or is it declaring a variable B of type
>>> pointer-to-A?
>>>
>>> Is 'F(G)' a function call to G with argument G, or is it declaring a
>>> variable G of type F, or is it the start of function declaration, or
>>> the start of function definition?
>>>
>>> I think you have your work cut out!
>>
>> This makes it sound as if C is particularly hard to parse, but it isn't,
>
> I was making the point that if the OP thought detecting labels was
> tricky, then other bits of syntax are worse.

OK, I see.  But (as you say later) that's a very low bar -- you might as
well have picked any of a dozen places where the syntax is "as hard to
parse" as labels.

Given your previously expressed antagonism to C's syntax, I thought you
were really saying that C is intrinsically hard to parse, not simply
that there are other constructs that as easy as the one DK was seeing a
problem with.

By the way, I suspect the problem he sees is because of *how* he wants
to parse C, rather than anything specific to the grammar of the
language.  As you say, labels aren't particularly hard, but he may have
set certain constraints on the process that is causing the problem.

<snip>
> But even knowing a starter symbol is a typedef name, then with 'T('
> you might still be a long way from knowing if this is a simple
> variable declaration, or the start of a 1000-line function definition.

Yes.  I think there are some places where you might want to re-factor
the grammar as given in the standard.  Both of your cases start the same
way (as a declarator) and I suspect you have to parse them like that,
only deciding on what to do when you see if you have function body.

I admit I may be over-simplifying it (but then again I may be over
complicating it).  But, in the end, I think the techniques one needs can
be found in standard texts.  In contrast (if memory serves) the authors
of Algol 68 compilers needed to come up with some new tools to get the
job done.

-- 
Ben.

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

#67509

On Saturday, August 15, 2015 at 12:22:01 PM UTC-7, Bart wrote:
> On 15/08/2015 17:46, David Kleinecke wrote:
> > One of the curious little problems encountered in making a C compiler
> > is how to recognize labels.
> >
> > There is no problem in a two-pass compiler - but let me assume a one
> > pass compiler.
> 
> Recognising labels isn't peculiar to C compilers, nor does it need 
> multiple passes: parsers are usually done in a single pass.
 
There are some arguemnts in favor of two-pass compilers which are not
obviously wrong - but I agree that, given one is writing a compiler,
a one-pass compiler is way to go. 

> > Then I am reading along compiling statements and I
> > start a new statement and the first token in the statement is an
> > identifier. Is this token a label?
> ...
> > But this seems clumsy. I think a better way to go is to admit I am
> > reading ahead one token.
> 
> That is not necessary. The way I wrote parsers (of the recursive descent 
> sort, nothing unusual), when a syntactic element has been identified, 
> the it is usually 'positioned' at the following symbol or token, ready 
> for the next lot of parsing.
> 
> So if '(a+b),' has just been processed, you've recognised Expression, 
> and the 'current' token will be whatever follows, Comma in this case.
> 
> In the case of reading a label, if Name has been seen, then you read the 
> next token. If it's a colon, then you've identified a Label, and you 
> read the following token (which determines what happens next).
> 
> If it isn't a colon, then return Name, and exit.
 
But then when you look for the token following the name it isn't in the
input stream any longer. So you need a device to get it.

>   When I discover this is not a label
> >     ahead = true;
> >     ahead_token = non-colon;
> > And then I call the expression subroutine with the usual argument -
> > the identifier - but ahead is now true. So the next_token call
> > becomes
> >     if(ahead) {
> >        ahead = false;
> >        token = ahead_token;}
> >     else
> >        token - next_token();
> > or even
> >     token = ahead ? ahead = false, ahead_token : next_token ();
> 
> You could also just write a Peek() function which tells you the next 
> token without advancing the token pointer (which might well be 
> implemented along the lines above, but it's easier to use).
 
I could systematically always read a one token ahead. I think to get
throigh the pre-processor there is one place where I need two tokens 
ahead. It's hardly worth writing a separate function for.

> > So far as I can tell this is the only place in the C syntax where
> > such a device is needed.
> 
> Really? It's more like one of the few places it isn't needed!
> 
> Is 'A*B' an expression, or is it declaring a variable B of type 
> pointer-to-A?
 
That is a well known crux. So far as I can tell the syntax must use
semantic information and recognize A as a typedef name (assuming 
that's what it is).

> Is 'F(G)' a function call to G with argument G, or is it declaring a 
> variable G of type F, or is it the start of function declaration, or the 
> start of function definition?

This is a non-problem. A well designed compiler will always know.   

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web