The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
63 views

Relations between Arboreal Group Theory and Tree Group Actions? [migrated]

By a tree group action, we mean an action of a group $G$ over the infinite regular binary tree $T_2$ such that for each $g \in G$, the mapping $x \rightarrow g.x$ is an automorphism of $T_2$; these ...
1
vote
1answer
40 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
99 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
79 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
78 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
188 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
288 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
210 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 ...
6
votes
2answers
612 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
420 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
524 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
141 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 ...
17
votes
4answers
771 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
616 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
841 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
249 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
461 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
151 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
890 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 ...