All Questions
Tagged with parsing fl.formal-languages
23 questions
26
votes
5
answers
4k
views
Recovering a parse forest from an Earley parser?
I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date. However, the algorithm in its traditional sense is a recognizer and not a parser, ...
- 2,262
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
22
votes
3
answers
3k
views
Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?
Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this ...
- 32.9k
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
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
14
votes
2
answers
1k
views
Efficient algorithm for updating a parse tree
Let's say I have a big block of code which I already have lexed and parsed.
Suppose that just one character changes; I would want to update my parsing, but since the modification is very small ...
- 243
9
votes
2
answers
1k
views
Chomsky normal form method: CYK parser performance implications?
Chart parsers can be implemented based on Chomsky normal form or
directly based on production rules. Lets for the moment assume
we have a CYK chart parser that uses Chomsky normal form. The
...
user4258
7
votes
2
answers
836
views
Maximal munch rule issue for lexers: is detection decidable?
Edit: I realise that one of my problems is that I don't have a clear definition of my problem, which makes the question of whether it is detectable hard to answer.
I'm therefore already happy with ...
- 4,730
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
5
votes
3
answers
726
views
Formal definition of parser?
I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a ...
- 163
5
votes
2
answers
1k
views
Brackets expression incremental parsing algorithm
I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.
Consider the example with expression like "((1)())(2)". Parse tree for that ...
- 151
5
votes
1
answer
295
views
Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?
Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition.
http://www.sciencedirect.com/science/article/pii/030439759190180A
Scott's algorithm on building ...
- 171
3
votes
1
answer
256
views
Generalizing Parsing Expression Grammar for Context Sensitive Grammars
One of the things I like about parsing expression grammars is that they're automatically unambiguous, and unambiguity is a very important property to have. However, context-free grammars are somewhat ...
- 103
2
votes
2
answers
635
views
are there fixed context sensitive grammars which are PSPACE complete?
wikipedia entry says without reference that
"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."
This is stronger than saying that CSG is ...
- 141
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
1
answer
260
views
Can abstract syntax trees be unparsed in subexponential time?
Abstract problem description
The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...
- 119
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
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
1
answer
102
views
Has anyone ever mixed strings in a language with position?
Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character. Define concatenation of such strings to be:
(by example):
$$
s\cdot t = (\omega \bullet \gamma ) \cdot ...
- 237