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$?

  • $\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 Dec 18 '15 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 Dec 19 '15 at 1:47

Your Answer

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

Browse other questions tagged or ask your own question.