Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
2
votes
1answer
1k views
4
votes
1answer
474 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?
1
vote
2answers
1k 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 ...
1
vote
1answer
139 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 ...
2
votes
1answer
122 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 ...
9
votes
1answer
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: ...
3
votes
1answer
193 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}\ \...
6
votes
1answer
285 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 ...
3
votes
1answer
941 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 ...
14
votes
1answer
210 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)$ (...
3
votes
1answer
4k 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 ...
7
votes
1answer
16k 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 ...
16
votes
2answers
4k 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 ...
2
votes
1answer
882 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 ...
3
votes
1answer
912 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 ...
1
vote
1answer
136 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 @...
23
votes
4answers
19k 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 } ...
4
votes
1answer
1k 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 ...
6
votes
2answers
164 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
votes
1answer
162 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 $\...
1
vote
2answers
72 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$$ ...
3
votes
2answers
5k 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 ...
0
votes
3answers
227 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}$ ...
4
votes
1answer
8k 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$ ...
7
votes
1answer
7k 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) ...
0
votes
1answer
475 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: $\...
6
votes
4answers
374 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 ...
5
votes
1answer
969 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 ? ...
3
votes
2answers
123 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?
1
vote
2answers
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.
7
votes
1answer
933 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 ...
21
votes
4answers
1k 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.
14
votes
2answers
991 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 ...
11
votes
2answers
4k 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-...
5
votes
1answer
566 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 ...
10
votes
1answer
383 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 $...
14
votes
2answers
2k 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 ...
36
votes
2answers
5k 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 ...
22
votes
1answer
268 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 ...
65
votes
1answer
11k 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 ...
33
votes
9answers
3k 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 ...
7
votes
1answer
575 views

How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...