Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
384
questions
4
votes
1answer
586 views
How to find unambiguous grammar for palindromes
I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.
...
4
votes
1answer
1k views
How can I check that the language of one context-free grammar is a subset of a second context-free grammar?
Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2).
G1 and G2 are two LL(1) grammars with ...
4
votes
4answers
3k views
What information do we get from a compiler's parse tree?
In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of ...
4
votes
2answers
528 views
Meta-grammar for context-free grammars
Formal grammars like regular expressions (REs) or context-free
grammars (CFGs) specify languages, i.e. sets of strings over an
alphabet.
Grammars themselves can be seen as languages, e.g.
the set of ...
4
votes
2answers
821 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 ...
4
votes
1answer
423 views
Parsing CFLs (simulating PDA vs CYK algorithm)
We can simulate the PDA and parse the language with the following operations (vaguely):
Read the input symbol and top of stack - $O(1)$
Check all the transition rules (must check all for non-...
4
votes
1answer
409 views
Building Simple Parse Trees
I am trying to learn how to build parse trees.
I have watched videos and tried to do some on my own, but am a little lost.
In this example, I am given the following:
$$
\begin{align*}
&S\to(L) ...
4
votes
2answers
286 views
Priority in formal grammar
From my recitation class, I have the following exercise:
$\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$
The above grammar is ambiguous.
...
4
votes
1answer
456 views
From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?
There is this question I read somewhere but could not answer myself.
Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a ...
4
votes
1answer
5k views
What is a “sentential form”?
I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" ...
4
votes
1answer
590 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....
4
votes
1answer
572 views
Is this phrase structure grammar from my textbook correct?
I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.
On page 12, the authors start describing a set of rules that can be used to ...
4
votes
1answer
135 views
Parser theory: How to systematically compute FOLLOW sets?
Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
4
votes
1answer
937 views
Bottom-Up Parser With Leftmost Derivation
I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:
[...] a parser can produce a list of ...
4
votes
1answer
159 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 ...
4
votes
2answers
22k views
Understanding LEADING and TRAILING operations of an operator precedence grammar
I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean.
I am ...
4
votes
0answers
111 views
Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?
The ...
4
votes
0answers
152 views
How does Earley parsing using an automaton work?
As described in this paper, you can use an pre-computed automaton to speed up an Earley parse. I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can ...
4
votes
1answer
155 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, ...
3
votes
1answer
198 views
What was Robert Floyd's algorithm for inserting brackets?
In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the āNobel Prizeā of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
3
votes
3answers
3k views
Is this language LL(1) parseable?
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.
$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$
Is my hypothesis true ...
3
votes
3answers
937 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 ...
3
votes
1answer
5k views
How to make a parse tree for the following propositional logic formula?
I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.
As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree ...
3
votes
3answers
1k views
Understanding $\text{handle}$ in parsing problem
Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there
The BNF is defined as followed:
...
3
votes
1answer
172 views
LL grammars and left-recursiviity
Why LL(k) and LL(ā) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
3
votes
1answer
114 views
Why doesn't the C/C++ compilers create different tokens for different types of numbers?
Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc.
However if we ...
3
votes
1answer
74 views
Is there a way to efficiently parse this grammar?
Consider the following context-free grammar:
$T \to (*) \mid (T*) \mid (*T) \mid (T*T)$
This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either ...
3
votes
1answer
580 views
Expressive power of lexer + parser
Most modern compilers split their syntax analysis into
a lexical phase that is followed by a parsing phase.
The lexical phase is given by a regular expression, while parsing
is guided by a context-...
3
votes
1answer
128 views
parsing at semantic level due to ambiguities
I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment
...
3
votes
1answer
2k views
LR(1) - Items, Look Ahead
I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ?
Say for an example that I have the following grammar:
S -> AB
A -> aAb | b
...
3
votes
1answer
307 views
Connection between non determinism and LL(1) conflicts
I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.
As per my understanding non deterministic context free grammar is a context free grammar ...
3
votes
1answer
586 views
Prove that every CFL is decidable in O(n) space
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:
Prove that every context free language $A$ is in $\mathrm{SPACE}...
3
votes
1answer
811 views
What is handle in bottom up LR parsing?
I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows:
Assume a rightmost ...
3
votes
1answer
85 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 ...
3
votes
1answer
416 views
Indentation based Grammars
Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars.
I can ...
3
votes
2answers
2k views
Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$
I am having difficulty with one of the exercises in the Dragon Book:
Exercise 2.4.1(c): Construct recursive-descent parsers, starting with
the following grammars:
$$S \rightarrow 0S1\ |\ 01$$...
3
votes
1answer
205 views
Can Earley parser work in parallel?
Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc.
You just need to modify the start of each ...
3
votes
1answer
162 views
Bottom up chart parser adding active arc step
I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is
I couldn't understand the 3rd step. I thought that when active arc is added the dot ...
3
votes
1answer
149 views
Is there a name for this tree traversal?
This came when I was looking at block scoping in compiler design.
{ A { B } { C {D} {E} } }
For the above pseudo code, the order in which the scope ...
3
votes
1answer
516 views
Where does LL parser belong in the top-down parsers classification
There are four types of top-down parsers according to this answer:
recursive descent backtracking
recursive descent predictive
table-driven with backtracking
table-driven predictive.
Also the author ...
3
votes
1answer
2k views
How to generate an LL(2) parse table?
The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that:
...
3
votes
2answers
4k views
Bottom-Up Evaluation of Inherited Attributes
I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows :
Using a top-down translation scheme, we can implement any
$L$-attributed definition ...
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-...
3
votes
1answer
310 views
Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar
How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar
Like for grammar $G$ with the following rules
$S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
3
votes
1answer
48 views
How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar
I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that
...
3
votes
1answer
76 views
SLR parse table and unambiguity
If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous?
I think that since we have constructed the parse table ...
3
votes
1answer
235 views
The upper bound on a Nondeterministic Finite Automata's configurations number
In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon,
in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2,
section "Equivalence of NFAs and DFAs"
discusses the upper bound of a NFA's ...
3
votes
1answer
271 views
If a grammar is SLR(1) then are the LALR and SLR tables the same?
I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all ...
3
votes
1answer
641 views
Eliminate left recursion from grammar
Consider the following grammar:
$$
A\to Ba|Aa|c \\
B\to Bb|Ab|d
$$
How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?
I have tried applying the ...
3
votes
0answers
44 views
Algorithm for undirected projective dependency parsing
I am looking for an algorithm that will get an optimal projective undirected dependency parse.
That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function ...
