标签: parser-generator

嘿伙计们,这是我在Stack Overflow上的第一个问题,我想知道我是否可以向那些比我更了解Python和Parser Generators的人提出建议.

我被赋予了一个任务,我必须为一个简单的类C语言创建一个解析器.我可以使用任何编程语言和工具,我希望创建解析器,但我同时学习Python,所以这将是我的首选.

我的Parser必须遵循一些限制.首先,它必须能够读入包含以下信息的文本文件:

kind1 : spelling1
kind2 : spelling2
kind3 : spelling3
      .
      .
      .
kindn : spellingn

每种类型和拼写都指代语言的标记类型和值.该文件是通过语言的词法分析器放置代码示例的结果.

其次,我必须能够自定义解析器的输出.理想情况下,我想输出一个已将类型:拼写列表转换为另一个令牌序列的文件,这些令牌将传递给语言的编译器以转换为MIPS汇编代码.这是我希望解析器能够生成的那种事情的一个小例子:

%function int test
  %variable int x
  %variable int y
%begin
  %if %id y , %id x > %do
  %begin
    %return %num 0
  %end
  %return %num 1
%end

如果有人可以就现有的Python解析器生成器提供建议,并且如果我能够在上面的示例中实现我正在寻找的那种东西,那将是一个很大的帮助.

我知道LL与LR解析器的基本区别.我也知道GLR,SLR和LALR都是LR解析器的扩展.所以我的问题更多细节是......

给定一个LL(*)解析器和LR解析器的任何变体,是否有任何语言可以在一个而不是另一个中描述？或者更简单的是,是否有任何功能或属性无法表达？

作为一个具体的例子.如果我要使用LL(*)解析器创建一种语言,我是否会遇到我想要添加到我的语言中的所需功能/属性,这只能通过LR解析器实现(反之亦然)？

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

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

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

我知道问题Lex和Yacc在PHP之前被问到但是1年前.

现在有没有新的成熟PHP解析器生成器？我的搜索将我带到了下面的那些,你对他们有什么看法,还有其他什么？

• code.google.com/p/antlrphpruntime/:ANTLR PHP版本,但它似乎是非常测试版本,我认为还有很多工作要做.优点是我可以在ANTLR Works工具中编写语法.
• pear.php.net/package/PHP_ParserGenerator/docs/0.1.7/:我试过但看起来很复杂,要与PHP_LexerGenerator一起使用.
• sourceforge.net/projects/lime-php/:我没试过
• bitbucket.org/wez/lemon-php/downloads:我没试过
• bitbucket.org/wez/jlexphp/downloads:我没试过

[答案:]有人给了我一个古老问题的精彩链接: 是否有可用于8位嵌入式系统的flex/bison替代方案？

这篇文章让我了解了生成的大部分ANTLR代码.所以我的选择保持不变:ANTLR虽然项目似乎已经死了.我希望我不必改变代码,因为我希望保持它的可维护性.

我会等一下,看看是否有另一个答案,否则我会接受你的建议继续使用ANTLR

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

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

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

我正在研究一门新语言,在编写语法时,我希望能够测试语法的完整性,冲突和类似情况.我并不是真的关心底层解析器生成器(但是.NET的一个是优选的)

所以功能列表简称为:

• 文本编辑器构建功能
• 语法/语义错误报告
• 冲突报道
• 语法测试功能(即用于在预期语法中编写代码以验证语法定义的正确性的窗口)

一个名为Irony的CodePlex项目确实有类似于我要求的东西,但不支持将语法编写为必需的BNF.

这是Python语法的一个子集:

single_input: NEWLINE | simple_stmt | compound_stmt NEWLINE

stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

small_stmt: pass_stmt
pass_stmt: 'pass'

compound_stmt: if_stmt
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

(您可以在Python SVN存储库中阅读完整语法:http://svn.python.org/.../Grammar)

我试图用这个语法在Python中生成Python的解析器.我遇到的问题是如何将这些INDENT和DEDENT令牌表达为pyparsing对象.

以下是我实现其他终端的方法:

import pyparsing as p

string_start = (p.Literal('"""') | "'''" | '"' | "'")
string_token = ('\\' + p.CharsNotIn("",exact=1) | p.CharsNotIn('\\',exact=1))
string_end = p.matchPreviousExpr(string_start)

terminals = …

我是编译器世界的新手,我最近听说过一种称为解析器生成器的东西.从我(我认为)我所理解的,解析器生成器接收语法文件并输出可以使用给定语法解析文件的源代码文件.

几个问题:

1. 我理解正确吗？

2. 如果是这样,Ragel是这样的工具吗？

3. 如果是,Ragel可以将D解析器输出为D源代码吗？

谢谢!

C++的许多(大多数)正则表达式库允许在运行时从字符串创建表达式.是否有人知道任何C++解析器生成器允许在运行时将表示为字符串的语法(最好是BNF)提供给生成器？我发现的所有实现都需要运行显式代码生成器,或者需要通过巧妙的模板元编程来表达语法.

我有一些使用ANTLR编写解析器的经验,我正在尝试(自我教育:))将其中一个移植到PEG(Parsing Expression Grammar).

当我想要了解这个想法时,有一件事让我觉得麻烦,我觉得我已经错过了一些:如何处理空白.

在ANTLR中,处理空格和注释的常规方法是将标记放在隐藏的通道中,但是使用PEG语法时,没有标记化步骤.考虑到诸如C或Java之类的语言,几乎在任何地方都允许使用注释,人们希望立即"隐藏"注释,但由于注释可能具有语义含义(例如,在生成代码文档,类图等时),不会只是想丢弃它们.

那么,有没有办法解决这个问题？