Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
255
questions with no upvoted or accepted answers
10
votes
1
answer
451
views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
- 233
7
votes
1
answer
627
views
Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?
The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
- 9,037
6
votes
0
answers
205
views
Is it decidable if this zipping operation gives a context-free language?
Motivation
Consider the following languages, are they context-free?
$\{x \# y: x \neq y\}$
$\{x y: |x|=|y|, x \neq y\}$
$\{x \# y: |x|=|y|, x \neq y\}$
$\{x y: |x|=|y|,d(x,y)>1\}$
$\{x x\}$
The ...
- 3,491
6
votes
0
answers
868
views
Which programming languages have a syntax that can be described by deterministic context-free grammars?
This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++".
Until ...
- 161
4
votes
0
answers
191
views
BNF rule to regular expression
I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression.
(With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
- 113
4
votes
0
answers
122
views
Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?
The ...
- 141
4
votes
0
answers
90
views
Can we define CFL without grammars or automata?
The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms:
Empty language: $\{\} \in R$
Singleton languages: $\forall a \in \Sigma : \{a\}...
- 416
3
votes
0
answers
30
views
Is there a context-agnostic concept of automatic (log-)text parsing that supports human reader filtering out redundancy?
This question is about ideas I regularly think about, and I would like to know what concepts already exist. Also I am not sure at all if this really makes sense, by now it is just a crazy idea
...
- 131
3
votes
0
answers
346
views
is it decidable whether a grammar in Chomsky normal form has useless rules?
Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
- 838
3
votes
0
answers
87
views
Are there context free grammars for all restricted Dyck paths?
A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
- 131
3
votes
0
answers
55
views
Conditions that imply closure under intersection of context-free languages
Context-free languages are not closed under intersection.
Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular).
Are there well-known theorems (and/or whole ...
- 12.4k
3
votes
0
answers
215
views
What strategies exist for handling/resolving ambiguity in parsers?
I define a parser as a context-free grammar with semantic actions for each production. It is not defined in what order the semantic actions run, just that the semantic actions of the non-terminals in ...
- 12.7k
3
votes
0
answers
107
views
Generating valid sentence with respect to attribute grammar
Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
- 225
3
votes
0
answers
434
views
CFG for $\lambda$-calculus with minimal parentheses
The typical presentation of the syntax of the $\lambda$-calculus is as an ambiguous CFG (or BNF) like the following:
$$T \rightarrow \lambda X . T \mid T ~ T \mid X \mid (T)$$
Where we permit $X$ to ...
- 31
3
votes
0
answers
29
views
How to model grammar ambiguity
Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings.
Practically, ...
- 341
3
votes
0
answers
378
views
How would I build a parser generator for a context free grammar using Pushdown Automata?
I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc.
I am at the point where I have lexer generation ...
- 141
3
votes
0
answers
335
views
Context free grammar as minimal solution of a system of equations
It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example:
$$\begin{align*}
X &=\{{\epsilon}\} \cup Y\\
X ...
- 203
3
votes
0
answers
382
views
Context-free grammar for DAGs?
I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser.
...
- 135
3
votes
0
answers
456
views
Recursive-descent parser for the grammar S -> S(S)S | ε
I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct ...
- 225
3
votes
0
answers
133
views
Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution
Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\...
- 630
2
votes
0
answers
101
views
How to write a grammar with a low-precedence unary postfix operator?
Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator.
The operator ...
- 121
2
votes
0
answers
136
views
Determining when a substring has a unique parse forest
Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
- 33
2
votes
0
answers
46
views
Is LR(1) closed under concatenation?
Suppose I have two LR(1) languages $L_1$, $L_2$. Is
$L_1 L_2$ (their concatenation) guaranteed to also be LR(1)?
References to proofs would be very helpful.
- 39
2
votes
0
answers
76
views
Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?
$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$
I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$.
...
2
votes
1
answer
152
views
Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?
$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j
;\ j \text{ is even, then } k =i+j\}$
I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even.
When $j$ is ...
- 21
2
votes
2
answers
136
views
Generating a recursive descent parser for grammar having Kleene star
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:
\begin{align}
&E \to E+T \mid T \\
&T \...
- 121
2
votes
0
answers
35
views
Generating an "approximate" grammar
This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form
...
- 121
2
votes
0
answers
64
views
Unparsing an operator grammar in the face of ambiguity
I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is:
user defined mixfix operators such as _+_ or <...
- 121
2
votes
0
answers
44
views
closure property violated by palindrome language
It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
- 21
2
votes
0
answers
2k
views
Empty string in language with grammar in Chomsky normal form
In their book, Ullman et al says:
Every nonempty CFL without $\epsilon$ has a grammar $G$ in which all productions are in one of two simple forms, either:
$A\rightarrow BC$, where $A,B$ and ...
- 1,637
2
votes
0
answers
400
views
Pumping lemma for L = {a^i b^j c^k: i < j < k}
I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.
Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free
...
2
votes
0
answers
49
views
CYK algorithm - how to handle unknown terminals given in a sentence to parse?
There is a given treebank which we derive the Probabilistic context free grammar.
I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules?
Is ...
- 181
2
votes
0
answers
2k
views
Turing machine VS Push Down Automaton in CFL
I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why?
I know that a pushdown automaton can ...
- 97
2
votes
0
answers
47
views
Is the language $L$ of coded CFG's Turing decidable?
Consider the following language
$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}
Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
- 33
2
votes
0
answers
292
views
What is the simplest automaton that can compute the sum of two integers of arbitrary length?
It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length?
I ...
- 121
2
votes
0
answers
55
views
How to know a certain grammar is parse-able
Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it.
...
- 133
2
votes
0
answers
58
views
Intuition on what an attribute grammar can achieve
I have seen attribute grammars for a small handful of tasks:
Parsing simple arithmetical expressions
Type checking
Checking that a variable is initialized
anbncn (seems to be a favorite toy example).....
- 225
2
votes
0
answers
92
views
Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages
Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language.
Is there a subclass, say $C$, ...
- 21
2
votes
0
answers
151
views
How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?
Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure.
Let $S$ be the start symbol ...
- 21
2
votes
0
answers
69
views
Examples of context-free grammars whose ambiguity is unknown
Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-...
- 141
2
votes
0
answers
95
views
Examples of context-free grammars with worst-case complexity
What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers?
I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
- 141
2
votes
0
answers
809
views
Is the complement of $L = \{a^nb^mc^p \, n= m= p\}$ context free language?
Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language.
I believe that we can write $L^{'} \ as \ L1 \cup L2$ where
$L1=(a^*b^*c^*){'} \ $
$L2={{a^nb^mc^p \ m\ne n \ or \ n\...
- 695
2
votes
0
answers
840
views
Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata
I read following here:
Unambiguous grammars do not always generate a DCFL.
Example:
For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
- 1,637
2
votes
0
answers
306
views
Intuitive Explanation on Converting BNF Grammar to LR(1)
Consider the following BNF Grammar G:
...
- 143
2
votes
0
answers
400
views
Is the problem that intersection of two cfl is a cfl or not undecidable?
I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.
- 121
2
votes
0
answers
84
views
Correct bracketing check with rotate operation on position i
Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations:
Check whether the sequence is correctly bracketed
Rotate bracket ...
- 49
2
votes
0
answers
92
views
Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic
Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic.
Someone ...
- 2,184
2
votes
0
answers
2k
views
Converting Chomsky Normal Forms to Greibach Normal Form
Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about:
Now we show how to convert an arbitrary grammar to an equivalent one (except possibly for $ \...
- 21
2
votes
0
answers
69
views
What kind of structural features of strings can be described by regular grammars?
Context-free grammars, as well as other types of grammars, can naturally
associate structure with the strings of the defined language, for
example tree structures in the case of context-free language.
...
- 19.4k
2
votes
0
answers
207
views
The grammar of the GeoQuery language
GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example:
answer(A,longest(A,(river(A),traverse(A,B),...
- 5,730