同一入力位置で複数発生する左再帰へ対応したPackrat Parsingの設計と実装  [in Japanese] Design and Implementation of Packrat Parsing to Parse Grammars That Have Multiple Left Recursions at an Input Position  [in Japanese]

Access this Article

Search this Article

Abstract

構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,バックトラックや無限先読みを用いた解析において,線型時間で解析可能である.また,Packrat Parsing は再帰下降構文解析法の一種であるため,左再帰を含む文法を解析できない.そこで従来は,左再帰を含む文法の解析を要求される際,左再帰部分を同一の入力を解析可能な右再帰へと変換し,左再帰を除去して解析を行う.だが,特定の左再帰は除去できないため,この手法で解析できない文法がある.Alessandro らは,Packrat Parsing において,左再帰を含む文法を,右再帰への文法の変換なしに解析可能にした.しかし,Alessandro らの実装では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗するという問題点がある.そこで本論文では,左再帰が複数発生する文法において,解析できる手法を提案・実装し,評価を行った.There is Packrat Parsing among parsing methods. Packrat Parsing can parse backtracking and unlimited look-ahead in linear parse time. And Packrat Parsing is Recursive Descent Parsing. So, Packrat Parsing can't parse left recursive rules. Traditionally, we must remove left recursions by converting to right recursions to parse same inputs as original recursion when parse left recursive rules. There are grammars that can't be parsed with this method because some left recursions can't be converted to right recursions. Alessandro et al made possible to support left recursive rules without converting in Packrat Parsing. But the method can't parse some grammars that have multiple left recursions at an input position. This paper presents method to parse grammars that have multiple left recursions and implementation and evaluation of this method.

Journal

  • 情報処理学会論文誌プログラミング(PRO)

    情報処理学会論文誌プログラミング(PRO) 4(2), 104-115, 2011-03-25

    情報処理学会

Codes

  • NII Article ID (NAID)
    110008616680
  • NII NACSIS-CAT ID (NCID)
    AA11464814
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7802
  • NDL Article ID
    024308493
  • NDL Call No.
    YH247-812
  • Data Source
    NDL  NII-ELS  IPSJ 
Page Top