Chapter 4, Problem 12RQ

Explanation of Solution

Parsing algorithms work only on a subset of grammars for the following reasons:

• Parsing based on a grammar (even unambiguous) is often complicated and inefficient.
• The complexity of parsing algorithms is generally ${\rm O}\left(n^3\right)$, which means the time will be of order of cube of the length of parsing string.
• Parsing algorithms are required to be repeated if parser makes some mistakes in the process. Also algorithms are required to be backed up as some times the parse tree created should be dismantled and rebuilt in some cases