Frown - an LALR(k) parser generator for Haskell

1. What is Frown?
2. Documentation
3. Download
4. A toy example
5. Changelog

Frown is an LALR(k) parser generator for Haskell 98 written in Haskell 98.

Its salient features are:

• The generated parsers are time and space efficient. On the downside, the parsers are quite large.
• Frown generates four different types of parsers. As a common characteristic, the parsers are genuinely functional (ie `table-free'); the states of the underlying LR automaton are encoded as mutually recursive functions. Three output formats use a typed stack representation, one format due to Ross Paterson (code=stackless) works even without a stack.
• Encoding states as functions means that each state can be treated individually as opposed to a table driven-approach, which necessitates a uniform treatment of states. For instance, look-ahead is only used when necessary to resolve conflicts.
• Frown comes with debugging and tracing facilities; the standard output format due to Doaitse Swierstra (code=standard) may be useful for teaching LR parsing.
• Common grammatical patterns such as repetition of symbols can be captured using rule schemata. There are several predefined rule schemata.
• Terminal symbols are arbitrary variable-free Haskell patterns or guards. Both terminal and nonterminal symbols may have an arbitrary number of synthesized attributes.
• Frown comes with extensive documentation; several example grammars are included.

2. Documentation

Frown comes with extensive documentation available in a variety of formats:

• Portable Document Format: 255K PDF
• Postscript: 200K gzipped postscript
• Online manual: HTML (one page per section, perfect for online viewing)
• Online manual: HTML (all in one page)

Source distribution of Frown:

• frown-0.6.1.tar.gz (andromeda release)
• Hackage: cabal-get install Frown

OS-specific distributions:

• Gentoo: Frown is in the official portage tree (dev-haskell/frown). You can install Frown with the command ACCEPT_KEYWORDS="~x86" emerge frown.

Here is a simple grammar that specifies a character-based parser for function applications (Examples/Call.lg). The grammar is enclosed in special curly braces; the rest is Haskell source.

> import Char > > data Expr = Ident Char > | Apply Expr Expr > deriving (Show) > > type Terminal = Char > > %{ > > Terminal = guard {isAlpha} as "letter" > | '(' > | ')'; > > Nonterminal = expr {Expr}; > > expr {Ident x} : "letter" {x}; > {Apply t u} | expr {t}, '(', expr {u}, ')'; > > }% > > frown ts = fail "syntax error"

Given this grammar, Frown generates (frown --suffix Call.lg) the following parser (Haskell part omitted).

data Stack = Empty | T_1_4 Stack Terminal | T_1_2 Stack Expr | T_2_3 Stack | T_2_6 Stack | T_5_6 Stack | T_5_7 Stack | T_6_4 Stack Terminal | T_6_5 Stack Expr data Nonterminal = Expr Expr expr tr = parse_1 tr Empty >>= (\ (Expr v1) -> return (v1)) parse_1 (v1 : tr) st | isAlpha v1 = parse_4 tr (T_1_4 st v1) parse_1 ts st = frown ts parse_2 tr@[] st = parse_3 tr (T_2_3 st) parse_2 ('(' : tr) st = parse_6 tr (T_2_6 st) parse_2 ts st = frown ts parse_3 ts (T_2_3 (T_1_2 st v1)) = return (Expr v1) parse_4 ts (T_1_4 st x) = parse_2 ts (T_1_2 st (Ident x)) parse_4 ts (T_6_4 st x) = parse_5 ts (T_6_5 st (Ident x)) parse_5 ('(' : tr) st = parse_6 tr (T_5_6 st) parse_5 (')' : tr) st = parse_7 tr (T_5_7 st) parse_5 ts st = frown ts parse_6 (v1 : tr) st | isAlpha v1 = parse_4 tr (T_6_4 st v1) parse_6 ts st = frown ts parse_7 ts (T_5_7 (T_6_5 (T_2_6 (T_1_2 st t)) u)) = parse_2 ts (T_1_2 st (Apply t u)) parse_7 ts (T_5_7 (T_6_5 (T_5_6 (T_6_5 st t)) u)) = parse_5 ts (T_6_5 st (Apply t u))

Readers familiar with LR parsing will possibly recognize the underlying LR(0) automaton: each state has become a function that takes the input and a stack of transitions as argument.

5. Changelog

• frown-0.6 (andromeda release):

  1 November 2005: initial release (0.6, beta quality)
  15 December 2005: improved look-ahead computation (0.6.1, beta quality)