0
$\begingroup$

One procedure for table-driven top-down parsing is given here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html

This gives for matching the input the lines:

else if NextInputSymbol == top then
    /* Match terminal symbol in input */
    Pop(stack)
    /* Get next terminal symbol in input */
    scanner(NextInputSymbol)

Which seems to be assuming that every product leading to terminal symbols has only one terminal.

But what if the product leading to terminals is of the following form:
$$A \rightarrow a_1 | a_2 | ...$$
where $a_i$s terminals.

How do you match for such product?

Merely by trying out each terminal symbol?
But reading them all to the stack would cause some overhead for keeping account of how many terminals symbols were added?


In predict table form:

enter image description here

$\endgroup$
2
$\begingroup$

If a symbol is on the top of the stack, it must have gotten there after being pushed by the code just above the test:

        for each symbol on RHS #action do
            Push(symbol)

(There is a small imprecision in that code; it doesn't mention that "for each symbol on RHS" actually means "for each symbol on RHS from right to left" but that's evident from examining the example stack sequence.)

That code snippet, in turn, was executed after the parse table is used to decide which production will apply, which it did by examining the next input token:

    if top is a nonterminal then
        action = ParseTable[top,NextInputSymbol]

So let's read the code forwards instead of backwards. We'll suppose that $A$ is on top of the stack, and that $A$ has productions as you indicate:

$$A\to a_1\\ A\to a_2\\ ...\\ A\to a_n$$

Now, we can only push one of those productions. Which one will we push? By the construction of the $ParseTable$, we can say that we will push the production whose $FIRST$ set includes the next input symbol. But in this case, that's even simpler because the $FIRST$ set of each of those productions obviously comprises the single terminal on the RHS of the production. So if the next input symbol is $a_2$, for example, the ParseTable will indicate an action corresponding to $A\to a_2$. So the $A$ will be popped from the top of the stack and then $a_2$ will be pushed.

At the next step, the top of the stack is a terminal; precisely the terminal $a_2$. And, surprise!, the next input symbol is also $a_2$. So we can just pop the stack and continue with the parse.

In short, the $ParseTable$ lookup substitutes for that long imaginary sequence of if statements. The lookup could internally be implemented with such a chain, but in real-life it would probably turn out to be a more efficient table lookup algorithm.

$\endgroup$

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.