我如何在不将其从缓冲区中删除的情况下查看 flex 中的下一个标记

Question

我正在尝试为 AMPL 语言的某些子集构建词法分析器。我现在需要词法分析器正在处理什么类型的符号名称。每个符号名称都是 var 或 param 或 set。幸运的是，所有这些都必须在使用前声明。所以我想我可以在 flex 中使用先行运算符，只需将词法分析器中的代码从

SYMBOLIC_NAME [a-zA-Z_][a-zA-Z0-9_]*
%%
param             { return PARAM; }
var               { return VAR; }
set               { return SET; }
{SYMBOLIC_NAME}   { yylval.string = (char*) strdup(yytext);
                    return SYMBOLIC_NAME;  
                  }
%%

像这样的事情

SYMBOLIC_NAME [a-zA-Z_][a-zA-Z0-9_]*
%{
 #include <vector>
 #include <algorithm>
 std::vector<std::string> paramNames;
 std::vector<std::string> setNames;
 std::vector<std::string> varNames;

%}
%%
param/(.|\n)+{SYMBOLIC_NAME}             { paramNames.push_back(&yytext[5]);
                                           return PARAM; }
var/(.|\n)+{SYMBOLIC_NAME}               { varNames.push_back(&yytext[3]);
                                           return VAR; }
set/(.|\n)+{SYMBOLIC_NAME}               { setNames.push_back(&yytext[3]);
                                           return SET; }
{SYMBOLIC_NAME}   { if ( std::find(setNames.begin(), setNames.end(), yytext) != setNames.end() ) {
                    yylval.string = (char*) strdup(yytext);
                    return SET_NAME;
                    }

                   if ( std::find(paramNames.begin(), paramNames.end(), yytext) != paramNames.end() ){
                    yylval.string = (char*) strdup(yytext);
                    return PARAM_NAME;  
                  }
                  if ( std::find(varNames.begin(), varNames.end(), yytext) != varNames.end() ){
                    yylval.string = (char*) strdup(yytext);
                    return VAR_NAME;  
                  }
               }
%%

我知道它不会起作用，因为 yytext 不包含前三个正则表达式的第二部分。问题出现了，我如何查看 (.|\n)+{SYMBOLIC_NAME} .

下的内容

PS

我知道代码不是最优的，但这不是问题:D

Answer 1

您可以使用开始条件有效地执行 "peeking"，但是如果您实际要做的是维护一个符号 table，并让词法分析器自动 return每个符号的正确语义类别，有更好的解决方案（见下文）。

首先，与其使用三个 std::vector 列表并线性搜索每个列表直到找到符号，不如使用一个 std::unordered_map 将每个名称与一种语义类型。（我知道你说不要考虑代码的低效率，但这个改变让事情变得简单了很多。）

如果你想让 lexer 负责维护符号 table，这很容易做到，尽管它有点强制，因为解析器也需要存储与每个符号关联的语义信息。尽管如此，它并不太痛。下面我使用一个单一的开始条件在定义关键字之后收集定义的名称（这基本上是你的前瞻所做的，但是这样词法分析器隔离了被定义的实际名称而不是以可变数量的空格开头的字符串）。

这里我利用散列 table 包含代表符号名称的 std::string 的事实，通过将 yylval.string 设置为散列 table条目。只要您不修改 yylval.string 的内容，那是绝对安全的，因为符号永远不会从符号 table 中删除，并且散列 table 永远不会移动其元素。在实践中，让 yylval 联合成员成为：

可能会更好

%union {
   std::string* string;
   // ...
}

但这是一个小细节。这是扫描仪：

%{
   #include <unordered_map>
   namespace {
     enum class Kind { UNDEFINED, PARAM, SET, VAR };
     std::unordered_map<std::string, Kind> symbols;
   }
%}
%x SC_DEFINE

id [[:alpha:]_][[:alnum:]_]*

%%
  /* Up to the first unindented line is inserted at the beginning of yylex */
  Kind to_define;

<*>[[:space:]] /* Ignore in all start conditions */
param          { kind_to_define = Kind::PARAM; BEGIN(SC_DEFINE); }
set            { kind_to_define = Kind::SET; BEGIN(SC_DEFINE); }
var            { kind_to_define = Kind::VAR; BEGIN(SC_DEFINE); }
{id}           { auto it = symbols.emplace(yytext, Kind::UNKNOWN).first;
                 yylval.string = it->first.c_str();
                 switch (it->second) {
                     case Kind::PARAM: return PARAM_NAME;
                     case Kind::SET:   return SET_NAME;
                     case Kind::VAR:   return VAR_NAME;
                     default:          return UNDEFINED_NAME;
                 }
               }
<SC_DEFINE>{id} { auto itbool = symbols.emplace(yytext, to_define);
                  if (!itbool.second) {
                    if (itbool.first->second != Kind::UNKNOWN) {
                      /* Redefinition: handle the error somehow */
                    } else {
                      /* Used previously, error presumably already issued */
                      itbool.first->second = to_define;
                    }
                  }
                  BEGIN(INITIAL);
                  yylval.string = itbool.first->first.c_str();
                  switch (to_define) {
                    case Kind::PARAM: return DEFINE_PARAM;
                    case Kind::SET: return DEFINE_SET;
                    case Kind::VAR: return DEFINE_VAR;
                    default: /* Logic error */
                  }
                }

注意：上面的return是一个DEFINE_PARAM（例如）token，已经表示了交易品种的名称（在 yylval.string 中），因此您的语法规则必须是 param_definition: DEFINE_PARAM ... 而不是 param_definition: PARAM SYMBOL ....

上面我没有做的一件事是在 SC_DEFINE 开始条件中填写其他条目：任何其他标记（大概）是语法错误，包括您碰巧需要的任何关键字标记（例如 var、set 和 param。

我认为这会起作用，尽管我还没有真正尝试编译它。但它不仅仅是有点笨重。

恕我直言，更好的方法是在解析器和词法分析器之间共享符号 table。（bison 手册解释了如何为 yylex 提供额外的参数，而 flex 手册解释了如何接收它们。）基本符号 table 看起来和上面一样，除了它属于解析器，或者更准确地说是调用解析器的程序。但是，它可能具有比符号种类更多的语义信息。映射值可能是可区分的联合、boost::variant 或任何其他被证明方便的东西。

在那种情况下，扫描仪将与上面的概述大致相同，但没有启动条件。当它看到一个未定义的符号时（在扫描定义关键字后的符号时应该如此），它将 return 一个 UNDEFINED_NAME 标记，所以你的解析器的规则看起来像：

param_definition: PARAM UNDEFINED_NAME ...

并且在定义的语义操作中，解析器将填充符号的种类以及任何其他有用的信息。在这种情况下，将 yylval.symbol 作为指向符号 table 中的值的指针可能会很方便（不是迭代器，它可能会失效，而是 &*iterator 即 stable) 这样就不需要重复查找。

在这种情况下，使用未定义的符号并尝试定义已定义的符号自然会出现语法错误，因为解析器没有处理这些情况的规则。要提供有意义的错误消息，您可能需要添加诸如错误案例之类的规则。

Answer 2

我认为您正在尝试检查一个符号 table 您看到的是哪种名称。

如果是这种情况，您应该通过符号 table 进行通信来做到这一点。即：

创建一个简单的 "symbol" 规则。你原来的规则没问题：

{SYMBOLIC_NAME}   { yylval.string = (char*) strdup(yytext);
                return SYMBOLIC_NAME;  
              }

在解析器级别处理声明语法：

var_decl : VAR SYMBOLIC_NAME
     { add name to symbol table }

现在返回并扩展您的 SYMBOLIC_NAME 规则以检查定义的符号：

{SYMBOLIC_NAME} {
             yylval.string = (char*) strdup(yytext);

             if ( std::find(setNames.begin(), setNames.end(), yytext) != setNames.end() ) {
                 return SET_NAME;
             }
             else if (... varNames ...) {
                 return VAR_NAME;
             else if (... paramNames ...) {
                 return PARAM_NAME;
             }
             else {
                 return SYMBOLIC_NAME;
             }
         }

现在您有一个 Flex 目标返回四个可能的标记，具体取决于定义。但是 Flex 不必担心记住什么符号定义是活动的 - 您可以让解析器处理它。

在解析器端，您编写不同的规则：

var_decl: VAR SYMBOLIC_NAME
set_decl: SET SYMBOLIC_NAME

expr: atom '+' atom
atom: VAR_NAME | SET_NAME | PARAM_NAME

Answer 3

你不应该在意语法。您的语法应该只处理 IDENTIFIER，然后查找符号 table 本身的语义操作。

词法分析器中的所有这些乱七八糟的做法肯定是错误的。

我如何在不将其从缓冲区中删除的情况下查看 flex 中的下一个标记

How can i peek next token in flex without removing it from buffer

regex

lex

bison

ampl

flex-lexer