15
$\begingroup$

In the C language, there's the 2 similar-in-form but distict-in-meaning constructs:

(type)value which is a casting, and (value), which is a grouping.

How do a $LR(1)$ parser deal with this? I can think of a compiler that breaks syntax and semantic boundary able to disambiguate it by providing information about the meaning of the token, but how does a generic parser handle this without high-level information?

$\endgroup$

2 Answers 2

22
$\begingroup$

It's not possible for an LR(1) parser to solve this problem without using the Lexer Hack: information from the symbol table, which is able to differentiate type names from variable names, is reported to the parser using two different token kinds for "identifier". The impossibility stems from the grammar being otherwise ambiguous, as shown by the example from the linked Wikipedia article, (A)*B, which can be either a cast of a pointer dereference (if A is a type) or a multiplication with redundant grouping parentheses around the first operand (if A is a variable).

The Wikipedia article goes on to claim that Clang does not use the Lexer Hack, although I see this as a technicality: the Clang parser (which is a hand-written, recursive descent parser, not LR(1) table-driven) gets identifier disambiguation information before deciding what to do, but via a separate semantic analysis query instead of using two distinct token kinds. It's the same information, for the same purpose, just delivered via an adjacent channel.

In a comment on another answer, Ben suggests parsing without (at first) fully disambiguating. Due to the aforementioned ambiguity (among others), this is not possible when using an LR(1) parser (you'd get unresolvable shift/reduce conflicts). However, a Generalized LR algorithm can be used instead, which in general yields an abstract syntax forest (which uses node sharing to avoid exponential blowup) rather than a syntax tree. My MS thesis, Elkhound, a Fast, Practical GLR Parser Generator, explored the feasibility of this approach for both C and C++. The resulting parser, called Elsa, could be regarded as a "generic parser [that handles] this without high-level information". (Beware: Elsa is relevant to this question as a proof of concept, but is very much a "fixer upper" for anyone trying to use it to parse real-world C/C++. Clang does that job much better.)

$\endgroup$
3
  • $\begingroup$ One could mention the annoying typename that is sometimes necessary in C++ to indicate that the following expression is a type name. $\endgroup$
    – Carsten S
    Mar 27 at 19:51
  • 1
    $\begingroup$ @CarstenS It's a good thought, and you're right that typename is related, but a mere mention could imply that's the only additional complication in C++, which isn't the case (see section 5.1 of my thesis for an arguably more impactful issue), and a more thorough treatment is out of scope. $\endgroup$ Mar 28 at 4:04
  • $\begingroup$ Fair enough. It's just what came to my mind as a C++ programmer. $\endgroup$
    – Carsten S
    Mar 28 at 7:04
12
$\begingroup$

They can easily be distinguished by a compiler: In the first case, the thing in parentheses is a type, in the second case it isn’t.

Now if you insist on parsing based on a grammar only, that may be a problem. But there is no reason why a compiler writer would limit themselves in this way. So how does a compiler do it without using high level information? It doesn’t. There is no reason to.

$\endgroup$
4
  • $\begingroup$ I'm thinking for myself what my next project should be, and I thought implementing yacc would be nice. Yacc doesn't have semantic-level information, so I thought asking in this regard. I think I'll just check out how other implementations of Yacc break the syntax-semantic barrier. $\endgroup$
    – DannyNiu
    Mar 25 at 10:57
  • 8
    $\begingroup$ @DannyNiu I don't know about actual C compilers, but if you want strict parse phase separation then a technique I've seen (and used) is to just parse into a form that technically isn't a "fully parsed AST" as some nodes just indicate the source structure, and let a later phase disambiguate what it means. Here you could parse a paren_expr for example, and then later a phase with more information decides cast or group. I've used it for programmable precedence/associativity; the parser just recognises a linear chain of terms and operators, turning that into a proper expression happens later. $\endgroup$
    – Ben
    Mar 26 at 2:14
  • 3
    $\begingroup$ I would not say easily. Distinguishing requires a symbol table which requires fully resolving all headers, including them, and parsing them. This is a general cause of issues with IDEs for C code, where the failure to fully understand the build-system (especially for new, unorthodox, build-systems) leads the IDE to fail to locate the header files, and from there to fail to correctly parse the code, resulting in either wrong or absent syntax highlighting. Not easy, no. $\endgroup$ Mar 27 at 8:14
  • $\begingroup$ I suppose casting would be trouble if you tried to implement a language where types and variables were in a different namespace. $\endgroup$
    – CPlus
    Mar 28 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.