The parsing tag has no wiki summary.
0
votes
1answer
167 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. ...
1
vote
2answers
253 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 ...
9
votes
0answers
171 views
Relationship between shift-reduce parsing and delimited continuations?
Has anyone formalized the relationship between shift-reduce parsing techniques and delimited continuations?
When constructing a bottom-up parser (eg, LR parsers), we take a grammar and then ...
20
votes
1answer
1k 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 ...
4
votes
1answer
327 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) ...
7
votes
2answers
332 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 ...
16
votes
3answers
491 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 ...
2
votes
0answers
113 views
Ref request: grammar specification how-to
I am looking for a reference where I can learn a reasonably systematic approach to how to specify a formal grammar for a given syntax.
By a "formal grammar" I mean something like a BNF description.
...
0
votes
1answer
134 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 ...
10
votes
2answers
515 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, ...
8
votes
1answer
556 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
...
5
votes
2answers
739 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 ...
5
votes
0answers
207 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, ...
5
votes
2answers
373 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 ...
1
vote
0answers
141 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 ...
10
votes
2answers
860 views
Efficient algorithm for updating a parse tree
first question here!
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 ...
13
votes
3answers
1k 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 ...
