Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
354
questions
1
vote
3answers
1k views
Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?
Table 4 in Problem Solving with Algorithms and Data Structures's
chapter on Infix, Prefix and Postfix Expressions gives the following examples:
...
0
votes
1answer
26 views
In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | …$, $a_i$s terminals
One procedure for table-driven top-down parsing is given here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html
This gives for matching the input the lines:
...
4
votes
2answers
588 views
What is the point of delimiters and whitespace handling
I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
0
votes
2answers
70 views
Is C → A B C | A left-factorizable?
$$C \to A B C \mid A$$
Obviously has the same FIRST(C) for the both productions.
But how can this be left-factorised?
Tried:
$$C \to A B C'$$
$$C' \to A C \mid \varepsilon$$
The FIRST sets are ...
0
votes
1answer
122 views
Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$
With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$
I need to:
run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
0
votes
1answer
131 views
Are parser combinators equivalent to scannerless parsing?
From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
-2
votes
1answer
258 views
Automata vs Earley parsing? [closed]
If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley.
Regular languages are a subset of context-free languages, but ...
0
votes
1answer
185 views
In NLP, does the lexer have to tag the tokens before the parser?
In NLP, does the lexer have to tag the tokens before the parser?
I.e. does the lexer have to classify the tokens to morphological categories before the parser?
I'm thinking yes, but is this also the ...
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
44 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
385 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
67 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
74 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
2k 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
592 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
144 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
258 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 ...
2
votes
1answer
337 views
What's 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 ...
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
157 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
140 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
271 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
256 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
844 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
520 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 ...
13
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
500 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
542 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
299 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
466 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
164 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
74 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
221 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
434 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
163 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
527 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
3k 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
61 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
63 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 ...
