Linear Parsing Expression Grammars

详细信息    查看全文

• 关键词：Parsing expression grammars ; Boolean finite automata ; Packrat parsing
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10168
• 期：1
• 页码：275-286
• 丛书名：Language and Automata Theory and Applications
• ISBN：978-3-319-53733-7
• 卷排序：10168

文摘

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. Since these operators are not explicitly defined in the classic formal language theory, it is significant and still challenging to argue PEGs’ expressiveness in the context of formal language theory. Since PEGs are relatively new, there are several unsolved problems. One of the problems is revealing a subclass of PEGs that is equivalent to DFAs. This allows application of some techniques from the theory of regular grammar to PEGs. In this paper, we define Linear PEGs (LPEGs), a subclass of PEGs that is equivalent to DFAs. Surprisingly, LPEGs are formalized by only excluding some patterns of recursive nonterminal in PEGs, and include the full set of ordered choice, unlimited lookahead, and greedy repetition, which are characteristic of PEGs. Although the conversion judgement of parsing expressions into DFAs is undecidable in general, the formalism of LPEGs allows for a syntactical judgement of parsing expressions.