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 ...
- 11.3k
14
votes
Accepted
Why separate lexing and parsing?
You don't have to separate them. People combine them into scannerless parsers.
The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more ...
- 8,178
14
votes
For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?
It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.
By regexp, I mean a modern ...
D.W.♦
- 141k
13
votes
Accepted
Removing left-recursion in grammar while maintaining left-association of operator
Compatibility of left associativity and LL(1) parsing
You just hit one of the major inconsistencies in the use of
context-free (CF) syntax. People want to choose grammars so that the
parse-tree will ...
- 19.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.
...
- 11.3k
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,004
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 "...
- 677
10
votes
Accepted
How do I reconstruct the forest of syntax trees from the Earley vector?
I am using terminology and notations from Earley's paper. It is possible that the description you read is different.
It seems frequent that general CF parsing algorithms are first
presented in the ...
- 19.1k
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.♦
- 141k
9
votes
Accepted
Is CYK still relevant today?
CYK is still relevant, afaik, as the simplest example of a family of general
parsing algorithm based on dynamic programming, ranging over all
parsing technique (that I know of) and many syntactic ...
- 19.1k
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 ...
- 18.9k
8
votes
Accepted
Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?
If a grammar is SLR(1), then: [Note 1]
The SLR(1) and LALR(1) state machines will have the same states
The set of shift transitions in the two machines will be identical (as will the goto actions).
...
- 11.3k
8
votes
Accepted
Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?
The answer is yes. However I would not do that with an Earley parser
because there are simpler ones with the same capabilities.
Basically, Earley parser belongs to a family of general context-free
...
- 19.1k
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 ...
- 17.7k
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
7
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 ...
- 231
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,342
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) ...
- 11.3k
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.6k
7
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 ...
- 11.3k
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 ...
- 246
6
votes
Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$
This is not much of an answer, but the parse trees do not fit the
normal comments.
Your grammar $S \rightarrow aSa\ |\ aa$ should parse the string
$aaaaaa$.
But the parse tree has the following form:...
- 19.1k
6
votes
Accepted
Why we use context-free grammar for parsing?
Because regular expressions are too weak and context-sensitive languages are too difficult to parse. More specifically, regular expressions can't specify that the brackets in your program match up; ...
- 80.2k
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 ...
- 11.3k
6
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 ...
- 70.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,108
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 \...
- 11.3k
5
votes
BNF and Simultaneous Parsing
If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at ...
- 11.3k
5
votes
Accepted
When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"
I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $...
- 8,857
5
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 ...
- 11.3k
Only top scored, non community-wiki answers of a minimum length are eligible