Given L(G), write G. Using our recursive programming exercise as a language, we can write few sentences of that language here using a prefix syntax and using list.
(head e)
(tail e)
(cons e e)
(if e e e ) // if cond true_action false_action
(eq e e)
(add e e)
(fun e e ) // first e is argument list,
second e is the body of function
And a complete function to count the number of element of a simple list:
(fun a
(if (eq a NIL) NIL
(add 1 (fun (tail a) ) ) ) )
which is the same as
count (a )
if ( a == NIL ) return NIL
else return 1 + count( tail(a))
To start writing a grammar, we identify what are terminal symbols:
They are: (, ), head, tail, cons, if, eq, add, fun, a,
NIL, 1.
We start with this recognition that a "statement" of this language is in the form of (operator argument*)
p ::= (op1 e) | (op2 e e ) | (op3 e e e)
op1 ::= head | tail
op2 ::= cons | eq | add | fun
op3 ::= if
Now we expand on e:
e can be an atom
e ::= atom
atom ::= a | 1
The last bit is a jump of understanding, e can be a program (list).
e ::= p
Voila, our grammar for the above language is now completed!
It is not difficult, isn't it?
Enjoy.
For further consideration, think about how you write a grammar to handle a variable length of argument list? That is
(fun a ...)
(fun (a b) ...)
(fun (a b ...) ...)
last update 3 Sept 2015