15
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 "...
14
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, ...
14
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 ...
13
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
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 ...
11
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 ...
11
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 "expansion" and yields a new grammar without $\text{but not }$occurrences. Then we can take two arbitrary context-free languages $L, L'$ with start nonterminals ...
10
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 ...
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
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 ...
9
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 only that, but unlike (say) Thompson's method, Brzozowski's method for constructing DFAs can be easily extended to handle the set difference operator.
I'm ...
8
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).
The set of accept transitions in the two machines will be identical.
The set of reduction actions in the LALR(1) machine will be a subset of the set of ...
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
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 ...
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
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 IELR(1) algorithm is a variation of the so-called "minimal" LR(1) algorithm developed by David Pager in 1977, which itself is a variation of the LR(k) parsing ...
7
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 uses a different mark for each type of parenthesis.
Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized ...
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
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 there are sixteen possible results: 0000, 0001, 0010, ... , 1111.
With the empty strings, though, since we could make 10 by $(\epsilon)(\epsilon)(1)(0)$, or ...
7
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 certain expansions are not permitted by using the phrase “but not” and then indicating the expansions to be excluded.
That phrasing is certainly not unique to ...
6
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 Software Reengineering Toolkit. This supports source-to-source program transformations used for large-scale program restructuring/reverse engineering/forward ...
6
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:
S
/|\
/ S \
/ /|\ \
/ / S \ \
/ / / \ \ \
a a a a a a
or if you prefer this presentation, with the terminals on different
lines
...
6
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; determining whether a string matches a context-sensitive language is PSPACE-complete (so probably takes exponential time).
6
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 language, then no, it is not right, and probably no non-trivial lexical statement would be either.
In many languages, integer literals do not have to be separated ...
6
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 lookahead.
See here for a comprehensive overview on how powerful this class of parsers is.
6
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:
*
**
***
**
*
There is no way to split a star triangle up in 5 parts $uvwxy$ such that $\{uv^nwx^ny|n>0\} $ is also a star triangle (with $vx$ non empty).
This means that the star triangle is not a context ...
6
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 \mid b A b \mid a B b \mid b B a\\
A &\to c \\
B &\to c
\end{align}$$
The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $...
5
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 least in the sense proposed in the post. A standard LALR(k) parser is deterministic; it only does a single table-lookup for each action, based on the current ...
5
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 $LL(k)$ and $LR(k)$ parsing.
Hope this helps!
5
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 context-free grammars. Informally, a CFG is a sequence of productions, where each production consists of a non-terminal, the derives symbol ($\to$) and a ...
Only top voted, non community-wiki answers of a minimum length are eligible