4
$\begingroup$

I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.

On page 12, the authors start describing a set of rules that can be used to generate the set of all enumerations of names of the type "tom, dick and harry": the rules allow single names (e.g. "tom") as well as repetitions ("tom, harry, dick, dick and harry"); multiple names in an enumeration are separated by commas except the last two names which are separated by "and", so the following aren't valid: ("tom, harry, dick") or ("harry and tom and dick").

A few pages later, and after having defined some more terms and formalisms, the authors come up with the following replacement rules (parse structure grammar) to generate the sentences of the desired type:

0. Name -> tom | dick | harry
1. Sentence-> Name | List End
2. List -> Name | Name, List
3. , Name End -> and Name

In the above, Sentence is the start symbol.

However it seems to me that these rules can generate incorrect sentences: if we replace Sentence by List End and List by Name we end up with Name End for which no replacement rule is defined.

It seems to me that the 2nd line in the rules above, if replaced by

Sentence -> Name | Name, List End

would fix this problem.

Am I correct that the authors have made an oversight, and is my modification correct? Or have I misunderstood something?

I don't have a CS background and this is the first time I'm reading about parsing, so please keep that in consideration in your replies. Thanks!

$\endgroup$
3
$\begingroup$

You are correct, in a sense. Speaking in formal notation, you have

$\qquad \displaystyle \mathtt{Sentence} \Rightarrow \mathtt{List}\ \mathtt{End} \Rightarrow \mathtt{Name}\ \mathtt{End}$

and we can not get rid of $\mathtt{End}$. We have not generated a wrong word, but a sentence that can not be derived further to any word. That is not a mistake in the grammar itself (with respect to the generated language), but certainly nasty if you think of parsing.

Your modification is valid. In particular, we do not need to generate lists of length one using rule 2 (which you make impossible by your modification) because we can just alternative 1 of rule 1.

Note that the grammar given is not the greatest (for parsing). For example, it is not context-free (rule 3). A better way to implement detection of the end is to generate the list the other way round ($\_$ denotes a space):

$\qquad \displaystyle \begin{align} \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\ \mathsf{List} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{,\_}\ \mathsf{Name} \\ \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry} \end{align}$

Of course, this grammar is now left-recursive which is problematic for some parsing strategies (e.g. LL). So it may be useful to create the list from left to right after all, but keep generating the $\mathtt{and}$ at the start:

$\qquad \displaystyle \begin{align} \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\ \mathsf{List} &\to \mathsf{Name} \mid \mathsf{Name}\ \mathtt{,\_}\ \mathsf{List} \\ \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry} \end{align}$

Now a parser working from left to right can always identify the next rule (with a lookahead of two to catch whether there is a comma behind a name).

$\endgroup$
  • 1
    $\begingroup$ Thanks. At this point the book hasn't gotten into some of the things you mentioned, so I'll reread your answer once I'm a bit further along. $\endgroup$ – Aky Sep 5 '12 at 10:57
  • $\begingroup$ @Aky: I thought it might not, and wrote the answer with that in mind. I would assume the authors to go on and change the grammar successively into something (easily) parseable. Have fun reading! $\endgroup$ – Raphael Sep 5 '12 at 11:04
  • $\begingroup$ Actually, I now find that a bit further down the authors state: " A determined and foolhardy attempt to generate the incorrect form without the and will lead us to sentential forms like tom, dick, harry End which are not sentences and to which no production rule applies. Such forms are called blind alleys." Hm. $\endgroup$ – Aky Sep 5 '12 at 11:10
  • $\begingroup$ @Aky Oh, right. Got me there. I edited the answer accordingly. $\endgroup$ – Raphael Sep 5 '12 at 12:47
  • 1
    $\begingroup$ @Aky Yes, you can always (and algorithmically) get rid of dead/useless rules and symbols; grammars without such are called reduced grammars. The construction can be found in formal language textbooks, e.g. Harrison's "Introduction to formal language theory.", theorem 3.2.1. $\endgroup$ – Raphael Sep 5 '12 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.