1
$\begingroup$

I read the dissertation [1] and the paper [2], but I'm not sure how to compute $H_{k}$.

$H_{k}$ is defined as:

$$H_{k}(\gamma) = \{ \alpha | \alpha \text{ is terminal,} |\alpha| = k \text{ and } \exists{\beta} \text{ such that } \gamma \overset{*}{\Rightarrow} \alpha\beta \}$$

The operation $\overset{*}{\Rightarrow}$ seems to be roughly defined as a recursive application of $\Rightarrow$:

enter image description here

Is really the goal here to generate every possible string of length $k$ reachable from the production rule?

Note: Although there are some other sources [3] stating the lookahead may not be necessary, I'm still curious to understand how it was initially intended to be computed.

  1. An efficient context-free parsing algorithm by Jay Earley (1968)
  2. An efficient context-free parsing algorithm by Jay Earley (CACM 1970)
  3. Practical Earley Parsing by John Ayock and R. Nigel Horspool (The Computer Journal vol45 no6 2002)
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ $\overset{∗}{⇒}$ is precisely the recursive application (or closure) of $⇒$. It's more common to see it written $\Rightarrow^*$, but the meaning is the same. $\endgroup$
    – rici
    Apr 19, 2022 at 0:26
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. We want others with a similar question to be able to find this page by search on the title of those references, and we want the question to continue to be understandable even if the links stop working. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$
    – D.W. ♦
    Apr 19, 2022 at 4:44
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W. ♦
    Apr 19, 2022 at 4:44
  • $\begingroup$ @D.W. thanks for the heads up, I was under the impression that latex was only available on the math stackexchange $\endgroup$
    – Augusto Hack
    Apr 19, 2022 at 12:57

1 Answer 1

Reset to default
1
$\begingroup$

The intention is to generate every reachable $k$-length terminal prefix reachable from $\gamma$, which is a much less daunting task than generating every possible derivation. You can do it with a simple least fixed-point algorithm.

As indicated, in practice this computation is unnecessary. It reduces the number of alternatives that have to be explored, but they will soon get dropped anyway and the speed-up is not considered sufficient to justify the cost of computing the lookahead sets.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Are there any sources I could use as a reference? I have two things in mind (1) Wondering how to handle grammars with left recursion efficiently (2) It seems the Informal explanation in the paper doesn't follow the formal definition, since the lookahead token is a terminal in the production itself, and not necessarily from the expansion of $\gamma$ $\endgroup$
    – Augusto Hack
    Apr 19, 2022 at 13:16
  • $\begingroup$ @AugustoHack: Left-recursion has almost no impact on the computation (or at least no more than any other recursion). New strings are added to the set only if not already present, which is essentially the same algorithm as doing a depth-first traverse on a graph. You don't first recursively generate all possibilities and then filter the result; that would create an infinite loop. You check each potential new addition as you come upon it, and add it to the set (and to the workqueue of items to process) only if it's not already present. $\endgroup$
    – rici
    Apr 19, 2022 at 16:01
  • $\begingroup$ @AugustoHack: I'm not sure what you mean by your point (2). The lookahead in an item in a state set consists of the $k$-prefixes which might follow the derivation of the entire item. (In other words, it's the head of the continuation of the item.) It's computed from an item $<N\to \beta \bullet \ \gamma, j, \alpha>$ by computing $H_k(\gamma\alpha)$; that is, the $k$-prefixes of the rest of the production augmented (if necessary) with the lookahead of the continuation. $\endgroup$
    – rici
    Apr 19, 2022 at 16:07
  • $\begingroup$ $H_k$ is the FIRST set of a sequence of grammar symbols, not the FOLLOW set of a non-terminal. The lookahead in an item is the FIRST of the continuation of the item, which is a subset of the FOLLOW set of the item's non-terminal. (So precomputing FIRST sets makes sense, but precomputing FOLLOW sets doesn't.) $\endgroup$
    – rici
    Apr 19, 2022 at 16:11
  • $\begingroup$ Sorry, I don't have a reference handy for all that, but it's not fundamentally different from Knuth's computation of the same sets. $\endgroup$
    – rici
    Apr 19, 2022 at 16:13

Your Answer

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

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