Hacker News Reader

Comment by jrockway | Hacker News Reader

Does the parser really need to know this information? XX yy; only means one thing: declare( type: XX, variable: yy). Making that work is the job of something else down the pipeline that knows about the concept of types and symbol tables.

As an example, Emacs syntax-highlights both "YY xx" and "int xx" the same way.

View on HN

Yes, the parser needs to know about this information. Example:

    (A) * B

This is either A multiplied by B, or type A casting the dereferenced value of B: http://en.wikipedia.org/wiki/The_lexer_hack

Fair enough. Would the problem be fixed if the C standard said that x (without spaces) had to be dereferencing and that x y (with spaces) had to be multiplication?

It was as if a million C programmers cried out and were suddenly silenced.

Significant whitespace is evil, at least in the context of C where it is not significant anywhere else.

Whitespace is significant in C. Consider the difference between "f o o" and "foo" :)

Idon'tknowwhatyou'retalkingabout! :)

You like your Commodore 64 BASIC (or Ye Olde Fortran)?

Yeah, if you could purely lexically distinguish dereferencing from multiplication, either because they used a different symbol, or had different mandatory whitespace rules, then there'd be no ambiguity, at least in this example.

That's basically what C++ did by requiring the space in:

   Foo<Bar<Baz> > var;

to make it easy to lexically distinguish the '>>' right-shift operator from the '> >' sequence of two successive template-parameter closing symbols.

C++0x is changing that though, due to the unpopularity of making programmers accomodate what looks like a parser-implementation hack.

No, consider int x; sizeof(x); and typedef int x; sizeof(x);.

That's not a syntactic ambiguity. Typically (when you're not trying to compress multiple passes, be clever and fast etc.), identifiers are not resolved during parsing, so it doesn't matter whether x denotes a type or a variable when the sizeof operator is applied.

You can write "A * B" and depending on nature of A, that would be a declaration of B as pointer to type B, or multiplication of A and B. You could say that this multiplication would be 'void' (as in 'not assigned to anything') and I could come up with even more complicated example, like "A * B();" where this is either function declaration or multiplication of A and function named B() with side-effect let's say. But that's not the point: if parser has to do heuristics like that to parse language properly, it is already context-dependent or at least not LALR(0) or LALR(1).

I was talking about sizeof.

I think it does matter, although my example fails to make clear why. Type identifiers have different syntactic requirements to regular identifiers (the parens in sizeof(typename) are required, but the parens in sizeof(varname) are optional).

Yes, but now you're getting deeper into requirements for context-sensitive grammar; go far enough, and you might as well go all Van Wijngaarden. A context-free parse is free to create an AST like (sizeof (parens (ident "x"))) for one, and (sizeof (ident "x")) for the other, and disambiguate based on the symbol table lookup of "x" later.

But "XX XX;" (the example was given in the article) is valid, and the parser needs to know the difference.

The article says that this code is "evil", but I disagree. There is a valid pattern that I use quite often (I described it in an article for ACCU a few years ago, too). It's an example from C++ but I think I could apply it to C as well. Consider (with a modification of the example I used in that article):

struct PirateShip { struct Cannons { char* cannon1; char* cannon2; } Cannons; }

Now you can use

PirateShip s; printf("Name of the first cannon: %s\n", s.Cannons.cannon1);

which is very readable and idiomatic (once you get used to it ;) )

More abstract, it provides an idiomatic way to group collections of objects/structs at the source code/syntactic level.

(one could name the struct and the member differently, I realize; the benefit of using the same name is when you define constant members in the inner struct, that way you can reference constants and properties with the same name and you never have to think about which one to use.)

(also again I use this from C++, there may be things that are different in C, but afaik this part is the same).

I'm not sure how you use "XX XX" in that code sample. Do you refer to the "struct Foo {...} Foo;" idiom? That's quite different, though :)

I think it is, I may be wrong. It's the same as (trying to preserve formatting this time):

    struct PirateShip {
        struct PirateShip {
            char* cannon1;
            char* cannon2;
        }
        PirateShip PirateShip;
    }

Am I misunderstanding?

I've seen similar code being used, but IMHO it's confusing

A complete parser has to be strict. Emacs's syntax-highlighting, as we all know, is very heuristic and approximate. While it does a good job for the common cases, it's easy to break it with more freakish examples. A real compiler can't allow that.

To parse this correctly, the parser has to receive a "TYPE-NAME" token for XX and an "IDENTIFIER" token for yy. If the parser receives an IDENTIFIER token for XX, this will result in a parse error.

To be more precise, "a context-free parser has to receive a TYPE-NAME token...". A hand-coded parser would be able to parse things just fine if both XX and yy were IDENTIFIERs.

Or, to put it another way, you resort to uglyfying the lexer to overcome definiciencies in the parser.

Indeed, which is exactly the point of the article this discussion refers to

Alternately, you can implement such context-sensitive features in another pass after the parse.

The parser needs to know about it iff you want your parser to disambiguate certain scenarios. An alternative approach is to handle the ambiguous scenarios generically in a specific parser construct (e.g. build a special AST node), and resolve it later after you've collected type information.

Reply on news.ycombinator.com