标签: lalr

对于一些主要的解析算法(LL(1),LR(1),LR(0),LALR(1)),是否有一个很好的在线资源和一组语法？我发现许多单独的语法属于这些家庭,但我知道没有好的资源,有人编写了大量的示例语法.

有谁知道这样的资源？

我想问的问题在标题中简明扼要.让我举一个问题语法的例子:

identifier_list
    : identifier
    | identifier_list identifier;

lambda_arguments
    : '(' identifier_list ')'
    | identifier;

lambda
    : lambda_arguments '=>' expression

然后我们添加正常的C表达式语法 - 特别是

primary_expression
    : '(' expression ')'
    | identifier
    | lambda;

真正的问题是,这个语法LALR(1)是否可解析,即能够被自动解析器生成器解析？或者它需要手动或GLR解析器？请注意,我希望特别了解此小节,而不是上下文相关的关键字内容或任何其他部分.

我现在想的是,如果解析器看到'(' identifier ')',它有两个有效的解析,所以如果解析器看到identifier,向前看')',它将无法决定哪个解析树失效.这可能只是一个转移/减少冲突,我可以通过分配一些任意优先权(可能是有利的'(' identifier ')')来消除.

编辑:实际上,我正在考虑使用这个语法小节来窃取新语言中的类似功能.我已经在语法形式上有类似于JavaScript的匿名函数,但我的豚鼠吱吱声反馈抱怨它们对于许多用途而言过于冗长,并且指出C#lambda表达式是更理想的解决方案.我担心这个解决方案可能导致模糊不清.所以,真的,我只对那个小节感兴趣.其他东西,如泛型和演员表对我来说都不是问题.

以前版本的语法都是机械可解析的,我不想失去这个属性,而我之前使用机械发生器的经验告诉我,最好先检查这里,而不是试试自己.对于我的手动解析器,我当然可以通过特殊情况'(' identifier向前看比正常情况更进一步.

我理解LR和LALR都是自下而上的解析算法,但两者之间有什么区别？

LR(0),LALR(1)和LR(1)解析之间有什么区别？如何判断语法是LR(0),LALR(1)还是LR(1)？

LL解析器比LR解析器有什么优势可以保证它们在今天的解析器生成器工具中相对流行？

根据维基百科,LR解析似乎比LL更有优势:

LR解析可以处理比LL解析更大范围的语言,并且在错误报告方面也更好,即它在输入不尽快符合语法时检测语法错误.这与LL(k)(或甚至更糟的LL(*)解析器)形成对比,LL(k)可能由于回溯而将错误检测推迟到语法的不同分支,通常使错误难以在具有长公共前缀的分离上进行本地化. .

注意:这不是作业.当我发现Antlr是一个LL解析器生成器(尽管名字中有"LR")时,我感到很惊讶.

我想知道C#和Java语法是否是LALR(x)？如果是的话,x的价值是多少？

编辑:

在接受了真正的答案之后,我认为以这种方式改变Q更好:

是否有任何LALR(x)解析器可以解析当前版本的Java(版本7)或C#(版本4)？如果是,x的值是多少？

我一直在使用lex/yacc,现在我正在尝试切换到ANTLR.主要关注的是ANTLR是一个LL(*)解析器,与yacc不同,它是LALR.我习惯于自下而上思考,我不知道LL语法的优点是什么.人们说LL语法现在更容易理解,更受欢迎.但似乎LR解析器更强大,例如LL解析器无法处理左递归,尽管似乎有一些解决方法.

那么问题是LL语法比LALR有什么优势？如果有人能给我一些例子,我会很感激.有用文章的链接也很棒.

感谢您的帮助!

(我认为这是一个很好的资源:LL解析器对LR解析器有什么优势？但是对于一些例子它会更好.)

Irony语法的相关部分:

var VARIABLE = new RegexBasedTerminal("variable", @"(?-i)\$?\w+");

variable.Rule = VARIABLE;
tag_blk.Rule = html_tag_kw + attr_args_opt + block;
term_simple.Rule = NUMBER | STRING | variable | boolean | "null" | term_list;
term.Rule = term_simple | term_filter;
block.Rule = statement_list | statement | ";";
statement.Rule = tag_blk | directive_blk | term;

问题是"标签"和"变量"都可以出现在同一个地方.我希望我的解析器更喜欢变量上的标记,但它总是更喜欢变量.我怎么能改变呢？

我试图改变tag_blk.Rule以PreferShiftHere() + html_tag_kw + attr_args_opt + block;和ImplyPrecedenceHere(-100) + html_tag_kw + attr_args_opt + block;,但它并不能帮助任何.解析器甚至没有抱怨含糊不清.

许多网站都声称packrat解析器可以在线性时间内解析输入.
所以初看起来他们比由工具yacc或bison构建的LALR解析器更快.

我想知道当使用公共输入(如编程语言源文件)而不是任何理论输入进行测试时,packrat解析器的性能是否比LALR解析器的性能更好/更差.

有没有人可以解释这两种方法之间的主要区别.
谢谢!

这不是我的功课,我正在尝试理解LALR(k)语法.所以我找到了这个

S -> aEa | bEb | aFb | bFa
E -> e
F -> e

我制作了一个分析器(在我的git repo中以PDF格式提供LR1notLARL1.pdf

但我无法弄清楚,为什么这个LR语法不是LALR？谁能帮我？谢谢

我已经看到一些声称优化的PEG解析器通常不会比优化的LALR(1)或LL(k)解析器更快.(当然,解析的性能取决于特定的语法.)

我想知道PEG解析器是否存在任何特定限制,无论是一般有效还是PEG语法的某些子集都会使它们在性能方面低于LALR(1)或LL(k).

特别是,我对解析器生成器很感兴趣,但是假设在任何特定情况下都可以调整它们的输出以提高性能.我还假设解析器已经过优化,如果需要提高性能,可以稍微调整一下特定的语法.