Linear parsing expression grammars

DOI10.1007/978-3-319-53733-7_20MaRDI QIDQ5739004zbMATH OpenOpenAlexFDO

Authors Nariyoshi Chida, Kimio Kuramitsu

Publication date 1 June 2017

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.01814

zbMATH Keywords

Boolean finite automatapackrat parsingparsing expression grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Abstract: 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.

Recommendations

• Some aspects of parsing expression grammar
• From EBNF to PEG
• Trying to understand PEG

Cites work

• Alternation
• An introduction to formal languages and automata.
• Constructions for alternating finite automata^∗
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• On equations for regular languages, finite automata, and sequential networks
• Optimization of LR(k) parsers
• Parsing algorithms with backtrack
• Parsing expression grammars: a recognition-based syntactic foundation
• Programming Techniques: Regular expression search algorithm

Cited in

(10)

• Using linear positional grammars for the LR parsing of 2-D symbolic languages
• Context-free grammars with lookahead
• More about converting BNF to PEG
• scientific article; zbMATH DE number 3999315 (Why is no real title available?)
• Context-freeness of parsing expression languages is undecidable
• From EBNF to PEG
• scientific article; zbMATH DE number 3230265 (Why is no real title available?)
• Linear time parsers for classes of non context free languages
• Simplified parsing expression derivatives
• Derived linear systems of context-free grammars

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: Linear parsing expression grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5739004)