0

我是野牛的新手，不幸的是需要为一种语言编写解析器，该语言可能具有变量名中的运算符。例如，根据上下文，表达式

FOO = BAR-BAZ

可以解释为：

  1. "FOO"分配给变量的值减去变量的"BAR"值"BAZ"，或
  2. "FOO"被赋予变量值的变量"BAR-BAZ"

幸运的是，该语言需要提前声明变量，因此我可以通过我实现的函数确定给定字符串是否为有效变量：

bool isVariable(char* name);

如果给定的字符串是有效的变量名，则返回 true，否则返回 false。

我如何告诉野牛首先尝试上面的第二种情况，并且只有当（通过使用isVariable()）该路径失败时，才返回并按照上面的第一种情况进行尝试？我读过你可以让野牛尝试多个解析路径并在遇到 a 时剔除无效的路径YYERROR，所以我尝试了一组类似于以下的规则：

variable:
    STRING { if(!isVariable($1)) YYERROR; }
    ;

expression:
    expression '-' expression
  | variable
  ;

但是当给定"BAR-BAZ"解析器时，它会尝试将其作为单个变量，并且当它遇到时完全停止，YYERROR而不是像我期望的那样探索"BAR" - "BAZ"路径。我究竟做错了什么？

编辑：我开始认为我的弹性规则STRING可能是罪魁祸首：

((A-Z0-9][-A-Z0-9_///.]+)|([A-Z]))  {yylval.sval = strdup(yytext); return STRING;}

在这种情况下，如果 '-' 出现在字母数字字符的中间，则整个批次被视为 1 STRING，解析器不可能进行细分（因此只探索了一条路径）。我想我可以STRING在解析器操作中手动解析，但似乎应该有更好的方法。也许 flex 可以返回备用令牌流（一个用于"BAR-BAZ"案例，另一个用于"BAR"-"BAZ"案例），这些令牌流被转移到不同的解析器堆栈进行探索？这样的事情可能吗？

4

1 回答 1

1

在野牛生成的解析器中解决这个问题并非不可能，但这并不容易，而且所需的黑客量可能会降低语法的可读性和可验证性。

需要明确的是，GLR 解析器不是回退解析器。GLR 算法并行探索所有可能的解析，并拒绝无效的解析。（bison 实现要求解析收敛到一个可能的解析；原始 GLR 算法产生解析树的森林。）此外，GLR 算法不考虑多个词法分析。

如果你想在解析器的上下文中解决这个问题，你可能需要引入对空白的特殊处理，或者至少对于-没有被空白包围的空白。否则，您将无法区分a - b（可能总是减法）和a-b（如果定义了该变量，则可能是该变量a-b）。撇开这个问题不谈，你会寻找这样的东西（但这不起作用，如下所述）：

expr  : term
      | expr '-' term
term  : factor
      | term '*' factor
factor: var
      | '(' expr ')'

var   : ident     { if (!isVariable($1)) { /* reject this production */ } }

ident : WORD
      | ident '-' WORD  { $$ = concatenate($1, "-", $3); }

这是行不通的，因为与关联的操作var : ident在解析消除歧义之后才会执行。因此，如果产生式被拒绝，则解析失败，因为解析器已经确定产生式是必要的。（在解析器做出决定之前，操作被推迟。）

Bison 允许 GLR 语法使用语义谓词，这些谓词立即执行而不是延迟执行。但这无济于事，因为语义谓词不能使用计算的语义值（因为在评估语义谓词时，语义值的计算仍然被推迟）。您可能认为可以通过将连接标识符的计算（在第二个ident产生式中）作为语义谓词来解决此问题，但随后会遇到另一个限制：语义谓词本身没有语义值。

可能有一个 hack 可以解决这个问题，但这可能会给你带来不同的问题。假设a、c和是已定义的变量a-b。b-c那么，到底是什么意思a-b-c呢？是错误(a-b) - c还是a - (b-c)错误？

如果您认为它是一个错误，那么没有问题，因为 GLR 解析器会发现可能的解析，如果解析不明确，则野牛生成的 GLR 解析器会发出语法错误信号。但是问题就变成了：a-b-c只有模棱两可的错误才算错误？或者它是一个错误，因为如果它的参数是连字符变量，你不能使用没有环绕空格的减法运算符？（因此，无论是否存在，a-b-c都只能解决为(a - b) - c或？）要强制执行后一个要求，您将需要更多的复杂性。(a-b-c)a-bb-c

另一方面，如果您的语言期望为“后备”方法建模，那么结果应该是(a-b) - c. 但是进行选择并不是两个expr归约之间的简单合并过程，因为可能存在更高优先级的*运算符：d * a-b-c要么解析为(d * a-b) - c要么(d * a) - b-c；在这两种情况下，解析树完全不同。

另一种解决方案是将连字符变量的消歧放入扫描器中，而不是解析器中。这导致了一个更简单和更清晰的定义，但它导致了一个不同的问题：当你不希望语义消歧发生时，你如何告诉扫描仪？例如，当变量名出现在声明中时，您不希望扫描程序坚持将变量名分成段。

尽管与扫描仪的语义关联有点难看，但在这种情况下我会采用这种方法。解决方案的大致轮廓如下：

首先，语法。在这里，我添加了一个简单的声明语法，它可能与您的语法有任何相似之处，也可能不相似。请参阅下面的注释。

expr  : term
      | expr '-' term
term  : factor
      | term '*' factor
factor: VARIABLE
      | '(' expr ')'

decl  : { splitVariables(false); } "set" VARIABLE 
        { splitVariables(true);  } '=' expr ';'
        { addVariable($2); /* ... */ }

（有关 的语义，请参见下文splitVariables。）

现在，词法分析器。同样，重要的是要知道预期的结果a-b-c是什么；我将概述两种可能的策略。一是fallback策略，可以在flex中实现：

 int candidate_len = 0;
[[:alpha:]][[:alnum:]]*/"-"[[:alpha:]] { yymore();
                                         candidate_len = yyleng;
                                         BEGIN(HYPHENATED);
                                       }
[[:alpha:]][[:alnum:]]*                { yylval.id = strdup(yytext);
                                         return WORD;
                                       }
<HYPHENATED>"-"[[:alpha:]][[:alnum:]]*/"-"[[:alpha:]] {
                                         yymore();
                                         if (isVariable(yytext))
                                           candidate_len = yyleng;
                                       }
<HYPHENATED>"-"[[:alpha:]][[:alnum:]]* { if (!isVariable(yytext))
                                           yyless(candidate_len);
                                         yylval.id = strdup(yytext);
                                         BEGIN(INITIAL);
                                         return WORD;
                                       }

它使用yymoreandyyless来查找最长的连字符前缀序列，这是一个有效的变量。（如果没有这样的前缀，它会选择第一个单词。如果没有这样的前缀，另一种方法是选择整个序列。）

一个类似的替代方案，它只允许完整的连字符序列（在这是一个有效变量的情况下）或单个单词。同样，我们使用 yyless 和 yymore，但这次我们不费心检查中间前缀，我们使用第二个开始条件来处理我们知道我们不会组合单词的情况：

 int candidate_len = 0;
[[:alpha:]][[:alnum:]]*/"-"[[:alpha:]] { yymore();
                                         candidate_len = yyleng;
                                         BEGIN(HYPHENATED);
                                       }
[[:alpha:]][[:alnum:]]*                { yylval.id = strdup(yytext);
                                         return WORD;
                                       }
<HYPHENATED>("-"[[:alpha:]][[:alnum:]]*)*[[:alpha:]][[:alnum:]]* {
                                         if (isVariable(yytext)) {
                                           yylval.id = strdup(yytext);
                                           BEGIN(INITIAL);
                                           return WORD;
                                         } else {
                                           yyless(candidate_len);
                                           yylval.id = strdup(yytext);
                                           BEGIN(NO_COMBINE);
                                           return WORD;
                                         }
                                       }
<NO_COMBINE>[[:alpha:]][[:alnum:]]*    { yylval.id = strdup(yytext);
                                         return WORD;
                                       }
<NO_COMBINE>"-"                        { return '-'; }
<NO_COMBINE>.|\n                       { yyless(0); /* rescan */
                                         BEGIN(INITIAL);
                                       }

上述两种解决方案都isVariable用于确定连字符序列是否为有效变量。如前所述，必须有一种方法可以关闭检查，例如在声明的情况下。为此，我们需要实现splitVariables(bool). 实现很简单；它只需要设置一个可见的标志isVariable。如果该标志设置为 true，则isVariable始终返回 true，而不实际检查符号表中是否存在变量。

所有这些都假设符号表和 splitVariables 标志在解析器和扫描器之间共享。一个天真的解决方案会使这两个变量都成为全局变量；更简洁的解决方案是使用纯解析器和词法分析器，并将符号表结构（包括标志）从主程序传递到解析器，然后从那里（使用%lex-param）传递到词法分析器。

于 2015-05-12T16:37:59.577 回答