patternMinor
Is THEADS the same as FIRST?
Viewed 0 times
samethetheadsfirst
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#50891, answer score: 2
Revisions (0)
No revisions yet.