c++ - Lemon Parser 会跳过一些东西(或者我的误解)

Question

更新了更多信息

我在使用 Lemon 解析简单的元素数组时遇到问题。谁能赐教一下？？

我正在尝试使用 mygrammar 定义解析此字符串“[0 0 612 792][100 200]”，解析器总是跳过第一个数组元素并复制最后一个...有什么想法吗？？

语法文件是

%token_type { char* }

%include {
    #include <assert.h>
}

%parse_accept { printf("The parser has completed successfully.\n"); }
%syntax_error { fprintf(stderr, "Syntax Error\n"); }
%parse_failure { fprintf(stderr, "Parse failure\n"); }

%start_symbol program

array_value ::= INT_LITERAL(A). {printf("Av: %s\n", A);} 

array_value_list ::=.
array_value_list ::= array_value_list array_value.

array_declaration ::= LBRACKET array_value_list RBRACKET.

array_list ::= array_declaration.
array_list ::= array_list array_declaration.

program ::= array_list END_TOKEN.

我使用 re2c 获取 token ，为每个 token 调用解析器的代码是

  while(token = scan(&scanner, buff_end)) { 
    // Send strings to the parser with NAME tokens  

    if(token == INT_LITERAL) {
      name_length = scanner.cur - scanner.top;
      strncpy(name_str, scanner.top, name_length);
      name_str[name_length] = '\0';
      //printf("Token:Pre: %s\tName: %s\n", tokenStr(token),name_str);
      Parse(parser, token, name_str);
    }
    else {
      //printf("Token: %s\n", tokenStr(token));
      Parse(parser, token, 0);
    }
    // Execute Parse for the last time
    if(token == END_TOKEN) {
      Parse(parser, 0, NULL);
      break;
    }
  }

对于输入字符串“[ 0 -100 612 792][100 200]”，输出为:

Av: -100
Av: 612
Av: 792
Av: 792
Av: 200
Av: 200

正如您所注意到的，第一个元素没有出现，最后一个元素是重复的。

柠檬的语法是:

State 0:
          array_declaration ::= * LBRACKET array_value_list RBRACKET
          array_list ::= * array_declaration
          array_list ::= * array_list array_declaration
          program ::= * array_list END_TOKEN

                      LBRACKET shift        3      
             array_declaration shift        1        /* because array_declaration==array_list */
                    array_list shift        1      
                       program accept

State 1:
          array_declaration ::= * LBRACKET array_value_list RBRACKET
          array_list ::= array_list * array_declaration
          program ::= array_list * END_TOKEN

                      LBRACKET shift        3      
                     END_TOKEN shift        4      
             array_declaration shift-reduce 5      array_list ::= array_list array_declaration

State 2:
          array_value ::= * INT_LITERAL
          array_value_list ::= array_value_list * array_value
          array_declaration ::= LBRACKET array_value_list * RBRACKET

                   INT_LITERAL shift-reduce 0      array_value ::= INT_LITERAL
                      RBRACKET shift-reduce 3      array_declaration ::= LBRACKET array_value_list RBRACKET
                   array_value shift-reduce 2      array_value_list ::= array_value_list array_value

State 3:
      (1) array_value_list ::= *
          array_value_list ::= * array_value_list array_value
          array_declaration ::= LBRACKET * array_value_list RBRACKET

              array_value_list shift        2      
                     {default} reduce       1      array_value_list ::=

State 4:
      (6) program ::= array_list END_TOKEN *

                             $ reduce       6      program ::= array_list END_TOKEN

----------------------------------------------------
Symbols:
    0: $:
    1: INT_LITERAL
    2: LBRACKET
    3: RBRACKET
    4: END_TOKEN
    5: error:
    6: array_value: INT_LITERAL
    7: array_value_list: <lambda> INT_LITERAL
    8: array_declaration: LBRACKET
    9: array_list: LBRACKET
   10: program: LBRACKET

样本字符串的输出轨迹是:

T__Input 'LBRACKET'
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[LBRACKET array_value_list RBRACKET]
T__Input 'LBRACKET'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 0.
T__Shift 'array_declaration', go to state 1
T__Shift 'LBRACKET', go to state 3
T__Return. Stack=[array_declaration LBRACKET]
T__Input 'INT_LITERAL'
T__Reduce [array_value_list ::=], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'INT_LITERAL'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'INT_LITERAL'
T__Return. Stack=[array_declaration LBRACKET array_value_list INT_LITERAL]
T__Input 'RBRACKET'
T__Reduce [array_value ::= INT_LITERAL], go to state 2.
T__Shift 'array_value'
T__Reduce [array_value_list ::= array_value_list array_value], go to state 3.
T__Shift 'array_value_list', go to state 2
T__Shift 'RBRACKET'
T__Return. Stack=[array_declaration LBRACKET array_value_list RBRACKET]
T__Input 'END_TOKEN'
T__Reduce [array_declaration ::= LBRACKET array_value_list RBRACKET], go to state 1.
T__Shift 'array_declaration'
T__Reduce [array_list ::= array_list array_declaration], go to state 0.
T__Shift 'array_list', go to state 1
T__Shift 'END_TOKEN', go to state 4
T__Return. Stack=[array_list END_TOKEN]
T__Input '$'
T__Reduce [program ::= array_list END_TOKEN], go to state 0.
T__Accept!
T__Return. Stack=]

我被这个错误困住了，我很确定这是一个我不理解的概念错误。感谢您的帮助。

谢谢

Answer 1

您没有在扫描代码中显示 name_str 的定义，但它似乎很可能是一个 char 数组。如果是这种情况，您将面临缓冲区溢出的风险，因为您从不检查以确保 name_length 小于缓冲区大小；此外，您还不如使用 memcpy 而不是 strncpy 因为您已经知道您复制的字符串中没有 NUL 字符。但这些都不是真正的问题:问题是您将每个标记复制到同一个缓冲区中。

您传递给解析器的是以 NUL 结尾的字符串的地址。解析器不复制字符串；它只是将地址存储为 token 的语义值。换句话说，解析器假定它拥有传入的标记字符串，至少在解析完成之前是这样。

但实际上字符缓冲区 (name_str) 归扫描器所有，一旦它把 token 插入解析器，它就假定它可以自由地对字符做任何它想做的事缓冲。也就是用下一个token覆盖buffer。

与野牛不同，当前瞻无关紧要时，柠檬不会立即减少。野牛一看到文字就会将 INT_LITERAL 缩减为 array_value，因为缩减不依赖于前瞻。但是 lemon 总是有一个先行标记，所以它不会将 INT_LITERAL 减少到 array_value 直到它收到下一个标记。不幸的是，如果下一个标记也是 INT_LITERAL，下一个标记将在缩减发生之前覆盖字符缓冲区，因此缩减操作将打印出 下一个 token 。如果下一个标记是 ]，那么字符缓冲区将不会被扫描器覆盖，因此在这种情况下，当前标记将被打印，尽管它已经被前一个标记的减少打印。

一般来说，扫描器无法知道解析器需要 token 值多长时间。对于该问题环境，只有两个明智的所有权策略:

• 扫描仪保留所有权。如果解析器需要保留该值，则它必须制作拷贝。
• 扫描器将所有权传递给解析器，然后解析器必须在完成处理后显式释放 token 。

第一个策略更清晰，因为它不需要两个组件就资源管理协议(protocol)达成一致。但是解析器生成器不太可能包含任何允许实现该策略的机制，因为它需要在解析器函数的顶部采取一些操作。

所以需要使用第二个策略；扫描器必须在新分配的内存中制作 token 字符串的拷贝，并将此内存及其所有权传递给解析器，以便解析器必须(最终)释放该拷贝。出于同样的原因，大多数功能正常的 bison 解析器都使用相同的协议(protocol)，并且在未制作拷贝时发生的各种错误可能是最常见的模糊 bison 错误。

当然，在这种简单的情况下，您可以通过让扫描器将字符串转换为整数来避免内存管理问题。