Previous Up Next

Chapter 5  Reference manual

5.1  Lexical syntax of Frown

⟨To do: that of Haskell including comments.⟩

⟨To do: Literate grammar file (Bird tracks)⟩.

5.2  Syntax of Frown

Grammar file.
>  file                          :  many "not special",
>                                   "%{",
>                                   many decl;
>                                   "}%",
>                                   many "not special";

Note that "not special" matches every token except the special curly braces "%{" and "}%".

Declaration.
>  decl                          :  terminals;
>                                |  nonterminals;
>                                |  fixity;
>                                |  signature;
>                                |  productions;

Terminal declaration.
>  terminals                     :  "Terminal", "=", sepBy term "|", ";";
> 
>  term                          :  opt "*", assoc, terminal;
>                                |  opt "*", assoc, literal, "=", terminal; -- deprecated
>                                |  opt "*", assoc, terminal,          "as", literal;
>                                |  opt "*", assoc, "guard", haskell,  "as", literal;
> 
>  assoc                         :  ;
>                                |  "left",      Numeral;
>                                |  "right",     Numeral;
>                                |  "nonassoc",  Numeral;

Nonterminal declaration.
>  nonterminals                  :  "Nonterminal", "=", sepBy nonterm "|", ";";
> 
>  nonterm                       :  opt "*", nonterminal;

Fixity declaration.
>  fixity                        : "left",      Numeral, terminal, ";";
>                                | "right",     Numeral, terminal, ";";
>                                | "nonassoc",  Numeral, terminal, ";";

Type signature.
>  signature                     :  "::", nonterminal, premise, ";";  -- deprecated
>                                |  nonterminal, premise, ";";
>                                |  "::", "*", nonterminal, ";";      -- deprecated
>                                |  "*", nonterminal, ";";
> 
>  premise                       :  ;
>                                |  "<-", sepBy1 nonterminal ",";

Productions.
>  productions                   :  nonterminal, ":", sepBy symbol ",", ";", alts;
> 
>  alts                          :  ;
>                                |  attributes, "|", sepBy symbol ",", ";", alts;
> 
>  symbol                        :  "insert",  terminal;
>                                |  "delete",  terminal;
>                                |  "prec",    terminal;
>                                |  terminal;
>                                |  nonterminal;

Nonterminal symbols (expr0 is a variant of expr lacking the embedded Haskell production).
>  nonterminal                   :  expr0, attributes;
> 
>  expr0                         :  Varid, many aexpr0;
> 
>  aexpr0                        :  Varid;
>                                |  Conid;
>                                |  literal;
>                                |  "(", sepBy expr ",", ")";
>                                |  "[", sepBy expr ",", "]";
> 
>  expr                          :  aexpr;
>                                |  Varid, many1 aexpr;
>                                |  Conid, many1 aexpr;
> 
>  aexpr                         :  Varid;
>                                |  Conid;
>                                |  literal;
>                                |  "(", sepBy expr ",", ")";
>                                |  "[", sepBy expr ",", "]";
>                                |  haskell;                       -- embedded Haskell

Terminal symbols.
>  terminal                      :  pat;
>                                |  literal, haskell, attributes;  -- shortcut
> 
>  pat                           :  apat;
>                                |  Conid, many1 apat;
> 
>  apat                          :  Conid;
>                                |  literal;                       -- either literal or shortcut
>                                |  "(", sepBy pat ",", ")";
>                                |  "[", sepBy pat ",", "]";
>                                |  haskell;
> 
>  literal                       :  String;
>                                |  Numeral;
>                                |  Char;

Embedded Haskell (types, patterns, and expressions).
>  attributes                    :  ;
>                                |  haskell, attributes;
> 
>  haskell                       :  "{", many hs, "}";
> 
>  hs                            :  "not brace";
>                                |  "{", many hs, "}";

Note that "not brace" matches every token except the curly braces "{" and "}".

5.3  Predefined schemes

Note that the predefined rules are left-recursive and `run' using constant stack space. Also note that we define rules for arity zero and arity one (the arity specifies the number of attributes/semantic values). The primed versions of the rules work on Hughes's efficient sequence type (a sequence of a's is represented by a function of type [a] -> [a]).

5.3.1  Optional elements

Arity zero.
>  opt x                         <-  x;
>  opt x                         :   ;
>                                |   x;

Arity one.
>  opt x  {Maybe a}              <-  x {a};
>  opt x  {Nothing}              :   ;
>         {Just a}               |   x {a};

5.3.2  Repetition of elements

Arity zero.
>  many x                        <-  x;
>  many x                        :   ;
>                                |   many x, x;
> 
>  many1 x                       <-  x;
>  many1 x                       :   x, many x;

Arity one.
>  many x  {[a]}                  <-  x {a};
>  many x  {s []}                 :   many' x {s};
> 
>  many' x  {[a] -> [a]}          <-  x {a};
>  many' x  {\ as -> as}          :   ;
>           {\ as -> s (a : as)}  |   many' x {s}, x {a};
> 
>  many1 x  {[a]}                 <-  x {a};
>  many1 x  {a : as}              :   x {a}, many x {as};

5.3.3  Repetition of elements separated by a second element

Arity zero.
>  sepBy x sep                   <-  x, sep;
>  sepBy x sep                   :   ;
>                                |   sepBy1 x sep;
> 
>  sepBy1 x sep                  <-  x, sep;
>  sepBy1 x sep                  :   x;
>                                |   sepBy1 x sep, sep, x;

Arity one.
>  sepBy x sep  {[a]}            <-  x {a}, sep;
>  sepBy x sep  {[]}             :   ;
>               {as}             |   sepBy1 x sep {as};
> 
>  sepBy1 x sep  {[a]}           <-  x {a}, sep;
>  sepBy1 x sep  {s []}          :   sepBy1' x sep {s};
> 
>  sepBy1' x sep  {[a] -> [a]}   <-  x {a}, sep;
>  sepBy1' x sep
>      {\ as -> a : as}          :   x {a};
>      {\ as -> s (a : as)}      |   sepBy1' x sep {s}, sep, x {a};

TODO: also versions where sep has arity one.

5.3.4  Repetition of possibly empty elements separated by a second element

⟨To do: better name.⟩

Arity zero.
>  optSepBy x sep                <-  x, sep;
>  optSepBy x sep                :   ;
>                                |   x;
>                                |   optSepBy x sep, sep;
>                                |   optSepBy x sep, sep, x;

Arity one.
>  optSepBy x sep  {[a]}          <-  x {a}, sep;
>  optSepBy x sep  {s []}         :   optSepBy' x sep {s};
> 
>  optSepBy' x sep  {[a] -> [a]}  <-  x {a}, sep;
>  optSepBy' x sep
>      {\ as -> as}               :   ;
>      {\ as -> a : as}           |   x {a};
>      {\ as -> s as}             |   optSepBy' x sep {s}, sep;
>      {\ as -> s (a : as)}       |   optSepBy' x sep {s}, sep, x {a};



5.4  Output formats

⟨To do: Used type names: Result and Terminal.⟩

⟨To do: Used function names: frown. For each start symbol a parser.⟩

The code=standard format is due to Doaitse Swierstra [1].

The code=stackless format is due to Ross Paterson [2].

The code=gvstack format is also due to Ross Paterson.
>  module Paren where
>  import Result
>  
>  {- frown :-( -}
> 
>  data Stack                      =  Empty | T_1 State Stack
>   
>  data State                      =  S_1 | S_2 | S_3 | S_4 | S_5 | S_6
>   
>  data Nonterminal                =  Paren
>   
>  paren tr                        =  parse_1 tr Empty >>= (\ Paren -> return ())
>   
>  parse_1 ts st                   =  reduce_2 ts S_1 st
>   
>  parse_2 tr@[] st                =  parse_3 tr (T_1 S_2 st)
>  parse_2 ('(' : tr) st           =  parse_5 tr (T_1 S_2 st)
>  parse_2 ts st                   =  frown ts
>   
>  parse_3 ts st                   =  reduce_1 ts st
>   
>  parse_4 ('(' : tr) st           =  parse_5 tr (T_1 S_4 st)
>  parse_4 (')' : tr) st           =  parse_6 tr (T_1 S_4 st)
>  parse_4 ts st                   =  frown ts
>   
>  parse_5 ts st                   =  reduce_2 ts S_5 st
>   
>  parse_6 ts st                   =  reduce_3 ts st
>   
>  reduce_1 ts (T_1 _ (T_1 s st))  =  return Paren
>   
>  reduce_2 ts s st                =  goto_5 s ts (T_1 s st)
>   
>  reduce_3 ts (T_1 _ (T_1 _ (T_1 _ (T_1 s st))))
>                                  =  goto_5 s ts (T_1 s st)
>   
>  goto_5 S_1                      =  parse_2
>  goto_5 S_5                      =  parse_4
>   
>  {- )-: frown -}
> 
>  frown _                         =  fail "syntax error"



Figure 5.1: frown --code=compact Paren.g.


>  module Paren where
>  import Result
> 
>  {- frown :-( -}
> 
>  paren tr                      =  state_1 (\ _ -> return ()) tr
>   
>  state_1 k_1_0 ts              =  let { goto_paren = state_2 k_1_0 (reduce_3 goto_paren) }
>                                   in reduce_2 goto_paren ts
>   
>  state_2 k_1_1 k_3_1 ts        =  case ts of {  tr@[]     -> state_3 k_1_1 tr;
>                                                 '(' : tr  -> state_5 k_3_1 tr;
>                                                 _         -> frown ts }
>   
>  state_3 k_1_2 ts              =  k_1_2 ts
>   
>  state_4 k_3_1 k_3_3 ts        =  case ts of {  '(' : tr  -> state_5 k_3_1 tr;
>                                                 ')' : tr  -> state_6 k_3_3 tr;
>                                                 _         -> frown ts }
>   
>  state_5 k_3_2 ts              =  let { goto_paren = state_4 (reduce_3 goto_paren) k_3_2 }
>                                   in reduce_2 goto_paren ts
>   
>  state_6 k_3_4 ts              =  k_3_4 ts
>   
>  reduce_2 g ts                 =  g ts
>   
>  reduce_3 g ts                 =  g ts
> 
>  {- )-: frown -}
> 
>  frown _                       =  fail "syntax error"



Figure 5.2: frown --code=stackless Paren.g.


>  module Paren where
>  import Result
>  
>  {- frown :-( -}
>   
>  data Nonterminal              =   Paren' | Paren
>  
>  type Parser                   =   [Terminal] -> Result Nonterminal
>  
>  type VStack vs v              =   ((vs, Nonterminal -> Parser), v)
>  
>  paren tr                      =   state_1 () tr >>= (\ Paren' -> return ())
>  
>  state_1                       ::  vs -> Parser
>  state_1                       =   state action_1 goto_1
>  action_1 t                    =   reduce_2
>  goto_1 Paren                  =   goto state_2 ()
>  
>  
>  state_2                       ::  VStack vs () -> Parser
>  state_2                       =  state action_2 undefined
>  action_2 t                    =  case t of {  '('  -> shift state_5 ();
>                                                '$'  -> shift state_3 ();
>                                                _    -> error }
>  
>  state_3                       ::  VStack (VStack vs ()) () -> Parser
>  state_3                       =   state action_3 undefined
>  action_3 t                    =   reduce_1
>  
>  state_4                       ::  VStack (VStack (VStack vs ()) ()) () -> Parser
>  state_4                       =   state action_4 undefined
>  action_4 t                    =   case t of {  '('  -> shift state_5 ();
>                                                 ')'  -> shift state_6 ();
>                                                 _    -> error }
>  
>  state_5                       ::  VStack (VStack vs ()) () -> Parser
>  state_5                       =   state action_5 goto_5
>  action_5 t                    =   reduce_2
>  goto_5 Paren                  =   goto state_4 ()
>  
>  state_6                       ::  VStack (VStack (VStack (VStack vs ()) ()) ()) () -> Parser
>  state_6                       =   state action_6 undefined
>  action_6 t                    =   reduce_3
>  
>  
>  reduce_1 (((((_, g), ()), _), ()), _) ts 
>                                =   accept Paren' ts
>  
>  reduce_2 (_, g) ts            =   g Paren ts
>  
>  reduce_3 (((((((((_, g), ()), _), ()), _), ()), _), ()), _) ts 
>                                =   g Paren ts
>  
>  state action goto vs ts       =   let { gs = (vs, g); g v = goto v gs } in action (head ts) gs ts
>  
>  shift state v vs ts           =   state (vs, v) (tail ts)
>  
>  shift' state v vs ts          =   state (vs, v) ts
>  
>  accept v _                    =   return v
>  
>  goto state v vs               =   state (vs, v)
>  
>  error gs ts                   =   frown ts
> 
>  {- )-: frown -}
>  
>  frown _                       =   fail "syntax error"



Figure 5.3: frown --code=gvstack Paren.g (requires an explicit EOF symbol).


5.5  Invocation and options

Usage: frown [option ...] file.g ...
-b or --backtrack

generate a backtracking parser (see Sec. 3.2.5)

-cc, -ccompact or --code=compact

(see Sec. 3.4.5 and 5.4)

-cg, -cgvstack or --code=gvstack

(see Sec. 3.4.5 and 5.4)

-cs, -cstackless or --code=stackless

(see Sec. 3.4.5 and 5.4)

-cstandard or --code=standard

(see Sec. 3.4.5 and 5.4)

--copying

display details of copying

-d or --debug

emit debugging information (see Sec. 3.4.4)

-e or --expected

pass a list of expected terminals to `frown' (see Sec. 3.3.3)

-g or --ghc

use GHC extensions (see Sec. 3.4.5)

-h, -? or --help

-i or --info

put additional information into generated file (see Sec. 3.4.4)

-k[nat] or --lookahead[=nat]

use k tokens of look-ahead (see Sec. 3.4.3)

-l or --lexer

use a monadic lexer (get :: M Terminal) (see Sec. 3.3.1)

-n or --noinline

generate NOINLINE pragmas (see Sec. 3.4.5)

-O or --optimize 

optimize parser (see Sec. 3.4.5)

-p[nat] or --pagewidth[=nat]

use the specified pagewidth for pretty printing (see Sec. 3.4.4)

--prefix[=string]

use prefix for Frown-generated variables (see Sec. 3.4.4)

-sm, -smono or --signature=mono

add monomorphic type signatures (see Sec. 3.4.5)

-sp, -spoly or --signature=poly

add polymorphic type signatures (see Sec. 3.4.5)

--suffix[=string]

use suffix for frown generated variables (see Sec. 3.4.4)

-t or --trace

insert calls to tracing routines (`shift', `reduce' and `accept') (see Sec. 3.4.4)

-v or --verbose

be verbose

--version

print version information

--warranty

display details of warranty
Previous Up Next