All Questions
Tagged with parsing fl.formal-languages
7 questions with no upvoted or accepted answers
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
7
votes
0
answers
347
views
The semantics of Parsing Expression Grammars
Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $...
- 81
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
1
vote
0
answers
31
views
Decidability of regular partition construction given its existence
Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$.
If we know that $G$ is LL(...
- 111
1
vote
0
answers
65
views
Grammars whose LR automata have singleton item sets?
The states in LR parsers correspond to sets of items (ie, sets of productions from the original grammar, with a "dot" marking how far into the rule the parser has gotten). In general, states ...
- 32.9k
1
vote
0
answers
218
views
LALR grammars subsets
If LR(0) condition for a grammar G is formulated as follows:
Every state is either reduction or a shift state and it can't be both at the same time
if it is a reduction state, it contains exactly one ...
- 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 ...
