All Questions
Tagged with parsing context-free
10 questions
1
vote
0
answers
81
views
Not possible to write deterministic CFG for balanced parenthesis?
I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language.
But what's an example of ...
- 163
0
votes
0
answers
91
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
2
votes
0
answers
76
views
A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar
It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1]
However, has it been proven that there exists an example of a ...
- 121
3
votes
1
answer
168
views
Compressing grammars by introducing ambiguity and left-recursion
This is a reference request. What is known about the following questions?
Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also ...
- 11.6k
5
votes
2
answers
232
views
Reducing the Height of Context-Free Grammars
Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.
Say that a string $w\in L(G)$ has ...
7
votes
0
answers
845
views
Does PEG contain CFG?
Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
- 420
23
votes
1
answer
2k
views
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(...
- 4,730
16
votes
2
answers
2k
views
Permutation phrases with LR parsing
A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$...
- 4,730
19
votes
3
answers
763
views
CFG parsing using $o(n^2)$ space
There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.
However, all algorithms for ...
- 4,730
0
votes
1
answer
191
views
Describing a grammar and associated parser
In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization ...
- 103