Nullifying rules influence on speed in context free grammar LL(1)

• Autorzy: Pavlov V.
• Języki publikacji: EN

Abstrakty

EN

This research is an investigation of nullifying rules influence on speed of parsing grammar type LL(1). As a prototype, it’s considered a free context language based on LL(1) grammar, containing no nullifying rules (ε-rules). It is shown that recognizer which is based on deterministic push-down automaton (DPDA), in this case parses terms of the language in a minimum number of steps equal to length of the analyzed chain of tokens. It was demonstrated that for terms of another context-free language, which is also described by grammar LL(1) but containing nullifying rules, parsing by push-down automaton needs more cycles. It was shown, a cause of this is presence of nullifying (canceling) rules in LL(1) grammar. After transformations of the original grammar for exclusion these rules from the grammar, parsing speed increased almost to level of the prototype. This fact was confirmed by number of reviewed examples.

Słowa kluczowe

EN

context free grammar; LL(1) grammar; Syntax Improving Device; nullifying rules; ε-production

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Journal of Theoretical and Applied Computer Science
• Rocznik: 2016
• Tom: Vol. 10, nr 2
• Strony: 3--15
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Pavlov V.

• Faculty of Informatics and Computer Science, National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute»

Bibliografia

• [1] Aho, A. V. and Ullman, J. D.: The Theory of Parsing, Translation, and Compiling. Vol. 1: Parsing, Prentice-Hall, Englewood Cliffs, N. J., 1972.
• [2] Aho, A. V. and Ullman, J. D.: The Theory of Parsing, Translation, and Compiling. Vol. 2: Compiling, Prentice-Hall, Englewood Cliffs, N. J., 1973.
• [3] Aho, A. V. and Ullman, J. D.: Principles of Compiler Design, Addison-Wesley, Reading, Mass., 1977.
• [4] Backus J. W.: The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference Proc International Conf. on Information Processing, UNESCO 125–132, 1959.
• [5] Chomsky N.: Syntactic Structures, Language and Culture University Press, The Hague, Mouton & Co., 1957.
• [6] Chomsky N.: On the certain formal properties of. grammars. Information and Control, 1959 (a), 2, № 2, 137—167, 1959.
• [7] Cocke J., Schwartz J. T.: Programming languages and their compilers: (Technical report), Courant Institute of Mathematical Sciences, New York University, 1970.
• [8] Earley J.: An efficient context-free parsing algorithm, Communications of the ACM, 13 (2): 94–102, 1970.
• [9] Foster J. M.: A Syntax Improving Device. Computer Journal,11, 31-34, 1968.
• [10] Ginsburg S.: The mathematical theory of context-free languages, McGraw-Hill Book Company, NewYork-San Francisco-Toronto-London, I966.
• [11] Greibach S. A.: A new normal-form theorem for context-free phrase structure grammars. — J. Assoc. Computing Machinery, 12, № 1, 42—52, 1965.
• [12] Griffiths M.: LL(1) Grammars and Analysers., In F. L. Bauer and J. Eickel (Eds), Compiler Construction, an Advanced Course, Springer-Verlag, New York, pp. 57-84, 1974.
• [13] Gross M. et Lentin A.: Notions Sur Les Gramm Aires Formelles, Gauthier-Villards, Paris,1967.
• [14] Hunter R.: The Design and Construction of Compilers, John Wiley & Sons, New York, Toronto, 1983.
• [15] Kasami T.: An efficient recognition and syntax-analysis algorithm for context-free languages (Technical report). Air Force Cambridge Research Laboratories. 65-758,1965.
• [16] Knuth D. E.: Topdown Syntax Analysis. Acta Informatica,1, 79-110,1971.
• [17] Knuth D. E.: Semantics of Context-free Languages.Mathematical Systems Theory, 2,No. 2, 127-145,1968.
• [18] Knuth D. E: On the Translation of Languages from Left to Right. Information and Control,8, 607-639, 1965.
• [19] Marcus S.: Algebraic Linguistic Analytical Models, Academic Press, New York, London,1967.
• [20] Naur (Ed) P.: Report on the algorithmic language Algol 60. Comm. ACM. 3 (1960), 299-314, and Comm. ACM, 1 (1963), 1-17,1963.
• [21] Pratt T. W., Zelkowitz M. V.: Programming Languages, Design And Implementation. Prentice Hall PTR, Upper Saddle River, New Jersey, 1979.
• [22] Wirth N.: Compiler Construction, Addіson-Wesley, Zurich, 131, 2005.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).