Building Sequence Span Attribute Model and Example Analysis

Full Text (PDF, 245KB), PP.19-25

Views: 0 Downloads: 0


Yuqiang Sun 1,* Yuwan Gu 1 Guodong Shi 1

1. Changzhou university International Institute of Ubiquitous Computing, Jiangsu, Changzhou213164, China

* Corresponding author.


Received: 20 Jun. 2010 / Revised: 3 Nov. 2010 / Accepted: 17 Jan. 2011 / Published: 8 May 2011

Index Terms

Parsing, Algorithm design, Parallelization


Parallel parsing is one of the key technologies of parallel system. Grammatical character affects the efficiency of parallel parsing and degree of difficulty of implement. Existing methods have problems as follows: Parallelism of grammar that adapt different data object is difference, if there is a large difference between considering attribute and analysis object structure, then affect efficiency. Specific grammar parallel parsing is systematically studied. Scanning parallel parsing methods from the new angle of sequence span after word lattice distortion. Considering sequence span attribute between some specific grammars makes parsing without changing structure and data of CYK table based on the structure of word lattice CYK initialization table; In passing item of the form [i , j , Bη•] in parallel parsing item table memory structure in circle structure is adopted chain breaking technology; When indexed optimize analysis, the key algorithms of increasing the feasibility and validity of sequence span attribute、reusing parsing tree、calculating of d space function and node separating are further studied, then unification and optimize effect between analysis table middle structure and data object structure is reached. New algorithm and implement strategy of parallel parsing of specific grammar is proposed.

Cite This Paper

Yuqiang Sun, Yuwan Gu, Guodong Shi, "Building Sequence Span Attribute Model and Example Analysis", International Journal of Intelligent Systems and Applications(IJISA), vol.3, no.3, pp.19-25, 2011. DOI:10.5815/ijisa.2011.03.03


[1]Shen Zhiyu etc. Parallel Compilation Method. Beijing: National defence industry press.2002.

[2]Chen Huowang etc. Programming Language Compilation Theory. Beijing: National defence industry press.2003.

[3]Fatos Xhafa, Claudi Paniagua, Leonard Barolli, Santi Caballé. Using Grid services to parallelize IBM's Generic Log Adapter Journal of Systems and Software, Volume 84, Issue 1, January 2011, Pages 55-62

[4]M. Manna, F. Scarcello, N. Leone .On the complexity of regular-grammars with integer attributes Journal of Computer and System Sciences, Volume 77, Issue 2, March 2011, Pages 393-421

[5]Cristian.Ciressan,Eduardo.Sanchez,Martin.Rajman. An FPGA-based coprocessor for the parsing of context-free grammars. Proceeding of the 2000 IEEE Symposium on Field-Programmable Custom Computing Machines.


[7]A. Giannone , M. R. A. Eltantawi, P. Maresca. Recursive Parser Optimization by Rewriting Context-free Grammars.Pages:104-126,2002.

[8]Chaiyaporn Chirathamjaree. The use of context-free grammars in isolated word recognition. pages:140-143,2004.

[9]Ming-Heng Zhang. Quantitative structural information for inferring context free grammars with an extended Cocke-Younger-Kasami algorithm Pattern Recognition Letters, In Press, Accepted Manuscript, Available online 7 January 2011

[10]Jiangtian Li, Xiaosong Ma, Srikanth Yoginath, Guruprasad Kora, Nagiza F. Samatova. Transparent runtime parallelization of the R scripting language Journal of Parallel and Distributed Computing, Volume 71, Issue 2, February 2011, Pages 157-168

[11]Stefan Petrik, Semantic and phonetic automatic reconstruction of medical dictations Computer Speech & Language, Volume 25, Issue 2, April 2011, Pages 363-385

[12]Fei Xia, Yong Dou, Dan Zhou, Xin Li .Fine-grained parallel RNA secondary structure prediction using SCFGs on FPGA Parallel Computing, Volume 36, Issue 9, September 2010, Pages 516-530