Parsing with truncated counter vectors of terminal symbols
Kouji Yamamoto, Takehiro Tokuda · Electronics and Communications in Japan (Part II Electronics) · 2005
Normal parsing is performed for an ordered string of input terminal symbols. In contrast, consider chart parsing in which a chart derived by using a parametrized context-free grammar, for example, is given, and a string that enumerates its constituent elements is parsed. In this case, the enumerated string, which does not necessarily match the order of a derived string, becomes a replacement string of a derived string. As a result, even if a grammar is used which added production rules that replaced each symbol of the right-hand side, for example, conventional methods that use order information could not generally parse this string properly. This paper shows two methods—a bottom-up method and a top-down method—which definitely enable parsing when order information cannot be used for the terminal symbols of the derived strings of a context-free grammar. These methods use counter vectors of truncated numbers of occurrences of each terminal symbol in the remaining input strings. The bottom-up method, which differs from normal parsing in that it does not consist of only reduce actions, also requires a uniquely determined shift action. The top-down method can handle some left-recursive productions that cannot be handled by normal parsing methods since the terminal symbol comparison position need not be limited to the left end. In other words, this paper shows methods that use counter vectors to uniquely parse an input string that does not necessarily match the order of a derived string to obtain parsing results for the corresponding derived string under fixed conditions. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 88(6): 54–63, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20191