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

fykwrbwg 于 12个月前发布在其他

关注(0)|答案(4)|浏览(96)

这不是一个与学校有关的问题，但它出现在龙书（作者：原则、技术和工具）：
语法：
S：：=阿萨|AA
生成所有偶数长度的字符串，除了空字符串。
a）为这个文法构造一个具有回溯的递归下降解析器，它在aa之前尝试替代阿萨。证明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;
}

来源：https://stackoverflow.com/questions/17456994/how-does-backtracking-affect-the-language-recognized-by-a-parser

4条答案

按热度按时间

d5vmydt91#

问题不在于这是一个回溯或递归下降解析器;问题在于所描述的实现没有适当地考虑递归下降解析的外部上下文。这类似于强LL（SLL）解析器和LL解析器之间的区别。
出现奇怪行为的最短输入是aaaaaa。
1.我们从规则S开始，匹配第一个a。

我们调用S。
我们匹配第二个a。
我们调用S。我将省略具体的步骤，但关键是S的 this 调用匹配aaaa，这是输入末尾的第3个a。（见以下注解。）
我们尝试匹配a，但由于已经到达输入的末尾，我们返回并匹配 * 仅 * 第二个到第三个aa。
我们匹配第四个a。

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

赞(0）回复(0）举报 12个月前

qncylg1j2#

即使使用回溯，这需要能够倒回输入流，递归下降解析器也不允许向前查看输入的结尾，也不允许从流的两端删除符号。
从左到右的解析器必须能够处理只有一个方法的输入流：

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()

赞(0）回复(0）举报 12个月前

yyhrrdl83#

我不可能为了好玩而用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', '')

我想这能帮你理解简短的回答是递归下降是一个非常具体的、有限的东西。这不是一个完整的搜索。
(it这是个好问题这一点很重要好书。）

赞(0）回复(0）举报 11个月前

mv1qrgav4#

[aa]

的分析过程
[a1]

的分析过程
[aaaa]

的分析过程
[aaaaaaaa]

的分析程序
递归下降分析器仅在发生错误时才进行回溯。它忽略了成功是“暂时”的情况。