如果不使用经典方法并将其转换为LL（1），则查找语法不是LL（1） [英] Finding a grammar is not LL(1) without using classical methods and transforming it to LL(1)

问题描述

假设我有这样的语法：

S -> A C x | u B A
A -> z A y | S u | ε
B -> C x | y B u
C -> B w B | w A

此语法显然不是LL（1），我可以找到它来构造解析表。但是，如果不使用经典方法，即不构造解析表或发现任何冲突，有什么方法可以证明该语法不是LL（1）？

This grammar is obviously not LL(1), which i can find constructing the parsing table. But is there any way i can prove that this grammar is not LL(1) without using the classical methods i.e. without constructing the parsing table or finding any conflicts?

我该如何将该语法转换为LL（1）？我认为我必须同时使用epsilon推导消除法和左递归消除法，但这有点棘手，而且我尝试过很多次，都无法将其转换为LL（1）。

Also how can i convert this grammar to LL(1)? I think i have to use both epsilon-derivation elimination and left recursion elimination but its a bit tricky and as many times i've tried i couldn't transform it to LL(1).

谢谢。

推荐答案

都 S / A 和 B / C 涉及间接左递归。

Both S/A and B/C involve indirect left-recursion.

由于任何 k 的左递归语法（直接或间接）都不是LL（k），因此可以通过以下方式证明该语法不是LL（1）：显示左递归循环。 （另一方面，如果您有一个计算FIRST和FOLLOW集的工具，那么经典方法确实非常简单。）

Since no left-recursive grammar (direct or indirect) is LL(k) for any k, you can prove the grammar is not LL(1) simply by showing the left-recursive cycle. (On the other hand, if you have a tool which computes FIRST and FOLLOW sets, the "classical" method is really very simple.)

首先要消除间接左递归找到一种可能的非末端拓扑结构，然后通过用其右侧替换非末端的某些用法来打破导数循环。之后，可以应用简单的左递归消除算法。

Eliminating indirect left recursion involves first finding one possible topological sort of the non-terminals and then breaking the derivation cycle by substituting some uses of a non-terminal with its right-hand side. After that, the simple left recursion elimination algorithm can be applied.

您可以找到此转换的具体示例在StackOverflow上，或此处，或其他任何有关解析理论的教科书。 （或者，当然，通过搜索间接左递归一词并查找具有一定可信度的页面。）

You can find concrete examples of this transformation here on StackOverflow, or here, or in any good textbook on parsing theory. (Or, of course, by searching for the term "indirect left recursion" and looking for pages with some credibility.)

这篇关于如果不使用经典方法并将其转换为LL（1），则查找语法不是LL（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！