Questions tagged [formal-grammars]
Questions about formal grammars, generative descriptions of formal languages.
216
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
9
votes
0
answers
376
views
Can any PEG grammar be parsed in linear time?
On the Wikipedia for PEG it is claimed:
Any PEG can be parsed in linear time by using a packrat parser, as described above.
However, packrat parsers can't handle left recursion.
You can eliminate ...
- 12.7k
6
votes
0
answers
867
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
81
views
Reference on relating Post systems to string rewriting systems and formal grammars?
wikipedia states:
Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]
It has been proved that any Post canonical system is reducible to such a ...
- 3,632
4
votes
0
answers
76
views
Acyclic Manhattan turtle
There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle
always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel
J.H. ...
- 229
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
938
views
Parsing family of grammars, determine if LR(k)
Consider the family of grammars $G_n,~n\geq2$.
$$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$
$$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$
where multiple alternative right ...
- 321
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
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
184
views
Semantic parsing with Grammatical Framework - is this possible?
So far I have learned about categorial grammars, type logical grammars and formal semantics of natural language, the relevant tools are Cornell Semantic Parsing Framework https://github.com/clic-lab/...
- 1,381
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
374
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
306
views
How to refactor a grammar to be suitable for recursive descent?
I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example:
$S \rightarrow AB \\
A \rightarrow a \\
A \rightarrow SA \\
B \rightarrow b \\
B \rightarrow ...
- 157
3
votes
0
answers
379
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
115
views
What kind of formal language is generated by Parsing Expression Grammars?
I've been unable to find what class of languages is recognized by PEGs. The original paper [1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also ...
- 31
3
votes
0
answers
192
views
Is there a grammar type for deterministic LBA?
Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
- 743
3
votes
0
answers
56
views
Tree Languages are Word Languages on an Infinite Alphabet of Contexts
I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand.
In the beginning of Chapter 2, ...
- 1,861
3
votes
0
answers
453
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
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
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
2
answers
135
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
296
views
Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules
I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
- 3,000
2
votes
0
answers
382
views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
- 1,637
2
votes
0
answers
116
views
Simple description of circularities in Knuth original attribute grammar paper
Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) introduced three types of circularity. More specifically section "Testing for circularity" page 134-5 figures 3.1-...
- 101
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
79
views
Give LL grammar for this language?
I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be:
$$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$
I have the following, ...
- 21
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
19
views
Induction / (machine learning) of Resource Grammars for Grammatical Framework?
Grammatical Framework is based in Abstract Categorial Grammars. It is known that Combinatory Categorial Grammars have grammar induction/learning capabilities see e.g. https://link.springer.com/article/...
- 1,381
2
votes
0
answers
148
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
807
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
826
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
232
views
Simple languages that are not of type-1?
To present interesting type-0 grammars to my students, I am looking for a very simple example of a type-0 language (=recursively enumerable language) that is not of type-1 (=not context sensitive). I ...
- 121
2
votes
0
answers
305
views
Intuitive Explanation on Converting BNF Grammar to LR(1)
Consider the following BNF Grammar G:
...
- 143
2
votes
0
answers
174
views
Unranked trees grammars?
Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{...
- 345
2
votes
0
answers
1k
views
What is the importance of the empty string in CFG derivations?
NOTE: This question is NOT the same as this other nearly-identically worded question with some amazing answers. I learned a lot from it regarding the mathematical importance of the empty string, but ...
- 495
2
votes
0
answers
64
views
Effectively compute bound and period of regular expression on single alphabet
It is known that an infinite language $L\subseteq \{a\}^*$ is regular iff the set $U:=\{x|a^x\in L\}$ is ultimately periodic. (A set $U\subseteq\mathbb{N}$ is said to be ultimately periodic if there ...
- 237
2
votes
0
answers
55
views
How to lexically list sentences in peano arithmetic?
I am working on building a toy automated theorem prover,
What I want to do is to efficiently generate sentences in peano arithmetic, that I can attempt to verify as True/False/requires-more-resources ...
- 353
2
votes
0
answers
297
views
Is asking a LL(1) parsing table for this grammar a trap?
I'm trying to solve some exercises for the upcoming Compilers' exam.
Teacher gave us some sheets from previous exams to practice with - no answers provided.
Let $\mathcal{G}$ be the following ...
user21206
2
votes
0
answers
423
views
How to find conflicts in LALR parser?
I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1).
I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 -...
- 339
2
votes
0
answers
43
views
Determine if two LR(1) action/goto tables always produce the same derivation
I am experimenting with implementing minimal LR(1) algorithms/techniques, but I find it very difficult to verify the correctness of what I've implemented.
Is there a fast algorithm to determine if ...
- 12.7k
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
723
views
Removing hidden ambiguity in grammar using left factoring
I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new non-...
- 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
1
answer
141
views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
- 19
2
votes
1
answer
7k
views
Converting CNF to GNF
I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
- 129
1
vote
0
answers
15
views
Number of DCFG parse tree nodes with respect to input length
I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
- 111
1
vote
0
answers
19
views
Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere
Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
- 111
1
vote
0
answers
30
views
How need help to specify a grammar for arithmetic expressions
I am trying to come up with a grammar for arithmetic expressions with the following order of operations:
Parentheses
Factorials
Exponents
Functions / unary plus and minus
Juxtaposition (implied ...
- 111