Questions tagged [parsers]
Questions about algorithms that decide whether a given string belongs to a fixed formal language.
341
questions
1
vote
0answers
181 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
423 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
68 views
1
vote
0answers
311 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
63 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
102 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
134 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
82 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
166 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
170 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
62 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
81 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
96 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
145 views
Upper bound of automaton states for SLR parsing
How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing?
My guess is that generating the canonical item collection ...
1
vote
0answers
73 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
454 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
710 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
203 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
469 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
98 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
80 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
56 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
95 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
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
101 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...
0
votes
1answer
62 views
Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?
For example, which part will detect these errors, Parser or Semantic Routine?
1) int Array[10.5] ( wrong size )
2) int x="some string"
3) A[10.5] + 3 (not in declaration, but in the middle of ...
0
votes
1answer
123 views
Context Free Grammar for Try-Catch-Finally Statement and Throw
I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "...
0
votes
1answer
926 views
Trouble understanding how to create a grammar parse tree
I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions:
To ...
0
votes
2answers
65 views
Is C → A B C | A left-factorizable?
$$C \to A B C \mid A$$
Obviously has the same FIRST(C) for the both productions.
But how can this be left-factorised?
Tried:
$$C \to A B C'$$
$$C' \to A C \mid \varepsilon$$
The FIRST sets are ...
0
votes
1answer
118 views
Are parser combinators equivalent to scannerless parsing?
From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
0
votes
1answer
170 views
In NLP, does the lexer have to tag the tokens before the parser?
In NLP, does the lexer have to tag the tokens before the parser?
I.e. does the lexer have to classify the tokens to morphological categories before the parser?
I'm thinking yes, but is this also the ...
0
votes
1answer
1k views
What exactly is the LL(k) grammar condition?
I have a bit of trouble understanding the definition of LL(k) grammars.
Here it's defined as:
for every pair of production rules
$A\rightarrow
α$
and
$A \rightarrow
β$
the following ...
0
votes
2answers
469 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 ...
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 ...
0
votes
2answers
10k 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]
...
0
votes
1answer
90 views
Prove that the syntax is equivalent
I don't "see" why the following syntax is equivalent to the second
syntax1:
E -> E + T
E -> T
syntax2:
...
0
votes
1answer
43 views
Why is left recursion and left factoring no problem in bottom up parsing?
i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced.
But why is this then a problem ...
0
votes
1answer
56 views
LL(1) and LR(0) Grammars
The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision.
For example, without reading a symbol from the input, we cannot decide in LL(1) ...
0
votes
1answer
54 views
Can you automatically generate a parser for a type using type theory some how?
Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
0
votes
1answer
34 views
extend ECMAScript by adding new keywords and syntax
I would like to extend ECMAScript by adding new keywords and syntax to it, for example:
|variableName| stipulates a special kind of variable which I would like to be able to include in a normal ...
0
votes
1answer
54 views
How to define whitespace for certain rules but else ignore it
I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? ...
0
votes
2answers
514 views
Is the given grammar LL(2)?
http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf
The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$
The example is $S -> a^kb/a^ka$
The ...
