HackerPapers

arXiv:2309.08717cs.FL

Ordered Context-Free Grammars Revisited

Brink van der Merwe

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We continue our study of ordered context-free grammars, a grammar formalism that places an order on the parse trees produced by the corresponding context-free grammar. In particular, we simplify our previous definition of a derivation of a string for a given ordered context-free grammar, and present a parsing algorithm, using shared packed parse forests, with time complexity O(n^4), where n is the length of the input string being parsed.

arXiv comments
In Proceedings NCMA 2023, arXiv:2309.07333
Journal reference
EPTCS 388, 2023, pp. 140-153
DOI
doi:10.4204/EPTCS.388.13
Subjects
cs.FLFormal Languages and Automata Theory

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jun 2024 to Jun 2024.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Use context-free grammars instead of parser combinators and PEG 1 comment

    • > The ordered choice operator should try all choices, not stop earlier. PEGs made this choice to ensure linear-time parsing. Another example of what I would consider a failure is the PEG grammar: Keyword = "else" / "elseif" This will only match "else", it will never match…

      orlpView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.