分词器拥有堆栈是否合法？

Question

我设计了一种新语言，我想为此编写一个合理的词法分析器和解析器。为了简洁起见，我已将这种语言减少到最低限度，以便我的问题仍然存在。

该语言具有隐式和显式字符串、数组和对象。隐式字符串只是不包含 <、{、[ 或 ] 的字符序列。显式字符串看起来像 <salt<text>salt>，其中 salt 是任意标识符（即 [a-zA-Z][a-zA-Z0-9]*），text 是不包含盐的任意字符序列。
数组以 [ 开头，后跟对象 and/or 字符串并以 ] 结尾。数组中不属于数组、对象或显式字符串的所有字符都属于隐式字符串，并且每个隐式字符串的长度最大且大于 0。
对象以 { 开头，以 } 结尾，由属性组成。属性以标识符开头，后跟冒号，然后是可选的空格，然后是显式字符串、数组或对象。

所以字符串 [ name:test <xml<<html>[]</html>>xml> {name:<b<test>b>}<b<bla>b> ] 表示一个包含 6 个项目的数组：" name:test "、"<html>[]</html>"、" "、{ name: "test" }、"bla" 和" "（对象在json中标注）。

如您所见，由于显式字符串（我不想错过），这种语言不是上下文无关的。但是，语法树是明确的。

所以我的问题是：属性是一个标记器可以 return 编辑的标记吗？或者分词器 return T_identifier, T_colon 当他读取一个对象属性?
真正的语言甚至允许在属性的标识符中使用前缀，例如ns/name:<a<test>a> 其中 ns 是命名空间的前缀。分词器应该 return T_property_prefix("ns")、T_property_prefix_separator、T_property_name("name")、T_property_colon 还是 T_property("ns/name") 甚至 T_identifier("ns")、T_slash, T_identifier("name"), T_colon?

如果 tokenizer 应该识别属性（这对语法高亮器很有用），他必须有一个堆栈，因为 name: 如果它在数组中则不是属性。要确定 [{foo:{bar:[test:baz]} bla:{}}] 中的 bla: 是属性还是隐式字符串，分词器必须跟踪他何时进入和离开对象或数组。因此，分词器将不再是有限状态机。

或者有两个标记器是否有意义 - 第一个将空格与字母数字字符序列和特殊字符（如 : 或 [ 分开，第二个使用第一个构建更多语义标记？然后解析器可以在第二个分词器之上运行。

无论如何，分词器必须具有无限前瞻性以查看显式字符串何时结束。还是应该在解析器内部检测显式字符串的结尾？

或者我应该使用解析器生成器来完成我的任务吗？由于我的语言不是上下文无关的，所以我认为没有合适的解析器生成器。

提前感谢您的回答！

Answer 1

我认为解析语言的传统方法是使用分词器 return T_identifier("ns")、T_slash、T_identifier("name")、T_colon ns/name:

无论如何，我可以看到三种实现对您的语言的支持的合理方法：

使用lex/flex和yacc/bison。 lex/flex 生成的分词器没有堆栈，因此您应该使用 T_identifier 而不是 T_context_specific_type。我没有尝试过这种方法，所以我无法就您的语言是否可以被 lex/flex 和 yacc/bison 解析给出明确的评论。所以，我的意见是尝试一下，看看它是否有效。您可能会发现有关 lexer hack 的信息很有用：http://en.wikipedia.org/wiki/The_lexer_hack
实现 hand-built 递归下降解析器。请注意，无需单独的 lexer/parser 阶段即可轻松构建。所以，如果词素依赖于上下文，那么使用这种方法就很容易处理。
实现您自己的解析器生成器，它根据解析器的上下文打开和关闭词素。因此，词法分析器和解析器将使用这种方法集成在一起。

我曾经在一家主要的网络安全供应商工作，他们使用方法 (3) 执行深度数据包检测，即我们有一个自定义解析器生成器。这样做的原因是方法 (1) 不起作用有两个原因：首先，数据不能递增地馈送到 lex/flex 和 yacc/bison，其次，HTTP 不能被解析使用 lex/flex 和 yacc/bison 因为字符串 "HTTP" 的含义取决于它的位置，即它可以是 header 值或协议说明符。方法 (2) 不起作用，因为无法将数据递增地馈送到递归下降解析器。

我要补充一点，如果您想要有意义的错误消息，强烈建议使用递归下降解析器方法。我的理解是当前版本的 gcc 使用 hand-built 递归下降解析器。

Answer 2

flex 可以请求提供上下文堆栈，许多 flex 扫描器使用此功能。因此，虽然它可能不符合扫描仪扫描方式的纯粹观点，但它是一个完全可以接受和支持的功能。有关如何拥有不同的词法上下文（称为 "start conditions"）的详细信息，请参阅 flex 手册的 this chapter；最后是对上下文堆栈的简要描述。（不要错过需要 %option stack 才能启用堆栈的句子。）[参见注释 1]

稍微棘手的是要求匹配带有可变结束标记的字符串。 flex 没有任何变量匹配功能，但它允许您使用函数 input() 从扫描仪输入中一次读取一个字符。这对您的语言来说已经足够了（至少如描述的那样）。

这是一个可能的扫描仪的粗略轮廓：

%option stack
%x SC_OBJECT

%%
 /* initial/array context only */
[^][{<]+ yylval = strdup(yytext); return STRING;
 /* object context only */
<SC_OBJECT>{
  [}]                     yy_pop_state(); return '}';
  [[:alpha:]][[:alnum:]]* yylval = strdup(yytext); return ID;
  [:/]                    return yytext[0];
  [[:space:]]+            /* Ignore whitespace */
}
 /* either context */
<*>{
  [][]     return yytext[0]; /* char class with [] */
  [{]      yy_push_state(SC_OBJECT); return '{';
  "<"[[:alpha:]][[:alnum:]]*"<" {
           /* We need to save a copy of the salt because yytext could
            * be invalidated by input().
            */
           char* salt = strdup(yytext);
           char* saltend = salt + yyleng;
           char* match = salt;
           /* The string accumulator code is *not* intended
            * to be a model for how to write string accumulators.
            */
           yylval = NULL;
           size_t length = 0;
           /* change salt to what we're looking for */
           *salt = *(saltend - 1) = '>';
           while (match != saltend) {
             int ch = input();
             if (ch == EOF) {
               yyerror("Unexpected EOF");
               /* free the temps and do something */
             }
             if (ch == *match) ++match;
             else if (ch == '>') match = salt + 1;
             else match = salt;
                /* Don't do this in real code */
             yylval = realloc(yylval, ++length);
             yylval[length - 1] = ch;
           }
           /* Get rid of the terminator */
           yylval[length - yyleng] = 0;
           free(salt);
           return STRING;
         }
  .      yyerror("Invalid character in object");
}

我没有彻底测试，但这是您输入示例的样子：

[ name:test <xml<<html>[]</html>>xml> {name:<b<test>b>}<b<bla>b> ]
Token: [
Token: STRING: -- name:test --
Token: STRING: --<html>[]</html>--
Token: STRING: -- --
Token: {
Token: ID: --name--
Token: :
Token: STRING: --test--
Token: }
Token: STRING: --bla--
Token: STRING: -- --
Token: ]

备注

在你的例子中，除非你想避免使用解析器，否则你实际上并不需要堆栈，因为唯一需要被压入堆栈的是一个对象上下文，而一个只有一个可能值的堆栈可以用计数器代替。

因此，您可以删除 %option stack 并在扫描顶部定义一个计数器。您不是推动开始条件，而是递增计数器并设置开始条件；不是弹出，而是递减计数器并在它下降到 0 时重置开始条件。
```
%%
  /* Indented text before the first rule is inserted at the top of yylex */
  int object_count = 0;
<*>[{]         ++object_count; BEGIN(SC_OBJECT); return '{';
<SC_OBJECT[}]  if (!--object_count) BEGIN(INITIAL); return '}'
```
一次读取输入的一个字符并不是最有效的。由于在您的情况下，字符串终止必须以 > 开头，因此最好定义一个单独的 "explicit string" 上下文，您可以在其中识别 [^>]+ 和 [>]。第二个将执行一次字符匹配，与上面的代码一样，但是如果它发现 > 以外的非匹配字符，它将终止而不是循环。然而，提供的简单代码可能已经足够快了，无论如何它只是为了足够好做一个测试运行.

分词器拥有堆栈是否合法？

Is it legitimate for a tokenizer to have a stack?

parsing

tokenize

lexer

备注