{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22566"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22566","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Table-driven parsing of natural language with constraint-based grammars","abstract":"In this dissertation, it is shown how efficient natural language parsing with constraint-based grammars can be achieved. In so doing, a variant of the LR-parsing algorithm is developed that deals with grammars using feature-based categories. It is shown that constraint-based grammars bring about the problems of potential nontermination and unnecessary nondeterminism with the LR parsing method, which do not arise from grammars using monadic categories. To achieve a terminating and deterministic algorithm, an extended method for constructing parsing tables is developed. The extended LR method is unable to handle schematic rules as in HPSG and CUG, however. To remedy this problem, a rule inference algorithm is developed that instantiates underspecified rules into more specified ones containing enough information to construct sets of items and parsing tables. The implementation and evaluation of the extended LR parsing method is also discussed.","abstract_html":"In this dissertation, it is shown how efficient natural language parsing with constraint-based grammars can be achieved. In so doing, a variant of the LR-parsing algorithm is developed that deals with grammars using feature-based categories. It is shown that constraint-based grammars bring about the problems of potential nontermination and unnecessary nondeterminism with the LR parsing method, which do not arise from grammars using monadic categories. To achieve a terminating and deterministic algorithm, an extended method for constructing parsing tables is developed. The extended LR method is unable to handle schematic rules as in HPSG and CUG, however. To remedy this problem, a rule inference algorithm is developed that instantiates underspecified rules into more specified ones containing enough information to construct sets of items and parsing tables. The implementation and evaluation of the extended LR parsing method is also discussed.","abstract_has_math":false,"creators":["Lee, Kang-Hyuk"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Linguistics","degree_department":null,"school":null,"contributors":["Morgan, Jerry L."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:44:00Z","date_published":"2011-05-07T13:44:00Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Language, Linguistics"],"languages":["eng"],"rights":["Copyright 1993 Lee, Kang-Hyuk"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9314899","(UMI)AAI9314899"],"render_values":[{"text":"AAI9314899","href":null,"code":true},{"text":"(UMI)AAI9314899","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22566","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Morgan, Jerry L."]},{"key":"dc:creator","label":"Author","values":["Lee, Kang-Hyuk"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:44:00Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Linguistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Language, Linguistics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1993 Lee, Kang-Hyuk"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9314899","(UMI)AAI9314899","http://hdl.handle.net/2142/22566"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this dissertation, it is shown how efficient natural language parsing with constraint-based grammars can be achieved. In so doing, a variant of the LR-parsing algorithm is developed that deals with grammars using feature-based categories. It is shown that constraint-based grammars bring about the problems of potential nontermination and unnecessary nondeterminism with the LR parsing method, which do not arise from grammars using monadic categories. To achieve a terminating and deterministic algorithm, an extended method for constructing parsing tables is developed. The extended LR method is unable to handle schematic rules as in HPSG and CUG, however. To remedy this problem, a rule inference algorithm is developed that instantiates underspecified rules into more specified ones containing enough information to construct sets of items and parsing tables. The implementation and evaluation of the extended LR parsing method is also discussed.","The LR-based parsing method is further explored to find out whether it can be used to model human sentence processing. Traditional approaches to local ambiguity resolution are reviewed. It is shown how the reduce-first LR parser and combinatory categorial grammar can be used with a semantics-based local ambiguity resolution technique.","Finally, prominent problems with the two-level model for morphological parsing are discussed. A two-level morphological processor augmented with feature-based CF word grammars is proposed which allows for more enriched morphosyntactic descriptions. It is shown how LR predictions manifested in the parsing table can used to optimize the dictionary lookup process.","Made available in DSpace on 2011-05-07T13:44:00Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9314899.pdf: 4379965 bytes, checksum: 1d736b58da015cec150eb8cc3e65e09a (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:58:29Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:31-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Table-driven parsing of natural language with constraint-based grammars"]}]}],"canonical_facts":{"dc:contributor":["Morgan, Jerry L."],"dc:creator":["Lee, Kang-Hyuk"],"dc:date":["2011-05-07T13:44:00Z","10000-01-01","1993"],"dc:description":["In this dissertation, it is shown how efficient natural language parsing with constraint-based grammars can be achieved. In so doing, a variant of the LR-parsing algorithm is developed that deals with grammars using feature-based categories. It is shown that constraint-based grammars bring about the problems of potential nontermination and unnecessary nondeterminism with the LR parsing method, which do not arise from grammars using monadic categories. To achieve a terminating and deterministic algorithm, an extended method for constructing parsing tables is developed. The extended LR method is unable to handle schematic rules as in HPSG and CUG, however. To remedy this problem, a rule inference algorithm is developed that instantiates underspecified rules into more specified ones containing enough information to construct sets of items and parsing tables. The implementation and evaluation of the extended LR parsing method is also discussed.","The LR-based parsing method is further explored to find out whether it can be used to model human sentence processing. Traditional approaches to local ambiguity resolution are reviewed. It is shown how the reduce-first LR parser and combinatory categorial grammar can be used with a semantics-based local ambiguity resolution technique.","Finally, prominent problems with the two-level model for morphological parsing are discussed. A two-level morphological processor augmented with feature-based CF word grammars is proposed which allows for more enriched morphosyntactic descriptions. It is shown how LR predictions manifested in the parsing table can used to optimize the dictionary lookup process.","Made available in DSpace on 2011-05-07T13:44:00Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9314899.pdf: 4379965 bytes, checksum: 1d736b58da015cec150eb8cc3e65e09a (MD5) Previous issue date: 1993","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:58:29Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:27:31-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9314899","(UMI)AAI9314899","http://hdl.handle.net/2142/22566"],"dc:language":["eng"],"dc:rights":["Copyright 1993 Lee, Kang-Hyuk"],"dc:subject":["Language, Linguistics"],"dc:title":["Table-driven parsing of natural language with constraint-based grammars"],"dc:type":["text"],"thesis:degree_discipline":["Linguistics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:20Z"}