LR(k)構文解析器自動生成法

概要

論文の詳細を見る
A new method for building LR(k) states and parsing tables, and efficient parsing algorithm are presented. In the case k>1, the numbers of LR(k) states and elements of look ahead sets will increase. Necessity of look ahead states comes from undecidabilty of actions for some state; some state contains shifts (pushing the symbol in the stack) and reductions (with a production rule) or contains two or more reductions. But there are few such undecidable states. So, to calculate all look ahead sets is inefficient. Another reason to make the syntax analysis complex is that grammar may contain the production rules of the form A→e. In the grammar which contains no production rule of the form A→e and equivalent to original one, the numbers of production rule increase in general. In the case of the language C, the production rules increase about 20%, by eliminatoin of the form A→e. We make e-free grammar G' equivalent to original grammer G. Then calculate necesary strings for later calculation of look ahead strings. Analyzing input strings, we usually push statementnumbers and syntax symboles. In this paper we present the method, only statementnumbers are pushed in the stack. In addition to that, we push such state numbers that we use after reduction is done. By this merhod, we can analyze LR(k) grammar more efficiently.
帝京平成大学の論文
1995-10-31