Re: Anyone know this book?

Frank Peelo wrote:
> I bought myself a copy of "Compiler Construction" by N. Wirth...


I have a first printing of that book, copyright 1996, but I couldn't
find the diagram you drew, so maybe you have a newer edition. Your
diagram resembles part of Figure 4.1, though.


> For example, in one section he discusses generating a "table" to
> represent a grammar. A construct like
> p = t { '+' | '-' t }.
> gets represented as
> +-----------------+
> v |
> p --> [ ] --> [ '+' ] --|
> ----/ | |
> / [ '-' ] --+
> t |
> [ EMP ]


In Wirth's EBNF, I think the production for p that yields this
syntax diagram would be written


        p = t { ("+" | "-") t }


The { ... } notation means zero or more repetitions of the stuff
inside the curly braces; in other words the production above is
equivalent to


        p = t q
        q = <empty> | sign t q
  sign = "+" | "-"


where <empty> stands for the empty sequence of tokens.


> but what I don't understand is: why the pseudo-terminal symbol "EMP"
> (indicating a lack of an alternative terminal symbol) is needed.


EMP serves the same purpose as <empty> in the productions above:
A p consists of a t followed by a q, where a q consists either of
nothing at all, or a sign followed by a t followed by a q. If we
didn't allow for the possibility that a q could be nothing at all,
we would have the grammar


        p = t q
        q = sign t q
  sign = "+" | "-"


which doesn't generate any terminal strings at all; no matter how
hard you try, you can't get rid of the nonterminal q.


It is always possible to get rid of these <empty> productions
(except possibly one for the start symbol) by rewriting the
grammar, but this rewriting usually makes the grammar more
complicated and harder to deal with.


William D Clinger
--

Return to the comp.compilers page.
Search the comp.compilers archives again.