区分具有共同前缀的规则

Question

我遇到了一个长期展望的规则问题

以使用整数或分数的解析器为例，分数在分子中也没有 GAPs（但是在分子和 [=17 之间可能有 GAPs =])

正则表达式[0-9_ ]*?([0-9]+\/[0-9_ ]+)|[0-9_ ]+描述了有效的输入你可以查看一些示例 here.

这是一种写法

Value: Integer | Fraction;
Fraction: IntegerTokenStar DigitPlus GapStar SLASH IntegerToken
DigitPlus: DIGIT DigitPlus | DIGIT
GapStar: GAP GapStar | %empty
Integer: IntegerTokenPlus
IntegerToken: DIGIT | GAP
IntegerTokenStar: IntegerToken IntegerTokenStar | %empty
IntegerTokenPlus: IntegerToken IntegerTokenPlus | IntegerToken

但它甚至无法解析像 0 0/0 这样的示例，IntegerTokenStar 将尽可能多地消耗，然后尝试解析分子没有可用数字，尝试继续使用整数也不是可能是因为它有一个“/”。

如何以概念清晰的方式编写此代码，以及我们可以生成有效的解析器。

例子

一些字符串和预期的 (i)nteger 部分，(n)umerator，(d)enominator。

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"}

frac.y

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


%token DIGIT SLASH GAP NEWLINE

%start File

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

Fraction: IntegerTokenStar DigitPlus SLASH IntegerToken
DigitPlus: DIGIT DigitPlus | DIGIT
Integer: IntegerTokenPlus
IntegerToken: DIGIT | GAP
IntegerTokenStar: IntegerToken IntegerTokenStar | %empty
IntegerTokenPlus: IntegerToken IntegerTokenPlus | IntegerToken

%%


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

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

frac.l

%option noyywrap yylineno

%{
#include <stdio.h>
#include "frac.tab.h"
#define YY_DECL int yylex()

int yycolumn = 1;

#define YY_USER_ACTION yylloc.first_line = yylloc.last_line = yylineno; \
    yylloc.first_column = yycolumn; yylloc.last_column = yycolumn + yyleng - 1; \
    yycolumn = yytext[0] == '\n' ? 1: yycolumn + yyleng;

%}


%%
[\n] {return NEWLINE;}
[_ ] {return GAP;}
[0-9] {return DIGIT;}
"/" {return SLASH;}

%%

生成文件

frac: frac.yy.c frac.tab.c
    gcc frac.tab.c frac.yy.c -o frac
frac.yy.c: frac.l
    flex -o frac.yy.c frac.l
frac.tab.c frac.tab.h: frac.y
    bison -d frac.y

Answer 1

基本问题是你把有间隙的数字序列和没有间隙的数字序列分成两个独立的规则，这意味着你需要决定你要先匹配哪个，这需要（可能是无限的）前瞻决定匹配哪个。

解决方案通常是“自下而上”匹配标记——独立于上下文的每个事物的单一规则，并从中构建依赖于前瞻的事物。在你的情况下，这意味着从 DigitStar 而不是直接从 DIGIT 构建 IntegerToken - 数字输入将被识别为 DigitStar 并且只有当你到达它的结尾（并看到非数字）你需要决定它是什么吗？

问题是对语法的明显修复（将 IntegerToken: DIGIT | GAP 更改为 DigitStar | GAP）不起作用，因为它使 IntegerTokenStar（和 -Plus）不明确的，因为任何 2 位或更多位数字的序列可能是任意数量的 DigitStar 标记。所以你需要重写它以确保你不能有两个连续的 DigitStar 标记，结果证明这是非常棘手的。你真的需要重新考虑“自下而上”的事情——输入是一系列交替数字（每个 1+ 位）和间隔（1+ 空格），可选的单个 / 可以直接出现在两个数字之间（无间隙）或一个数字和一个间隙（/ 之前没有间隙）。所以你得到的规则看起来更像：

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

Fraction: OptGap Integer GapPlus DigitPlus SLASH OptGap Integer OptGap
        | OptGap DigitPlus SLASH OptGap Integer OptGap
DigitPlus: DIGIT DigitPlus | DIGIT
GapPlus: GAP GapPlus | GAP
OptGap: %empty | GapPlus
Integer: Integer GapPlus DigitPlus | DigitPlus

这可以解决问题，但不必要地复杂，因为它在语法而不是词法分析器中识别 'number' 和 'gap'¹ 标记。还有一个奇怪的角落情况，不允许分数中的分子和 / 之间存在间隙——否则我们可以忽略词法分析器中的空格（间隙）并使事情变得更简单：

File: Value | Value NEWLINE File
Value: Integer | Fraction ;
Fraction: Integer NUMBER SLASH Integer | NUMBER SLASH Integer
Integer: Integer NUMBER | NUMBER

¹_{旁注——您的词法分析器似乎不同意您的示例，因为它将 _ 视为 GAP 令牌而不是 DIGIT 令牌.
但是你的例子与你的正则表达式不匹配——在 / 之前有一个 _ 将不匹配}

区分具有共同前缀的规则

Distinguish rules with common prefix

parsing

bison

例子

frac.y

frac.l

生成文件