Simple question about grammar derivations

Question

I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation.

Here is an example of a grammar derivation in a Youtube lecture I found. I get everything he covers here except that it isn't clear to me how a derivation is chosen when there are multiples available.

For example, in the video he constructs a grammar E that has productions E + E, E * E, and id. I'm assuming that the correct derivation is chosen by pattern matching the input string to the grammar but that isn't made clear, nor is it really made clear in other sources I've read and watched. The derivation used at a given step sometimes seems arbitrarily chosen.

My reason for asking is because if it isn't matched to the input pattern, what is to keep his grammar from expanding an E into the (arbitrarily chosen) non-terminal production E + E infinitely, and never reach a terminal condition?

Edit Related question:

On the bottom of this page there is a discussion of leftmost and rightmost derivation. In the leftmost derivation example, how does it know the correct derivation to use to move from the second to third derivation? In other words, how does it know to make this derivation: a+X → a+ X*X

Why couldn't it just derive a+X → a+a and terminate? I know it doesn't match the input string, but what actually prevents that incorrect derivation from being chosen?

Answer 1

Actually you have to study the working of a parser in detail to get the answer to your question.

Parsers can be top down or bottom up. In top down parsing, we try to derive the input string from the start symbol. In bottom up parsing, the reverse procedure is applied, i.e. we try to reduce the input string to the start symbol.

Let me try to answer your question by explaining the working of recursive descent parser, a general top down parser.

Recursive descent parser will choose the productions based on the order in which they are specified. I will explain with an example.

The grammar given is

    S-> aAB | bAB
    A-> d | a
    B-> b

Let the input be

    bab

The input pointer points to the first symbol 'b'. The recursive descent parser will start with start symbol S. The working is as follows

    S-> aAB

Whenever a terminal symbol is obtained, it is checked for match with the current input symbol. Input symbol 'b' doesn't match with the terminal 'a'. So the parser will backtrack and choose the next production

    S->bAB

The terminal symbol matches with the input. Hence input pointer is advanced and it points to 'a'. Next substitute for A.

    S-> bdB

Input symbol and the obtained terminal does not match. So backtrack and choose the next production for A.

    S-> baB

Now a match is obtained and B is replaced with its production

    S->bab

Thus input is successfully parsed. The steps in derivation can be summarised as

    S-> aAB (backtrack)
     -> bAB
     -> bdB (backtrack)
     -> baB
     -> bab

Answer 2

The answer to your question lies in the way we construct the parser. The parser constructs its parsing tables based on the next input character(lookahead) which it expects. As explained in the answer by @elantra the recursive descent chooses the production by checking on the input symbol.

if you have come across the terms such as LR(k) parsers , here 'k' represents the number of lookaheads parsers decides to check in the input before deciding which production to use . However for some values of k , such as zero there is a chance that parser is not able to decide which production to use. These situations while parsing are called conflicts. We chose the value of 'k' such that we don't face such conflicts. LR(1) and canonical LR are great examples.

Another aspect to your question is in the case of ambiguous grammars. It is difficult building a parser for the ambiguous grammars so we first convert the grammar to remove the ambiguity by introducing some sort of precedence or we could also use the operator precedence grammar which removes the ambiguity and construction of parser becomes feasible.

Answer 3

The answer to how to find out derivation of an input string require understanding of few basic computations like First and Follow.

To give you an intuition, what we are essentially trying to find out is "For each grammar symbol where in the sentential form this symbol can appear?".

There are multiple algorithms to find this out based on bottom-up or top-down approach. Once we know where possibly a grammar symbol derivation can be used we scan the input string left-to-right and use the appropriate derivation.

It might happen that we end up with multiple derivation appearing at same place in the sentential form. In such cases we cannot be sure which one to use. To tackle this problem we try to find out symbols that can appear after a grammar symbol in the sentential form and we look ahead one or more characters in the input string to check if those characters are the one that can follow the grammar symbol.

If you continue to watch the same video series that you mentioned, it goes on to explain the algorithms to do this.