高速なLL（1）構文解析表作成方式

• Item type: Trans(1)
• 公開日: 2002-03-15
• タイトル: 高速なLL（1）構文解析表作成方式
• タイトル / 言語: en
• タイトル: Fast LL (1) Parsing Table Construction Algorithm
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京農工大学工学部
• 著者所属: 拓殖大学工学部
• 著者所属: 東京農工大学工学部
• 著者所属: 拓殖大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Takushoku University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Takushoku University
• 著者名: 橋本, 裕; 早川, 栄一; 吉澤, 康文; 高橋, 延匡
• 著者名(英): Yutaka, Hashimoto; Eiichi, Hayakawa; Yasufumi, Yoshizawa; Nobumasa, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: LL（1）構文解析は，そのトップダウン解析という性質により，現在でも使用されることがある．この解析を実現するための一手法として，表駆動パーサを使う方法がある．これは，文法からLL（1）構文解析に必要となる表を作成し，その表に基づき解析を行うという方法である．本発表はこの表の高速な作成方式について述べたものである．本方式の特徴は次のとおりである．(1)探索に基づく作成方式．一般的に，LL（1）解析表の作成ではFirstとFollowという集合を計算し，それに基づいて表を作成する．この表の作成に使用されるアルゴリズムとしてよく知られているものに，Ahoらの著書に掲載されているアルゴリズムがある．このアルゴリズムではFirstとFollowの計算させるために値を伝播させている．本方式では不要な繰返しを防ぐため，伝播ではなく探索により計算を行う．(2)必要に応じたFirstとFollowの計算．前述のアルゴリズムでは表の作成のためにすべてのFirstとFollowを計算しているが，本方式では不要な部分の計算は行わない．(3)FirstとNullableの同時計算．あるアルゴリズムではあらかじめNullableを計算済みであることを要求するものがある．本方式ではFirstを計算するときに同時にNullableを計算することで高速化を図っている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: LL(1) parsing is still used because of the top-down parsing feature. The one method to realize this parsing is to use a table driven parser which parse input symbols by using a table which is generated from some other tables to parse the LL(1) grammar. In this presentation, we show a fast construction algorithm to generate these tables. The features are following: (a) Construction based on traverse: Generally, to construct the tables, algorithm calculates FIRST and FOLLOW sets and then calculates a final table from those sets. One of famous algorithm is written in a book by Aho et al. It propagates values to calculate FIRST and FOLLOW. Our method is based on traverse rather than propagation because of reducing redundant calculation loops. (b) Demand calculations for FIRST and FOLLOW: The algorithm written in the book mentioned above calculates all FIRST and FOLLOW sets, but our method does not calculate unnecessary parts of the sets. (c) Simultaneous calculations for FIRST and NULLABLE: Some algorithms request NULLABLE is already calculated. Our method calculates FIRST and then simultaneously calculates NULLABLE for faster
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 43, 号 SIG03(PRO14), p. 91-91, 発行日 2002-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会