Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
327
questions
3
votes
3answers
726 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
459 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 ...
9
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
455 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 ...
3
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
490 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
255 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
439 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
146 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
72 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
211 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
320 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
1k 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
91 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
150 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
436 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
61 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
254 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
897 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
679 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
700 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 ...
2
votes
2answers
135 views
BNF and Simultaneous Parsing
Let's say we have the following grammar
expr1 ::= ... // Actual definition doesn't matter
expr2 ::= ... //
expr3 ;:= ... //
foo ::= expr1 | expr2 | expr3
...
1
vote
0answers
198 views
LALAR vs SLR Table for Given SLR Grammar
i'm so glad that ask my first question on my favorite site.
Infact i ran into multiple choice question in recent exam on Compiler Course.
Suppose T1, T2 is created with SLR(1) and LALR(1) for ...
0
votes
2answers
1k views
Are constituency grammars and dependency grammars two different types of context free grammars?
From http://en.wikipedia.org/wiki/Parse_tree
A concrete syntax tree or parse tree or parsing tree[1] or derivation
tree is an ordered, rooted tree that represents the syntactic
structure of a ...
3
votes
1answer
485 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-...
2
votes
2answers
473 views
Lexing and parsing a language with juxtaposition as an operator
Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for ...
9
votes
1answer
746 views
How do I reconstruct the forest of syntax trees from the Earley vector?
Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have ...
1
vote
0answers
432 views
LL(1) grammar for postfix ternary operations
Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary.
Obvious approach is
$N$ - number
$O$ - operation
$S$ - expression
rules:...
1
vote
1answer
1k views
LR(0) parsing: how can I know sets of items corresponding to states?
I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(...
0
votes
1answer
1k views
Computing FOLLOW sets for a LL(1) grammar
I am trying to learn compiler design. But I get confused when I have to deal with Follow set specifically for the empty word. I am trying to figure this out please help me with the same.
...
4
votes
1answer
331 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) ...
3
votes
1answer
123 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
...
0
votes
0answers
179 views
Parsing Turing Machine
Have a question that requires me to write the rules for parsing a turing machine
This is the question
The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether ...
1
vote
1answer
256 views
Why does left recursion have to be eliminated? [closed]
For example,
Let the Grammar be:
S->Sa|B
Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa
What's wrong with ...
-1
votes
1answer
243 views
Left recursion for LL(1) [closed]
Hi I am trying to solve a LL(1) form question for first n follow rule The question is
A::=BC|C
B::=Bd|ef
C::=gh|j
What I have done to eliminate left recursion
<...
2
votes
2answers
296 views
What type of recursion is this?
I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar:
$\qquad A \to 0 A 1 \mid 0 1$
Which produces:
$\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \...
