如何判断语言是否为LL(1)LR(0)SLR(1)
首先，我们需要了解什么是LL(1)、LR(0)和SLR(1)。
- LL(1)：LL(1)是一种自顶向下的语法分析方法，它使用了预测分析的方法，并且在每个产生式的左侧添加了一个预测符号。
- LR(0)：LR(0)是一种自底向上的语法分析方法，它使用了预测分析的方法，并且在每个产生式的左侧添加了一个预测符号。
- SLR(1)：SLR(1)是一种自底向上的语法分析方法，它使用了预测分析的方法，并且在每个产生式的左侧添加了一个预测符号。
要判断一个语言是否为LL(1)、LR(0)或SLR(1)，我们需要进行以下步骤：
- 构造预测分析表：根据语言的文法，构造预测分析表。
- 检查分析表：检查分析表中的每个条目，确保它们都是唯一的。
- 检查冲突：检查分析表中的每个条目，确保它们都没有冲突。
如果一个语言是LL(1)、LR(0)或SLR(1)，那么它的文法是LL(1)、LR(0)或SLR(1)文法。如果一个语言的文法是LL(1)、LR(0)或SLR(1)文法，那么它可以被自顶向下或自底向上的语法分析器分析。
总之，要判断一个语言是否为LL(1)、LR(0)或SLR(1)，我们需要构造预测分析表，并检查分析表中的每个条目。如果分析表中的每个条目都是唯一的，并且没有冲突，那么该语言是LL(1)、LR(0)或SLR(1)。
相关·内容
我真的在努力理清以下之间的关系：
LR(0)
LL(0)
LALR(1)
SLR(1)
LR(1)
LL(1)
我很确定LALR(1)和SLR(1)是LR(1)的子集，但是我对其他的都迷茫了。它们都是独家的吗？LL(0)是LL(1)的子集吗？
谢谢
浏览 0提问于2016-04-15得票数 8
回答已采纳
有没有一种简单的方法来确定一个文法是否是LL(1)，LR(0)，SLR(1)……仅仅看语法而不做任何复杂的分析？
例如:要确定BNF语法是否为LL(1)，您必须先计算集合，然后再计算集合-在某些情况下，这可能很耗时。
有没有人知道如何更快地做到这一点？任何帮助都将不胜感激！
浏览 12提问于2009-01-24得票数 23
回答已采纳
如何识别语法是LL(1)、LR(0)还是SLR(1)？
有人能用这个例子或其他例子来解释它吗？
X→Yz _a
Y bZ→ε
Z→ε
浏览 16提问于2011-12-13得票数 77
回答已采纳
7回答
我知道LL和LR解析器的基本区别。我还知道GLR、SLR和LALR都是LR解析器的扩展。所以我更详细的问题是...
给定LL(*)解析器和LR解析器的任何变体，有没有一种语言可以用其中一种描述，而不能用另一种描述？或者更简单地说，是否有任何特性或属性不能用其中任何一个来表示？
作为一个具体的例子。如果我使用LL(*)解析器创建一种语言，我是否会遇到我想要添加到我的语言中的所需功能/属性，而这些功能/属性只有使用LR解析器才能实现(反之亦然)？
浏览 0提问于2011-03-29得票数 13
回答已采纳
1回答
这是语法SLR(1)吗？
、、、
我使用为这个LL(1)/LR(1)文法生成SLR(1)解析表(它生成一个小的XML子集)：
document ::= element EOF
element ::= < elementPrefix
elementPrefix ::= NAME attribute elementSuffix
attribute ::= NAME = STRING attribute
attribute ::= EPSILON
elementSuffix ::= > elementOrData endTag
elementSuffix ::= />
elementOrData ::= <
浏览 0提问于2016-10-30得票数 0
在许多地方(例如，在这个答案中)，我看到一个LR(0)语法不能包含ε生成。
在中，我也看到过这样的语句:ε免费LL(1)语法也是SLR(1)。
现在，我所面临的问题是，我无法推理出这些说法背后的逻辑。
我知道LR(0)语法通过空堆栈接受DPDA接受的语言，即它们接受的语言必须具有前缀属性。但是，如果我们假设结束标记，并且在给定任何语言时，前缀属性将始终得到满足，则可以处理该前缀属性。许多文本，如Sipser的“计算理论”()，都认为这是一个简单的论点。话虽如此，我们还是可以说(非正式的？)如果LR(0)项的规范集合中没有状态，则语法为LR(0)，这些项具有shift-还原冲突或约简冲突。
在
浏览 9提问于2022-01-16得票数 1
回答已采纳
1回答
由于LR (1)语法比LALR或SLR语法更广泛，我对LR语法的证明有疑问。如果语法是SLR或LALR，那么这是否意味着语法也是LR (1)？
事实上，由于使用查找头的方法执行起来比较复杂，因此我可以使用SLR方法(不带前瞻性)或LALR方法来证明语法是LR (1)。
浏览 11提问于2022-07-08得票数 1
4回答
我有以下语法，据说是LR(1)，但没有SLR(1)：
S ::= a A x b A c_b_b d_a
A ::= d
我不明白这是为什么。你怎么证明这个？
浏览 19提问于2012-05-08得票数 7
1回答
假设你有一个语法G，我们为它找到一个LR(1)自动机。我们可以通过执行状态合并和转换规则将其转换为LALR(1)或SLR(1)解析器，但可能会出现冲突。
我的问题是：必须在合并状态中出现所有问题？在LALR(1)或SLR(1)自动机中没有合并的非冲突LR(1)状态是否可能有冲突？
浏览 10提问于2022-05-16得票数 1
回答已采纳
2回答
有人问我LL(3)是否是LR(2)的子集，反之亦然。
我成功地证明了LL(3)不是LR(2)的子集：
在LL(3)中，我们可以在读取开头后面的3个字符后识别规则。
在LR(2)中，我们可以在读取超过结尾的2个字符后识别规则。
因此，假设规则是空的，那么LL(3)会比LR(2)给我们更多的信息。因此，LL(3)不包含在LR(2)中。
我如何证明另一种方式呢？
浏览 3提问于2013-04-27得票数 1
我注意到了一些有趣的事情，但我不确定它是否会这样发生。
我得到了一些使用fgetc()；从文件中读取符号并将它们存储到int中的代码，比如l；
l=fgetc(file);
文件以读二进制模式(“rb”)打开；使用
file=fopen("filename", "rb");
然后使用字符串流将每个符号转换为十六进制格式并发送到字符串中，然后存储在字符数组中；
std::stringstream sl;
sl << std::hex << l; sl >> sll;
char as[i]=sll[i
浏览 0提问于2016-10-19得票数 2
回答已采纳
1回答
我必须创建一个C++程序来显示编译器设计中SLR解析中的有效LR(0)项。到目前为止，我能够将语法作为用户的输入，并找到它的闭包。但是我不能继续在SLR中实现goto。谁可以提供我的链接或代码，如何显示有效的LR(0)项目的语法。
提前使用-Thanks
浏览 2提问于2011-03-13得票数 2
众所周知，SLR(1)解析器通常比LR(1)具有更少的状态。但是，与LR(1)相比，在SLR(1)解析器中查找导致冲突的字符串是更容易还是更难呢?为什么？
提前谢谢你。
浏览 15提问于2018-12-16得票数 0
1回答
找到一个等价的LR语法
、、、、
我试图为pascal找到LR(1)或LR(0)语法。这里是我语法的一部分，它不是LR(0)，因为它有移位/减少冲突。
EXPR --> AEXPR | AEXPR realop AEXPR
AEXPR --> TERM | SIGN TERM | AEXPR addop TERM
TERM --> TERM mulop FACTOR | FACTOR
FACTOR --> id | num | ( EXPR )
SIGN --> + | -
(大写单词是变量，小写词，+，- are终端)
正如您所看到的，EXPR --> AEXPR | AEXPR rea
浏览 2提问于2015-12-30得票数 0
回答已采纳
2回答
我从我们的老师那里得到了一个假设，他希望我们去寻找并验证它。我们有SLR(1)和LALR(1)解析器。假设是：
假设我们有一个名为X的语言结构，如果我们不能为这个结构提供一个LALR(1)语法，我们也不能提供一个SLR(1)，也许LR(1)语法可以解决问题。但是如果我们能为这个结构提供一个LALR(1)文法，我们也可以提供一个SLR(1)。
如果你在互联网上搜索，你会发现很多网站说这种语法不是SLR(1)，而是LALR(1)：
S -> R
S -> L = R
L -> * R
L -> id
R -> L
("id“、"*”和"=
浏览 2提问于2019-05-17得票数 0
回答已采纳
我正在尝试实现Warshall的算法，以快速计算LR(1)闭包。
我想我理解LR(0)的工作原理：
图的节点是，类似于A → B • C
边缘是从A → B • C到C → • D的“过渡”。
问题是，LR(1)需要计算查找头，而我不知道如何将它们合并到算法中。
在我看来，即使我知道任何给定LR项的传递闭包，我仍然需要进行所有相同的计算，以确定每个项的前瞻性设置是什么。
甚至可以使用Warshall的算法来计算标准LR(1)闭包，还是只可能对更多的受限情况(如LR(0)、SLR(1)等)进行计算？
浏览 2提问于2013-06-08得票数 7
回答已采纳
1回答
我正试图解答有关LR(1)语法的问题：
S->AA
A->Aa
A-> b
我被困在第四州时：
S-> AA. ,$
A-> A.a ,$
A->.Aa ,$
A->.a ,$
a和A转移到其他状态，A在相同的状态下减少，我是否应该考虑这种语法不是LR(1)和SLR(1)，因为这种冲突？
浏览 0提问于2015-03-10得票数 0
回答已采纳
这些语法是如何相互联系的呢？例如，SLR是LALR1的一个子集。有没有什么固定的方法来解决它们之间的关系？
浏览 0提问于2011-01-19得票数 6
回答已采纳
1回答
我写了以下语法：
S->S ( S ) S
S->e
E代表“空字符串”。
因此，这个语法识别的语言包括所有字符串，都有匹配的左括号和右括号，比如()、(())、(())等等。
这个语法不是SLR，以下是我如何构造SLR解析表：
增加这种语法：
S1->S -> S->S(S) S ->e
然后为它构造LR(0)自动机：
I0: S1->.S ->. S->.S(S) S ->.e
I1: S1-> S ->S.(S)S
..。
请注意，对于I0，输入符号'(‘)不存在移位或减少操作，这是该语法生成
浏览 5提问于2013-04-07得票数 0
回答已采纳
1回答
是否有可能构建一个LR(0)解析器，它可以同时解析具有前缀和后缀运算符的语言？例如，如果我有一个+(加法)和！具有通常优先级的(阶乘)运算符，然后是1+3！应该是1+ 3！=1+6= 7，但是如果解析器是LR(0)，那么当它在堆栈上有1+3时，它会减少而不是移位？
另外，正确的结合运算符会带来问题吗？例如，2^3^4应该是2^(3^4)，但是同样地，当解析器的堆栈中有2^3时，它怎么知道是缩减还是移位呢？
如果这是不可能的，是否还有一种方法可以使用LR(0)解析器，可能是通过修改语法在适当的位置添加括号？
浏览 5提问于2012-08-29得票数 1
1回答
所有的LL文法都是LR文法，但不是反过来，但我仍然在努力处理区别。我对没有等价LL表示的LR文法的小示例感到好奇。
浏览 0提问于2012-01-11得票数 19
回答已采纳
有人告诉我这句话是假的，但我认为这是真的。
考虑在LR(0)中没有SR冲突的文法，那么它在SLR(1)中也不应该有SR冲突，因为它比LR(0)更强大。因此，在这种情况下，两者的SR冲突是相等的。因此，给定的语句应该是正确的。我是不是搞错了？
浏览 9提问于2021-12-03得票数 0
它的时间复杂度似乎是O(nlogn)，因为我们首先对数组进行排序，然后执行4指针方法(在时间复杂度上是线性的)。
它们使用4个指针LL、LR、RR和RL，其中4个指针的和被加起来，并且根据最优的运动，他们选择相应地移动指针。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n = 8;
int a[n] = {1, 2, 3, 4, 6, 5, 7, 8};
int x = 16;
sort(a, a + n);
for
浏览 16提问于2022-05-17得票数 0
我的英语能力很差，因为我不是说英语的人。请理解。
我写这篇文章是因为我想讨论这个话题。
我认为LR解析器与LL解析器相比没有“实际”优势。许多工具使用LR解析器这一事实并不是一个有效的优势。
我认为实际优势的标准如下。
速度(快速->实用，慢->不切实际)
错误恢复(容易的->实用，困难的->不切实际)
编译器错误显示的方便性(容易->实用，困难->不实用)
解析器开发的成本(简单的->实用，困难的->不切实际)
我认为LL解析器和LR解析器的速度没有太大的不同。LR解析器比LL解析器速度快得多，因为过去的硬件性能很低。但在今天，LR解析器的速度
浏览 0提问于2020-11-26得票数 7
回答已采纳
1回答
如果下一个输入符号没有转换(因为它没有前瞻性)，那么LR(0)-Parsers是否简单地减少了？
SLR(1)-Parsers使用产品的后续集合作为前瞻性是正确的吗？
它是正确的，LR(1)-Parsers使用的是第一，而不是的后继集作为展望？
closure算法清楚地使用了FIRST
closure(S)
For each item [A → α ⋅ B β, t] in S,
For each production B → γ in G,
For each token b in FIRST(βt),
Add [B → ⋅ γ, b] to S
浏览 0提问于2017-10-18得票数 1
回答已采纳
考虑下面的语法
S -> for id:= E to E by E do S end
S -> other
E -> num
假设上面的语法是LL(1)，也是SLR(1)。
在自下而上的解析器中，如“编译器”一书中的Pr.Alfred.Vho，“原则和技术与工具”规定，我们在一次翻译中使用额外的产生规则(M -> e)来增加语法，以翻译条件跳转而不是条件跳转。
S -> for id:= E M to E by E do S M end M
S -> other
E -> num
M -> e {Semantic Action()}
正如您所看
浏览 4提问于2020-08-02得票数 0
回答已采纳
1回答
我对Python还比较陌生。我在做一个创建物体，广场和点的项目。正方形由左上角、右上角等4个点组成。
现在，在我的主要函数中，我创建了4个点对象，并将它们发送到Square类的构造函数中，它创建了我的Square。
当我对另一个对点对象有不同值的平方做同样的操作时，我以前创建的Square的值会被覆盖，所以在最后我有两个相同的对象。你知道为什么会这样吗？
这是我的密码：
class Point(object):
def __init__(self, x = 0, y = 0):
self.x = x
self.y = y
class Square(ob
浏览 2提问于2014-04-02得票数 1
回答已采纳
1回答
LL(1)-parser需要一个前瞻性符号来决定使用哪种产品。这就是为什么我总是认为“展望”这个词是使用的，当解析器查看下一个输入令牌而不“消费”它(也就是说，它仍然可以在下一个操作中从输入中读取)。然而，LR(0)解析器使我怀疑这是否正确：
我看到的LR(0)-parsers的每个例子都使用下一个输入令牌来决定是移位还是减少。在减少的情况下，不消耗输入令牌。
我使用免费软件工具"ParsingEmu“生成LR表，并在下面对单词"aab”执行LR评估。如您所见，列头包含标记。从计算中可以看到，解析器通过查看下一个输入令牌来决定使用哪一列。但是，当解析器在步骤4-6中减少时，输入
浏览 3提问于2015-03-14得票数 4
回答已采纳
7回答
LL解析器与LR解析器相比有哪些优势来保证它们在中的相对流行
根据的说法，LR解析似乎比LL更有优势：
LR语法分析能够处理比LL语法分析更广泛的语言，并且在错误报告方面也更好，即当输入不符合语法时，它会检测语法错误。这与LL(k) (甚至更糟糕的是LL(*)解析器)形成了对比，后者可能会由于回溯而将错误检测推迟到语法的另一个分支，这通常会使错误更难在具有长公共前缀的析取之间定位。
注:这不是作业。当我发现Antlr是一个LL解析器生成器(尽管它的名字中有"LR“！)时，我感到很惊讶。
浏览 3提问于2010-11-03得票数 38
回答已采纳
作为家庭作业，我得到了以下语法：
S: D
D: AbBb | BaAb
A: ε
B: ε
我使用LL(1)很好地计算了它。第一组是：
S: a, b
D: a,b
A: ε
B: ε
以下集合是：
S: $
D: $
A: b
B: a,b
当我创建解析表时，示例字符串"ab“解析得很好。但是，当我尝试使用LR(1)解析相同的语法时，我遇到了错误。
对于项目集0，我得到了以下内容：(，分隔先行终端)
Item set 0:
S: .D, $
D: .AbBb, $
D: .BaAb, $
A: ., b
B: ., a,b
如果你制作了表格，你会清楚地看到在项目集0中A和B
浏览 5提问于2019-11-05得票数 1
1回答
我还没找到答案。是否有上下文自由且不含糊的语法不能转换为LL(1)？
我发现了一个无法转换为LL(1)的产品:C99中的C99产品：
parameter-type-list:
parameter-list
parameter-list , ...
这是一个没有LL(1)等价的LR(k)语法的例子，还是我做错了什么？
编辑:我复制了错误的名称，我想复制参数声明：
parameter-declaration:
declaration-specifiers declarator
declaration-specifiers abstract-declarator(op
浏览 2提问于2015-07-17得票数 4
1回答
我有一个低分辨率图像(sLR)，这是由选择中心部分的参考高分辨率图像(sHR)在频率(k-空间)域中的行方向。当我在频域上对这幅低分辨率图像进行零点处理时，我得到了空域上的振铃伪影。我试图通过使用Hamming窗口过滤图像来删除这个工件。请看下面的代码。我对将fft和ifft应用于图像和过滤过程有疑问，如果有人能检查我的代码并确认它是正确的，我将非常感激。
% sHR: HR reference image
n = size(sHR,1);
kspHR = fftshift(fft(sHR,n,1),1)/n; % HR image in k-space
% Generating LR im
浏览 5提问于2017-11-07得票数 0
回答已采纳
在我目前的编译器课程中，我已经了解了如何找到语法的第一组和后续组，到目前为止，我处理过的所有语法都包含epsilon。现在我被要求找到没有epsilon的文法的第一组和后续组，并确定它是否是LR(0)和SLR。没有epsilon已经把我弄丢了，所以我不知道我做得是否正确。我非常感谢任何关于我是否在第一个和后续集合的正确轨道上的评论，以及如何开始确定它是否是LR(0)。
考虑下面描述Lisp算法的语法：
S -> E // S是开始符号，E是表达式
E -> (FL) // F是数学函数，L是列表
L -> LI |I // I是列表中的一项
I -> n|E //项是数
浏览 0提问于2016-03-24得票数 0
对于一些主要的解析算法(LL(1)，LR(1)，LR(0)，LALR(1))，是否有很好的在线资源来收集语法？我已经找到了许多属于这些家族的单独的语法，但我不知道有人编写了大量示例语法的好资源。
有没有人知道这样的资源？
浏览 2提问于2011-06-26得票数 60
回答已采纳
2回答
编写编译器
、、、、
我基本上需要为bibtex文件做一个编译器，这样就可以查询给定的bibtex数据库。现在我熟悉了理论的某些方面，比如自动机、语法、SLR、LR(1)和LALR解析。然而，我仍然觉得所有这些都是理论和抽象的，因为我从未应用过它。如果有人能勾勒出构建编译器所需的坚实步骤，那将会有很大帮助。我可能会使用flex和bison/yacc，所以如果你能让我知道设计过程是如何进行的，在哪个阶段生成什么文件，每个阶段的输出是什么，以及事情是如何联系在一起的，我可能会对事情是如何完成的有一个更实际的看法……
谢谢!
浏览 2提问于2011-03-17得票数 1
回答已采纳
1回答
我正在编写算法，必须在这个数字中计数方格：
在数据库中，我有以下列的所有点：x-coordinate、y-coordinate、toRight、toLeft、up和down。toRight，toLeft等都是布尔人，这意味着你可以从那个点向那个方向移动。
然而，我不清楚如何利用关于方向的信息。我现在有这样的代码：
public function count(array $points)
{
$pointsGroupedByX = array();
$edges = array();
foreach ($points as $point) {
浏览 0提问于2019-05-05得票数 1
回答已采纳
1回答
我有以下语法，它是的一个小子集
chunk -> | chunk stat.
stat -> var `=´ exp.
var -> Name | exp `[´ exp `]´.
exp -> var | exp `(´ exp `)´ | `(´ exp `)´.
根据的说法，这种语法不是LR(1)，因此？不是LALR(1)，SLR(1)，LR(0)或LL(1)。
这个语法有歧义吗？如果是的话，请给出一个模棱两可的句子的例子。如果不是，是否有充分的理由说明为什么不是LR(1)？
编辑：--一个稍微简化的语法，它展示了同样的问题：
stat -> exp
浏览 2提问于2016-07-17得票数 2
回答已采纳
1回答
为k>1制作人工LR(k)语法很容易：
Input: A1 B x
Input: A2 B y (introduce reduce-reduce conflict for terminal a)
A1 : a
A2 : a
B : b b b ... b (terminal b occurs k-1 times)
然而，是否有任何真实的非LR(1)计算机语言是LR(k > 1)-parsable？
还是非LR(1)语言也不是LR(k)？
浏览 3提问于2013-11-26得票数 3
回答已采纳
1回答
我想对此进行编码，但我被卡住了
假设我们有一个语法
S→x|LR|LT
T→SR
L→(
R→)
下面是列表在每次循环后的样子：
0 steps: [ S ]
1 step: [ x, LR, LT ]
2 steps: [ (R, L), (T, LSR ]
3 steps: [ (), (), (SR, (SR, LxR, LLRR, LLTR, LS) ]
诸若此类
假设我想检查字符串"(xx)“是否在语法中，所以我将进行2n-1次迭代，即2x4-1=7步。
我遇到了如何编写代码来查看以下内容的问题：
假设我在第2步，现在我想扩展LR。我在LR上循环，并将L扩展为相应的RHS值
浏览 15提问于2020-02-13得票数 0
回答已采纳
4回答
实现逻辑移位
、、、
因此，我正在研究nand2tetris项目，并且我希望在软件级别上实现正确的转换逻辑，因为硬件不支持它。
我知道右移逻辑是除以二。因此，我第一次尝试实现它时，会计算出在值变为0或负值之前，我能够从初始值减去2的次数。如果数字为负数，则类似。
但是，我发现了一种不起作用的情况。我想右转-27139。移动后的二进制值是19199。应该是19198。因此，我正在寻找一种新的方式来实现这一转变。
我可以and值、or值、add和subtract，这是我所拥有的一切。
超临界水
下面是我在Hack实现的汇编语言中的代码：
//=======================================
浏览 0提问于2014-02-11得票数 0
回答已采纳
2回答
我正在根据以下语法编写SLR(1)解析器：
1) S -> aSb
2) S -> cB
3) B -> cB
4) B -> ε
首先，我开始寻找相关的LR(0)自动机，并添加S' -> S产生的增广文法，并开始计算各种状态。我发现的州是：
I0 ={S‘->·S，S->·aSb，S->·cB}
(I0，S) = I1；(I0，a) = I2；(I0，c) = I3；
I1 ={S‘->S·}
I2 ={S->a·Sb，S->·aSb，S->·cB}
(I2，S) = I4；(I2，a) = I2；(I2，c)
浏览 1提问于2017-01-25得票数 1
回答已采纳
1回答
有多少种方法可以构建一个解析器？
、、、、
我正在学习ANTLR v4，它是一个基于所谓Adaptive (*)算法的解析器生成器。它声称比LL(*)算法有很大的改进，但我也听说过一些类似LR的算法。
ANTLR的自适应LL(*)算法(大于LR)的优点/局限性是什么？
浏览 3提问于2017-01-02得票数 3
回答已采纳
我知道有一个类似的帖子：
但我还是不知道该怎么办。
public class Rectangle {
double length, height, rectArea; // assigning variables for length, height and area of the rectangle
Point ul; // assigning variables for all corners
Point ur;
Point lr;
Point ll;
Rectangle(Point p_ul, Point p_ur, Point p_lr, Point p_ll) { //con
浏览 0提问于2014-08-12得票数 1
我有一个语法，我可以检查is是否是LL(1)。但是，有没有办法检查语法生成的语言是否为LL(1)？LL(1)文法和LL(1)语言到底有什么区别？
浏览 2提问于2011-08-21得票数 14
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
