2
$\begingroup$

I am fairly confident that my textbook (Concepts of Programming Languages 11th edition, international edition, Robert Sebesta) has an error in its definition of what a phrase is in the section on bottom-up parsers. After an infuriating conversation with the professor using that textbook in which I was told that the book's definition was correct, but was given no reason why or why my reasoning was incorrect, I still think it has an error. I haven't been able to find any information about errata in the book online (not the main point of the question, but I'd like to find that also).

Here is the book's definition:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\gamma = \alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2$.

Here is what I think the definition should be:

$\beta$ is a phrase of the right sentential form $\gamma$ if and only if $S \Rightarrow^{*}\alpha_1A\alpha_2\Rightarrow^{+}\alpha_1\beta\alpha_2 = \gamma$

Here is my reasoning: Definitions are mostly arbitrary, so I can't really prove that it's "wrong" without comparing it with a bunch of other books out there (I just have the one, so if those of you with more could check that for me, that'd be great. I can't seem to find any definitions online). But I can prove that it's not consistent with the rest of the book.

The book states that simple phrases are a subset of phrases, that the handle of any rightmost sentential form is its leftmost simple phrase, and that in this example grammar

$\begin{align} E &\to E + T \mid T\\ T &\to T * F \mid F\\ F &\to (E) \mid id \end{align} $

the handle of the sentence "id + id * id" is the first id. Observe that according to the book's definition of phrase, a sentential form consisting entirely of terminals can have no phrases, because the sentential form is never of the form $\alpha_1{}A\alpha_2$. This means that there are also no simple phrases of sentential forms consisting entirely of terminals. This means that there are also no handles of sentential forms consisting entirely of terminals. This means that there are no handles in "id + id * id", despite them saying there are. So the definition isn't consistent with what else they say. Based on what I've read elsewhere and heard in class, the definition seems wrong, not the other parts.

Is my reasoning sound? Is the definition of phrase correct / what is the "correct" definition of phrase?

(apologies if I left out anything essential, I lost the first draft when I got to the captcha requirement and filled it out with spyblock enabled)

$\endgroup$
  • $\begingroup$ Your interpretation fits the example from the book "So, the phrases of the sentential form E + T * id are E + T * id, T * id, and id." $\endgroup$ – Hendrik Jan Nov 16 '17 at 9:30
  • $\begingroup$ Your corrected definition matches how the term phrase is used in practice, e.g. in linguistics, where it originated. $\endgroup$ – reinierpost Mar 19 '18 at 14:15
1
$\begingroup$

To be a phrase is to be reducible to a single non-terminal. What you call a definition of phrase is actually the definition of what it is to be a phrase of a sentential form.

$\beta$ is a phrase of $\alpha_{1}A\alpha_{2}$, because it will be reduced to $A$. There are (obviously) phrases in sentential forms consisting entirely of terminals, i.e., sequences of symbols that will be reduced to a single non-terminal. They are not phrases of that sentential form, though.

A handle is the simple phrase of the sentential form that will be the result of the reduction to be made immediately, at some point. $\beta$ exists as a phrase, because it will be reduced to $A$. A bottom-up parser will usually reduce first its leftmost simple phrase, which will then be the handle of the resulting sentential form.

Definitions are not arbitrary, they serve a purpose.

$\endgroup$
  • $\begingroup$ So if I understand correctly, they aren't saying "the handle of any rightmost sentential form is the leftmost simple phrase of that rightmost sentential form", they're saying "the handle of any rightmost sentential form is the leftmost simple phrase (of any sentential form) that is a substring of the rightmost sentential form in question"? That is, just because there aren't any phrases of some sentential form doesn't mean it doesn't contain any substrings that are phrases. $\endgroup$ – Reepca Nov 16 '17 at 19:15
  • $\begingroup$ And that would also mean that the quote mentioned by Hendrik in a comment should actually read "So, the substrings of the sentential form E + T * id that are also phrases are E + T * id, T * id, and id." Also, by "definitions are mostly arbitrary", I meant the binding of name to concept. The concept is of course not arbitrary, but the name used is for the most part. $\endgroup$ – Reepca Nov 16 '17 at 19:23
  • $\begingroup$ I believe that the sentence "So, the phrases of the sentential form E + T * id are E + T * id, T * id, and id" could be... rephrased as "So, the phrases in the sentential form E + T * id are E + T * id, T * id, and id." $\endgroup$ – André Souza Lemos Nov 16 '17 at 20:15

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.