回溯如何影响解析器识别的语言？

Question

这不是与学校相关的问题,而是在练习中出现在龙书(编者:原则,技巧和工具)中:

语法:

S :: = aSa | AA

生成除了空字符串之外的所有偶数长度的字符串.

a)构造一个递归下降解析器,为这个语法提供回溯,在aa之前尝试替代aSa.显示S的过程在2,4或8 a上成功,但在6 a上失败.b)您的解析器识别哪种语言？

我很难过.似乎4 a被识别为S,并且S之间的两个a被识别,那么应该识别6 a.我尝试在C中实现解析器,但是这个也能识别所有偶数的a.这并不是没有认识到6个.这项练习有什么用途？

/* A C implementation of Exercise 4.13 in the Dragon Book */

/* The grammar:

   S ::= aSa | aa

*/

/* Construct a recursive-descent parser with backtracking for this grammar 
   that tries the alternative aSa before aa. Show that the procedure for S 
   succeeds on 2, 4, or 8 a's, but fails on 6 a's. 
*/

#include <string.h>
#include <stdio.h>

int S(const char *str, int start, int end);
int aSa(const char *str, int start, int end);
int aa(const char *str, int start, int end);

/* returns 1 if a match, 0 otherwise */
int S(const char *str, int start, int end)
{
  if(aSa(str, start, end))
    return 1;
  else
    if(aa(str, start, end))
      return 1;
  return 0;
}

/* returns 1 if a match, 0 otherwise */
int aSa(const char *str, int start, int end)
{
  int len = end - start;
  if (len < 3)
    return 0;
  if(str[0] != 'a')
    return 0;
  if (!S(str, start+1, end-1))
    return 0;
  if(str[len-1] != 'a')
    return 0;
  return 1;
}

/* returns 1 if a match, 0 otherwise */
int aa(const char *str, int start, int end)
{
  int len = end - start;
  if(len != 2)
    return 0;
  if(str[0] == str[1] && str[0] == 'a')
    return 1;
  return 0;
}

int main()
{
  char str[20];
  printf("Enter a string: \n");
  scanf("%s", str);
  int match = S(str, 0, strlen(str));
  if(match)
    printf("The string %s matches\n", str);
  else
    printf("The string %s does not match\n", str);
  return 0;
}

Answer 1

问题不在于这是一个回溯或递归下降解析器；而在于它是一个回溯或递归下降解析器。问题在于所描述的实现没有正确考虑递归下降解析的外部上下文。这类似于强 LL (SLL) 解析器和 LL 解析器之间的区别。

表现出奇怪行为的最短输入是aaaaaa。

1. 我们从规则开始S，并匹配第^一个 a。
2. 我们调用S.
   • 我们匹配第二^个 a。
   • 我们调用S. 我将省略具体步骤，但关键是调用matches ，这是输入末尾的第三^个S步骤。（请参阅下面的注释。）aaaa a
   • 我们尝试匹配a，但由于已经到达输入的末尾，所以我们返回并仅匹配第 2^个到第 3^个 aa。
3. 我们匹配第 4^个 a。

S关于匹配的内部调用的附加说明aaaa：如果我们知道a在步骤 3 的输入末尾保留 an ，那么对的内部调用S可能会匹配aa而不是aaaa，从而成功解析完整的输入aaaaaa。ANTLR 4 在递归下降解析器中提供了这种“完整上下文”解析能力，并且是第一个能够正确匹配的递归下降 LL 解析器，aa而不是aaaa针对S.

SLL 解析器与此语法匹配^{2 k 。}适当的 LL 解析器（例如 ANTLR 4）与此语法匹配^{2k 。}

Answer 2

即使使用回溯（需要能够倒回输入流），递归下降解析器也不允许向前查看输入的末尾，也不允许从流的两端删除符号。

从左到右的解析器必须能够处理只有一种方法的输入流：

get() : consume and read one symbol, or return an EOF symbol.

回溯版本需要一个带有另外两个方法的流：

posn = tell()  : return an opaque value which can be used in seek()
seek(posn)     : reposition the stream to a previous position returned by tell()