マクロ処理の実装に適したパックラットパーサーコンビネータの設計と実装

• Item type: Trans(1)
• 公開日: 2017-12-12
• タイトル: マクロ処理の実装に適したパックラットパーサーコンビネータの設計と実装
• タイトル / 言語: en
• タイトル: Design and Implementation of Packrat Parser Combinator for Implementing Macro Processor
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 芝浦工業大学大学院理工学研究科
• 著者所属: 芝浦工業大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering and Science, Shibaura Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering and Science, Shibaura Institute of Technology
• 著者名: 今泉, 良紀; 篠埜, 功
• 著者名(英): Yoshiki, Imaizumi; Isao, Sasano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: パックラット構文解析ではLALR(1)よりも強力な形式文法であるParsing Expression Grammar（以下PEG）によって構文解析を行う．PEGによる文法規則には曖昧さがなく，プログラミング言語の構文の記述やその処理系の作成に際し非常に有用である．既存のPEGベースの構文解析器では直接文字列を入力として受け付けるが，字句解析と構文解析を分けたい場合にそのままでは使用に適さない．たとえば，字句ベースのマクロ処理系であるCプリプロセッサを実装する際，マクロ展開後のコードに再度マクロ展開の処理が行われうる．その結果，マクロ展開の過程で同じレクシムに対して字句解析を複数回実行する場合がある．これを避けるためにPEGベースの構文解析器を使用しないとすると，字句解析や構文解析用にPEG以外の形式文法を学んだりその処理系を導入したりする必要がある．そこで文字列だけでなく字句列などを入力できるパックラットパーサーコンビネータをC++で実装し，本発表では実装の詳細について報告する．この実装を用いて生成した構文解析器はchar型だけでなく任意の型を返す前方反復子（Forward Iterator）を入力として受け付ける．結果はtuple・variant・optional・expectedなどを組み合わせたデータ構造として得られ，意味規則によって自由に変換することが可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Packrat parsing is based on Parsing Expression Grammar (PEG), which is more expressive than LALR(1) and is not ambiguous. So it is useful on describing the syntax of a programming language and implementing the language. However, it is not suitable to use PEG-based parser generators when we separately implement lexical analysis and syntax analysis, since existing PEG-based parsers receive only a string. For example, since a C preprocessor, which is a token-based macro processor, may expand a code fragment that is obtained by expanding macros, a lexer may process same lexemes more than once in macro expansion. When we do not use PEG-based parser for avoiding unnecessary lexical analysis, we need to study and use another lexer and parser. In this presentation we report a packrat parser combinator, implemented in C++, that receives not only strings but also sequences of tokens. The parser described by the combinator can receive as its input a Forward Iterator that returns not only characters but also values of any type. The output of the parser is obtained as a data structure that consists of tuples, variants, optionals and expecteds. We can process the result by describing semantic actions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 10, 号 6, p. 1-1, 発行日 2017-12-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会