如何区分公共前缀规则，实现支持长look ahead的整数分数parser

问题根源 #

你遇到的问题由两个原因导致：

1. 默认的Bison LALR(1)解析器仅支持1个前看符号，无法处理当前场景下需要判断后续是否存在/才能决定归约分支的需求，导致IntegerTokenStar贪心匹配所有数字和间隔符，分子部分无可用字符。
2. 你贴出的Bison代码中Fraction规则存在两处笔误：缺失了分子与SLASH之间的GapStar匹配，且分母仅匹配单个IntegerToken，无法匹配多字符的分母。

修改方案 #

仅需极小改动即可保留原规则的清晰性，同时实现需求：

1. 开启Bison的GLR解析器支持，可处理长前看、歧义语法场景，自动并行尝试所有合法解析路径，匹配到SLASH后会自动筛选出正确的解析路径。
2. 修正Fraction规则的两处笔误。
3. 可按需添加语义动作拼接对应字段值，实现示例中的输出效果。

完整修改后代码 #

frac.y #

%define parse.error verbose
%locations
%glr-parser
%{
void yyerror(const char* s);
extern int yylex();
extern int yylineno;
extern int yycolumn;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define YYSTYPE char*
%}


%token DIGIT SLASH GAP NEWLINE

%start File

%%
File: Value | Value NEWLINE File
Value: Integer | Fraction;

Fraction: IntegerTokenStar DigitPlus GapStar SLASH IntegerTokenPlus {
    printf("fraction {i:\"%s\",n:\"%s\",d:\"%s\"}\n", $1?$1:"", $2?$2:"", $5?$5:"");
    free($1); free($2); free($5);
}
DigitPlus: DIGIT {
    $$ = malloc(2);
    strcpy($$, yytext);
}
| DIGIT DigitPlus {
    $$ = malloc(strlen(yytext) + strlen($2) + 1);
    strcpy($$, yytext);
    strcat($$, $2);
    free($2);
}
GapStar: GAP GapStar | %empty
Integer: IntegerTokenPlus {
    printf("integer {i:\"%s\",n:\"\",d:\"\"}\n", $1?$1:"");
    free($1);
}
IntegerToken: DIGIT | GAP {
    $$ = malloc(2);
    strcpy($$, yytext);
}
IntegerTokenStar: %empty { $$ = strdup(""); }
| IntegerToken IntegerTokenStar {
    $$ = malloc(strlen($1) + strlen($2) + 1);
    strcpy($$, $1);
    strcat($$, $2);
    free($1); free($2);
}
IntegerTokenPlus: IntegerToken IntegerTokenPlus {
    $$ = malloc(strlen($1) + strlen($2) + 1);
    strcpy($$, $1);
    strcat($$, $2);
    free($1); free($2);
}
| IntegerToken { $$ = $1; }

%%


int main(){
    yyparse();
    return 0;
}

void yyerror(const char* s) {
    fprintf(stderr, "Line %d: %s\n", yylineno, s);
    exit(1);
}

frac.l #

无需修改，原有规则可直接使用。

Makefile #

无需修改，原有编译规则可直接使用。

验证效果 #

修改后可正确解析你给出的所有示例：

• 输入1_1_ 1___/1_1，输出fraction {i:"1_1_ ",n:"1___",d:"1_1"}
• 输入1_1_ 1___1_1，输出integer {i:"1_1_ 1___1_1",n:"",d:""}
• 输入1_1_1___/1_1，输出fraction {i:"",n:"1_1_1___",d:"1_1"}

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