Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
1,251
questions
8
votes
1
answer
16k
views
Left-Factoring a grammar into LL(1)
I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ...
- 183
4
votes
2
answers
25k
views
Understanding LEADING and TRAILING operations of an operator precedence grammar
I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean.
I am ...
- 143
1
vote
1
answer
161
views
Phrase generators for use with testing grammars that don't use a seed
In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and ...
- 5,091
4
votes
1
answer
215
views
Are there grammar classes between Chomsky level 1 and 2?
Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?
crudolf
5
votes
2
answers
1k
views
What if a formal grammar cannot be terminated?
I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out ...
- 349
20
votes
2
answers
3k
views
What is an IELR(1)-parser?
I try to teach myself the usage of bison. The manpage bison(1) says about bison:
Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
- 876
4
votes
1
answer
589
views
Is this phrase structure grammar from my textbook correct?
I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.
On page 12, the authors start describing a set of rules that can be used to ...
- 225
5
votes
3
answers
2k
views
Proving a grammar only generates words whose alternating digit sums are multiples of three
This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point.
Here's the problem:
The following ...
3
votes
3
answers
3k
views
Is this language LL(1) parseable?
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.
$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$
Is my hypothesis true ...
- 876
2
votes
1
answer
2k
views
4
votes
1
answer
1k
views
Proof of equivalence of parse-trees and derivations
Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa.
Is this intuition correct? If so how can I formalize and prove such a thing?
- 3,678
1
vote
2
answers
2k
views
LL(1) parsing table of left-recursive grammar
I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:
S -> Sa | b
According to the professor parsing table ...
- 139
1
vote
1
answer
158
views
What's wrong with this LL grammar? (very short)
S --> Ta | b | Sc
T --> Tc | λ
This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never ...
Pablo Miranda
2
votes
1
answer
130
views
Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?
Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w ...
oskarkv
9
votes
1
answer
1k
views
Arithmetic expressions grammar transformation
In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions:
...
- 290
3
votes
1
answer
442
views
Factor a grammar
Consider the context free grammar:
$\qquad \begin{align}
\mathrm{bill} &\to \mathrm{items}\ \mathrm{total}\ \mathrm{vat} \\
\mathrm{items} &\to \mathrm{item} \mid \mathrm{item}\ \...
jamie jenkins
6
votes
1
answer
513
views
Determining whether a CFG is $LL(k)$ for any $k$?
In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.
Is there a similar result ...
- 9,037
3
votes
1
answer
1k
views
How to call something that can be either a terminal or a nonterminal?
I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C.
I came across a terminology problem however that I remember in the past I couldn't ...
- 153
14
votes
1
answer
264
views
When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"
According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (...
- 9,037
3
votes
1
answer
5k
views
Context-free grammar to a pushdown automaton
I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
- 225
9
votes
1
answer
20k
views
Left recursion and left factoring -- which one goes first?
if I have a grammar having a production that contains both left recursion and left factoring like
$\qquad \displaystyle F \to FBa \mid cDS \mid c$
which one has priority, left recursion or left ...
- 355
16
votes
2
answers
5k
views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
- 355
2
votes
1
answer
1k
views
Eliminating useless productions resulting from PDA to CFG converison
In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.
For example, for two transitions, I am getting the following productions
...
- 461
3
votes
1
answer
1k
views
Unambiguity of Reverse Polish Notation
Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation:
$G=({E},{a,+,*},P,E)$
$P={ E \rightarrow EE+ | EE* | a }$
I know this grammar is ...
- 131
1
vote
1
answer
188
views
Where should we place action symbols in a grammar?
In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?
E -> TE`
E'-> +T @...
- 111
32
votes
4
answers
31k
views
How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous?
I have the following grammar:
$$S
→ statement
∣ \mbox{if } expression \mbox{ then } S
∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
- 521
5
votes
1
answer
2k
views
Non-linear grammars
I look for information about grammars which can be described by a non-linear equation such as a quadratic equation:
$\qquad \displaystyle G \to G G a \mid b$
or
$\qquad \displaystyle G \to G G \mid ...
- 59
6
votes
2
answers
200
views
Computing follow sets conservatively for a PEG grammar
Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
- 1,194
-1
votes
1
answer
167
views
generation of linear grammar
We have the following linear grammar:
$$E \rightarrow aO | bO | bbE | bb$$
$$O \rightarrow aE | bE | abaE | aba$$
Does the linear grammar generate a regular language, if yes why ?
Our alphabet is $\...
- 521
1
vote
2
answers
77
views
Transform in linear grammar
i have the following regular grammar :
$$S \rightarrow aS | cS | bQ_1$$
$$Q_1 \rightarrow bQ_2$$
$$Q_2 \rightarrow aQ_3 | cQ_3 | bQ_1$$
$$Q_3 \rightarrow aQ_4 | cQ_4$$
$$Q_4 \rightarrow \varepsilon$$
...
- 521
3
votes
2
answers
8k
views
Context-free grammar for $\{ a^n b^m a^{n+m} \}$
I've got a problem with this task. I should declare a context-free grammar for this language:
$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$
My idea is: We need a start ...
- 521
0
votes
3
answers
260
views
Transform regular grammar in linear grammar
My problem is how can I transform a regular grammar into a linear grammar?
I know that a linear grammar has the form
$\begin{align} A &\to w_1Bw_2 \\
A &\to w \end{align}$
...
- 521
4
votes
1
answer
9k
views
Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:
Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ ...
clebert
10
votes
1
answer
12k
views
Relation between simple and regular grammars
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) ...
- 203
0
votes
1
answer
572
views
Is this grammar ambiguous?
I have the grammar:
$\qquad \begin{align}
S &\to S = P \mid S \neq P \mid P \\
P &\to NUM
\end{align}$
This grammar suffers from left recursion. To eliminate left recursion, I got:
$\...
barq
7
votes
4
answers
542
views
Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.
$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
- 1,697
5
votes
1
answer
2k
views
Chomsky normal form and regular languages
I'd love your help with the following question:
Let $G$ be context free grammar in the Chomksy normal form with $k$
variables.
Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ?
...
- 1,697
4
votes
2
answers
149
views
Is the set of LL(*) grammars the same as the set of CFG grammars?
Is the set of LL(*) grammars the same as the set of context-free grammars?
- 151
1
vote
2
answers
2k
views
Proof that a language involving $gcd$ is not context-free
How would you prove that the following language is not context-free?
$$ L= \{a^n b^m |\, gcd(n,m)=1 \}$$
I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.
Eren Bellisoy
7
votes
1
answer
1k
views
reduce reduce and shift reduce error in LALR grammar
I have to write a grammar for Pascal, and there is just one thing that is causing problems.
Lets say we have operators (sorted by priority from low to high):
Postfix ...
- 171
22
votes
4
answers
2k
views
Are there other ways to describe formal languages other than grammars?
I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
- 323
15
votes
2
answers
1k
views
Are the Before and After sets for context-free grammars always context-free?
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
- 9,036
11
votes
2
answers
6k
views
How can I prove this language is not context-free?
I have the following language
$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$
I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
- 435
6
votes
1
answer
1k
views
Can every linear grammar be converted to Greibach form?
Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$?
($T$ is the set of ...
- 2,193
10
votes
1
answer
476
views
Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.
Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
- 203
17
votes
3
answers
3k
views
Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
40
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.8k
23
votes
1
answer
417
views
Is there any nongeneral CFG parsing algorithm that recognises EPAL?
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:
$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S a$
$S \...
- 9,036
76
votes
1
answer
15k
views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
- 72k
35
votes
9
answers
4k
views
What is the significance of context-sensitive (Type 1) languages?
Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
- 1,755