8

不是学校相关的问题，但它出现在Dragon Book（编译器：原理，技术和工具）中的一个练习中：

语法：

S ::= aSa | 啊

生成除空字符串外的所有偶数长度字符串。

a) 构造一个带有回溯的递归下降解析器，用于在 aa 之前尝试替代 aSa 的语法。证明 S 的过程在 2、4 或 8 个 a 上成功，但在 6 个 a 上失败。b) 你的解析器能识别什么语言？

我难住了。似乎如果 4 个 a 被识别为 S，并且一个 S 之间的两个 a 被识别，那么 6 个 a 应该被识别。我尝试在 C 中实现解析器，但这个解析器也可以识别所有偶数的 a。识别 6 a 并不是失败。这个练习的目的是什么？

/* 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;
}
4

4 回答 4

5

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

显示奇怪行为的最短输入是aaaaaa.

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

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

SLL 解析器匹配此文法的2 k。适当的 LL 解析器（例如 ANTLR 4）匹配此文法的2k。

于 2013-07-04T01:27:39.450 回答
3

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

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

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()
于 2013-07-03T20:07:44.807 回答
2

我不可能为了好玩而用 c 写这个，但这是用 python 编写的解析器，尽可能简单（我希望它像伪代码一样清晰，即使你不知道这种语言）：

class Backtrack(Exception): pass

def asa(input):
    if input[0:1] == 'a':
        parsed, remaining = s(input[1:])
        if remaining[0:1] == 'a':
            return 'a' + parsed + 'a', remaining[1:]
    raise Backtrack

def aa(input):
    if input[0:2] == 'aa':
        return 'aa', input[2:]
    raise Backtrack

def s(input):
    try:
        return asa(input)
    except Backtrack:
        return aa(input)

for i in range(17):
    print(i, ': ', end='')
    try:
        print(s('a' * i))
    except Backtrack:
        print('failed')

结果为length: (parsed, remaining)：

0 : failed
1 : failed
2 : ('aa', '')
3 : ('aa', 'a')
4 : ('aaaa', '')
5 : ('aa', 'aaa')
6 : ('aaaa', 'aa')
7 : ('aaaaaa', 'a')
8 : ('aaaaaaaa', '')
9 : ('aa', 'aaaaaaa')
10 : ('aaaa', 'aaaaaa')
11 : ('aaaaaa', 'aaaaa')
12 : ('aaaaaaaa', 'aaaa')
13 : ('aaaaaaaaaa', 'aaa')
14 : ('aaaaaaaaaaaa', 'aa')
15 : ('aaaaaaaaaaaaaa', 'a')
16 : ('aaaaaaaaaaaaaaaa', '')

我怀疑这会帮助你理解。简短的回答是递归下降是一个非常具体、有限的事情。这不是一个完整的搜索。

（这确实是一个好问题。提出了一个重要的观点。好书。）

于 2013-07-04T01:03:08.973 回答
1

aa的分析流程

aaa的分析流程

aaaaa的分析流程

aaaaaaaa的分析流程

递归下降解析器仅在发生错误时回溯。它错过了成功是“暂时”的情况。

于 2018-03-24T14:29:02.630 回答