预测解析器LL(1)条件
-
29-09-2020 - |
题
让我们说我们使用预测解析器LL(1)。为什么有必要
$ figly(\ alpha)\ cap first(\ beta)=imptyset $ ,
对于所有 $ \ alpha,\ beta $ 右侧的替代产品I.,与相同的非终端相关联的产品。为什么这种条件是必要的?
解决方案
这是一个直观的解释:
它基本上介绍了LL(1)解析器的性质:LL(1)解析器构建LL(1)解析表。表的行是非终端的,并且列是终端。我们可以考虑LL(1)解析为执行LL(1)表查找在遇到输入中的每个符号时:我们查看由当前非终端和输入端确定的条目,并应用相应的生产规则。因此,LL(1)表不能在每个条目处包含多个生产规则,否则,解析器无法确定要应用的规则。
如果生产的右侧 $ \ alpha $ , $ \ beta $ 才有相交第一个集合,然后我们在LL(1)表中的单个条目处有多个规则(即,重复/冲突条目)---具有第一组的非活动交叉点基本上防止我们构建LL(1)解析表。
如果您仍然不清楚为什么需要这种情况,我建议您构建一个与生产右侧的第一个集合的一个例子,然后尝试手动构建一个ll (1)解析表或使用其中一个在线可视化工具你会立即找到冲突。
不隶属于 cs.stackexchange