代码之家 › 专栏 › 技术社区 › Algoman

bison:有效表达式的glr解析失败,没有错误消息

glr cobol bison parsing

Algoman · 技术社区 · 8 年前

我正在GNU Bison中研究一个GLR解析器,我有以下问题:

我试图解析的语言允许布尔表达式,包括关系(<、>、<=、…)和布尔组合(和、或、或、不)。现在的问题是,语言还允许在关系的右侧有多个算术表达式…它们是用和布尔合成相同的符号组成的!这是一个非常愚蠢的语言设计,但我不能改变它。

所以你可以 a > b and c 应该相当于 (a > b) and (a > c) 你也可以 a > b and c > d 应该相当于 (a > b) and (c > d)

在本例中,S/R冲突这一原因已经很明显:在阅读之后 a > b 向前看 and 你可以减少 A>B 到一个布尔表达式,然后等待另一个布尔表达式,或者您可以将 和 然后等待另一个算术表达式。

我的语法当前如下:

booleanexpression
    : relation
    | booleanexpression TOK_AND booleanexpression
    ...
;
relation
    : arithmeticexpression TOK_GT maxtree
    ...
;
maxtree
    : arithmeticexpression
    | maxtree TOK_AND maxtree
    ...
;

语言显然不是 LR(k) 对于任何 K ,因为使用任何常量都无法解决S/R冲突 K -向前看,因为中间的算术表达式可以有任意多个标记。因此,我打开了GLR解析。

但当我试图分析 A>B和C 通过这个,我可以在调试输出中看到解析器的行为如下:

它读到 a 展望未来 > 它减少了 一 对 arithmeticexpression
它读到 b 展望未来 和 它减少了 乙 对 算术表达式 然后已经到了 maxtree
它减少了 A>B 到A relation
它读到 c 并将其简化为 算术表达式

然后什么也没发生!这个 and c 显然被丢弃了-调试输出不显示这些令牌的任何操作。甚至没有错误信息。对应的if语句在我的ast中不存在(我仍然得到一个ast,因为我有错误恢复)。

我想,读完 乙 ,应该有两个堆栈。但是后来 乙 不应该减少。或者至少它应该给我一些错误信息(“语言不明确”是可以的,我以前见过这个信息——我不明白为什么它在这里不适用)。有人能理解吗?

从一段时间的语法来看,这里的主要问题是下一个算术表达式之后是否会出现

另一个关系标记(那么您应该减少)
另一个布尔组合(然后您应该移动)
布尔/算术表达式语法(如then)之外的一个标记,它将终止表达式,您还应该移动

你能想出一种不同的语法来更好地/更具确定性地捕捉情况吗?你将如何处理这个问题?我现在正在考虑让语法从右到左,比如

booleanexpression : relation AND booleanexpression
maxtree : arithmeticexpression AND maxtree
etc.

我认为这会使野牛更喜欢迁移,只会先减少右边的数量。也许通过使用不同的非终端,它将允许算术表达式后面有一个准“先行”…

旁注:gnucobol只需收集所有令牌,将它们推送到中间堆栈上,然后从中手动构建表达式,就可以处理这个问题。这让我泄气,但我坚持希望他们这样做,因为野牛在开始时不支持GLR解析…

编辑: 一个小的可重复的例子

%{
#include <stdio.h>
int yylex ();
void yyerror(const char* msg);
%}

%glr-parser
%left '&'
%left '>'

%%
input: %empty | input bool '\n' {printf("\n");};

arith : 'a' | 'b' | 'c';
maxtree : arith { printf("[maxtree : arith]  "); }
        | maxtree '&' maxtree { printf("[maxtree : maxtree & maxtree]  "); } ;
rel : arith '>' maxtree { printf("[rel : arith > maxtree]  "); } ;
bool : rel { printf("[bool : rel]  "); }
     | bool '&' bool { printf("[bool : bool & bool]  "); } ;
%%

void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex () {
    int c;
    while ((c = getchar ()) == ' ' || c == '\t');
    return c == EOF ? 0 : c;
}
int main (int argc, char** argv) {
    return yyparse();
}

奇怪的是,这一个会在输入时打印错误消息“语法错误” a>b&c .

3 回复 | 直到 8 年前

rici 8 年前

优先声明背后的思想是,它们使用简单的单标记先行和配置的优先权来解决含糊不清的问题(或者更准确地说,移位/减少冲突)。如果语法没有移位/减少冲突,则不会使用优先声明,但如果使用了它们,则会根据(静态)优先关系,使用它们来抑制移位或减少。

在您的语言中,不可能静态地解决移位/减少冲突的不确定性,正如您在问题中注意到的那样。您的语法不是lr(1),更不是运算符优先级,因此,glr解析是一个实用的解决方案。但是你必须允许GLR去做它的工作。过早地通过优先级比较消除其中一个可能的解析器将阻止GLR算法稍后考虑它。如果您设法消除唯一可能是正确的解析,那么这将特别严重。

rel & 相对

在您的完整语言中,布尔表达式和算术表达式都有类似于运算符优先级的内容,但只在各自的域内。运算符优先级分析器(与yacc/bison的优先级声明等效)通过消除不同非终端之间的差异来工作;它不能处理类似于语法的语法,其中某些运算符在不同域(或不同域之间)具有不同的优先级。

                              %left '+' '-'
                              %left '*' '/'
%%                            %%
expr  : term
      | expr '+' term         expr: expr '+' expr
      | expr '-' term             | expr '-' expr
term  : factor
      | term '*' factor           | expr '*' expr
      | term '/' factor           | expr '/' expr
factor: ID                        | ID
      | '(' expr ')'              | '(' expr ')'

%code top {
#define _GNU_SOURCE 1
}

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

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

%define api.value.type { char* }
%glr-parser
%token ID

%%
input   : %empty
        | input bool '\n'   { puts($2); }

arith   : ID
maxtree : arith 
        | maxtree '&' arith { asprintf(&$$, "[maxtree& %s %s]", $1, $3); }
rel     : arith '>' maxtree { asprintf(&$$, "[COMP %s %s]", $1, $3); }
bool    : rel
        | bool '&' rel      { asprintf(&$$, "[AND %s %s]", $1, $3); }
%%

void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex(void) {
    int c;
    while ((c = getchar ()) == ' ' || c == '\t');
    if (isalpha(c)) {
      *(yylval = strdup(" ")) = c;
      return ID;
    }
    else return c == EOF ? 0 : c;
}

int main (int argc, char** argv) {
#if YYDEBUG
    if (argc > 1 && strncmp(argv[1], "-d", 2) == 0) yydebug = 1;
#endif
    return yyparse();
}

$ bison -t -o glr_prec.c glr_prec.y
glr_prec.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
$ gcc -Wall -o glr_prec glr_prec.c
$ ./glr_prec
a>b
[COMP a b]
a>b & c
[COMP a [maxtree& b c]]
a>b & c>d
[AND [COMP a b] [COMP c d]]
a>b & c & c>d
[AND [COMP a [maxtree& b c]] [COMP c d]]
a>b & c>d & e
[AND [COMP a b] [COMP c [maxtree& d e]]]
$

a recent answer to a different question

user9835153 8 年前

这里还有其他问题。一种表达式,如 A > B AND C 直到你知道C是怎么宣布的。考虑以下程序:

   IDENTIFICATION DIVISION.
   PROGRAM-ID EXAMPLE.
   DATA DIVISION.
   WORKING-STORAGE SECTION.
   01     A     PIC 9 VALUE 2.
   01     B     PIC 9 VALUE 1.
   01     W     PIC 9 VALUE 3.
       88 C           VALUE 3.
   PROCEDURE DIVISION.
       IF A > B AND C
          DISPLAY 'A > B AND 88 LEVEL C is TRUE because W = ' W
       ELSE
          DISPLAY 'A not > B or 88 LEVEL C is not TRUE'
       END-IF
       DISPLAY 'A: ' A ' B: ' B ' W:' W  
       GOBACK
       .

A > B AND 88 LEVEL C is TRUE because W = 3
A: 2 B: 1 W: 3

A>B和C A > B AND W = 3 .有C 已经: A > B AND A > C

Algoman 8 年前

上面提到的代码工作得很好,但是我从来没有让它在我的实际项目中工作过,即使我看不到我的实际项目和这个代码之间的区别。

我有一个(公认的货物崇拜者) %skeleton "lalr1.cc"

%skeleton "glr.cc"