The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
44 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
37 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 ...
1
vote
1answer
49 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 ...
2
votes
2answers
44 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 ...
1
vote
0answers
57 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 ...
3
votes
1answer
49 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) ...
0
votes
0answers
39 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
47 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
37 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 ...
0
votes
3answers
135 views

What data is stored in the symbol table for a number token?

I'm reading the Dragon Book. The following is from the start of Section 3.1.3. When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases ...
0
votes
2answers
54 views

Which Type of Grammar is this?

I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the ...
0
votes
2answers
503 views

Drawing Annotated Parse Tree for Syntax Directed Definition [closed]

Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following: [Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308] ...
1
vote
2answers
83 views

Need solution for infinite right recursive grammar in Predictive parsing?

i am new to compiler design, currently studying Ullmans book on this.He says: Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite ...
6
votes
1answer
182 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
1
vote
1answer
86 views

Binary operators with higher precedence than unary operators

Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators ...
1
vote
0answers
227 views

lexical scoping vs. dynamic scoping

I'm wondering about the result of this program as I get confused when it comes to lexical scoping and dynamic scoping. ...
0
votes
0answers
57 views

LR(1) constructing DFA

Consider the following grammar, where $ [ \ ] \ | \ , \ $ are terminal symbols $ \begin{eqnarray} L \rightarrow [ \ ] \qquad(1) \\ L \rightarrow [ \ H\ T\ ] \qquad(2) \\ H \rightarrow L \qquad (3) ...
0
votes
1answer
53 views

Parsing Dice Notation

The syntax of dice notation follows the following grammar: $$ Roll \rightarrow Dice | Dice'x'Int | More \quad Mod \quad More $$ $$ Dice \rightarrow Int_{1}'d'Int_2$$ $$ Mod \rightarrow '+'|'-'$$ $$ ...
1
vote
0answers
50 views

what does “Configuration is valid for a viable prefix ” actually means?

I am learning LR(1) parsing from the Dragon Book. I am really confused with this sentence. Formally we say that a configuration $[A \to u•v, a]$ is valid for a viable prefix $α$ if there is a ...
4
votes
1answer
116 views

Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
0
votes
1answer
96 views

How can I define this syntax? [closed]

I wanted to define syntax for a graph path considering it may branch out anywhere. For instance, I have a path going from a to ...
1
vote
2answers
170 views

Parse Tree building

I am trying to learn how to build parse trees. This is a very simple example as I am hoping I can catch on to the concept. $\mathtt{y=x+z}$ Wouldn't this simply require $\mathtt{(term) = (term) + ...
7
votes
5answers
348 views

Does an abstract syntax tree have to be a tree?

Does the output of a parser have to be a tree or could it also be general graph? Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees ...
0
votes
1answer
24 views

$FIRST_k$ set — is algorithm given by Aho&Ullman correct?

I am writing this, because no matter how I look at the algorithm I see an error :-) Aho & Ullman in "Theory of Parsing, vol.1" (pp. 357-359) described the algorithm for building $FIRST_k(A)$ set ...
4
votes
1answer
164 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
1k 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
1answer
102 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
90 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. ...
7
votes
0answers
171 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 ...
3
votes
1answer
34 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
207 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
273 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
562 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
275 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 ...
9
votes
2answers
1k 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 ...
3
votes
2answers
3k 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
123 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
243 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
261 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
377 views
1
vote
2answers
334 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
92 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
94 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
181 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 ...