Frown - an LALR(k) parser generator for Haskell


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

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

Its salient features are:

Furthermore, Frown supports the use of monadic lexers, monadic semantic actions, precedences and associativity, the generation of backtracking parsers, multiple start symbols, error reporting and a weak form of error correction.

2. Documentation

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

3. Download

Source distribution of Frown:

OS-specific distributions:

4. A toy example

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

Ralf Hinze,, 2nd November 2007.

Valid HTML 4.01!