Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
383
questions
1
vote
1answer
19 views
Choosing correct action in bottom up parsing
Using grammar:
$
S \to aABe \\
A \to bcA \mid c \\
B \to b
$
to bottom parse a string $abcccde$, the course of action would be:
$
\begin{array}{c|c|c|c}
\hline
Step & Stack & Input &...
1
vote
1answer
155 views
1
vote
1answer
99 views
How do I build a left derivation tree from an expression including right-to-left associativity?
Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
1
vote
2answers
132 views
CFG - Left factoring in recursive nested productions
I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
1
vote
1answer
42 views
Follow set confusion about inclusion
The book I am learning about compilers from states that $M \to \alpha N \beta$
will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable.
This ...
1
vote
1answer
534 views
What is a “special sequence” in EBNF?
In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...?
What does this mean?
1
vote
1answer
45 views
Why is particular token missing in LALR lookahead set?
I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin:
S' ::= S
S ::= L = R | R
L ::= * R | id
R ::= L
The items associated ...
1
vote
1answer
53 views
operator precendence grammar
According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
1
vote
1answer
206 views
How to treat Ļµ-productions in table-driven predictive parsing?
Here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html
in chapter Driver Procedure, it's shown how table-drive predictive parsing works.
The predict table however can ...
1
vote
1answer
402 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
2answers
632 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 parse)...
1
vote
0answers
20 views
Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?
LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items.
Is ...
1
vote
0answers
46 views
How to write “āx.F(x)” for “F(x)=Ī»x.Ī¦(x)” in one expression (sequel from question about “ā(Ī»Ļ. (Ļ x mā Ļ y))”?
This question is sequel from How to understand quantifier without predication " ā(Ī»Ļ. (Ļ x mā Ļ y))"? which further explains the notation and context.
So - I have anonymous Boolean-valued ...
1
vote
1answer
31 views
Why is the following grammar not LL(1)
Consider the following grammar:
S ā bAb
| bBa
A ā aS
| CB
B ā b
| Bc
C ā c
| cC
I have to provide the reasons as to why this grammar is not LL(1). So far ...
1
vote
1answer
24 views
Grammar still ambigous after removing left recursion LL(1)
I have following grammar it doesnt not have Epsilon-derivation problem I can only see left recursion:
S -> a b S
S -> S a b
S -> c d
S -> a d
in ...
1
vote
1answer
58 views
Why table-driven LL (1) parser does not work with division and subtraction?
Everywhere, one grammar is used as an example table-driven LL(1) parser.
Grammar
...
1
vote
0answers
27 views
Using DPDA instead of LR parsers
If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
1
vote
0answers
95 views
Does SLR(0), LALR(0) exists?
I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
1
vote
0answers
35 views
CYK algorithm - how to handle unknown terminals given in a sentence to parse?
There is a given treebank which we derive the Probabilistic context free grammar.
I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules?
Is ...
1
vote
0answers
17 views
State of the art of parser handling of offset errors
Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the ...
1
vote
1answer
77 views
Is the following Grammar LL(1)
I was given the following grammar
$S \rightarrow S ( S ) S\mid \epsilon$
First I was asked to eliminate left recursion, yielding me the following :
$S \rightarrow S' $
$S' \rightarrow (S)...
1
vote
0answers
30 views
Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?
Definite clause grammars have been around a long time and are included in logic languages such as Prolog.
They can be translated into (are just syntactic sugar for) Prolog programs and are therefore ...
1
vote
0answers
129 views
Do SLR(1) parsers have lookahead?
The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
1
vote
0answers
19 views
Clear definitions of various terms related to top down parsers and classification of the same
I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am ...
1
vote
0answers
360 views
How to design a LL(1) grammar for basic regular expression?
I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.ļ¼\| is the escape character, since | is a special character in grammar's pattern).
...
1
vote
0answers
648 views
Are LL(1) grammars a subset of LR(0) grammars?
As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction.
Grammar :
S -> (S) | [S] | {S} | Īµ
This is an LL1 while it seems ...
1
vote
1answer
104 views
1
vote
0answers
421 views
Can a YACC parse an ambiguous grammar
I found a question while studying compilers :-
Given a grammar E->E+E/EĆE/number
The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC.
1) it ...
1
vote
0answers
80 views
Generate an AST from an indefinite grammar and logic
As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
1
vote
0answers
397 views
How do we evaluate semantic actions in L attributed SDT?
I came across following problem:
$SāER$
$RāāE\{print(ā²āā²);\}Rā£Īµ$
$EāF+E\{print(ā²+ā²);\}ā£F$
$Fā(S)ā£id\{print(id.value);\}$
Here $id$ is a token that represents an integer and $id.value$ ...
1
vote
0answers
156 views
Can the HTML5 parsing algorithm be implemented in linear time?
Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input? It seems ...
1
vote
0answers
85 views
Where is left recursion in this little CF grammar?
S ā D
D ā E | EC
E ā anyId
C ā B | .D | B.D
B ā <S> | <SA>
A ā ,S | ,SA
The tool I am using keeps complaining about left recursion in this grammar. I ...
1
vote
0answers
209 views
Is the Java 8 Grammar still a LALR(1) grammar?
As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't ...
1
vote
0answers
41 views
Determining the set of valid next terminals when generating from a CFG
I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this ...
1
vote
0answers
192 views
Converting Ambiguous Grammar G to LL(1)
So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...
1
vote
0answers
75 views
Is it possible to transform this grammar into LL(1)?
This is the original grammar:
S -> ABe
A -> ab | a | Ļµ
B -> b
I did try left factoring and this is what I got:
...
1
vote
0answers
93 views
How do merged lookahead sets help LALR parse more grammars than SLR? [closed]
From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-...
1
vote
0answers
99 views
How can we avoid mistake in LL(1) parse tree?
I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
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] ...
1
vote
0answers
24 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):...
1
vote
0answers
502 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 \ ...
1
vote
0answers
718 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 ...
1
vote
0answers
208 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 ...
1
vote
0answers
511 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
0answers
244 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
0answers
113 views
Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?
I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related.
Suppose I have a regular expression:
RE=(aa)?(aa)
and I convert it to a grammar:
G ::= A B
A ::= C | (...
1
vote
0answers
81 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 ...
