The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
91 views

Complexity of a GLR parser on an ambiguous grammar

Let's consider the following expression grammar that is ambiguous: $E ::= E + E~|~a$ Although GLR parsing (recognition actually, I'm not interested in parse tree creation) is worst case $O(n^3)$, ...
3
votes
1answer
67 views

Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

It is often said that memoization brings the complexity of recursive-descent parsers from exponential to polynomial. However, I had a hard time finding an example grammar that triggers the exponential ...
2
votes
1answer
50 views

Define the properties of a grammar that is the fastest to parse

It's possible to define the properties of a grammar that is fast to parse as it is indeed possible to classify algorithm based on their complexity ? In other words it's possible to evaluate and ...
1
vote
1answer
117 views

How can an inherited attribute be simulated using a synthesized attribute?

Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized ...
0
votes
0answers
82 views

Is it possible to simulate a regular expression using a single stack?

I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? ...
-2
votes
1answer
80 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 ...
0
votes
1answer
191 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
302 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 ...
12
votes
1answer
213 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 ...
9
votes
2answers
708 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
442 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
532 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
116 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
146 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 ...
18
votes
4answers
881 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
632 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
874 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 ...
6
votes
0answers
258 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
3answers
471 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
154 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
898 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 ...
14
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 ...