부산대학교 도서관

Presents near constant time associative parallel lexing (APL) algorithms. The best time complexity thus far claimed is O(logn) (n denotes the number of input characters for the parallel prefix lexing (PPL) algorithm. The linear state recording step in the PPL algorithm, which needs to be done only once for each grammar has been ignored in claiming the log n time complexity for the PPL algorithm. Furthermore, the PPL algorithm does not consider recording line numbers for the tokens and distinguishing identifier tokens as keywords or user-identifiers. The APL algorithms perform all of these functions. Thus, without considering the efforts spent on these functions, the APL algorithm takes constant time since every step depends on the length of the tokens, not on the length of the input. Generalizing and including these extra functions, the APL algorithm takes near constant time.ETX