S( )
{
if (input =='a' )
{
advance( );
if (A( ) != error)
if (input =='b')
{ advance( );
if (input == endmarker)
return(success);
else
return(error);
}
else
return(error);
}
else
return(error);
}
A( )
{
if (input =='c')
{
advance( );
if (input == 'd')
advance( ); }
else
return(error);
}
main( )
{
Append the endmarker to the string w to be parsed;
Set the input pointer to the left most token of w;
if ( S( ) != error)
print f ("Successful completion of the parsing");
else
printf ("Failure");
}
where advance() is a routine that, when called, advances the input's pointer to the next occurrence of the symbol w.
| Caution� |
In a backtracking parser, the order in which alternatives are tried affects the language accepted by the parser. For example, in the above parser, if a production A → c is tried before A → cd, then the parser will fail to accept the string w = acdb, because it first expands S, as shown in Figure 1.
|
The first input symbol matches the left-most leaf; and therefore, the parser will advance the pointer to c and consider the nonterminal A for expansion in order to obtain the tree shown in Figure 2.
The second input symbol also matches. Therefore, the parser will advance the pointer to d, the third input symbol, and consider the next leaf, labeled b in Figure 2. It finds that there is no match; and therefore, it will backtrack to S (as shown in Figure 2 by the thick arrow). But since there is no alternative to S that can be tried, the parser will return failure. Because the point of mismatch is the descendent of a node labeled by S, the parser will backtrack to S. It cannot backtrack to A. Therefore, the parser will not accept the string acdb. Whereas, if the parser tries the alternative A → cd first and A → c second, then the parser is capable of accepting the string acdb as well as acb because, for the string w = acb, when the parser encounters a mismatch, it is at a node labeled by d, which is a descendent of a node labeled by A. Hence, it will backtrack to A and try A → c, and end up in the parse tree for acb. Hence, we conclude that the order in which alternatives are tried in a backtracking parser affect the language accepted by the compiler or parser.
EXAMPLE 1
Consider a grammar S → aa | aSa. If a top-down backtracking parser for this grammar tries S → aSa before S → aa, show that the parser succeeds on two occurrences of a and four occurrences of a, but not on six occurrences of a.
In the case of two occurrences of a, the parser will first expand S, as shown in Figure 2.
The first input symbol matches the left-most leaf. Therefore, the parser will advance the pointer to a second a and consider the nonterminal S for expansion in order to obtain the tree shown in Figure 3.
The second input symbol also matches. Therefore, the parser will consider the next leaf labeled S and expand it, as shown in Figure 4.
The parser now finds that there is no match. Therefore, it will backtrack to S, as shown by the thick arrow in Figure 5. The parser then continues matching and backtracking, as shown in Figures 6 through 11, until it arrives at the required parse tree, shown in Figure 12.
Now, consider a string of four occurrences of a. The parser will first expand S, as shown in Figure 13.
The first input symbol matches the left-most leaf. Therefore, the parser will advance the pointer to a second a and consider the nonterminal S for expansion, obtaining the tree shown in Figure 14.
The second input symbol also matches. Therefore, the parser will consider the next leaf labeled by S and expand it, as shown in Figure 15.
The third input symbol also matches. So, the parser moves on to the next leaf labeled by S and expands it, as shown in Figure 16.
The fourth input symbol also matches. Therefore, the next leaf labeled by S is considered. The parser expands it, as shown in Figure 17.
Now it finds that there is no match. Therefore, it will backtrack to S (Figure 18) and continue backtracking, as shown in Figures 19 through 26, until the parser finally arrives at the successful generation of a parse tree for aaaa in Figure 27.
Now consider a string of six occurrences of a. The parser will first expand S, as shown in Figure 28.
The first input symbol matches the left-most leaf. Therefore, the parser will advance the pointer to the second a and consider the nonterminal S for expansion. The tree shown in Figure 29 is obtained.
The second input symbol also matches. Therefore, the parser will consider next leaf labeled S and expand it, as shown in Figure 30.
The third input symbol also matches, as do the fourth through sixth symbols. In each case, the parser will consider next leaf labeled S and expand it, as shown in Figures 31 through 34.
Now the parser finds that there is no match. Therefore, it will backtrack to S, as shown by the thick arrow in Figure 35.
Since there is no alternate of S that can be tried, the parser will backtrack one more step, as shown in Figure 36. This procedure continues (Figures 37 through 43), until the parser tries the sixth alternate aa (Figure 44) and fails to find a match.
