如何实现左递归消除器？ [英] How to implement a left recursion eliminator?

问题描述

如何实现这个删除器？

 A := AB |
      AC |
      D  |
      E  ;

推荐答案

这是所谓的 immediate左递归，并按如下方式删除：

This is an example of so called immediate left recursion, and is removed like this:

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

基本思想是首先注意当解析 A 你必须以 D 或 E 开头。在 D 或 E 之后，您将结束（尾部为ε）或继续（如果我们在 AB 或 AC 构建）。

The basic idea is to first note that when parsing an A you will necessarily start with a D or an E. After the D or an E you will either end (tail is ε) or continue (if we're in a AB or AC construction).

这样工作：

对于任何向左递归的生产，像这样： A - > A a1 | ... | A ak | b1 | b2 | ... | bm 使用 A - >替换生产。 b1 A'| b2 A'| ... | bm A'并添加生产 A' - > ε| a1 A'| ... | ak A'。

For any left-recursive production like this: A -> A a1 | ... | A ak | b1 | b2 | ... | bm replace the production with A -> b1 A' | b2 A' | ... | bm A' and add the production A' -> ε | a1 A' | ... | ak A'.

查看 Wikipedia：Left Recursion 有关消除算法的更多信息（包括消除间接左递归）。

See Wikipedia: Left Recursion for more information on the elimination algorithm (including elimination of indirect left recursion).

这篇关于如何实现左递归消除器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！