Skip to main content

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

220 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 votes
1 answer
461 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 ...
Jakub Lédl's user avatar
9 votes
0 answers
386 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 ...
orlp's user avatar
  • 13.8k
6 votes
0 answers
915 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 ...
user200783's user avatar
4 votes
0 answers
125 views

Constructing worst case for L* by D.Angluin

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
4 votes
0 answers
90 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 ...
user56834's user avatar
  • 4,002
4 votes
0 answers
79 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. ...
Ignat Insarov's user avatar
4 votes
0 answers
413 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 ...
jchitel's user avatar
  • 151
4 votes
0 answers
126 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 ...
Liisi's user avatar
  • 141
4 votes
0 answers
943 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 ...
Ethan's user avatar
  • 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 ...
philipp's user avatar
  • 131
3 votes
0 answers
92 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 ...
Robert D-B's user avatar
3 votes
0 answers
186 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/...
TomR's user avatar
  • 1,401
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, ...
matanox's user avatar
  • 351
3 votes
0 answers
317 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 ...
Jon McClung's user avatar
3 votes
0 answers
411 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. ...
vog's user avatar
  • 135
3 votes
0 answers
119 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 ...
AlexBG's user avatar
  • 31
3 votes
0 answers
210 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 ...
lukas.coenig's user avatar
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, ...
john_leo's user avatar
  • 1,901
3 votes
0 answers
484 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 ...
Aky's user avatar
  • 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 $\...
sjmc's user avatar
  • 630
2 votes
0 answers
143 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 ...
breandan's user avatar
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$. ...
Andrei Hodoroaga's user avatar
2 votes
0 answers
312 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 ...
Charlie Parker's user avatar
2 votes
0 answers
462 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 ...
RajS's user avatar
  • 1,677
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-...
Node.JS's user avatar
  • 151
2 votes
0 answers
61 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).....
lightning's user avatar
  • 225
2 votes
0 answers
81 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, ...
New's user avatar
  • 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$, ...
kumar's user avatar
  • 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/...
TomR's user avatar
  • 1,401
2 votes
0 answers
158 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 ...
JOHNKYON's user avatar
2 votes
0 answers
70 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-...
Tob Ernack's user avatar
2 votes
0 answers
847 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\...
Kishan Kumar's user avatar
2 votes
0 answers
936 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-...
RajS's user avatar
  • 1,677
2 votes
0 answers
258 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 ...
Leif Sabellek's user avatar
2 votes
0 answers
329 views

Intuitive Explanation on Converting BNF Grammar to LR(1)

Consider the following BNF Grammar G: ...
Grant Miller's user avatar
2 votes
0 answers
175 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{...
Andrey Lebedev's user avatar
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 ...
Dave's user avatar
  • 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 ...
Faustus's user avatar
  • 237
2 votes
0 answers
56 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 ...
Sidharth Ghoshal's user avatar
2 votes
0 answers
300 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 ...
user avatar
2 votes
0 answers
445 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 -...
Milano's user avatar
  • 349
2 votes
0 answers
44 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 ...
orlp's user avatar
  • 13.8k
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 $ \...
Sam Sauce's user avatar
2 votes
0 answers
730 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-...
viv1's user avatar
  • 21
2 votes
0 answers
70 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. ...
babou's user avatar
  • 19.6k
2 votes
1 answer
157 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 ...
Swordow's user avatar
  • 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 ...
Ramirez77's user avatar
  • 129
1 vote
0 answers
47 views

Alternative solution for the Dangling Else Problem

I understand that one of the ways to solve the Dangling Else Problem is by imposing innermost binding. So, we have to transform the following ambiguous grammar: ...
Librapulpfiction's user avatar
1 vote
0 answers
31 views

Effect of slight modification to LL(1) parse table generation

I am experimenting with LL(1) parsers that do not use a separate lexer. I have the following grammar: S = (('<' S '>' | 'a'+) ' '?)+ The notation uses ' ...
Maximilian's user avatar
1 vote
0 answers
13 views

Why would a control flow block need access to the labels associated with a higher or lower level nested control flow block?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
Dean DeRosa's user avatar

1
2 3 4 5