The parsing tag has no wiki summary.
3
votes
1answer
33 views
Parsing a string with LR parsing table
Me and my friends are studying for an upcoming test and this exercise is one of the harder ones for us.
We have been trying to solve it and we have been looking at similar exercises, the problem is ...
4
votes
2answers
102 views
Two-State Turing Machine for Parenthesis Matching
In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet ...
-2
votes
2answers
62 views
A problem on first and follow sets of a grammar
Let me know the first and follow sets of the following grammar, also the explanation to it
$A \to Ba \mid Aa \mid c$
$B \to Bb \mid Ab \mid d$
Non-terminals: $\{A,B\}$
Terminals: $\{a,b,c,d\}$
2
votes
1answer
63 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$
4
votes
2answers
60 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
0answers
116 views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
0
votes
1answer
52 views
Parsing: Tutorial? [closed]
Does anyone know of a good website/online resource that provides a tutorial on writing a parser? I've done a few google searches, and haven't had any worthwhile results returned. I was hoping to find ...
3
votes
1answer
30 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
...
1
vote
1answer
81 views
Facebook Hackercup 2013: Balanced Smileys
On Facebook HackerCup 2013, they asked the following question:
Your friend John uses a lot of emoticons when you talk to him on
Messenger. In addition to being a person who likes to express ...
2
votes
0answers
148 views
Parsing family of grammars, determine if LR(k)
Consider the family of grammars $G_n,~n\geq2$.
$$S \rightarrow A_ib_i~,~for~~1\leq i \leq n$$
$$A_i \rightarrow a_jA_i~|~a_j~,~for~~1 \leq i,j \leq n~~and~~i \neq j$$
where multiple alternative right ...
2
votes
1answer
158 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
...
2
votes
1answer
58 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 ...
7
votes
2answers
244 views
Is there any way to distinguish between LL(k) and LR(k) grammar?
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.
We also know the facts that every LL grammar is LR that is LL ...
2
votes
1answer
760 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 ...
1
vote
1answer
77 views
Phrase generators for use with testing grammars that don't use a seed
In helping someone understand phrase generators for use with testing grammars, think compiler test cases, I noted that I have never found a phrase generator that is knowledgeable of the grammar, and ...
1
vote
2answers
128 views
Can an LL(k) parser parse any grammar without left recursion or common prefixes?
I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can ...
4
votes
1answer
194 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 ...
2
votes
1answer
172 views
0
votes
1answer
214 views
LL(1) parsing table of left-recursive grammar
I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:
S -> Sa | b
According to the professor parsing table ...
1
vote
1answer
75 views
What's wrong with this LL grammar? (very short)
S --> Ta | b | Sc
T --> Tc | λ
This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never ...
2
votes
1answer
68 views
Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?
Say I have an LR grammar G and a string w. I know that I can check if w is in the language of G in linear time. But what if w itself is not in the language of G, but I want to find all substrings of w ...
6
votes
1answer
135 views
Determining whether a CFG is $LL(k)$ for any $k$?
In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.
Is there a similar result ...
