61
There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability.
Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$.
Grammar level
For LL
$LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
$SLL(1) = LL(1), ...
19
Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.
The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not ...
15
All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with ...
14
Consider the following sketch of a parsing strategy at your own risk.
Instead of reading the input only from one end, we read from both sides and look for matching rules. We can do this in recursive descent style; in a call to $A()$, find prefix $w$ and suffix $v$ to the input such that there is a rule $A \to wBv$, descend to $B()$ on the remaining word. If ...
14
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 grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "...
13
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 complicated than the corresponding combination of a regular expression doing lexing and a context-free grammar doing parsing on the token-stream. In particular, ...
13
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 regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression. This is more ...
12
Let's have a look at your grammar:
$\qquad \begin{align}
X &\to aE \mid IXE \mid (X)E \\
E &\to IE \mid BXE \mid \varepsilon \\
I &\to \text{++} \mid \text{--} \\
B &\to \text{+} \mid \text{-} \mid \varepsilon
\end{align}$
Note that $X$ does not need left-factoring: all rules have disjoint FIRST sets¹.
If you want to make this obvious, you ...
12
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 reflect the intended structure of the sentence, close to its semantics, especially in the case
of non associative operators, such as application. This was ...
11
$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in ...
11
Transformations such as left factoring or removing left recursion do not have precedence rules. Obviously, the resulting grammars may be different but they will recognize the same language.
The question's example grammar is more difficult than the typical undergrad homework problem. So showing our work will be useful.
Left Recursion
Let's define a ...
11
It is just an LL(1) parser implemented with recursive descent.
Starts with:
AdditionExpression ::=
MultiplicationExpression
| AdditionExpression '+' MultiplicationExpression
| AdditionExpression '-' MultiplicationExpression
apply left-recursion removal to get an LL(1) grammar:
AdditionExpression ::=
MultiplicationExpression ...
10
In principle, there is nothing wrong.
In practice,
most non-textual data formats I know are not context-free and are therefore not suitable for common parser generators. The most common reason is that they have length fields giving the number of times a production has to be present.
Obviously, having a non context-free language has never prevented the use ...
10
First, let's give your productions a number.
1 $S \to AaAb$
2 $S \to BbBa$
3 $A \to \varepsilon$
4 $B \to \varepsilon$
Let's compute the first and follow sets first. For small examples such as these, using intuition about these sets is enough.
$$\mathsf{FIRST}(S) = \{a, b\}\\
\mathsf{FIRST}(A) = \{\}\\
\mathsf{FIRST}(B) = \{\}\\
\mathsf{FOLLOW}(...
10
If you are not asked, you don't have to construct the LL(1) table to prove that it is an LL(1) grammar. You just compute the FIRST/FOLLOW sets as Alex did:
$\qquad \begin{align}
\operatorname{FIRST}(S)&={a,b} \\
\operatorname{FIRST}(A)&={ε} \\
\operatorname{FIRST}(B)&={ε} \\
\operatorname{FOLLOW}(A)&={a,b} \\
\operatorname{FOLLOW}(B)&={a,...
10
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 strings.
To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a ...
9
A PDA is deterministic, hence a DPDA, iff for every reachable configuration of the automaton, there is at most one transition (i.e., at most one new configuration possible). If you have a PDA which can reach some configuration for which two or more unique transitions may be possible, you do not have a DPDA.
Example:
Consider the following family of PDAs ...
9
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 form of a recognizer, and then the information
management needed to actually build parse trees and parse forests is
sort of added as an afterthought. One reason ...
8
You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques.
One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma ...
8
Just a "source code" compendium of Raphael's answer: this a working version that uses the same trick (on state q1) and has tape alphabet:
_ ( ) [ { / \ (where $\_$ is the initial blank symbol)
q0: _ -> accept // accept on empty string and on balanced parenthesis
( -> {,R,q1 // mark the first open "(" with "{" and goto q1
) -> ...
8
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 formalisms. There is a simpler
general parsing algorithm (below), but where the dynamic programming (DP)
aspect is no longer visible. as things are defined more ...
8
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
parsers, that produces all possible parses for a given string, when
the grammar is ambiguous.
There are two ways (at least) of understanding these parsers:
as ...
8
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 have only one derivation in this grammar.
I suspect the word you really mean is 'deterministic'. YACC must declare that this grammar has 'shift-reduce' ...
7
Let's categorize data into three categories: data readable by humans (usually texts, varying from books to programs), data intended to be read by computers and other data (parsing images or sound).
For the first category, we need to process them into something a computer can use. As the languages used by humans can generally be captured relatively well by ...
7
Dumb answer: your result promises that there is a universal Turing machine with two states.
Construct any TM for the Dyck language, compute its index and hardcode it into the universal
machine.
But that's of course not very satisfying. Your approach actually works if you "trick" the
difference between moving left and moving right while matching pairs of ...
7
Here are examples (from Wikipedia):
The language of even-length palindromes over the alphabet of 0 and 1 is a non-deterministic, but unambiguous language. A grammar for this language is $S \rightarrow 0S0 | 1S1|\varepsilon$. The language is non-deterministic because you need to look at the whole string to figure out where the middle is. The grammar is ...
7
Prelude It might be useful to be pedantic and start with a surprising fact: compilers do not use context free grammars, contrary to what you've been told. Instead they use something closely related but subtly different, which might be termed context-free transducers (please let me know if there's an official name for it). They relate to context free ...
7
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 this fact, there's an automated way of determining whether $L(G_{1}) \subseteq L(G_{2})$ or not.
In this case however, things are fairly simple, and we can ...
7
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) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before ...
7
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.
The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm ...
Only top voted, non community-wiki answers of a minimum length are eligible
