回溯如何影响解析器识别的语言？
回溯如何影响解析器识别的语言？
提问于 2013-07-04 03:55:02
这不是一个与学校相关的问题，但它在Dragon Book (编译器:原则、技术和工具)的一个练习中出现了：
语法：
S ::= aSa | aa
生成除空字符串以外的所有偶数长度字符串。
a)构造一个递归下降解析器，对此语法进行回溯，在aa之前尝试替代aSa。说明S的过程在2个、4个或8个a上成功，但在6个a上失败。b)您的解析器识别哪种语言？
我被难住了。似乎如果4a被识别为S，并且S之间的两个a被识别，那么6a也应该被识别。我试着用C语言实现解析器，但是这个解析器也能识别所有偶数的a。它并不是不能识别6a。这个练习的目的是什么？
/* 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;
}回答 3
Stack Overflow用户
回答已采纳
发布于 2013-07-04 04:07:45
即使使用回溯，也不允许递归下降解析器向前看输入的末尾，也不允许从流的两端删除符号。
从左到右的解析器必须能够处理只有一种方法的输入流：
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()Stack Overflow用户
发布于 2013-07-04 09:03:09
我不会为了好玩而用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', '')我想这会帮助你理解。简而言之，递归下降是一个非常具体、有限的东西。这不是一个完整的搜索。
(这是一个很好的问题。提出了一个重要的观点。好书。)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17456994
复制相关文章
相似问题
腾讯云开发者
