Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
346
questions
1
vote
1answer
35 views
Duplicating the quotation marks in in the quotation-mark enclosed strings
There is such a grammar
string_literal ::= " { graphic_character } "
The double-quotes that you see must appear in the user program and curly braces mean "any ...
1
vote
1answer
39 views
How to detect plurals in English sentences?
I'm wondering how to detect English plurals in natural language sentences.
Such as:
fish
computers
houses
...
Using Earley parsing I'm able to get to the s or no-s, but I have difficulties in ...
-2
votes
1answer
370 views
How should I show that a grammar is not LL(1) and convert grammar to LL(1)
I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
6
votes
0answers
66 views
Is THEADS the same as FIRST?
I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph:
We will first of all briefly review the LR(1) parsing and ...
1
vote
0answers
73 views
Parsing based on logical connectives and quantifiers?
What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers.
E.g.
[A] ...
0
votes
1answer
1k views
What exactly is the LL(k) grammar condition?
I have a bit of trouble understanding the definition of LL(k) grammars.
Here it's defined as:
for every pair of production rules
$A\rightarrow
α$
and
$A \rightarrow
β$
the following ...
0
votes
1answer
579 views
Construct SLR Parse table problems
Consider the augmented grammar G is:
S` -> S
S -> a
S -> (T)
T -> T,S
T -> S
I have tried to construct parse table. But, when I read '(' ...
2
votes
1answer
62 views
Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?
I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
4
votes
1answer
140 views
An intuitive explanation for LR grammars?
With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR ...
3
votes
1answer
2k views
Ambiguous Grammar and SLR parsing table : No conflicts?
We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-...
8
votes
0answers
252 views
Can any PEG grammar be parsed in linear time?
On the Wikipedia for PEG it is claimed:
Any PEG can be parsed in linear time by using a packrat parser, as described above.
However, packrat parsers can't handle left recursion.
You can eliminate ...
0
votes
0answers
74 views
Linear time parsing from star of context free language
I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar:
...
16
votes
2answers
1k views
For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?
Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA.
Is it ...
1
vote
1answer
303 views
Whats Wrong with this LL(1) Grammar?
I am trying to build a LL(1) parse table for the following Grammar:
S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon
There are two Problems here. First the L rules are a left recursion ...
1
vote
0answers
23 views
How equality of item (production state) is defined in LR parser?
Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):...
0
votes
1answer
149 views
Chomsky NF or Greibach NF benefits for LR parser?
Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind:
total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
4
votes
1answer
134 views
Are there automatic transformation of grammar algorithms?
From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, ...
10
votes
1answer
261 views
Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?
There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something ...
2
votes
1answer
247 views
fixed point in regular expressions
I've posted this question first on StackOverflow but this section seems more suited for this kind of questions.
Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
3
votes
3answers
808 views
What techniques can I use to hand-write a parser for an ambiguous grammar?
I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
10
votes
2answers
488 views
How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?
In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
12
votes
2answers
2k views
Removing left-recursion in grammar while maintaining left-association of operator
I have a problem with this exercise:
Let G be the following ambiguous grammar for the λ-calculus:
E → v | λv.E | EE | (E)
where E is the single non-...
0
votes
1answer
483 views
How do I form a parse tree for equations? [closed]
I have the following equation
if (x > y) {
if (y < a) {
x:= a
y:= b
} else {
x:= b;
}
}
I was thinking of something like this ...
5
votes
1answer
2k views
Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?
Consider a grammar G which is SLR(1) except for some shift/reduce conflicts which can be resolved by imposing some precedence or associativity of operators.
Is it the case that the construction of ...
4
votes
1answer
525 views
What is a real-world use-case/need for a left-recursive grammar?
I understand the basics of how left-recursion works, and why some people say it's bad. And I've also ready opinions such as:
...like LL and LR parsing, PEGs are often frustrating to use in practise....
1
vote
1answer
293 views
CFGs: detecting infinitely many derivations of a single string
Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \...
1
vote
0answers
461 views
LL(1) grammar for the untyped lambda-calculus
What I want to do
I am trying to define a LL(1) grammar of the lambda-calculus.
What I did
Here is the grammar:
$Term \to Abs$
$Term \to App$
$Abs \to \lambda \ id \ . \ Term$
$App \to Var \ ...
0
votes
1answer
154 views
How to create an LR($k$) grammar for a given language?
How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:
$$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
15
votes
1answer
4k views
Why separate lexing and parsing?
It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test ...
0
votes
1answer
73 views
LL(k) Prediction Techniques (and Insight on method applied)
I'm requesting references for LL(k) in situations where k > 1 for reasons described below.
I'm looking for research/notes/...
0
votes
2answers
218 views
generating recursive descent parser
I have a grammar,
$L \to A \langle A \rangle^*$
$A \to () \mid (L)$
but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^*T\...
0
votes
1answer
376 views
Are regular grammars always LR(1)
The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are
LL(1)
LR(1)
I guess they can't be LL(1) because of left recursion, but how ...
2
votes
1answer
1k views
Why we use context-free grammar for parsing?
Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?
0
votes
2answers
2k views
Computing FOLLOW sets for LL(1) grammar. Stuck on question
Calculate the FOLLOW sets for all the non terminals:
$S \rightarrow bEx \mid Db \mid b \mid F$
$D \rightarrow EDc \mid Y$
$E \rightarrow dED \mid dDY$
$Y \rightarrow ab \mid aDx \...
1
vote
2answers
2k views
Is this grammar LALR(1)
I am working through creating a LALR(1) parser generator. I have the following grammar which I designed to highlight the epsilon for rule 3.
...
1
vote
2answers
124 views
Min-Max number of shifts and reductions in bottom-up parser [closed]
Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?
1
vote
2answers
92 views
How can this grammar parse such an input?
I've an example which I simply don't get at all.
Implement an attributed grammar that checks that either
the word ends in $b$ or
each prefix of the word contains at least as many $b$s ...
-1
votes
1answer
156 views
Is this $LL(1)$ grammar valid?
Is the following a valid $LL(1)$ grammar:
$ \begin{align} S &\rightarrow L \$ \\ L &\rightarrow M L_2 \\ L_2
&\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M
&\...
0
votes
2answers
482 views
Relation between CLR Grammar and Ambiguity
I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous?
Is it possible that a grammar which is ...
2
votes
1answer
2k views
LALR(1) parsers and the epsilon transition
I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table.
Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an ...
0
votes
0answers
60 views
Can we say we reduced a rule if we reduced an equivalent set of smaller rules?
I have constructed an SLR(1) parsing table with the following rules.
S -> S + S + S (rule 1)
S -> S + S (rule 2)
S -> y
Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
0
votes
1answer
62 views
Given family of grammars, determine if LR(k)
Parsing family of grammars, determine if LR(k)
I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
0
votes
1answer
332 views
How does the Earley Parser store possible parses of an ambiguous sentence?
I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two?
...
0
votes
2answers
3k views
Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?
This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was,
Consider the following six classes of languages: Context free (...
10
votes
3answers
5k views
Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$
Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
2
votes
1answer
4k views
Resolving ambiguity in dangling else
Initially the ambiguous grammar is as follows (with some cropped production rules):
...
5
votes
1answer
958 views
Is CYK still relevant today?
I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today.
Is it or an extension of it still being used in compilers (for example), or have other ...
0
votes
1answer
706 views
LR(0) expressive power
So I have grouped the following formalisms into a power hierarchy (and made classes for them):
Class 1
DFA
NFA
NFAϵ
reg.exp
Class 2 (DCFL expressivity?)
LR(1)
DPDA
Class 3
CFG
PDA
Class 4
TM
...
1
vote
0answers
713 views
What are the fundamental differences between predictive and LALR(1) parsers?
I'm reading the Dragon book. The beginning describes recursive descent parsers. Then it states that a predictive parser is the table version of a RD parser.
I also read up on LALR(1) parsers.
The ...
