使用Bison与Flex解析机票文本文件时的语法错误及移进/归约冲突问题求助

算力阿峰

2026-4-22

Bison与Flex解析机票文本文件时的语法错误及移进/归约冲突问题求助

嘿，我仔细看了你用Bison和Flex解析机票文件遇到的问题，咱们一步步拆解排查，帮你解决这些麻烦：

一、最初的语法错误根源：Flex规则匹配顺序问题

你最初遇到的语法错误，很大概率是Flex的规则匹配逻辑导致的。看你最初的billet.l规则：

"DOSSIER"               { return DOSSIER; }
{ALPHA}{6}              { return CODE_DOSSIER; }
{ALPHA}{3}"/"           { yylval.sval = strdup(yytext); return CODE_AEROPORT; }
{ALPHA}{4}+("/"{ALPHA}+)?("-"{ALPHA}+)?  { yylval.sval = strdup(yytext); return NOM_PRENOM; }

Flex的匹配规则是优先匹配最长文本，相同长度时选先定义的规则。这里{ALPHA}{6}排在名字规则前面，当解析乘客名字ANTOINE/DESAINT-EXUPERY时，开头的ANTOINE是6个字母，会被优先识别成CODE_DOSSIER，而不是名字的一部分。这直接导致Bison语法里infos_passager期望的nom_prenom '/' nom_prenom规则不满足，触发语法错误。

二、后续出现的移进/归约冲突

你修改后把名字规则改成STRING，并在Bison里定义nom_prenom: STRING | STRING '/' STRING;，这就出现了移进/归约冲突：当Bison解析到STRING后面跟着/时，它不知道应该把当前的STRING直接归约成nom_prenom，还是移进/等待后面的STRING，组成STRING '/' STRING的完整名字格式。

三、具体修复方案

1. 调整Flex规则的匹配顺序与细节

把CODE_DOSSIER的规则移到名字规则后面，确保名字这类长文本被优先匹配；同时删掉无用的{ALPHA}{3}"/"规则（你的示例里没有这种格式），还要给需要传递字符串的token赋值yylval.sval：

%{
#include "billet.tab.h"
void yyerror(const char *s);
%}

DIGIT [0-9]
ALPHA [A-Za-z]
SEP [ \t]

%%
"DOSSIER"               { return DOSSIER; }
{ALPHA}{4}+("/"{ALPHA}+)?("-"{ALPHA}+)?  { yylval.sval = strdup(yytext); return STRING; }
{ALPHA}{6}              { return CODE_DOSSIER; }
{DIGIT}{2}"/"{DIGIT}{2}"/"{DIGIT}{2} { yylval.sval = strdup(yytext); return DATE; }
{ALPHA}{2}{DIGIT}{2,4}  { yylval.sval = strdup(yytext); return NUM_VOL; }
{ALPHA}{3}              { yylval.sval = strdup(yytext); return CODE_AEROPORT; }
{DIGIT}{2}":"{DIGIT}{2} { yylval.sval = strdup(yytext); return HEURE_OR_DUREE_VOL; }
"+"                     { return PLUS; }
{SEP}+                  { }
\n                      { return NEWLINE; }
.                       { fprintf(stderr, "Caractère non autorisé: '%s'\n", yytext); exit(1); }
%%

2. 改写Bison规则解决移进/归约冲突

把名字相关的规则改写，避免歧义，直接定义完整的乘客信息格式：

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void yyerror(const char *s);
int yylex();
%}

%union {
    char *sval;
}

%token DOSSIER CODE_DOSSIER NEWLINE PLUS
%token <sval> DATE NUM_VOL CODE_AEROPORT HEURE_OR_DUREE_VOL STRING

%%

billet: DOSSIER CODE_DOSSIER NEWLINE infos_passager NEWLINE vols;

// 直接处理两种乘客名字格式，避免歧义
infos_passager: nom_complet NEWLINE { 
    printf("Infos passager : %s\n", $1); 
    free($1); // 释放内存
};
nom_complet: STRING '/' STRING { 
    asprintf(&$$, "%s/%s", $1, $3); 
    free($1); free($3); // 释放原字符串
} | STRING { $$ = strdup($1); };

vols: vol NEWLINE vols | vol NEWLINE;

vol: DATE NUM_VOL CODE_AEROPORT HEURE_OR_DUREE_VOL CODE_AEROPORT heure_arrivee HEURE_OR_DUREE_VOL { 
    printf("Vol : %s %s %s %s %s %s %s\n", $1, $2, $3, $4, $5, $6, $7);
    // 按需释放内存
    free($1); free($2); free($3); free($4); free($5); free($6); free($7);
};

heure_arrivee: heure_avec_plus | HEURE_OR_DUREE_VOL;
heure_avec_plus: PLUS HEURE_OR_DUREE_VOL { $$ = $2; };

%%

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

void yyerror(const char *s) {
    fprintf(stderr, "Erreur de syntaxe : %s\n", s);
}

这样改写后，Bison能明确识别乘客名字的两种格式，不会再出现移进/归约冲突。

3. 额外调试技巧

编译Bison时加上-Wcounterexamples参数，可以查看冲突的具体场景，帮助排查；
运行程序时设置yydebug=1（比如yydebug=1 ./your_program < ExampleAirplaneTicket.txt），能看到详细的解析过程，精准定位哪个token触发了语法错误。

按照这些修改后，你应该能成功解析示例机票文件了。

备注：内容来源于stack exchange，提问作者Portyio