An Algorithm for Constructing a Semi-LL(2) Grammar's Parsing Table
スポンサーリンク
概要
- 論文の詳細を見る
Most of the researches on constructing parsing tables for LL(k) grammars are those for k= 1, in short, for LL(1) grammars. There are few researches for LL(k) grammars in the case of k≧2 except for Aho and Ullman's. This results from the fact that every LL(1) grammar is strong but in the case of k≧2 there are two grammar classes, non-strong LL(k) grammars and strong LL(k) grammars. When we construct tables for strong LL(k) grammars, where k≧2, we can apply the same methods with LL(1) grammars. On the other hand, entirely different methods shou1d be applied to construct tables for non-strong LL(k) grammars, where k≧2, because the context problems are involved. This paper presents an algorithm on constructing parsing tables for semi-LL(k) grammars (where k=2) derived from giving a few restrictions to LL(k) grammars, and its validity and evaluation. There are also strong and non-strong grammars in the semi-LL(k) grammars but this algorithm is relatively straighforward, and the same constructing method can be applied for both strong and non-strong semi-LL(k) grammars. An experimentation on the performance of the algorithm using some example data shows that constructing time is about 1/ 1O, the memory size of the tab1es for parsing and production rules ranges about 1/ 120-1/400 of Aho and U1lman's algorithm. The memory size for codes, which are not affected by grammars, is larger than theirs approximately by 7%. The memory size for codes occupies about 29% of the whole program in the case of PASCAL- and about l00% in the case of ISO PASCAL. Generally, the more the number of the production rules increases, the more the rate of the codes part in the total memory decreases. Therefore, this slight increase in our case is thought to be negligible in the cases of languages in practical use.
- 一般社団法人情報処理学会の論文
- 1992-03-31
著者
-
Yoshida Keiichi
Department Of Applied Biology Kyoto Institute Of Technology
-
Takeuchi Yoshiko
Department Of Computer Science Hamamatsu Polytechnic College
-
Yoshida Keiichi
Department Of Computer Science College Of Engineering Shizuoka University
関連論文
- Fructose 1,6-Bisphosphate Aldolase Is a Heparin-Binding Protein
- Importance of 2-O-Sulfate Groups of Uronate Residues in Heparin for Activation of FGF-1 and FGF-2
- Neutralization of Toxic Heme by Plasmodium Falciparum Histidine-Rich Protein 2
- Effect of Antifungal Azoles on the Heme Detoxification System of Malarial Parasite
- Importance of 6-O-Sulfate Groups of Glucosamine Residues in Heparin for Activation of FGF-1 and FGF-2
- Some Properties of an Algorithm for Constructing LL(1) Parsing-Tables Using Production Indices
- An Algorithm for Constructing a Semi-LL(2) Grammar's Parsing Table
- Occlusion,prothodontic treatment, and temporomandibular disorders:A Review
- Pressure Effects on Electronic Structure and Magentism of Cu_2Sb-Type Compound Mn_2Sb
- Relationship of the Peripheral Cold Tolerance to Place of Birth, Body Mass Index and AIcohol Consumption
- Detection of fusion genes in sarcomas using paraffin-embedded tissues
- Changes in Stainability of Cortical Granule Materials with Tannic Acid before and after Fertilization in Mouse Ova(COMMUNICATION)(Developmental Biology)
- The Whole-Body (Human) Counter of the University of Tokyo:Its Structure and Performance