1

更新了更多信息

我在用 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] = '\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=]

我被这个错误困住了，我很确定这是一个我不理解的概念错误。任何帮助表示赞赏。

谢谢

4

2 回答 2

2

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

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

但实际上字符缓冲区 ( name_str) 归扫描器所有，一旦将令牌推入解析器，它就假定它可以自由地对字符缓冲区做任何事情。这是用下一个令牌覆盖缓冲区。

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

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

  • 扫描仪保留所有权。如果需要保留该值，解析器必须进行复制。
  • 扫描器将所有权传递给解析器，解析器必须在处理完令牌后显式释放令牌。

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

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

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

于 2016-06-28T07:20:21.470 回答
0

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

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

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.
于 2016-06-27T19:29:17.363 回答