Questions tagged [parsing]
The parsing tag has no usage guidance.
49 questions
4
votes
0
answers
118
views
Higher dimensional automata?
An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices.
Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional ...
- 101
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
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
603
views
Is classical lambda calculus grammar an `LL(k)` one?
I am playing with a lambda calculus and faced a question I find hard to reason about.
On the screenshot you may find the lambda calculus grammar. Is it an instance of the ...
- 212
1
vote
0
answers
64
views
Enumerating all parse trees from a parse forest
Say a generalized parsing algorithm whether a GLL parser or Early parser generates a parse forest. Would it be possible to enumerate all of the parse trees from the forest? If possible, in a lazy ...
- 11
0
votes
0
answers
64
views
Are there parsers that can parse languages in more expressive grammars than context-free grammars?
The Earley Parser is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and ...
- 101
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
1
answer
69
views
Why can a Predictive Parser contain E' -> TE' | ε
I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused ...
- 41
-1
votes
1
answer
130
views
DPDA with parameterized states
I'm considering an extension of Sublime Text's syntax definition format. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to ...
- 109
2
votes
0
answers
76
views
A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar
It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1]
However, has it been proven that there exists an example of a ...
- 121
3
votes
1
answer
168
views
Compressing grammars by introducing ambiguity and left-recursion
This is a reference request. What is known about the following questions?
Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also ...
- 11.6k
1
vote
0
answers
164
views
Does an Earley parser equipped with LL(1)-style lookahead parse in linear time for all LL(1) grammars?
If a standard Earley parser (with proper handling of nullable non-terminals, see Section 4 of "Practical Earley Parsing" by Aycock and Horspool) is modified with LL(1)-style lookahead, does ...
- 895
7
votes
4
answers
7k
views
Difference between syntax and semantic error in programming languages
When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, ...
- 181
5
votes
2
answers
232
views
Reducing the Height of Context-Free Grammars
Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.
Say that a string $w\in L(G)$ has ...
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
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
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
5
votes
1
answer
589
views
Parse structure of a range concatenation grammar (RCG)
I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS ...
- 615
9
votes
1
answer
1k
views
Fully linear time regular expression matching
Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters?
The standard NFA algorithm is $O(nm)$ worst ...
- 3,313
1
vote
1
answer
738
views
What is the grammar of network protocols and file formats?
For network protocols and/or file formats with fixed length fields, the grammar is fairly simple, and can be explained with a regular expression.
However, for protocols with varying data lenghts, ...
- 5
5
votes
1
answer
294
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
8
votes
1
answer
215
views
Is $LL(k)$ for large $k$ considered harmful? If so, why?
I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well).
Over the course of the ...
- 249
13
votes
1
answer
766
views
Why Tomita created GLR and didn't use Earley?
When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR?
Performance? Any ...
- 386
14
votes
2
answers
740
views
Category theory and parsers --- references wanted
Since I'm interested in parsers (mainly in parser expression grammars), I'm wondering if there's some work that gives a categorical treatment of parsing. Any reference on applications of category ...
- 295
10
votes
4
answers
6k
views
Good books on parser theory?
One of my Java projects is a fork of parboiled, and unlike, say, Antlr or JavaCC, parsers are generated at runtime. Grammars generated are Parsing Expression Grammars, or PEGs (I hear another term for ...
- 203
0
votes
0
answers
231
views
Correctness proof of recursive-descent recognizer
Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G.
How ...
- 386
2
votes
1
answer
1k
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)$, ...
- 386
4
votes
1
answer
1k
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 ...
- 386
2
votes
1
answer
280
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 ...
- 161
2
votes
1
answer
1k
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 ...
- 175
0
votes
0
answers
127
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 ? ...
- 101
-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
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
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
13
votes
1
answer
347
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 ...
- 32.9k
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
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
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
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
2
votes
0
answers
126
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.
(...
- 531
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
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
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
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
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
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
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
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