15
votes
Accepted
What would you get if you add parameters to context free grammars?
Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative ...
- 12.1k
12
votes
What was Robert Floyd's algorithm for inserting brackets?
The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today.
...
- 12.1k
11
votes
Correct name for a recursive descent parser that uses loops to handle left recursion?
It is just an LL(1) parser implemented with recursive descent.
Starts with:
...
- 3,099
11
votes
Representing "but not" in formal grammar
For context-free grammars (I guess your question concerns this type of formal grammars), it would be not only painful, but also impossible in general.
Suppose we have an algorithm that provides such "...
- 717
10
votes
any hope for a universal automatic parser?
You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those ...
D.W.♦
- 164k
10
votes
Accepted
What is an IELR(1)-parser?
The IELR(1) Parsing Algorithm
The IELR(1) parsing algorithm was developed in 2008 by Joel E. Denny as part of his Ph.D. research under the supervision of Brian A. Malloy at Clemson University. The ...
- 261
9
votes
Representing "but not" in formal grammar
In the case of regular languages (and in your examples, we're just talking about character classes, which are an especially simple form of regular language), they are closed under set difference. Not ...
- 23.1k
8
votes
How to find unambiguous grammar for palindromes
First, I believe you are looking for a different word than 'unambiguous'. A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must ...
- 81
8
votes
Representing "but not" in formal grammar
The particular grammar formalism used in the grammar you cite is defined in Appendix A of that document, which includes in section A.3, a precise definition:
A grammar production may specify that ...
- 12.1k
7
votes
Check for balanced parentheses in an expression in log-space
The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares.
The automaton simply ...
- 3,492
7
votes
Accepted
Is there a different resolution of the "dangling else" problem other than "match closest"?
This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) ...
- 12.1k
7
votes
Accepted
Finding the number of distinct strings in regular expression
In your example, think of the result as having filled four slots: _ _ _ _, each of which can take one or three substrings, namely 0, 1, or the empty string. Ignoring the empty strings, it's clear that ...
- 14.9k
6
votes
What would you get if you add parameters to context free grammars?
Take the pumping lemma for CFGs:
Take the grammar
S -> A("")
A(p) -> p
| p '\n' A(p"*") '\n' p
This describes a star triangle:
...
- 4,646
6
votes
What is a "sentential form"?
Assuming you know what leftmost and rightmost derivations are, let $S \Rightarrow^*W_1W_2\dots W_m$ be a derivation (a sequence of replacement using derivation rules), where $W_i$ is a terminal or ...
- 9,877
6
votes
Accepted
Is there a LL(K) Grammar which is not LALR(K) Grammar?
Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.
There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen
$$\begin{align}S &\to a A a \...
- 12.1k
5
votes
Accepted
Parsing CFLs (simulating PDA vs CYK algorithm)
Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free ...
- 278k
5
votes
Correct name for a recursive descent parser that uses loops to handle left recursion?
You want to look into LL($k$) parsing. The Wikipedia article is mostly useless, but it's basically recursive descent with $k$ symbols lookahead.
There is also LL($*$) which permits unbounded ...
- 72.8k
5
votes
Accepted
Number of nodes of a parse tree when the Grammar is in CNF?
Both of the answers are wrong. To find the correct answer, let us consider the grammar
$$ S \to SA \mid a \\ A \to a $$
You can check that the tree corresponding to $S \to a$ has 2 nodes, the one ...
- 278k
5
votes
Accepted
How to find First in a left recursive grammar?
Here is how to apply the production rule $ A\to AX$ to compute $\text{first}(A)$.
When $\epsilon\in\text{first}(A)$, add all (non-$\epsilon$) members of $\text{first}(X)$ to $A$.
More generally, ...
- 39.1k
4
votes
What would a formal grammar for a binary file format look like?
The Chomsky hierarchy is a hierarchy of grammars described by a given formalism. The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they ...
- 3,099
4
votes
Is the word problem of CFLs in NC?
The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete.
Interestingly, Ullman ...
- 41
4
votes
How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?
A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you ...
- 278k
4
votes
Accepted
Eliminating cycles from a grammar
An algorithm to specifically remove cycles can be adapted from the more general algorithm to reduce a grammar to its Chomsky normal form. Specifically, it is the elimination of unit productions, ...
- 151
4
votes
Accepted
Tokenization Problem
Tokenisation does not search. [Note 1]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.
Although there are other tokenisation ...
- 12.1k
4
votes
Is there a way to efficiently parse this grammar?
The grammar is ambiguous: (I used | for a and * for b ...
- 12.1k
4
votes
Accepted
Why doesn't the C/C++ compilers create different tokens for different types of numbers?
This is in fact an implementation detail of the compiler. The page you referenced only shows one way of assigning types to tokens, while there are also others. The compiler could have a lexer that ...
- 2,797
4
votes
Accepted
Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?
Theorem 1 in "If the Current Clique Algorithms are Optimal,
so is Valiant’s Parser" shows an explicit context-free grammar $G$ such that if $G$ can be parsed in linear time (or even a bit slower), ...
- 3,501
4
votes
What is handle in bottom up LR parsing?
"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."
Charles Dodgson -- who wrote those words under ...
- 12.1k
4
votes
How does SpaCy make its dependency tree?
Matthew Honnibal, who created Spacy, answered me :
The full answer is rather complicated :). I've written a few blog
posts over the years to make it more accessible. The best place to
start is ...
Only top scored, non community-wiki answers of a minimum length are eligible