Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
373
questions
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
202 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
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(...
1
vote
1answer
397 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
622 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
1answer
27 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
23 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
54 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
26 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
80 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
33 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
68 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
29 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
122 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
326 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
633 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
98 views
1
vote
0answers
405 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
2answers
125 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
0answers
385 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
148 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
206 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
186 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
98 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
23 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
717 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
503 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
233 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
108 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 ...
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 (...
0
votes
1answer
94 views
Is there a LL(K) Grammar which is not LALR(K) Grammar?
It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
0
votes
2answers
111 views
Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?
Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?
This question seems very trivial, but I don't know ...
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 string ...
0
votes
3answers
2k 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
1answer
102 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 e...
