请求排查简易Java解析器Bison/Yacc文法的Shift/Reduce冲突

Hey there! Let's break down why your Bison grammar is hitting a shift/reduce conflict and work through a solution step by step.

First, let's recap your original grammar snippet for clarity:

Programme : Class{ printf("Programme OK!\n");} ;
Class : ClassPrototype O_ACCOL VariableDeclaration Main C_ACCOL
ClassPrototype : ACCESS CLASS ID ClassInheritance | CLASS ID ClassInheritance ;
ClassInheritance : EXTENDS ID | ;
VariableDeclaration : TYPE ID VariableDeclarations | ACCESS TYPE ID VariableDeclarations | ;
VariableDeclarations : COMA ID VariableDeclarations | S_COLON VariableDeclaration ;
Main : MainPrototype O...

What's Causing the Shift/Reduce Conflict? #

The core issue lies in your VariableDeclaration and VariableDeclarations rules, combined with the empty production for VariableDeclaration:

1. When the parser encounters a S_COLON (semicolon), it has two conflicting options:
   • Shift: Wait for a subsequent VariableDeclaration (since VariableDeclarations allows S_COLON VariableDeclaration)
   • Reduce: Treat the semicolon as the end of the current variable declaration sequence, especially since VariableDeclaration can be empty.
2. The ambiguity gets worse because Class expects a VariableDeclaration followed by Main—the parser can't tell if an empty VariableDeclaration means it should jump straight to Main or keep waiting for more variable declarations.

How to Fix It #

We'll refactor the variable declaration rules to eliminate ambiguity by making each declaration a self-contained, explicit unit. Here's the revised grammar:

%{
#include <stdio.h>
%}

// Define all required tokens first (adjust based on your lexer)
%token ACCESS CLASS ID EXTENDS TYPE COMA S_COLON O_ACCOL C_ACCOL MAIN

%%

Programme : Class { printf("Programme OK!\n"); } ;

Class : ClassPrototype O_ACCOL VariableDeclarationList Main C_ACCOL ;

ClassPrototype : ACCESS CLASS ID ClassInheritance | CLASS ID ClassInheritance ;

ClassInheritance : EXTENDS ID | /* empty */ ;

// List of zero or more variable declarations
VariableDeclarationList : /* empty */ 
                        | VariableDeclaration VariableDeclarationList 
                        ;

// Single, complete variable declaration: optional access modifier + type + 1+ IDs + semicolon
VariableDeclaration : (ACCESS)? TYPE ID (COMA ID)* S_COLON ;

// Explicit Main rule (fill in the body as needed)
Main : MAIN O_ACCOL /* Main method body rules here */ C_ACCOL ;

%%

// Example error handler
void yyerror(const char* msg) {
    fprintf(stderr, "Error: %s\n", msg);
}

Key Changes Explained #

1. Simplified Variable Declarations: Instead of nested recursive rules, we define a single VariableDeclaration that represents a complete declaration:
   • Optional access modifier (ACCESS), followed by a type, one or more IDs (comma-separated), and a mandatory semicolon.
   • This removes ambiguity because every declaration ends with a semicolon, so the parser knows exactly when to reduce.
2. Variable Declaration List: We use a separate VariableDeclarationList to handle zero or more declarations, which is a standard, non-ambiguous way to represent sequences in Bison.
3. Explicit Main Rule: Ensuring Main starts with a distinct MAIN token means the parser can't confuse it with variable declaration syntax—once it sees MAIN, it knows to shift into the main method parsing.

This refactoring eliminates the shift/reduce conflict by removing ambiguous recursive paths and making each syntax unit explicit.

内容的提问来源于stack exchange，提问作者Romain B