Validity test for Floyd's operator-precedence parsing algorithms is polynomial in time

Peter Růžička

Kybernetika (1981)

  • Volume: 17, Issue: 5, page 368-379
  • ISSN: 0023-5954

How to cite

top

Růžička, Peter. "Validity test for Floyd's operator-precedence parsing algorithms is polynomial in time." Kybernetika 17.5 (1981): 368-379. <http://eudml.org/doc/28659>.

@article{Růžička1981,
author = {Růžička, Peter},
journal = {Kybernetika},
keywords = {operator-precedence grammars; worst-case time complexity of algorithms; equivalence problem},
language = {eng},
number = {5},
pages = {368-379},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Validity test for Floyd's operator-precedence parsing algorithms is polynomial in time},
url = {http://eudml.org/doc/28659},
volume = {17},
year = {1981},
}

TY - JOUR
AU - Růžička, Peter
TI - Validity test for Floyd's operator-precedence parsing algorithms is polynomial in time
JO - Kybernetika
PY - 1981
PB - Institute of Information Theory and Automation AS CR
VL - 17
IS - 5
SP - 368
EP - 379
LA - eng
KW - operator-precedence grammars; worst-case time complexity of algorithms; equivalence problem
UR - http://eudml.org/doc/28659
ER -

References

top
  1. A. V. Aho J. D. Ullman, The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing, Prentice-Hall, 1972. (1972) MR0408321
  2. A. J. Demers, Skeletal LR parsing, 15th Annual Symposium on Switching and Automata Theory 1974, 185-198. (1974) MR0426507
  3. N. El Djabri, Extending the LR Parsing Techniques to Some Non-LR Grammars, TR-121, Princeton University, New Jersey 1973. (1973) 
  4. M. J. Fischer, Some properties of precedence languages, 1st Annual ACM Symposium on Theory of Computing 1969, 181-190. (1969) 
  5. J. N. Gray, Precedence Parsers for Programming Languages, Ph. D. Thesis, Department of Computer Science, University of California, Berkeley 1969. (1969) 
  6. D. S. Henderson M. R. Levy, An extended operator-precedence parsing algorithm, Comput. J. 19 (1976), 3, 229-233. (1976) MR0449038
  7. D. Knuth, Top down syntax analysis, Acta Informatica I (1971), 2, 79-110. (1971) 
  8. M. R. Levy, Complete operator precedence, Information Processing Lett. 4 (1975), 2, 38-40. (1975) Zbl0322.68055MR0502298
  9. R. Mc Naughton, Paranthesis grammars, J. Assoc. Comput. Mach. 14 (1967), 3, 490-500. (1967) MR0234781
  10. M. C. Paull S. H. Unger, Structural equivalence of context-free grammars, J. Comput. System Sci. 2 (1968), 1, 427-463. (1968) MR0241203
  11. P. Růžička, Validity test for Floyd's operator-precedence parsing algorithms, In: Mathematical Foundations of Computer Science (J. Bečvář, ed.), Lecture Notes in Computer Science 74. Springer-Verlag, Berlin 1979, 415-424. (1979) Zbl0412.68082

NotesEmbed ?

top

You must be logged in to post comments.