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 获取标记，为每个标记调用解析器的代码是

  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] = '[=11=]';
      //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

无法从您提供的解析器定义中生成 Lemon 解析器。它允许递归列表 array_value_list 的终端元素 array_value 为空。解析器可以减少这条规则不定式的次数和报告解析冲突。

为了解决冲突，切换到空列表规则的概念而不是空元素。这是 lemon 文档中推荐的列表的左递归定义：

list ::= .
list ::= list element.

将此模式应用于您的解析器会得到下一个结果：

array_value ::= INT_LITERAL(A). {printf("Array value: %s\n", A);}
array_value_list ::= .
array_value_list ::= array_value_list array_value.
init_array ::=. {printf("Init Array\n");}
end_array ::=. {printf("End Array\n");}
array_declaration ::= init_array LBRACKET array_value_list RBRACKET end_array.
array_list ::= array_declaration.
array_list ::= array_list array_declaration.
program ::= array_list END_TOKEN.

Answer 2

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

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

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

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

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

扫描仪保留所有权。如果解析器需要保留该值，则必须进行复制。

扫描器将所有权传递给解析器，解析器在使用完令牌后必须显式释放令牌。

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

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

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

Lemon Parser 会跳过一些东西（或者我的误解）

Lemon Parser skips things (Or my misunderstanding)

c++

parsing

grammar

lemon

更新了更多信息