retagged by
488 views

1 Answer

Best answer
3 votes
3 votes
I think order in which alternative are tried only improves the no. of times parser  has to backtrack.

Suppose

S->aAb|aB

A->c|d

B->ddc

Check for w=addc.  

Parser will choose S->aAb and undergoes backtracking 2 times. If it can choose another alternative i.e S->aB there will be no backtracking.

As far as talking about languages it will be the same because ultimately parser will generate the language whether it has generated it with backtracking or without backtracking.
selected by

Related questions

1 votes
1 votes
1 answer
1
durgesh94 asked Jun 15, 2016
1,737 views
Which of the following feature(s) is/are needed to implement top down parsingSource string marker Prediction making mechanismMatching and Backtracking me...
2 votes
2 votes
1 answer
2
admin asked Mar 31, 2020
4,339 views
Which type of algorithm is used to solve the "$8$ Queens" problem ?GreedyDynamicDivide and conquerBacktracking
1 votes
1 votes
0 answers
3
LavTheRawkstar asked Sep 9, 2018
644 views
Find all the possible solution for sum of subset problem for the instance m=35 and S=<1,2,5,7,8,10,15,20,25 using Backtracking.I am totally confused hence please provide ...
1 votes
1 votes
1 answer
4
LavTheRawkstar asked Apr 19, 2017
2,655 views
Genearate atleast 3 solutions for 5 x 5 queen problem