Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân tích LL song song
Tóm tắt
Một thuật toán phân tích LL song song có tính quyết định được trình bày. Thuật toán này dựa trên một sự chuyển đổi từ vấn đề phân tích thành giảm song song. Đầu tiên, một phiên bản không quyết định của bộ phân tích LL song song được giới thiệu. Sau đó, nó được chuyển đổi thành phiên bản có tính quyết định - bộ phân tích LLP. Bộ phân tích LLP(q,k) có tính quyết định sử dụng hai loại thông tin để chọn lựa hoạt động tiếp theo - một chuỗi nhìn tới có độ dài lên tới k ký tự và một chuỗi nhìn lùi có độ dài lên tới q ký tự. Phân tích có tính quyết định khả thi cho ngữ pháp LLP, là một phân lớp của ngữ pháp LL. Do cả hai bộ phân tích song song có tính quyết định và không có tính quyết định được dựa trên việc giảm song song, chúng thích hợp cho hầu hết các kiến trúc song song.
Từ khóa
#thuật toán phân tích LL #phân tích song song #ngữ pháp LLP #giảm song song #kiến trúc song songTài liệu tham khảo
Adriaens G., Hahn U., (eds) (1994) Parallel Natural Language Processing. Ablex Publishing Corporation, Norwood
Aho A.V., Ullman J.D. (1972) The theory of parsing, translation and compiling, parsing, vol 1, compiling, vol 2. Prentice-Hall Inc., Englewood Cliff
Andrei S.: Bidirectional parsing. Ph.D. Thesis, Fachbereich Informatik, Universiteit Hamburg, Germany, 2000, pp. 39–54. Available in electronic form: http://www.sub.unihamburg.de/disse/134/inhalt.html
Aycock J., Horspool N., Janoušek J., Melichar B. (2001) Even faster generalized LR parsing. Acta Inf. 37, 633–651
Bunt H., Tomita M. (1996) Recent Advances in Parsing Technology. Kluwer Academic Press, Dordrecht
Cole M.: List homomorphic parallel algorithms for bracket matching. Department of Computer Science, University of Edinburgh, CSR-29-93 (1993)
Chang J.H., lbarra O.H., Palis M.A. (1987) Parallel parsing on a one-way array of finite-state machines. IEEE Trans. Comput. 36, 64–75
Chiang Y.T., Fu K.S. (1984) Parallel parsing algorithms and VLSI implementations for syntactic pattern recognition. IEEE Trans. Pattern Anal. Mach. Intell. 6, 302–314
Gibbons A., Rytter W. (1988) Efficient Parallel Algorithms, Chapt 4. Cambridge University Press, London
Hill J.M.D.: Parallel lexical analysis and parsing on the AMT distributed array processor. In: Parallel Computing, pp. 699–714 (1992)
Ibarra O.H., Pong T.-C., Sohn S.M. (1991) Parallel recognition and parsing on the hypercube. IEEE Trans. Comput. 40, 764–770
Janoušek J.: Some new results in sequential and parallel (generalized) LR parsing and translation. Ph.D. Thesis, CTU FEE Prague (2001)
Kosaraju S. (1975) Speed of recognition of context-free languages by array automata. SIAM J. Comput. 4, 331–340
Kurki-Suonio R. (1969) Notes on top–down languages. BIT 9, 225–238
Luttighuis P.O. (1993) Parallel Algorithms for Parsing and Attribute Evaluation. FEBO druk, Enschede, The Netherlands
Melichar B., Vagner L.: Parallel LLP(q,k) parsing. In: Proceedings of Workshop 02, vol. A, CTU Prague, pp. 190–191 (2002)
Melichar B., Vagner L.: Time-optimal LLP parsing with parallel parentheses matching. In: POSTER 2002 – Book of Extended Abstracts, CTU Prague, Faculty of Electrical Engineering (2002)
Melichar B., Vagner L.: Formal parallel translation directed by parallel LLP(q,k) parser. In: Proceedings of Workshop 03, CTU Prague, vol. A, pp. 236–237 (2003)
Prasad S.K., Das S.K., Chen C.C.-Y. (1994) Efficient EREW PRAM Algorithms for Parentheses-Matching. IEEE Trans. Parallel Distrib. Syst. 5(9): 995–1008
Ra D.-Y., Kim J.-H. (1996) A parallel parsing algorithm for arbitrary context-free grammars. Inf. Process. Lett. 58, 87–96
Šaloun P., Melichar B. (2002) Parallel Parsing of LRP(q,k) Languages. MARQ, Ostrava
Shankar P.: O(log(n)) parallel parsing of a subclass of LL(1) languages. In: Parallel Computing, pp. 511–516 (1990)
Skillicorn D.B., Barnard D.T.: Parallel parsing on the connection machine. In: Information Processing Letters, pp. 111–117 (1989)
Tseytlin G.E., Yushchenko E.L.: Several aspects of theory of parametric models of languages and parallel syntactic analysis. In: Ershov A., Koster C.H.A. (eds.) Methods of Algorithmic Language Implementation, LNCS 47, pp. 231–245. Springer, Berlin Heidelberg New York (1977)