Parsing with yecc

This is a jump start guide to parsing with yecc it uses the example of parsing a list.

Step 1 ) Define the grammar

Enter this into the file list.yrl:

Nonterminals list element elements.

Terminals '(' ')' 'atom'.

Rootsymbol list.

list -> '(' ')' : nil.
list -> '(' elements ')' : '$2'.

elements -> element : {cons, '$1', nil}.
elements -> element elements : {cons, '$1', '$2'}.
element -> atom : '$1'.
element -> list : '$1'.

Step 2) - create the parser

Do like this:

1> yecc:yecc("list.yrl","list_parser.erl").
Parsing input file ...
Computing states and goto table ...
Computing parse actions ...
Writing file ...
list_parser.erl
{2700,110}

Step 3) Compile the parser

Like this:

2> c(list_parser).                         
./list_parser.erl:161: Warning: function return_error/2 not called
{ok,list_parser}

Step 4) - Test the parser

3> list_parser:parse([{'(',1},{atom,1,aaa}, 
	              {atom,2,b}, {')',2}, {'$end',2}]).
{ok,{cons,{atom,1,aaa},{cons,{atom,2,b},nil}}}

Here:

{'(', 1}: means a "(" was found on line 1
{atom, 2, b}: means the atom "b" was found on line 2

The tokeniser is expected to produce a list like this from the input.

Note that for Erlang this is done by erl_scan

4> erl_scan:string("(a)").    
{ok,[{'(',1},{atom,1,a},{')',1}],1

Putting it together

Just for fun we can sew things together like this:

5> Toks = fun(I) -> element(2,erl_scan:string(I)) ++ [{'$end',999}] end. 
#Fun<erl_eval>

6> Toks("(a b c)").
[{'(',1},{atom,1,a},{atom,1,b},{atom,1,c},{')',1},{'$end',999}]

7> Parse =fun(I) -> list_parser:parse(Toks(I)) end.                     
#Fun<erl_eval>

8> Parse("(a b c)").                                                    
{ok,{cons,{atom,1,a},{cons,{atom,1,b},{cons,{atom,1,c},nil}}}}

9> Parse("(a b c 12)").
{error,{1,list_parser,["syntax error before: ","12"]}}