Hot answers tagged

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 ...
rici's user avatar
  • 11.9k
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. ...
rici's user avatar
  • 11.9k
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: ...
AProgrammer's user avatar
  • 3,024
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 "...
Vladislav's user avatar
  • 687
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.'s user avatar
  • 156k
9 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 ...
Robert Jacobson's user avatar
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 ...
Pseudonym's user avatar
  • 21.6k
8 votes
Accepted

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Here you have a couple of salient points. Firstly, the grammars are right linear (strictly $G_{1}$ needs some small changes, but they're trivial). This means that the two languages are regular. Given ...
Luke Mathieson's user avatar
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 ...
PMar's user avatar
  • 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 ...
rici's user avatar
  • 11.9k
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 ...
András Salamon's user avatar
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) ...
rici's user avatar
  • 11.9k
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 ...
Rick Decker's user avatar
  • 14.8k
6 votes
Accepted

What is the point of delimiters and whitespace handling

Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that? If by "right" you mean it is the case in every programming ...
rici's user avatar
  • 11.9k
6 votes

Parsing arbitrary context-free grammars, mostly short snippets

My company (Semantic Designs) has used GLR parsers very successfully to do exactly what OP suggest in parsing both domain specific languages, and parsing "classic" programming languages, with our DMS ...
Ira Baxter's user avatar
6 votes

Lookahead in LL(k) parsing

No, you still consume one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol. Here's a simple example: the grammar of ...
rici's user avatar
  • 11.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: ...
ratchet freak's user avatar
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 ...
fade2black's user avatar
  • 9,757
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 \...
rici's user avatar
  • 11.9k
5 votes
Accepted

What exactly is the LL(k) grammar condition?

It's actually a definition of a strong LL(k) grammar. First of all, see Raphael's comment. In short, the condition means that while parsing $A$ you can choose the next production rule in a ...
Anton Trunov's user avatar
  • 3,469
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 ...
Yuval Filmus's user avatar
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 ...
Raphael's user avatar
  • 72k
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 ...
Yuval Filmus's user avatar
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, ...
John L.'s user avatar
  • 38.6k
4 votes
Accepted

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used. First, let's remark that there are three kinds of items: ...
AProgrammer's user avatar
  • 3,024
4 votes

How to detect plurals in English sentences?

Morphological parsing requires a lexicon (stems and their part of speech) , morphotactics (ordering of morpheme classes), and orthographic rules (e.g. fox + PL = foxes rather than foxs). The ...
GEL's user avatar
  • 829
4 votes

When does one need an Earley parser or something else vs just a DFA?

The context free languages are a strict superset of the regular languages, meaning that all regular languages are context free and there's at least one context-free language that isn't regular. As a ...
templatetypedef's user avatar
4 votes
Accepted

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

The grammar $$\begin{array}{l} S \rightarrow T_0 \\ T_n \rightarrow a \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \; t_n \\ T_N \rightarrow t_N \end{array} $$ has the ...
AProgrammer's user avatar
  • 3,024
4 votes
Accepted

Meta-grammar for context-free grammars

Backus–Naur Form's syntax can be represented with a BNF itself. Here is an example taken from this Wikipedia article: ...
Anton Trunov's user avatar
  • 3,469

Only top scored, non community-wiki answers of a minimum length are eligible