假令牌并不能完全解决问题。当您有一些想要解析的语言的子规则时,您可能还需要重复调用该规则(多次调用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_char
and中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 适应这个令牌。