用正则表达式识别标记的歧义

Question

我正在用 C++ 编程，使用 Flex 词法分析器，我需要识别两个不同的标记，但它们共享一些符号。我需要识别类型 (a<b+c*4) 的表达式，其次我需要识别逻辑运算 <->。如果我输入 a <-> b (a iff b)，词法分析器将其视为 a<、-> 和 b，但我想得到 a， <-> 和 b.

//REGEX FOR MATH EXPRESSIONS.
[a-zA-Z0-9<>=]+
//REGEX FOR THE <-> LOGIC OPERATOR
"<->"

这是我的弹性代码：

%option noyywrap
%{
    #include <iostream>
    #include "parser.tab.c"
    using namespace std;
%}

%%

[a-zA-Z0-9<>=]+  {
    yylval = strdup(yytext);
    return SYMBOL;
}

"&&" {
    return AND;
}

"||" {
    return OR;
}

"!" {
    return NOT;
}

"!(" {
    return DIST;
}

[ [=11=][=11=]] {
    return END;
}

"("     {
    return LEFT_PAR;
}

")"     {
    return RIGHT_PAR;
}

"->"    {
    return THEN;
}

"<->"   {
    return IFF;
}

%%

我该如何解决这个问题？

你好。

Answer 1

对我来说，只想解析表达式语法的一部分似乎有点奇怪。尝试在扫描仪中识别表情确实不合适，尽管它肯定可以做到。就个人而言，我只是将它留给解析器来处理表达式的算术部分（可能通过将标记重新组合成一个字符串），特别是因为无论如何它都需要进行干预来处理括号。

尽管如此，可以强制 flex 完成这项工作，方法是使用 yymore() 来累积令牌，或者通过自己在字符串累加器中累积令牌。无论哪种方式，当您找到其他一些标记（例如，您的逻辑运算符之一）时，您最终将不得不 "send" 累积表达式；如果您使用推送解析器（绝对是我的偏好），这会容易得多，但可以使用开始条件来完成。

为了不需要字符串累加器对象或特定版本的 bison（并且不知道您如何处理标记），这里有一个基于开始条件的解决方案，它使用 flex 来累加代币：

%x IN_ARITH
arith_piece     [[:alnum:]]+|[-+<>=]
%%
                            int symbol_leng = 0;

"&&"                      { return AND;                    }
"||"                      { return OR;                     }
"->"                      { return THEN;                   }
"<->"                     { return IFF;                    }
"!("                      { return DIST;      /* Note 1 */ }
" "                       { return END;       /* Note 2 */ }
.|\n                      { return yytext[0]; /* Note 3 */ }

<*>{arith_piece}          { BEGIN(INITIAL);   /* Note 5 */
                            yylval = strdup(yytext);
                            return SYMBOL;                 }

<*>{arith_piece}/(.|\n)   { BEGIN(IN_ARITH);  /* Note 4 */
                            symbol_leng = yyleng; 
                            yymore();                      }

<IN_ARITH>"->"|"<->"|.|\n { BEGIN(INITIAL);   /* Note 6 */
                            yyless(symbol_leng);
                            yylval = strdup(yytext);
                            yylval[symbol_leng] = 0;
                            return SYMBOL;                 }

备注

我不禁想到返回 DIST 而不是 NOT 然后 LPAREN 会使解析更复杂而不是更简单。
没有模式匹配换行符（至少，在原始扫描仪中）。在 OP 中，这是 [ [=16=][=16=]]，这对我来说似乎很奇怪；没有理由重复 [=17=]，并且在任何情况下 [=17=] 几乎不会出现在输入中，而换行符很常见。我想您希望扫描在空白处终止；我更喜欢 [[:space:]] { return END; } 那样做。万一你在输入流中真的有一个 NUL 字符，我添加的默认规则将处理它 "correctly".
此默认规则 returns 字符代码作为任何其他不匹配字符（包括换行符，但见上文）的标记号。如果 LEFT_PAR，这将完美工作， RIGHT_PAR 和 NOT 的值分别为 '('、')' 和 '!'。如果你使用 bison 来解析，你可以通过完全不使用命名标记来实现这个结果。你可以只把 '(' 放在生产中，甚至不用声明它是一个令牌。

如果所有这些都不适合您的解析模型，请使用原始规则。
{arith_piece}匹配的标记（字母和数字序列，或单个算术运算符）只是使用yymore()添加到累积标记中。（有关尾随上下文的解释，请参阅注释 5。）我们无条件地切换到 <IN_ARITH> 开始条件，如果我们已经处于该开始条件，则什么都不做，以便我们可以在输出逻辑之前输出累积的标记操作员。（见注释 6）。

flex 将此标记为 "dangerous trailing context"，但它会正常工作；在这种情况下，您可以忽略警告消息。
此规则只有在后面的规则不匹配时才能匹配，并且由于前一个规则的尾随上下文将匹配任何后面的字符，因此只有在匹配正确的情况下该规则才能匹配输入结束。所以在这条规则的行动中，我们知道我们在 EOF。这个复杂的游戏是必要的，因为 yytext 在 <<EOF>> 规则中是无效的，即使之前的标记被保留 yymore().
任何不被 {arith_piece} 匹配的东西——也就是说，任何可以被 <INITIAL> 开始条件中的模式匹配的东西——需要 "send"累积的令牌，然后按照在该开始条件下的方式进行处理。但是，如果没有推送解析器，就不可能从一次扫描操作中发送两个标记，所以这里我们只发送累积的算术字符串，然后切换到 <INITIAL> 开始条件。我们使用 yyless 来调整累加字符串的长度，有效去除我们刚刚扫描的token；这将强制它在 <INITIAL> 开始条件下重新扫描，这将发送相应的令牌。

Answer 2

[a-zA-Z0-9<>=]+  {

这真的是你想要的吗？通常，您不应在标识符中使用 <、> 或 = 等特殊字符。你为什么不为它们定义特定的规则，就像你已经为 ( 等所做的那样？那么Flex的最长匹配规则就是return SYMBOL, IFF and SYMBOL 看到a<->b.

另请检查 the Flex manual 文件结束规则以将此规则替换为：

[ [=11=][=11=]] {
    return END;
}

用正则表达式识别标记的歧义

Ambiguity with regular expressions to recognize tokens

c++

regex

token

flex-lexer

备注