7
$\begingroup$

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph:

We will first of all briefly review the LR(1) parsing and parser construction algorithms. In this paper the symbols of a grammar are denoted by Roman letters while Greek letters are employed to denote strings. $\epsilon$ is the null-string. $\alpha \Rightarrow^* \beta$ means $\beta$ is derivable from $\alpha$ (which is considered to be true if $\beta = \alpha$). By THEADS($\alpha$) we refer to the set $\{b \mid b \text{ is the head of a terminal string derivable from $\alpha$}\}$.

From what I can see THEADS here is what is usually called FIRST. Is this correct? Does THEADS predate FIRST?

Improve this question
$\endgroup$
2
  • $\begingroup$ Some notations are not completely standard – this may be an example. If both definitions seem the same to you, just treat it as the same thing under two different names. $\endgroup$
    – Yuval Filmus
    Commented Dec 18, 2015 at 22:35
  • $\begingroup$ @YuvalFilmus The reason I ask is because I don't know what terminology was standard in 1977. If $FIRST$ was standard terminology back then Pager must've been aware of it. If he was aware of it, then why did he not use $FIRST$? Is there a subtle difference (e.g. perhaps $\alpha \Rightarrow^* \epsilon$ does not mean that $\epsilon \in THEADS(\alpha)$)? $\endgroup$
    – orlp
    Commented Dec 19, 2015 at 1:47

1 Answer 1

Reset to default
2
$\begingroup$

I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. Quoting that paper:

The concepts of state, configuration and theads(α, k) used here are equivalent to “item set”, “item” and FIRSTk(α) correspondingly in some other literature.

Note that a lot of good references on Pager (and Chen's) work can be found at the HYACC web site.

As for why Pager uses his own terminology in his papers, I don't have an adequate explanation, but it does indeed appear that THEADS and FIRST are the same.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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