spell1
LL(1) parser generator for Erlang and LFE
This is a basic LL(1) parser generator for use together with
Erlang. There are two interfaces for different languages, Erlang and
LFE, and others can be added. The generator has been split into
separate files for handling the grammar and the reading of grammar
files and outputing the resultant module code. The grammar is
processed in the file spell1_core.erl and the IO-files for Erlang
and LFE are inte spell1.erl and lspell1.lfe. It is easy to add
IO-files for other languages.
Using the generated parser
The parser which spell1 generates contains by default two exported functions. They have the same name as the root symbol (see below) and are the default entry into the parser. They have the type:
<root symbol>(Tokens) -> Return.
<root symbol>(Continuation, Tokens) -> Return.
Types:
Tokens = [Token]
Continuation = [] | continuation()
Token = {Type,LINE} | {Type,LINE,Value}
Return = {ok,Form,RestTokens} | {more,Continuation} |
{error,Error,RestTokens}
In a token: Type is one of the terminals; LINE is some form of metadata
about the token usually containing the line number; and Value gives
a specific value for that terminal, for example the actual number or
atom.
The functions returns return any remaining tokens which weren't used
in the form, these can then be used to parse the next form. When the
functions return {more,Continuation} they don't have enough tokens
to parse a form and the function can be called again with the
continuation and more tokens to continue parsing. This can be repeated
until enough tokens have been received and the form is parsed.
Grammar definition files
The grammar definitions are in files with the default extension
.spell1. A grammar file must: list all the terminal and non-terminal
symbols; indicate the root symbol; give all the grammar rules; and
give any extra code. The default function for parsing has the same
name as the root symbol.
Erlang
The syntax of the Erlang grammar file is the same as for yecc but only
the following declarations are recognised: Terminals, Nonterminals
and Rootsymbol. Other declarations generate a warning and are
ignored. Rules take the same format as in yecc.
LFE
The syntax is of the LFE grammar file recognises the following forms:
(terminals terminal-1 terminal-2 ...)
(non-terminals non-terminal-1 non-terminal-2 ...)
(root-symbol root)
(rule non-term (symbol-1 ...) code)
An optional section containing LFE code starts with the declaration lfe-code.
Example grammar files
Here is the grammar file for LFE both as an Erlang version and as an LFE version.
Erlang
Terminals
symbol number string binary fun '(' ')' '[' ']' '.' '\'' '`' ',' ',@'
'#(' '#B(' '#M(' '#.' '#\''.
Nonterminals form sexpr list list_tail proper_list .
Rootsymbol form.
form -> sexpr : '$1'.
sexpr -> symbol : value('$1').
sexpr -> number : value('$1').
sexpr -> string : value('$1').
sexpr -> binary : value('$1').
sexpr -> '#\'' : make_fun(value('$1')).
sexpr -> '#.' sexpr : eval_expr(line('$1'), '$2').
sexpr -> '\'' sexpr : [quote,'$2'].
sexpr -> '`' sexpr : [backquote,'$2'].
sexpr -> ',' sexpr : [comma,'$2'].
sexpr -> ',@' sexpr : ['comma-at','$2'].
sexpr -> '(' list ')' : '$2'.
sexpr -> '[' list ']' : '$2'.
sexpr -> '#(' proper_list ')' : list_to_tuple('$2').
sexpr -> '#B(' proper_list ')' :
make_bin(line('$1'), '$2').
sexpr -> '#M(' proper_list ')' :
make_map(line('$1'), '$2').
list -> sexpr list_tail : ['$1'|'$2'].
list -> '$empty' : [].
list_tail -> sexpr list_tail : ['$1'|'$2'].
list_tail -> '.' sexpr : '$2'.
list_tail -> '$empty' : [].
proper_list -> sexpr proper_list : ['$1'|'$2'].
proper_list -> '$empty' : [].
%% Extra Erlang code.
Erlang code.
-define(CATCH(E, Error), try E catch _:_ -> Error end).
%% For backwards compatibility
-export([sexpr/1,sexpr/2]).
sexpr(Ts) -> form(Ts).
sexpr(Cont, Ts) -> form(Cont, Ts).
%% make_fun(String) -> FunList.
%% Convert a fun string to a fun sexpr.
%% "F/A" -> ['fun', F, A].
%% "M:F/A" -> ['fun', M, F, A].
make_fun("=:=/2") ->
['fun', '=:=', 2];
make_fun(FunStr) ->
J = string:rchr(FunStr, $/),
A = list_to_integer(string:substr(FunStr, J + 1)),
case string:chr(FunStr, $:) of
0 ->
F = list_to_atom(string:substr(FunStr, 1, J - 1)),
['fun', F, A];
I ->
F = list_to_atom(string:substr(FunStr, I + 1, J - I - 1)),
M = list_to_atom(string:substr(FunStr, 1, I - 1)),
['fun', M, F, A]
end.
%% make_bin(Line, Segments) -> Binary.
%% Make a binary from the segments.
make_bin(Line, Segs) ->
?CATCH(lfe_eval:expr([binary|Segs]),
return_error(Line, "bad binary")).
%% make_map(Line, Elements) -> Map.
%% Make a map from the key/value elements.
make_map(Line, Es) ->
?CATCH(maps:from_list(pair_list(Es)),
return_error(Line, "bad map")).
%% pair_list(List) -> [{A,B}].
%% Generate a list of tuple pairs from the elements. An error if odd
%% number of elements in list.
pair_list([A,B|L]) -> [{A,B}|pair_list(L)];
pair_list([]) -> [].
%% eval_expr(Line, Expr) -> Val.
%% Evaluate #. expression.
eval_expr(Line, Expr) ->
?CATCH(lfe_eval:expr(Expr),
return_error(Line, "bad #. expression")).LFE
(terminals symbol number string binary fun |(| |)| |[| |]| |.| |'| |`| |,| |,@|
|#(| |#B(| |#M(| |#'| |#.| )
(non-terminals form sexpr list list-tail proper-list )
(root-symbol form)
(rule form (sexpr) $1)
(rule sexpr (symbol) (value $1))
(rule sexpr (number) (value $1))
(rule sexpr (string) (value $1))
(rule sexpr (binary) (value $1))
(rule sexpr (|#'|) (make-fun (value $1)))
(rule sexpr (|#.| sexpr) (eval-expr (line $1) $2))
(rule sexpr (|'| sexpr) `(quote ,$2))
(rule sexpr (|`| sexpr) `(backquote ,$2))
(rule sexpr (|,| sexpr) `(comma ,$2))
(rule sexpr (|,@| sexpr) `(comma-at ,$2))
(rule sexpr (|(| list |)|) $2)
(rule sexpr (|[| list |]|) $2)
(rule sexpr (|#(| proper-list |)|) (list_to_tuple $2))
(rule sexpr (|#B(| proper-list |)|)
(make-bin (line $1) $2))
(rule sexpr (|#M(| proper-list |)|)
(make-map (line $1) $2))
(rule list (sexpr list-tail) (cons $1 $2))
(rule list ($empty) ())
(rule list-tail (sexpr list-tail) (cons $1 $2))
(rule list-tail (|.| sexpr) $2)
(rule list-tail ($empty) ())
(rule proper-list (sexpr proper-list) (cons $1 $2))
(rule proper-list ($empty) ())
;; Extra LFE code.
lfe-code
(defmacro CATCH (expr error)
`(try ,expr
(catch (`#(,_ ,_ ,_) ,error))))
;; For backwards compatibility
(extend-module (export (sexpr 1) (sexpr 2)))
(defun sexpr (ts) (form ts))
(defun sexpr (cont ts) (form cont ts))
;; make_fun(String) -> FunList.
;; Convert a fun string to a fun sexpr.
;; "F/A" -> ['fun', F, A].
;; "M:F/A" -> ['fun', M, F, A].
(defun make-fun
(["=:=/2"] `(fun =:= 2))
([str]
(let* ((j (string:rchr str #\/))
(a (list_to_integer (string:substr str 1 (+ j 1)))))
(case (string:chr str #\:)
(0 (let ((f (list_to_atom (string:substr str 1 (- j 1)))))
`(fun ,f ,a)))
(i (let ((f (list_to_atom (string:substr str (+ i 1) (- j i 1))))
(m (list_to_atom (string:substr str 1 (- i 1)))))
`(fun ,m ,f ,a)))))))
;; make-bin(Line, Segments) -> Binary.
;; Make a binary from the segments.
(defun make-bin (line segs)
(CATCH (lfe_eval:expr (cons 'binary segs))
(return_error line "bad binary")))
;; make-map(Line, Elements) -> Map.
;; Make a map from the key/value elements.
(defun make-map (line es)
(CATCH (maps:from_list (pair-list es))
(return_error line "bad map")))
;; pair_list(List) -> [{A,B}].
;; Generate a list of tuple pairs from the elements. An error if odd
;; number of elements in list.
(defun pair-list
([`(,a ,b . ,l)] `(#(,a ,b) . ,(pair-list l)))
([()] ()))
;; eval-expr(Line, Expr) -> Val.
;; Evaluate #. expression.
(defun eval-expr (line expr)
(CATCH (lfe_eval:expr expr)
(return_error line "bad #. expression")))