291 grammars as two different parse-trees for a string means a program can

   291 grammars because two different parse-trees for a string mean a program can

   292 be interpreted in two different ways. Then we have to somehow make sure

   292 be interpreted in two different ways. In such cases we have to somehow make sure

   296 is ambiguous or not is in general undecidable. But in concrete instances we can

   296 is ambiguous or not is in general undecidable. 

   297 often make a choice.

   297 

   298 Let us now turn to the problem of generating a parse-tree for a grammar and string.

   299 In what follows we explain \emph{parser combinators}, because they are easy

   300 to implement and closely resemble grammar rules. Imagine that a grammar

   301 describes the strings of natural numbers, such as the grammar $N$ shown above.

   302 For all such strings we want to generate the parse-trees or later on we actually 

   303 want to extract the meaning of these strings, that is the integers ``behind'' these 

   304 strings. The parser will therefore be functions of type

   305 

   306 \begin{center}

   307 \texttt{I $\Rightarrow$ (T, I)}

   308 \end{center}

   309 

   310 \noindent 

   311 that is they take as input something of type \texttt{I}, typically a list of token or a string,

   312 and return a pair. 

   313 

   314 

   315