Viable prefix

The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. An equivalent definition of a viable prefix is that it is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that sentential form. By this definition, it is always possible to add terminal symbols to the end of a viable prefix to obtain a right sentential form. Therefore, there is apparently no error as long as the portion of the input seen to a given point can be reduced to a viable prefix.

Bibliography

• Database Systems: The Complete Book (with H. Garcia-Molina and J. Widom), Prentice-Hall, Englewood Cliffs, NJ, 2002.
• Introduction to Automata Theory, Languages, and Computation, (with J. E. Hopcroft and R. Motwani), Addison-Wesley, Reading MA, 1969, 1979, 2000.
• Elements of ML Programming, Prentice-Hall, Englewood Cliffs, NJ, 1993, 1998.
• A First Course in Database Systems (with J. Widom), Prentice-Hall, Englewood Cliffs, NJ, 1997, 2002.
• Foundations of Computer Science (with A. V. Aho), Computer Science Press, New York, 1992.C edition, 1994.
• Principles of Database and Knowledge-Base Systems (two volumes), Computer Science Press, New York, 1988, 1989.
• Compilers: Principles, Techniques, and Tools (with A. V. Aho and R. Sethi), Addison-Wesley, Reading MA, 1977, 1986.
• Computational Aspects of VLSI, Computer Science Press, 1984
• Data Structures and Algorithms (with A. V. Aho and J. E. Hopcroft), Addison-Wesley, Reading MA, 1983.
• Principles of Compiler Design (with A. V. Aho, Harkirat Singh), Addison-Wesley, Reading, MA, 1977.
• Fundamental Concepts of Programming Systems, Addison-Wesley, Reading MA, 1976.
• The Design and Analysis of Computer Algorithms (with A. V. Aho and J. E. Hopcroft), Addison-Wesley, Reading MA, 1974.