tailieunhanh - Báo cáo khoa học: "INTERRUPTABLE TRANSITION NETWORKS "

A specialized transition network mechanism, the interruptable transition n e t w o r k (ITN) is used to p e r f o r m the last of three stages in a m u l t i p r o c e s s o r s y n t a c t i c parser. This approach can be seen as an exercise in implementing a parsing procedure of the active chart parser family. Most of the ATN parser implementations use the left-to-right top-down chronological backtracking control structure (cf. Bates, 1978 for discussion). | INTERRUPTABLE TRANSITION NETWORKS Sergei Nirenburg Colgate University Chagit Attiya Hebrew University of Jerusalem ABSTRACT A specialized transition network mechanism the interruptable transition network ITN is used to perform the last of three stages in a multiprocessor syntactic parser. This approach can be seen as an exercise in implementing a parsing procedure of the active chart parser family. Most of the ATN parser implementations use the left-to-right top-down chronological backtracking control structure cf. Bates 1978 for discussion . The control strategies of the active chart type permit a blend of bottom-up and top-down parsing at the expense of time and space overhead cf. Kaplan 1973 . The environment in which the interruptable transition network ITN has been implemented is not similar to t hat of a typical ATN model. Nor is it a straightforward implementation of an active chart. ITN is responsible for one stage in a multiprocessor parsing technique described in Lozinskii Nirenburg 1982a and b where parsing is performed in essentially the bottom-up fashion in parallel by a set of relatively small and dumb processing units running identical software. The process involves three stages a producing the candidate strings of preterminal category symbols - b determining the positions in this string at which higher-level constituents start and c determining the closing boundaries of these constituents. Each of the processors allocated to the first stage obtains the set of all syntactic readings of one word in the input string. Using a table grammar the processors then choose a subset of the word s readings to ensure compatibility with similar subsets generated by this processor s right and left neighbor. Stage 2 uses the results of stage 1 and a different tabular grammar to establish the left opening boundaries for composite sentence constituents such as NP or pp. The output of this stage assumes the form of a string of triads ilabel X y where label belongs to .