The computational power of parsing expression grammars

DOI10.1007/978-3-319-98654-8_40zbMath1444.68087arXiv1902.08272OpenAlexW2887990295MaRDI QIDQ5915559

Rogério Reis, Nelma Moreira, Bruno Loff

Publication date: 22 November 2018

Published in: Journal of Computer and System Sciences, Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

context-free grammarpumping lemmaparsing expression grammarreal-time Turing machinescaffolding automata

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Other nonclassical models of computation (68Q09)

Related Items (3)

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages ⋮ A linear-time simulation of deterministic \(d\)-limited automata ⋮ Ordered context-free grammars

Uses Software

• TRX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A pumping lemma for deterministic context-free languages
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• Packrat parsing:
• Cut Points in PEG
• Parsing expression grammars
• TRX: A Formally Verified Parser Interpreter
• The Hardest Context-Free Language
• Trying to Understand PEG
• A New Approach to Formal Language Theory by Kolmogorov Complexity
• Computational Complexity
• On the Computational Complexity of Algorithms
• From EBNF to PEG
• Real-Time Definable Languages
• Linear Parsing Expression Grammars

This page was built for publication: The computational power of parsing expression grammars