An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages

摘要: Abstract : An efficient algorithm of recognition and syntaxanalysis for the full class context-free languages without difficulty exponential growth computing time with length n input sequence is presented. This makes use essential property a language as multi-parenthesis system. It shown in this paper that cubed-recognizable sense Hartmanis Stearns ('Computational complexity recursive sequences'. Proc. Fifth Annual Symposium Switching Circuit Theory Logical Design (Oct. 1964) p.82-90) by double-tape or double-head single-tape Turing machine it to 4th power-recognizable single-head machine. If we random-access memory whose size proportional cubed, required upperbounded C(1)n cubed + C(2)n squared N, where N denotes number nonequivalent valid derivation sequences given C(i)'s are constants independent sequences. tape C(3)n one C(4)n working memories, syntax-analysis C(5)n (1 N). The can be reduced order squared, but rises power. (Author)