Parsing Expression Grammars with Unordered Choices

• Nariyoshi, Chida

• Kimio, Kuramitsu

抄録

Parsing expression grammars (PEGs) were formalized by Ford in 2004, and have several pragmatic operators (such as ordered choice and unlimited lookahead) for better expressing modern programming language syntax. In addition, PEGs can be parsed in a linear time by using recursive-descent parsing and memoization. In this way, PEGs have a lot of positive aspects. On the other hand, it is known that ordered choices defy intuition. They may cause bugs. This is due to a priority of an ordered choice. To avoid this, unordered choices are required. In this paper, we define a parsing expression grammar with unordered choices (PEGwUC), an extension of a PEG with unordered choices. By the extension, it is expected that a PEGwUC includes both a PEG and a context-free grammar (CFG), and this allows us to write a grammar more intuitively. Furthermore, we show an algorithm for parsing a PEGwUC. The algorithm runs in a linear time when a PEGwUC does not include unordered choice and in a cubic time in worst-case running time.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2015) (online)------------------------------

Parsing expression grammars (PEGs) were formalized by Ford in 2004, and have several pragmatic operators (such as ordered choice and unlimited lookahead) for better expressing modern programming language syntax. In addition, PEGs can be parsed in a linear time by using recursive-descent parsing and memoization. In this way, PEGs have a lot of positive aspects. On the other hand, it is known that ordered choices defy intuition. They may cause bugs. This is due to a priority of an ordered choice. To avoid this, unordered choices are required. In this paper, we define a parsing expression grammar with unordered choices (PEGwUC), an extension of a PEG with unordered choices. By the extension, it is expected that a PEGwUC includes both a PEG and a context-free grammar (CFG), and this allows us to write a grammar more intuitively. Furthermore, we show an algorithm for parsing a PEGwUC. The algorithm runs in a linear time when a PEGwUC does not include unordered choice and in a cubic time in worst-case running time.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2015) (online)------------------------------

収録刊行物

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

  情報処理学会論文誌プログラミング（PRO） 10 (5), 2017-11-14

キーワード

• [通常論文] parsing expression grammars, regular expressions, packrat parsing

詳細情報

• CRID: 1050282812885201664
• NII論文ID: 170000149011
• NII書誌ID: AA11464814
• ISSN: 18827802
• Web Site: http://id.nii.ac.jp/1001/00184158/
• 本文言語コード: en
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles