parsing - 左递归语法中先找后跟的困惑

Question

最近我遇到了先查找并关注的问题

S->cAd
A->Ab|a

在这里，我对 A 中的第一个感到困惑，其中一个是正确的 {a} ， {empty,a} 因为在 A 的生产中存在左递归。我很困惑是否在 A 的第一个中包含空字符串 任何帮助将不胜感激。-------------编辑---------------

什么将是第一个和后面的，这是我见过的如此令人困惑的语法

S->SA|A
A->a

我需要使用解析表证明此语法不在 LL(1) 中，但由于我没有在单个单元格中获得 2 个条目而无法做到。

Answer 1

首先，您需要删除左递归导致

S -> cAd
A -> aA'
A' -> bA' | epsilon

然后，你可以计算

FIRST(A) = a         // as a is the only terminal nderived first from A.

EDIT :-

对于你的第二个问题，

S -> AS'
S' -> AS' | epsilon
A -> a

FIRST(A) = a
FIRST(S) = a
FIRST(S') = {a,epsilon}.

在计算之前删除左递归的想法FIRST()可以FOLLOW()在这里学习。