使bison开始使用与start规则不同的规则进行解析

Question

目前我正在开发一个源代码到源代码的编译器，我已经编写了一个bison解析器，可以正确地为输入创建AST。我现在需要对语法树进行几个转换，因此我需要在树中插入许多节点。

我可以手动创建我想添加到语法树中的所有结构/联合，但这似乎是非常繁重的工作。

对我来说，创建一个字符串会容易得多，我希望这个字符串能被我已有的解析器解析。然后，解析器应该返回这个字符串的树，我可以将其插入到我的原始语法树中。

不幸的是，字符串不能用我的解析器的start规则解析，因为它必须由子规则解析（例如，我的解析器解析包含语句的函数列表，字符串是单个语句）。

如何让bison解析字符串，从一个不同于开始规则的规则开始？

提前谢谢！

Answer 1

假代币并不能完全解决问题。当你想要解析某个语言的子规则时，你可能还需要重复调用该规则（多次调用yyparse）。

这就要求你用伪令牌“初始化”解析器，这会使它在每次调用时返回到有趣的规则，并保持实际非伪令牌流的正确状态。另外，您需要一种方法来检测yyparse调用是否遇到了EOF。

此外，理想情况下，您希望能够将调用与流上的yyparse和其他操作混合在一起，这意味着对Flex-Yacc组合执行的先行操作有精确的控制。

我在TXR语言的解析器中解决了所有这些问题。在这种语言中，有一些有趣的子语言：Lisp语法和regex语法。

问题是提供一个Lisp读取函数，它从流中提取单个对象，并使流处于合理的状态（关于前瞻）。例如，假设流包含以下内容：

 (a b c d) (e f g h)

我们使用到达Lisp子语法所需的伪标记初始化解析器。然后调用yyparse。当yyparse完成时，它将消耗到这里的所有内容：

 (a b c d) (e f g h)
            ^ stream pointer is here
           ^ the lookahead token is the parenthesis

在这个调用之后，如果有人调用函数从流中获取字符，他们将获得e，而不是（括号，很遗憾）。

总之，我们调用了yyparse，得到了（abcd）Lisp对象，流指针位于e，而先行标记是（）。

下一次调用yyparse，它将忽略这个先行标记，我们将得到一个错误消息。我们不仅必须使用伪伪标记来初始化解析器，使其解析Lisp表达式，还必须让它在（先行标记）处开始解析。

这样做的方法是将此令牌插入启动流。

在TXR解析器中，我实现了一个token stream对象，它最多可以占用四个pushback令牌。当调用yylex时，将从该回推中提取令牌，并且只有当其为空时才执行真正的lexing。

这在prime_解析器函数中使用：

void prime_parser(parser_t *p, val name, enum prime_parser prim)
{
  struct yy_token sec_tok = { 0 };

  switch (prim) {
  case prime_lisp:
    sec_tok.yy_char = SECRET_ESCAPE_E;
    break;
  case prime_interactive:
    sec_tok.yy_char = SECRET_ESCAPE_I;
    break;
  case prime_regex:
    sec_tok.yy_char = SECRET_ESCAPE_R;
    break;
  }

  if (p->recent_tok.yy_char)
    pushback_token(p, &p->recent_tok);
  pushback_token(p, &sec_tok);
  prime_scanner(p->scanner, prim);
  set(mkloc(p->name, p->parser), name);
}

解析器的recent_-tok成员跟踪最近看到的令牌，这使我们能够从最近的解析中访问前瞻令牌。

为了控制yylex，我在解析器中实现了这个黑客程序。l：

/* Near top of file */

#define YY_DECL \
  static int yylex_impl(YYSTYPE *yylval_param, yyscan_t yyscanner)

/* Later */

int yylex(YYSTYPE *yylval_param, yyscan_t yyscanner)
{
  struct yyguts_t * yyg = convert(struct yyguts_t *, yyscanner);
  int yy_char;

  if (yyextra->tok_idx > 0) {
    struct yy_token *tok = &yyextra->tok_pushback[--yyextra->tok_idx];
    yyextra->recent_tok = *tok;
    *yylval_param = tok->yy_lval;
    return tok->yy_char;
  }

  yy_char = yyextra->recent_tok.yy_char = yylex_impl(yylval_param, yyscanner);
  yyextra->recent_tok.yy_lval = *yylval_param;

  return yy_char;

如果token pushback索引为非零，我们将弹出封装的token并将其返回给Yacc。否则我们称之为真正的lexeryylex_impl。

注意，当我们这样做的时候，我们还可以窥视lexer返回的内容，并将其保存在最近的_-tok中。yy_char和最近的_tok。yy_lval。

（如果yy_lval是一个堆分配的对象类型呢？幸好我们在这个项目中有垃圾收集功能！）

在匹配这些子语言的规则中，我必须使用yyapt。请注意，byacc_foolbusiness:这是让黑客与伯克利Yacc合作所需要的。（T.E.Dickey维护的版本，支持Bison可重入解析器方案。）

spec : clauses_opt              { parser->syntax_tree = $1; }
     | SECRET_ESCAPE_R regexpr  { parser->syntax_tree = $2; end_of_regex(scnr);
     | SECRET_ESCAPE_E n_expr   { parser->syntax_tree = $2; YYACCEPT; }
       byacc_fool               { internal_error("notreached"); }
     | SECRET_ESCAPE_I i_expr   { parser->syntax_tree = $2; YYACCEPT; }
       byacc_fool               { internal_error("notreached"); }
     | SECRET_ESCAPE_E          { if (yychar == YYEOF) {
                                    parser->syntax_tree = nao;
                                    YYACCEPT;
                                  } else {
                                    yybadtok(yychar, nil);
                                    parser->syntax_tree = nil;
                                  } }
     | SECRET_ESCAPE_I          { if (yychar == YYEOF) {
                                    parser->syntax_tree = nao;
                                    YYACCEPT;
                                  } else {
                                    yybadtok(yychar, nil);
                                    parser->syntax_tree = nil;
                                  } }
     | error '\n'               { parser->syntax_tree = nil;
                                  if (parser->errors >= 8)
                                    YYABORT;
                                  yyerrok;
                                  yybadtok(yychar, nil); }

     ;

    }

为什么要接受？我不记得了；好在我们有详细的变更记录信息：

* parser.y (spec): Use YYACCEPT in the SECRET_ESCAPE_E clause for
pulling a single expression out of the token stream. YYACCEPT
is a trick for not invoking the $accept : spec . $end production
which is implicitly built into the grammar, and which causes
a token of lookahead to occur.  This allows us to read a full
expression without stealing any further token: but only if the
grammar is structured right.

我认为这一评论略带误导性。隐式的$end生产导致了一个问题，这个问题不仅仅是不必要的前瞻性问题：它是前瞻性的，因为它实际上想要匹配EOF。我似乎记得，yyaccpt是一种退出解析器的方法，这样当下一个标记不是$end标记时，它就不会抛出语法错误，后者是EOF的内置表示。

不管怎样，Yacc最终还是展望未来；我们不希望它产生语法错误，因为前瞻并不像规则所预期的那样是文件的结尾。当我们有

 (a b c d) (e f g h)

我们有一个简单的语法规则来匹配一个表达式，（ef g h）东西看起来像是散乱的材料，这是一个语法错误！解析器获得第一个）标记后，它再次调用yylex，并得到（，这是一个语法错误；它希望yylex在该点指示EOF。yyaccpt是一种解决方法。我们让Yacc调用yylex，并取出第二个（，并记下它，以便我们可以在下一个yyparse调用中将其推回；但我们防止Yacc对该令牌产生不适。

Answer 2

考虑到你似乎愿意做的事情，你可能会从这篇论文中找到有趣的想法。

它提供了从C代码支持具体语法的方法，比如（这里，从Bison解析器本身进行去语法）：

exp: exp "&" exp
{
  // Sub−ASTs are used as−is (they are not printed, then parsed,
  // as in the previous example). Spaces are no longer critical.
  $$ = parse(Tweast() <<
             "if" << $1 << "then" << $3 << "<> 0 else 0");
};

Answer 3

有一个简单的黑客，这在野牛FAQ中有描述。。

基本上，对于您希望能够使用的每个非终端，您创建一个伪令牌，然后创建一个“元开始”非终端，选择您想要使用的终端：

%token START_PROGRAM
%token START_STATEMENT
%token START_EXPRESSION

%start meta_start

%%

meta_start: START_PROGRAM program
          | START_STATEMENT statement
          | START_EXPRESSION expression
          ;

（在每个产品的操作中，您可以将2美元的价值保存在调用者可以获得的地方。）

现在您只需要安排您的lexer来传递正确的开始标记。您可以通过使用纯解析器和纯lexer并通过共享数据结构传递消息来做到这一点。这将是最好的方法，但是为了这个答案的目的，我将展示如何使用全局变量来实现它，因为原理是相同的：

extern int start_token;

// If all your start non-terminals produce a value of the same type, possibly a union
// type, you could arrange to return it instead of the error report.

int yyparse(int start) {
  // I left out the code to cause the lexer to scan a given string.
  start_token = start;
  return real_yyparse();
}

int yylex() {
  int rv = start_token;
  if (start_token)
    start_token = 0;
  else
    rv = real_yylex();
  return rv;
}