S→S + aF|aF| + aF
回溯过程详细一点!!
为什么是
S->aFS'|+aFS'
S'->+aFS'|ε
这里看不懂啊
S → S + aF | aF | aF
为了处理该文法中的左递归和避免回溯,我们可以对其进行改写。具体来说,我们需要先找到这个文法中的左递归部分,然后将其转化为右递归形式。在此过程中,可能还需要添加新的非终结符号,以便更好地表示文法的含义。
回到原始的文法,我们可以看到它存在三个产生式,其中两个产生式都以“a”开头。因此,我们可以提取出共同的前缀“a”,得到以下的文法:
现在我们已经将左递归部分提取了出来,并将其转化为右递归的形式。同时,为了防止回溯,在 S' 的第一个产生式中使用了一个新的非终结符号“S'”,表示 S 可以选择继续匹配加号(+)和 aF 去匹配更多的符号串,或者不选择,直接返回上一级。此处的“ε”表示可以匹配空串。
根据这个文法,我们可以生成如下的推导过程:
在上述过程中,我们首先选择 S 作为起始符号,然后根据这个文法选择第一个产生式,生成 aF S'。接下来,我们可以选择使用 S' 的第一种产生式,继续匹配加号和 aF,或者选择使用 S' 的第二种产生式,回溯到上一级。