如何实现左递归消除器？

发布于 2024-09-05 12:38:27 字数 89 浏览 9 评论 0原文

我该如何为此实施消除器？

 A := AB |
      AC |
      D  |
      E  ;

原文

How can i implement an eliminator for this?

 A := AB |
      AC |
      D  |
      E  ;

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

傾旎 2024-09-12 12:38:27

这是所谓的立即左递归的示例，并按如下方式删除：

A := DA' |
     EA' ;

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

基本思想是首先注意，在解析 A 时，您必须以 <代码>D 或E。在 D 或 E 之后，您将结束（尾部是 ε）或继续（如果我们处于 AB 或 AC 结构）。

实际的算法是这样工作的：

对于任何像这样的左递归产生式： A ->一个 a1 | ... |一个AK | b1 | b2 | ... | bm 将产生式替换为 A ->; b1 A' | b2 A' | ... | bm A' 并添加产生式 A' -> ε | a1 A'| ... |又名 A'。

有关消除算法（包括消除间接左递归）的更多信息，请参阅维基百科：左递归。

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

A := DA' |
     EA' ;

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

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

The actual algorithm works like this:

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'.

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

回复收藏 0 原文

毅然前行 2024-09-12 12:38:27

另一种可用的形式是：

A := (D | E) (B | C)*

执行此操作的机制大致相同，但某些解析器可能会更好地处理该形式。还要考虑如何将动作规则与语法本身一起修改；另一种形式需要分解工具为 A' 规则生成新类型以返回此形式不需要的位置。

Another form available is:

A := (D | E) (B | C)*

The mechanics of doing it are about the same but some parsers might handle that form better. Also consider what it will take to munge the action rules along with the grammar its self; the other form requires the factoring tool to generate a new type for the A' rule to return where as this form doesn't.

回复收藏 0 原文

~没有更多了~