AITEC Contract Research Projects in FY1995 : Software

(15) A Study on Parallel Robust Parsing System based on GLR Algorithm

Dr. Susumu Kunifuji, Professor, Japan Advanced Institute for Science and Technology

R-LRPar : A Robust Generalized LR Parser

Dr. Thanaruk Theeramunkong
Mr. Hiroki Imai
Associate Prof. Manabu Okumura
Prof. Susumu Kunifuji

[Features of the Software]

This software is useful for analyzing natural language based on a given context-free grammar. As the result of the software, the syntactic trees of the analyzed input will be outputed. This resultant trees are used as an input to the succeeding processing, such as semantic analysis, discourse analysis and reasoning. The algorithm applied is based on the fastest parsing algorithm named `Generalized LR parsing method'. Due to this, our software is expected to parse an input efficiently and with high speed. Furthermore, this software can analyze not only grammatical inputs but also ungrammatically ill-formed inputs. Although it can robustly parse an _ill-formed_ input, efficiency of the analysis of _grammatical_ inputs is not sacrificed because the extra processing steps which are needed for analyzing ill-formed inputs are not executed.

[Required Environment]

The software is constructed using Prolog(Sicstus), Perl, Shell, C languages. We mainly check the software on SunOS 4.1.3. However, we expect that this software can run on several environments which prolog interpreter, especially Sicstus prolog, is installed. Several programs written in Shell language or Perl can used in almost UNIX environments.

[File Configuration]

./README
./README.j
./src ./src/LR_prolog # Including the main program ./src/LR_prolog/action2entry.pl ./src/LR_prolog/append.pl ./src/LR_prolog/change_form.pl ./src/LR_prolog/decide_action_write_table.pl ./src/LR_prolog/error_handling.pl ./src/LR_prolog/expand.pl ./src/LR_prolog/extract.pl ./src/LR_prolog/first.pl ./src/LR_prolog/flags.pl ./src/LR_prolog/table1 ./src/LR_prolog/tmp.entry ./src/LR_prolog/make_all_gss.pl ./src/LR_prolog/maketable_write_table.pl ./src/LR_prolog/mkcnd.pl ./src/LR_prolog/mkinterface.pl ./src/LR_prolog/mkstart.pl ./src/LR_prolog/mkstart2.pl ./src/LR_prolog/mymakegss.pl ./src/LR_prolog/other_entry.pl ./src/LR_prolog/parseinterf ./src/LR_prolog/parser.pl ./src/LR_prolog/print_tree.pl ./src/LR_prolog/record_info.pl ./src/LR_prolog/retrieve-E.pl ./src/LR_prolog/start.pl ./src/LR_prolog/symbol_handling.pl ./src/LR_prolog/table2 ./src/LR_prolog/time.pl ./src/LR_prolog/tmp.cnd ./src/LR_prolog/gram1 ./src/LR_prolog/tmp.start ./src/LR_prolog/tree.pl ./src/LR_prolog/util.pl ./src/LR_prolog/gram ./src/LR_prolog/gram2 ./src/LR_prolog/run.pl ./src/LR_prolog/table ./src/LR_prolog/sent_file.re ./src/LR_prolog/changesent.pl ./src/LR_kl1 # RLRPar for PIM (under construction) ./src/LR_kl1/action2entry.pl ./src/LR_kl1/append.pl ./src/LR_kl1/change_form.pl ./src/LR_kl1/decide_action_write_table.pl ./src/LR_kl1/error_handling.pl ./src/LR_kl1/expand.pl ./src/LR_kl1/extract.pl ./src/LR_kl1/first.pl ./src/LR_kl1/flags.pl ./src/LR_kl1/gram ./src/LR_kl1/gram.orig ./src/LR_kl1/make_all_gss.pl ./src/LR_kl1/maketable_write_table.pl ./src/LR_kl1/mkcnd.pl ./src/LR_kl1/mkinterface.pl ./src/LR_kl1/mkstart.pl ./src/LR_kl1/mkstart2.pl ./src/LR_kl1/mymakegss.pl ./src/LR_kl1/other_entry.pl ./src/LR_kl1/parseinterf ./src/LR_kl1/parser.pl ./src/LR_kl1/print_tree.pl ./src/LR_kl1/record_info.pl ./src/LR_kl1/retrieve-E.pl ./src/LR_kl1/start.pl ./src/LR_kl1/symbol_handling.pl ./src/LR_kl1/table ./src/LR_kl1/time.pl ./src/LR_kl1/tmp.cnd ./src/LR_kl1/tmp.entry ./src/LR_kl1/tmp.start ./src/LR_kl1/tree.pl ./src/LR_kl1/util.pl ./src/gram # grammar directory ./src/gram/gram260 ./src/gram/gram ./src/gram/gram.orig ./src/gram/gramtable ./src/gram/gram260.org ./src/gram/gram260_table ./src/R-LRParser # Interface program for RLRPar ./src/R-LRParser/exam_sent ./src/R-LRParser/sfile ./src/R-LRParser/sfile.re ./src/R-LRParser/README ./src/R-LRParser/runtagger ./src/R-LRParser/sent_file.re ./src/R-LRParser/changeform ./src/btagger # Brill's tagger (see license) ./src/btagger/Tagger_Code ./src/btagger/Tagger_Code/nbest-tagger.c ./src/btagger/Tagger_Code/start-state-tagger.c ./src/btagger/Tagger_Code/final-state-tagger.c ./src/btagger/Tagger_Code/tagger.c ./src/btagger/Utils ./src/btagger/Utils/lex.c ./src/btagger/Utils/lex.h ./src/btagger/Utils/registry.c ./src/btagger/Utils/registry.h ./src/btagger/Utils/registryP.h ./src/btagger/Utils/darray.c ./src/btagger/Utils/darray.h ./src/btagger/Utils/darrayP.h ./src/btagger/Utils/memory.c ./src/btagger/Utils/memory.h ./src/btagger/Utils/useful.h ./src/btagger/Utils/bool.h ./src/btagger/Utils/sysdep.h ./src/btagger/Utils/useful.c ./src/btagger/Utils/lex.o ./src/btagger/Utils/useful.o ./src/btagger/Utils/darray.o ./src/btagger/Utils/registry.o ./src/btagger/Utils/memory.o ./src/btagger/Docs ./src/btagger/Docs/README.FIRST ./src/btagger/Docs/README.LONG ./src/btagger/Docs/README.QUICK ./src/btagger/Docs/README.TRAINING ./src/btagger/Docs/aaai94-tagger.ps ./src/btagger/Docs/README.NBEST ./src/btagger/Makefile ./src/btagger/Learner_Code ./src/btagger/Learner_Code/fix-kbest-rule-learn.c ./src/btagger/Learner_Code/contextual-rule-learn.c ./src/btagger/Learner_Code/unknown-lexical-learn.prl ./src/btagger/Learner_Code/unknown-lexical-learn-continue.prl ./src/btagger/Learner_Code/kbest-contextual-rule-learn.c ./src/btagger/COPYRIGHT ./src/btagger/Utilities ./src/btagger/Utilities/combine-lexicons.prl ./src/btagger/Utilities/comparitor-nbest.prl ./src/btagger/Utilities/comparitor.prl ./src/btagger/Utilities/delete-top-n.prl ./src/btagger/Utilities/incorporate-new-bigrams.prl ./src/btagger/Utilities/incorporate-new-words.prl ./src/btagger/Utilities/make-restricted-lexicon.prl ./src/btagger/Utilities/trim-bigrams.prl ./src/btagger/Utilities/divide-in-two-rand.prl ./src/btagger/Utilities/tagged-to-untagged.prl ./src/btagger/Utilities/bigram-generate.prl ./src/btagger/Utilities/wordlist-make.prl ./src/btagger/Utilities/word-tag-count.prl ./src/btagger/Bin_and_Data ./src/btagger/Bin_and_Data/BIGRAMS ./src/btagger/Bin_and_Data/CONTEXTUALRULEFILE ./src/btagger/Bin_and_Data/CONTEXTUALRULEFILE.BROWN ./src/btagger/Bin_and_Data/LEXICON.BROWN ./src/btagger/Bin_and_Data/CONTEXTUALRULEFILE.WSJ ./src/btagger/Bin_and_Data/LEXICALRULEFILE ./src/btagger/Bin_and_Data/LEXICALRULEFILE.BROWN ./src/btagger/Bin_and_Data/LEXICALRULEFILE.WSJ ./src/btagger/Bin_and_Data/LEXICON ./src/btagger/Bin_and_Data/LEXICON.BROWN.AND.WSJ ./src/btagger/Bin_and_Data/LEXICON.WSJ.Z ./src/btagger/Bin_and_Data/NBEST-RULES ./src/btagger/Bin_and_Data/CONTEXTUALRULEFILE.WSJ.NOLEX ./src/btagger/Bin_and_Data/contextual-rule-learn ./src/btagger/Bin_and_Data/kbest-contextual-rule-learn ./src/btagger/Bin_and_Data/fix-kbest-rule-learn ./src/btagger/Bin_and_Data/tagger ./src/btagger/Bin_and_Data/final-state-tagger ./src/btagger/Bin_and_Data/start-state-tagger ./src/btagger/Bin_and_Data/nbest-tagger ./src/btagger/Bin_and_Data/README ./src/btagger/Bin_and_Data/Example ./src/btagger/Bin_and_Data/Example/example_sentences ./src/btagger/Bin_and_Data/Example/example_sentences.re ./src/btagger/README ./src/btagger/HOWTOUSE
./README
./Manual.jis # Manual (in jis code)
./README.jis # README (in jis code)
./Files # The List of File
./Specification # Specification
./Manual # Manual File
./man # Electronic Manual Directory ./man/cat1 ./man/cat1/rlrpar.1 ./man/man1 ./man/man1/rlrpar.1 ./man/whatis

[Others]

For Brill's Tagger, please see its license.

This software is still now under development.

[FTP]

README
Program and Documents in Japanese [1768K]

www-admin@icot.or.jp