wvx*_*xvw 0 yacc bison flex-lexer
我真的更喜欢一个有效的例子来解释.无论我到目前为止在Bison的文档网站上所阅读的内容都与Flex所说的相矛盾.有人说要宣布yylex为
int yylex (yyscan_t yyscanner);
另一个人希望它是:
int yylex(YYSTYPE *lvalp, YYLTYPE *llocp);
我真正需要的是位置信息.我现在还不确定是否需要YYSTYPE(我现在没有使用这些信息,但将来我可能会这样做).
与上述无关,作为奖励,我很有兴趣知道为什么这个基础设施如此糟糕.这似乎是一件非常直截了当的事情,但它却非常糟糕.它从不适用于默认值.即使编写一个最简单的教科书计算器示例,也需要多天修复配置错误...为什么？
ric*_*ici 12
本答案的第2部分提供了一种关于如何将可重入配置为野牛和弯曲的解释.示例代码的其他注释在第3节中.
%option noinput nounput noyywrap 8bit nodefault
%option yylineno
%option reentrant bison-bridge bison-locations
%{
#include <stdlib.h>
#include <string.h>
#include "eval.tab.h"
#define YY_USER_ACTION \
yylloc->first_line = yylloc->last_line; \
yylloc->first_column = yylloc->last_column; \
if (yylloc->last_line == yylineno) \
yylloc->last_column += yyleng; \
else { \
yylloc->last_line = yylineno; \
yylloc->last_column = yytext + yyleng - strrchr(yytext, '\n'); \
}
%}
%%
[ \t]+ ;
#.* ;
[[:digit:]]+ *yylval = strtol(yytext, NULL, 0); return NUMBER;
.|\n return *yytext;
%define api.pure full
%locations
%param { yyscan_t scanner }
%code top {
#include <stdio.h>
}
%code requires {
typedef void* yyscan_t;
}
%code {
int yylex(YYSTYPE* yylvalp, YYLTYPE* yyllocp, yyscan_t scanner);
void yyerror(YYLTYPE* yyllocp, yyscan_t unused, const char* msg);
}
%token NUMBER UNOP
%left '+' '-'
%left '*' '/' '%'
%precedence UNOP
%%
input: %empty
| input expr '\n' { printf("[%d]: %d\n", @2.first_line, $2); }
| input '\n'
| input error '\n' { yyerrok; }
expr : NUMBER
| '(' expr ')' { $$ = $2; }
| '-' expr %prec UNOP { $$ = -$2; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '%' expr { $$ = $1 % $3; }
%%
void yyerror(YYLTYPE* yyllocp, yyscan_t unused, const char* msg) {
fprintf(stderr, "[%d:%d]: %s\n",
yyllocp->first_line, yyllocp->first_column, msg);
}
有关此文件需求的说明,请参阅3.1.
#include "eval.tab.h"
#include "eval.lex.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "eval.h"
#if !YYDEBUG
static int yydebug;
#endif
int main(int argc, char* argv[]) {
yyscan_t scanner;
yylex_init(&scanner);
do {
switch (getopt(argc, argv, "sp")) {
case -1: break;
case 's': yyset_debug(1, scanner); continue;
case 'p': yydebug = 1; continue;
default: exit(1);
}
break;
} while(1);
yyparse(scanner);
yylex_destroy(scanner);
return 0;
}
all: eval
eval.lex.c: eval.l
flex -o $@ --header-file=$(patsubst %.c,%.h,$@) --debug $<
eval.tab.c: eval.y
bison -o $@ --defines=$(patsubst %.c,%.h,$@) --debug $<
eval: main.c eval.tab.c eval.lex.c eval.h
$(CC) -o $@ -Wall --std=c11 -ggdb -D_XOPEN_SOURCE=700 $(filter %.c,$^)
clean:
rm -f eval.tab.c eval.lex.c eval.tab.h eval.lex.h main
最重要的是要记住Bison/Yacc和Flex/Lex是两个独立的代码生成器.虽然它们经常一起使用,但这不是必需的; 任何一个都可以单独使用或与其他工具一起使用.
注意:以下讨论仅适用于普通的"推送"解析器.Bison可以生成拉解析器(类似于Lemon)并允许有用的控制流反转,这实际上简化了下面提到的几个问题.特别是,它完全避免了3.1中分析的循环依赖性.我通常更喜欢推送解析器,但它们似乎超出了这个特定问题的范围.
Bison/Yacc生成的解析器被调用一次来解析整个文本体,因此它不需要在调用之间维护可变的持久数据对象.它依赖于许多指导解析器进度的表,但这些不可变表具有静态生命周期的事实不会影响重入.(至少在Bison中,这些表没有外部链接,但当然它们仍然可以通过插入解析器的用户编写的代码看到.)
主要的问题,那么,是外部可见可变全局yylval和yylloc,用于扩充解析器词法分析器接口.这些全局变量绝对是Bison/Yacc的一部分; Flex生成的代码甚至没有提及它们,并且在Flex定义文件中的用户操作中明确执行它们的所有使用.为了使野牛解析器具有可重入性,有必要修改解析器用来从词法分析器收集有关每个令牌的信息的API,而Bison采用的解决方案是提供附加参数的经典解决方案,这些参数是指向数据的指针结构被"返回"到解析器.所以这个重入需求改变了Bison生成的解析器调用的方式yylex; 而不是调用
int yylex(void);
原型成为:
int yylex(YYSTYPE* yylvalp);
要么
int yylex(YYSTYPE* yylvalp, YYLTYPE* yyllocp);
取决于解析器是否需要存储的位置信息yylloc.(Bison将自动检测操作中位置信息的使用,但您也可以坚持提供位置对象yylex.)
这意味着必须修改词法分析器以便与可重入的野牛解析器正确通信,即使词法分析器本身不是可重入的.
还有少量额外的Bison/Yacc变量供用户代码使用:
yynerrs计算遇到的语法错误的数量; 使用重入解析器,yynerrs是本地的yyparse,因此只能用于操作.(在遗留应用程序中,它有时由yyparse调用者引用;需要为重入解析器修改此类用法.)
yychar是前瞻符号的令牌类型,有时用于错误报告.在可重入的解析器中,它是本地的,yyparse因此如果错误报告功能需要它,则必须显式传递.
yydebug如果已启用调试代码,则控制是否生成解析跟踪.yydebug在重入解析器中仍然是全局的,因此不可能仅为单个解析器实例启用调试跟踪.(我认为这是一个错误,但它可以被视为功能请求.)
通过定义预处理器宏YYDEBUG或使用-t命令行标志来启用调试代码.这些由Posix定义; Flex还提供--debug命令行标志; 的%debug指令和parse.trace配置指令(其可设置与-Dparse.trace野牛命令行上.
yylex在解析过程中被反复调用; 每次调用它时,它都会返回一个令牌.它需要在调用之间保持大量的持久状态,包括其当前缓冲区和跟踪词汇进度的各种指针.
在默认词法分析器中,此信息保存在全局struct中,除了特定的全局变量(主要是现代Flex模板中的宏)之外,该全局不会被用户代码引用.
在重入词法分析器中,Flex的所有持久性信息都被收集到由类型变量指向的不透明数据结构中yyscan_t.必须将此变量传递给每次调用Flex函数,而不仅仅是yylex.(该列表包括,例如,各种缓冲区管理功能.)Flex约定是持久状态对象始终是函数的最后一个参数.一些已重新定位到此数据结构中的全局变量具有关联的宏,因此可以通过其传统名称Flex动作来引用它们.除此之外yylex,所有访问(以及在可变变量的情况下的修改)必须使用Flex手册中记录的getter和setter函数来完成.显然,getter/setter函数列表不包含Bison变量的访问器,例如yylval.
所以yylex在一台可重入的扫描仪中有原型
int yylex(yystate_t state);
Flex/lex本身只识别令牌; 由每个模式关联的用户操作决定了匹配的结果.通常,解析器期望yylex返回表示令牌的句法类型的小整数或0以指示已到达输入的结尾.令牌的文本存储在变量(或yyscan_t成员)中yytext(及其长度yyleng)但由于yytext是生成扫描器中内部缓冲区的指针,因此字符串值只能在下次调用之前使用yylex.由于LR解析器通常不会处理语义信息,直到读取了几个令牌,yytext因此不是用于传递语义信息的适当机制.如上所述,Bison/Yacc生成的解析器改为使用全局yylval来传递语义信息.yylloc如果需要,Bison还提供全球通信源位置信息.
正如我们所看到的,重入词法分析器和重入分析器都需要对原型进行更改yyparse.如果两个组件都是可重入的,则需要应用这两个更改,并且原型变为:
int yylex(YYSTYPE* yylvalp, YYLTYPE* yyllocp, yystate_t state);
(如果未使用位置,yylex则消除该参数.)
鉴于上述情况,在宣布yylval之前不可能yylloc宣布.在声明yyllocp之前%bison-bridge也不可能宣布.由于%bison-bridge和%bison-locations在该柔性生成的报头和yylex与yylval当前正在使用野牛生成的头,对于两个集管既不包含顺序可以工作.或者,换句话说,存在循环依赖.
因为union它只是一个类型别名%union(而不是指向不完整类型的指针,这可以说是将指针传递给不透明数据结构的一种更简洁的方法),所以可以通过插入冗余来打破循环yylval.tag:
typedef void* yyscan_t;
#include "flex.tab.h"
#include "flex.lex.h"
这很好.下一步似乎是将第二步yylval->tag和第二步%define api.value.type放在野牛生成的标题中yylval = ...,使用一个*yylval = ...块放置yylex()在开头附近,一个YYSTYPE块放在yyparse()接近结尾(或至少在yyscan_t声明之后).不幸的是,这不起作用,因为yylex它包含在flex生成的扫描程序代码中.这将导致将flex生成的头部包含在flex生成的源代码中,并且不支持.(尽管flex生成的标头确实有一个标头保护,但生成的源文件不需要存在头文件,因此它包含内容的副本而不是yyscan_t语句,并且副本不包括标头保护.)
在示例代码中,我做了下一个最好的事情:我使用了一个yyparse块来插入YYSTYPEbison生成的头文件,并创建了一个额外的yyscan_t头文件,可供包含bison和flex生成的头文件的其他翻译单元使用按正确的顺序.
那很难看.已经提出了其他解决方案,但它们都是,恕我直言,同样难看.这恰好是我使用的那个.
yylex和yyerror原型都取决于解析器是否需要源位置.由于这些更改将通过各种项目文件进行回响,我认为最可取的是强制使用位置信息,即使它尚未被解析器使用.有一天你可能想要使用它,并且维护它的运行时开销并不是很大(虽然它是可测量的,所以你可能想在资源受限的环境中忽略这个建议).
为了简化负载,我在第10-17行中包含了一个简单的通用实现,void*其中使用了在typedef所有flex规则操作的开头插入代码.这个typedef宏应该适用于不使用任何扫描仪#include,flex.tab.h,code requires或typedef.正确地处理这些功能并不是太困难,但这似乎超出了范围.
示例代码实现了一个简单的面向行的计算器,可用于交互式评估.(不包括一些对交互式评估有用的其他功能.交互式计算器可以从code provides集成和访问以前计算的值中获益很大;变量和命名常量也很方便.)为了使交互式使用合理,我插入了一个非常小的错误恢复策略:丢弃令牌的#include第24行生成,YYSTYPE直到遇到换行符,然后用于flex.tab.h避免丢弃错误消息.
Bison和Yacc生成的解析器遵循Posix的要求,即除非#include定义了预处理器宏并且具有非零值,否则不会编译生成的源中的调试代码.如果将调试代码编译到二进制文件中,则调试跟踪由全局变量控制code requires.如果typedef为非零,eval.h则给定默认值0,这将禁用跟踪.如果使用flex.lyydebug YY_USER_ACTIONYYDEBUG YY_USER_ACTION-t`命令行选项,则在这种情况下它将具有默认值1.
Bison将yyless()宏定义插入到生成的头文件中(虽然Posix没有强制要求),所以我测试它yymore()并提供input()变量的替代定义(如果尚未定义).这允许代码使得调试跟踪能够编译,即使它无法打开跟踪.
Flex生成的代码通常使用全局变量REJECT来打开和关闭跟踪; 与yacc/bison不同,readline()如果将调试代码编译到可执行文件中,则默认值为1.由于可重入扫描程序无法使用全局变量,因此可重入扫描程序将调试启用程序放入error对象中,可以使用flex.y和yyerrok访问函数访问该对象,无论是否已编译调试代码,都会定义这些函数.但是,可重入调试标志的默认值为0,因此,如果创建可重入扫描程序,则即使已将跟踪编译到可执行文件中,也需要显式启用跟踪.(这使得可重入扫描器更像解析器.)
YYDEBUG如果使用yydebug命令行选项运行,则示例程序将打开扫描程序跟踪,并使用该YYDEBUG选项进行解析器跟踪.