Title: A bottom‐up parsing method for complete context‐free tree languages
Abstract: Abstract This paper proposes a bottom‐up parsing method for complete context‐free tree grammar. The complete context‐free tree grammar is an extension both of one‐dimensional context‐free grammar and regular tree grammar. This parsing method is an extension of the parsing method of Cocke‐Kasami‐Younger for one‐dimensional context‐free languages, and is the base of an error‐correcting parser for complete context‐free languages. The parsing method is divided into two steps. In the first step, the structure of the parsing table is generated. In the next step the input tree is parsed using the structure of the parsing table and a complete context‐free tree grammar. Both time and space complexities of generating the structure of a parsing table are fourth order of the number of nodes of the input tree. Those in step two are fourth and third order of the number of nodes of the input tree, respectively. This parsing method includes the use of the right‐hand context‐free tree grammar as a special case. Here, both complexities decrease by one order. Also, both complexities are the same as those of a top‐down parsing method for right‐hand context‐free tree grammar. Finally, this paper shows implementation of the parsing method and experimental results.
Publication Year: 1986
Publication Date: 1986-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot