BNFC解析CPP时的"typedef-name: identifier"（词法分析器hack）问题求解

Ah, the classic typedef problem—one of C++'s most infamous context-dependent parsing gotchas, right? I've wrestled with this too when using BNFC for C-like languages, so I'll walk you through the practical approaches to tackle it in BNFC.

The Core Issue #

BNFC generates a traditional separate lexer-parser setup (usually Flex for lexing, Happy for parsing). The problem here is that the lexer runs before the parser, so it can't know which identifiers are typedef'd types until the parser processes those declarations. This means the lexer can't distinguish between a type name and a regular identifier upfront.

Solution 1: Use GLR Parsing + Semantic Symbol Table Checks #

This is the most straightforward approach with BNFC, since it leans into BNFC's ability to generate GLR parsers that handle ambiguous grammars, then resolves the ambiguity later in semantic analysis.

Here's how to implement it:

1. Adjust Your BNFC Grammar

   • First, define your built-in types as tokens, and keep identifiers as a generic token:

     token Int "int" ;
     token Float "float" ;
     token Char "char" ;
     token Ident (letter (letter | digit)*) ;
     

   • Create a Type non-terminal that includes both built-in types and identifiers:

     Type. Type ::= Int ;
     Type. Type ::= Float ;
     Type. Type ::= Char ;
     Type. Type ::= Ident ;
     

   • Add the typedef declaration rule:

     Decl. Decl ::= "typedef" Type Ident ";" ;
     

   • Define your variable declaration rule to use the Type non-terminal:

     VarDecl. Decl ::= Type Ident ";" ;
     

2. Generate a GLR Parser
   BNFC's default LALR(1) parser will hit shift/reduce conflicts with this grammar (since x y; could be a variable declaration or an expression). To fix this, generate a GLR parser instead using the --glr flag:

   bnfc --haskell --glr YourCPPGrammar.cf
   

   GLR parsers can handle ambiguous grammars and generate all possible parse trees.

3. Resolve Ambiguity with a Symbol Table
   In your semantic analysis phase, maintain a scoped symbol table (a stack of hash maps works well) to track which identifiers are typedef'd types:

   • When you process a typedef declaration, add the identifier to the current scope's symbol table with a "type" marker.
   • When evaluating parse trees, filter out any trees where a Type uses an identifier not marked as a type in the symbol table.
   • Don't forget to handle scope nesting (push a new scope when entering a block, pop it when exiting).

Solution 2: Hack the Lexer with State (Advanced) #

If you prefer to handle this in the lexer (like the traditional C++ lexer hack), you can modify the Flex code generated by BNFC to use state transitions. However, this requires tight coordination between the parser and lexer, which BNFC doesn't support out of the box:

• Add Lexer States: Edit the generated .l file to add a TYPEDEF state. When the parser encounters the typedef keyword, it tells the lexer to switch to this state.
• Mark Typedef Names: In the TYPEDEF state, the next identifier is marked as a type token (e.g., TYPE_IDENT instead of Ident).
• Manage Scope: You'll need to track scope to switch back to the default state when exiting a block where the typedef was declared.

This approach is more complex because BNFC doesn't natively support parser-lexer communication, so you'll have to manually modify the generated parser code to trigger lexer state changes. I only recommend this if you absolutely need to resolve the ambiguity in the lexer.

Key Takeaways #

• The GLR + symbol table approach is the most maintainable and BNFC-friendly solution.
• Avoid trying to fix this purely in the lexer unless you're prepared to manually tweak BNFC's generated code.
• Make sure your semantic analysis handles scoping correctly—typedefs are block-scoped in C++, so your symbol table needs to reflect that.

内容的提问来源于stack exchange，提问作者Conor Quinn