Validity test for Floyd's operator-precedence parsing algorithms is polynomial in time.
Peter Růžička · Czech digital mathematics library · 1981
A polynomial time algorithm is developed to decide the equivalence of an operator-precedence grammar with the underlying Floyd's operator-precedence parsing algorithm, a result of possible practical significance.As a consequence the necessary and sufficient condition for an operatorprecedence grammar to be the valid grammatical characterization of the underlying Floyd's operator-precedence parsing algorithm is obtained.