4

目前我正在研究源到源编译器,并且我已经编写了一个野牛解析器,可以正确地为输入创建 AST。我现在需要对语法树进行几次转换,因此我需要向树中插入许多节点。

我可以手动创建要添加到语法树中的所有结构/联合,但这似乎需要做很多工作。

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

不幸的是,字符串不能用我的解析器的开始规则解析,因为它必须由子规则解析(例如,我的解析器解析包含语句的函数列表,字符串是单个语句)。

我怎样才能让野牛解析一个字符串,从一个不同于开始规则的规则开始?

提前致谢!

4

3 回答 3

8

有一个简单的 hack,在bison 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调用者可以获取的某个位置的值。)

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

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;
}
于 2013-09-03T15:20:15.373 回答
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");
};
于 2013-09-03T15:27:23.610 回答
0

假令牌并不能完全解决问题。当您有一些想要解析的语言的子规则时,您可能还需要重复调​​用该规则(多次调用yyparse)。

这要求您使用假令牌“启动”解析器,使其在每次调用时返回有趣的规则保持实际非假令牌流的正确状态。另外,您需要一种方法来检测yyparse调用是否遇到 EOF。

同样,理想情况下,您希望能够yyparse在流上混合调用和其他操作,这意味着可以精确控制 Flex + Yacc 组合执行的前瞻。

我在 TXR 语言的解析器中解决了所有这些问题。在这种语言中,有一些有趣的子语言:Lisp 语法和正则表达式语法。

问题是提供一个 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了 ,得到了(a b c d)Lisp 对象,流指针在e,前瞻标记在(

下一次 call yyparse,它将忽略这个前瞻标记,我们将得到一个错误解析。我们不仅必须使用导致解析器解析 Lisp 表达式的伪伪标记来启动解析器,而且还必须让它开始解析(前瞻标记。

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

在 TXR 解析器中,我实现了一个令牌流对象,它最多可以接收四个推送令牌。当yylex被调用时,令牌从这个推回中被拉出,只有当它为空时才会执行真正的词法分析。

这在prime_parser函数中使用:

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,我实现了这个黑客parser.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;

如果令牌推回索引不为零,我们弹出罐头令牌并将其返回给 Yacc。否则我们调用yylex_impl, 真正的词法分析器。

请注意,当我们这样做时,我们还会查看词法分析器返回的内容并将其存储在recent_tok.yy_charand中recent_tok.yy_lval

(如果yy_lval是堆分配的对象类型怎么办?幸好我们在这个项目中有垃圾收集!)

在匹配这些子语言的规则中,我不得不使用YYACCEPT. 并注意byacc_fool业务:这是让黑客与 Berkeley Yacc 合作所必需的。(TE 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); }

     ;

    }

为什么YYACCEPT?我不记得了;好在我们有详细的 ChangeLog 消息:

* 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。我似乎记得这YYACCEPT是一种摆脱解析器的方法,这样当下一个令牌不是$end令牌时它不会抛出语法错误,这是 EOF 的内置表示。

无论如何,Yacc 最终还是向前看。我们不希望它做的是引发语法错误,因为前瞻不是文件结尾,正如规则所期望的那样。当我们有

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

我们有一个匹配表达式的简单语法规则,这些(e f g h)东西看起来像杂散的材料,那就是语法错误!解析器得到第一个)token后,yylex再次调用,得到(的是语法错误;它想yylex在那时指示EOF。 YYACCEPT是一种解决方法。我们让 Yacc 调用yylex并拉出第二个(,并记下它,以便我们可以在下一次yyparse调用时将其推回;但是我们阻止 Yacc 适应这个令牌。

于 2016-07-23T03:23:37.713 回答