如何一次 flex return 多个终端
How can flex return multiple terminals at one time
为了让我的问题更容易理解,我想用下面的例子:
下面的代码在fortran语言中叫做nonblock do-loop
DO 20 I=1, N ! line 1
DO 20 J=1, N ! line 2
! more codes
20 CONTINUE ! line 4
注意第 4 行的标签 20
表示 内部 do 循环和外部 do 循环的结束。
我希望我的 flex 程序正确解析该功能:当 flex 读取标签 20
时,它将 return ENDDO
终止两次。
首先,因为我也用bison,所以bison每次调用yylex()
都会得到一个terminal。如果我可以让 bison 在某些情况下从 yylex()
获取终端,而在其他情况下从另一个函数获取终端,也许我可以解决这个问题,但是,我当时对此一无所知。
当然有一些解决方法,例如,我可以使用 flex 的启动条件,但我认为这不是一个好的解决方案。所以我问有没有什么方法可以在没有解决方法的情况下解决我的问题?
感谢我的一个朋友,他提供了实现的方法
If I can ask bison to get terminals from yylex() in some cases, and from another function in other cases
在flex生成的flex.cpp代码中,有一个宏
/* Default declaration of generated scanner - a define so the user can
* easily add parameters.
*/
#ifndef YY_DECL
#define YY_DECL_IS_OURS 1
extern int yylex (void);
#define YY_DECL int yylex (void)
#endif /* !YY_DECL */
所以我可以 "rename" 将 flex 的 yylex()
函数转换为另一个函数,例如 pure_yylex()
.
所以我的问题解决了:
- push all terminals 我想给bison一个全局的
vector<int>
- 自己实现一个
yylex()
函数,当bison调用yylex()
时,这个函数会先尝试从那个全局的vector<int>
获取终端
- 如果
vector<int>
为空,yylex()
调用pure_yylex()
,flex开始工作
修改 (f)lex 生成的词法扫描器来实现令牌队列很容易,但这不一定是最佳解决方案。 (请参阅下文以获得更好的解决方案。)(另外,我真的不清楚对于您的特定问题,在词法分析器中制造额外的标记是否真的合适。)
一般方法是在 yylex
函数的顶部插入代码,您可以将代码紧跟在 %%
行之后和第一条规则之前。 (代码必须缩进,这样它就不会被解释为规则。)对于非重入扫描器,这通常涉及使用本地 static
变量来保存队列。举一个简单但愚蠢的例子,使用 C API 但用 C++ 编译以便访问 C++ 标准库:
%%
/* This code will be executed each time `yylex` is called, before
* any generated code. It may include declarations, even if compiled
* with C89.
*/
static std::deque<int> tokenq;
if (!tokenq.empty()) {
int token = tokenq.front();
tokenq.pop_front();
return token;
}
[[:digit:]]+ { /* match a number and return that many HELLO tokens */
int n = atoi(yytext);
for (int i = 0; i < n; ++i)
tokenq.push_back(HELLO);
}
以上代码没有尝试为排队的令牌提供语义值;您可以为令牌队列使用类似 std::queue<std::pair<int, YYSTYPE>>
的东西来实现这一点,但 YYSTYPE
通常是 union
的事实会导致一些复杂情况。此外,如果这是使用令牌队列的唯一原因,很明显可以用一个简单的计数器代替它,这样效率会高得多。例如,请参阅 ,它做的事情与您的问题有些相似(并注意该答案注释 1 中的建议)。
更好的选择:使用推送解析器
尽管令牌队列解决方案既吸引人又简单,但它很少是最佳解决方案。在大多数情况下,如果您要求 bison 生成 "push parser",代码会更清晰、更容易编写。使用推送解析器,每当有可用的标记时,词法分析器就会调用解析器。这使得从词法分析器操作中 return 多个标记变得微不足道;您只需为每个标记调用解析器。类似地,如果规则不产生任何标记,它只是无法调用解析器。在这个模型中,唯一实际 return
s 的词法分析器操作是 <<EOF>>
规则,它仅在使用 END
标记调用解析器以指示解析完成后才这样做。
不幸的是,推送解析器的接口不仅会发生变化,如手册 link 所示;它的记录也很糟糕。所以这是一个简单但完整的示例,展示了它是如何完成的。
推送解析器将其状态保存在 yypstate
结构中,需要在每次调用时将其传递给解析器。由于每个输入文件只调用一次词法分析器,因此词法分析器拥有该结构是合理的,这可以通过局部静态变量完成如上[注1]:解析器状态在yylex
时初始化被调用,并且 EOF
规则删除解析器状态以回收它正在使用的任何内存。
构建可重入推送解析器通常最方便,这意味着解析器不依赖全局yylval
变量[注2]。相反,指向语义值的指针必须作为附加参数提供给yypush_parse
。如果您的解析器不引用特定标记类型的语义值,您可以为此参数提供 NULL。或者,如以下代码所示,您可以在词法分析器中使用局部语义值变量。不必每次调用推送解析器都提供相同的指针。总之,对扫描器定义的更改是最小的:
%%
/* Initialize a parser state object */
yypstate* pstate = yypstate_new();
/* A semantic value which can be sent to the parser on each call */
YYSTYPE yylval;
/* Some example scanner actions */
"keyword" { /* Simple keyword which just sends a value-less token */
yypush_parse(pstate, TK_KEYWORD, NULL); /* See Note 3 */
}
[[:digit:]]+ { /* Token with a semantic value */
yylval.num = atoi(yytext);
yypush_parse(pstate, TK_NUMBER, &yylval);
}
"dice-roll" { /* sends three random numbers */
for (int i = 0; i < 2; ++i) {
yylval.num = rand() % 6;
yypush_parse(pstate, TK_NUMBER, &yylval);
}
<<EOF>> { /* Obligatory EOF rule */
/* Send the parser the end token (0) */
int status = yypush_parse(pstate, 0, NULL);
/* Free the pstate */
yypstate_delete(pstate);
/* return the parser status; 0 is success */
return status;
}
在解析器中,除了添加必要的声明外,根本不需要更改太多:[注 4]
%define api.pure full
%define api.push-pull push
注释
如果您也在构建可重入词法分析器,您将使用词法分析器状态对象的额外数据部分而不是静态变量。
如果您在解析器中使用位置对象来跟踪源代码位置,这也适用于 yylloc
。
示例代码没有很好地检测错误,因为它没有检查来自对 yypush_parse
的调用的 return 代码。我常用的一种解决方案是宏 SEND
:
的一些变体
#define SEND(token) do { \
int status = yypush_parse(pstate, token, &yylval); \
if (status != YYPUSH_MORE) { \
yypstate_delete(pstate); \
return status; \
} \
} while (0)
也可以使用 goto
来避免 yypstate_delete
和 return
的多个实例。 YMMV.
您可能需要修改yyerror
的原型。如果您使用位置 and/or 为 push_parser 提供额外参数,位置对象 and/or 额外参数也将出现在 yyerror
调用中。 (错误字符串始终是 last 参数。)无论出于何种原因,解析器状态对象 not 提供给 yyerror
,这意味着 yyerror
函数不再可以访问 yych
等变量,这些变量现在是 yypstate
结构的成员而不是全局变量,因此如果您在错误中使用这些变量报告(这不是真正推荐的做法),那么您将不得不找到替代解决方案。
为了让我的问题更容易理解,我想用下面的例子:
下面的代码在fortran语言中叫做nonblock do-loop
DO 20 I=1, N ! line 1
DO 20 J=1, N ! line 2
! more codes
20 CONTINUE ! line 4
注意第 4 行的标签 20
表示 内部 do 循环和外部 do 循环的结束。
我希望我的 flex 程序正确解析该功能:当 flex 读取标签 20
时,它将 return ENDDO
终止两次。
首先,因为我也用bison,所以bison每次调用yylex()
都会得到一个terminal。如果我可以让 bison 在某些情况下从 yylex()
获取终端,而在其他情况下从另一个函数获取终端,也许我可以解决这个问题,但是,我当时对此一无所知。
当然有一些解决方法,例如,我可以使用 flex 的启动条件,但我认为这不是一个好的解决方案。所以我问有没有什么方法可以在没有解决方法的情况下解决我的问题?
感谢我的一个朋友,他提供了实现的方法
If I can ask bison to get terminals from yylex() in some cases, and from another function in other cases
在flex生成的flex.cpp代码中,有一个宏
/* Default declaration of generated scanner - a define so the user can
* easily add parameters.
*/
#ifndef YY_DECL
#define YY_DECL_IS_OURS 1
extern int yylex (void);
#define YY_DECL int yylex (void)
#endif /* !YY_DECL */
所以我可以 "rename" 将 flex 的 yylex()
函数转换为另一个函数,例如 pure_yylex()
.
所以我的问题解决了:
- push all terminals 我想给bison一个全局的
vector<int>
- 自己实现一个
yylex()
函数,当bison调用yylex()
时,这个函数会先尝试从那个全局的vector<int>
获取终端
- 如果
vector<int>
为空,yylex()
调用pure_yylex()
,flex开始工作
修改 (f)lex 生成的词法扫描器来实现令牌队列很容易,但这不一定是最佳解决方案。 (请参阅下文以获得更好的解决方案。)(另外,我真的不清楚对于您的特定问题,在词法分析器中制造额外的标记是否真的合适。)
一般方法是在 yylex
函数的顶部插入代码,您可以将代码紧跟在 %%
行之后和第一条规则之前。 (代码必须缩进,这样它就不会被解释为规则。)对于非重入扫描器,这通常涉及使用本地 static
变量来保存队列。举一个简单但愚蠢的例子,使用 C API 但用 C++ 编译以便访问 C++ 标准库:
%%
/* This code will be executed each time `yylex` is called, before
* any generated code. It may include declarations, even if compiled
* with C89.
*/
static std::deque<int> tokenq;
if (!tokenq.empty()) {
int token = tokenq.front();
tokenq.pop_front();
return token;
}
[[:digit:]]+ { /* match a number and return that many HELLO tokens */
int n = atoi(yytext);
for (int i = 0; i < n; ++i)
tokenq.push_back(HELLO);
}
以上代码没有尝试为排队的令牌提供语义值;您可以为令牌队列使用类似 std::queue<std::pair<int, YYSTYPE>>
的东西来实现这一点,但 YYSTYPE
通常是 union
的事实会导致一些复杂情况。此外,如果这是使用令牌队列的唯一原因,很明显可以用一个简单的计数器代替它,这样效率会高得多。例如,请参阅
更好的选择:使用推送解析器
尽管令牌队列解决方案既吸引人又简单,但它很少是最佳解决方案。在大多数情况下,如果您要求 bison 生成 "push parser",代码会更清晰、更容易编写。使用推送解析器,每当有可用的标记时,词法分析器就会调用解析器。这使得从词法分析器操作中 return 多个标记变得微不足道;您只需为每个标记调用解析器。类似地,如果规则不产生任何标记,它只是无法调用解析器。在这个模型中,唯一实际 return
s 的词法分析器操作是 <<EOF>>
规则,它仅在使用 END
标记调用解析器以指示解析完成后才这样做。
不幸的是,推送解析器的接口不仅会发生变化,如手册 link 所示;它的记录也很糟糕。所以这是一个简单但完整的示例,展示了它是如何完成的。
推送解析器将其状态保存在 yypstate
结构中,需要在每次调用时将其传递给解析器。由于每个输入文件只调用一次词法分析器,因此词法分析器拥有该结构是合理的,这可以通过局部静态变量完成如上[注1]:解析器状态在yylex
时初始化被调用,并且 EOF
规则删除解析器状态以回收它正在使用的任何内存。
构建可重入推送解析器通常最方便,这意味着解析器不依赖全局yylval
变量[注2]。相反,指向语义值的指针必须作为附加参数提供给yypush_parse
。如果您的解析器不引用特定标记类型的语义值,您可以为此参数提供 NULL。或者,如以下代码所示,您可以在词法分析器中使用局部语义值变量。不必每次调用推送解析器都提供相同的指针。总之,对扫描器定义的更改是最小的:
%%
/* Initialize a parser state object */
yypstate* pstate = yypstate_new();
/* A semantic value which can be sent to the parser on each call */
YYSTYPE yylval;
/* Some example scanner actions */
"keyword" { /* Simple keyword which just sends a value-less token */
yypush_parse(pstate, TK_KEYWORD, NULL); /* See Note 3 */
}
[[:digit:]]+ { /* Token with a semantic value */
yylval.num = atoi(yytext);
yypush_parse(pstate, TK_NUMBER, &yylval);
}
"dice-roll" { /* sends three random numbers */
for (int i = 0; i < 2; ++i) {
yylval.num = rand() % 6;
yypush_parse(pstate, TK_NUMBER, &yylval);
}
<<EOF>> { /* Obligatory EOF rule */
/* Send the parser the end token (0) */
int status = yypush_parse(pstate, 0, NULL);
/* Free the pstate */
yypstate_delete(pstate);
/* return the parser status; 0 is success */
return status;
}
在解析器中,除了添加必要的声明外,根本不需要更改太多:[注 4]
%define api.pure full
%define api.push-pull push
注释
如果您也在构建可重入词法分析器,您将使用词法分析器状态对象的额外数据部分而不是静态变量。
如果您在解析器中使用位置对象来跟踪源代码位置,这也适用于
yylloc
。示例代码没有很好地检测错误,因为它没有检查来自对
的一些变体yypush_parse
的调用的 return 代码。我常用的一种解决方案是宏SEND
:#define SEND(token) do { \ int status = yypush_parse(pstate, token, &yylval); \ if (status != YYPUSH_MORE) { \ yypstate_delete(pstate); \ return status; \ } \ } while (0)
也可以使用
goto
来避免yypstate_delete
和return
的多个实例。 YMMV.您可能需要修改
yyerror
的原型。如果您使用位置 and/or 为 push_parser 提供额外参数,位置对象 and/or 额外参数也将出现在yyerror
调用中。 (错误字符串始终是 last 参数。)无论出于何种原因,解析器状态对象 not 提供给yyerror
,这意味着yyerror
函数不再可以访问yych
等变量,这些变量现在是yypstate
结构的成员而不是全局变量,因此如果您在错误中使用这些变量报告(这不是真正推荐的做法),那么您将不得不找到替代解决方案。