Haskell或Scala等功能语言是否有LL语法分析器？ [英] Are there any LL Parser Generators for Functional Languages such as Haskell or Scala?

问题描述

我注意到在函数式语言中创建解析器的LL解析器明显缺乏。对于我一直在寻找而没有成功的理想发现是为ANTLR样式的LL（*）语法生成一个Haskell解析器（对语法进行模次重新格式化），并且惊讶于每一个具有函数的解析器生成器我发现的语言目标是某种LR解析器。

我想转换我正在使用的这种语言的解析器，它具有从ANTLR到自主机器的功能特性在语言本身中，如果我能够使用另一种函数式语言（最好是我熟悉的，Haskell和Scala），而不是必须从头开始重写它，那么它将对我的语言有很大的帮助。尽管最终我可能会这样做，因为核心语言很小。

在这一点上，甚至比这个解决方案还要多，我很好奇<为什么没有这样的LL（*）甚至LL（k）解析器生成器，但是很多LR生成器，因为LL看起来本质上更容易。

递归下降。

Haskell的parsec ， attoparsec 和<一个href =http://hackage.haskell.org/package/polyparse> polyparse 和Scala的股票解析器组合器都会生成有效的LL（*）解析器。

parsec和attoparsec都要求你使用一个明确的尝试组合器来获得回溯，但这只是为了效率和scala 分类器组合器也可以处理 packrat parsing 。

考虑以下公告 Brent Yorgey最近的 unbound 包：

  parseAtom = parens parseTerm 
< |> var< $> ident 
< |> lam< $>括号（ident）*< parseTerm 
  

很容易看到原文。

LR解析器需要更复杂的预处理来生成要高效执行的表，因为直接手工编码使用类似于递归上升是非常糟糕的。通过将您的解析器组合器作为EDSL而不是外部工具实现，您可以更好地使用编程语言的高级功能。

您可以使语法部分更高级，直接在解析器中构建词法分析器等。典型的LR语法分析器生成器可以不做这些事情，或者只能在有限的情况下以特别的方式提供，因为最终必须能够发布表格。

I've noticed a distinct lack of LL parsers that create parsers in functional languages. The ideal find for what I've been looking for without success is something to generate a Haskell parser for an ANTLR-style LL(*) grammar (modulo minor reformatting of the grammar), and was surprised that every last parser generator with a functional language target I found was some kind of LR parser.

I want to transition the parser of this language I'm working on which has functional features from ANTLR to self-host in the language itself, and it would help a lot if I could port to my language something almost surely correct in another functional language (preferably ones I'm familiar with, Haskell and Scala), instead of having to rewrite it entirely from scratch, though in the end I might do this, since the core language is small.

At this point more than even a solution to this is I'm very curious as to why there are no such LL(*) or even LL(k) parser generators, but many LR generators, since LL seems inherently easier.

解决方案

The major reason for this is that most LL(k) parsers that are written in functional languages are just implemented using parser combinators, because the easiest path to generate a parser combinator library is recursive descent.

Haskell's parsec, attoparsec, and polyparse and Scala's stock parser combinators all produce what are effectively LL(*) parsers.

Both parsec and attoparsec require you to use an explicit try combinator to get backtracking, but this is only done for efficiency and the scala parser combinators can also deal with packrat parsing.

Consider the following fragment from the announcement of Brent Yorgey's recent unbound package:

parseAtom = parens parseTerm
    <|> var <$> ident
    <|> lam <$> brackets ident <*> parseTerm

it is pretty easy to see the original grammar.

LR parsers require much more complicated preprocessing to generate the tables to execute efficiently, since the direct hand encoding of one using something like recursive ascent is pretty awful.

By implementing your parser combinators as an EDSL rather than an external tool you enable greater use of advanced features of your programming language. You can make portions of the grammar higher order, build the lexer hack directly into the parser, etc. Typical LR parser generators can't do these things, or can only offer them in ad hoc ways in limited contexts because of the need to be able to emit the tables in the end.

这篇关于Haskell或Scala等功能语言是否有LL语法分析器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！