211 questions
1
vote
0
answers
34
views
Transform grammar of functional language to LL(1)
I am trying to transform a grammar for a functional language into an LL(1) one. I am erasing left recursion in favor of right recursion and then the first condition on non overlapping firstsets is ...
- 11
0
votes
1
answer
65
views
Parsing extended lambda calculus using recursive descent
I'm writing interpreter for simple lambda calculus based language in C. EBNF for language is
S ::= E
E ::= 'fn' var '->' E | T {'+' T} | T {'-' T}
T ::= F {'*' F} | F {'/' F}
F ::= P {P}
P ::= var |...
- 3
0
votes
1
answer
43
views
How can the expression rule be converted into LL(1) without becoming right-associative?
In the following small grammar, I am confused about how this basic rule for defining a binary operator combination can be converted to an LL(1) grammar that will produce a left-associative AST:
...
0
votes
1
answer
47
views
Is this grammar LL(1)? Why so? If not, make it LL(1)
A -> Aac | Ab | Bb | a
B -> Ac | Ad | ϵ
Is this grammar LL(1)? Why so? If not, make it LL(1)
I need help solving this. I think it's not LL(1) because it has left recursion but I don't know ...
0
votes
1
answer
185
views
Generate an equivalent LL(1) language
I need to convert a context free grammar G to an equivalent grammar of type LL(1), but I cannot meet the conditions such that this grammar is in LL(1). I have already performed left factorization and ...
- 1
0
votes
1
answer
90
views
How to turn a Grammar to LR(0)
Is there a general algorithm that turns a given grammar into LR(0) grammar?
I tried turning the grammar into CNF but even when I succeeded it didnt work out to be LR0
0
votes
1
answer
445
views
Is there a simple example how Earley parser outperforms (or allows less verbose grammar than) LL(k) parser?
I've read that Earley is easier to use and that it can handle more cases than LL(k) (see https://www.wikiwand.com/en/Earley_parser):
Earley parsers are appealing because they can parse all context-...
- 402
0
votes
1
answer
159
views
Grammer Left Factoring
I'm preparing midterm exam, so I found some questions and tried to solve it.
But my answer is not as same as given answer
Question:
Consider The Following Grammar, Which Generates Email Addresses:
...
0
votes
1
answer
80
views
Is this rule LL(1)?
On a sort of academic note, I am wondering whether the following rule is LL(1) or 2:
tableItem:
Identifier (Dot Identifier)? (Dot Identifier)? (Dot Identifier)? # simplePath
| OpenParen ...
- 1,794
0
votes
1
answer
130
views
Definition of First and Follow sets of the right-hand sides of production
I am learning about LL(1) grammars. I have a task of checking if grammar is LL(1) and if not, I then need to find the rules, which prevent it from being LL(1). I came across this link https://www.csd....
- 17
3
votes
1
answer
4k
views
Epsilon(ε) productions and LR(0) grammars and LL(1) grammars
At many places (for example in this answer here), I have seen it is written that an LR(0) grammar cannot contain ε productions.
Also in Wikipedia I have seen statements like: An ε free LL(1) grammar ...
- 695
1
vote
1
answer
234
views
antlr parsing of java 8 file (python binding) - slow running time
I'm trying to scan a java 8 file with antlr4, based on this java 8 grammar. Everything goes fine, except the running time:
input_stream = FileStream("/main.java")
lexer = Java8Lexer(...
- 7,200
2
votes
2
answers
1k
views
Why do we need FOLLOW set in LL(1) grammar parser?
In generated parsing function we use an algorithm which looks on a peek of a tokens list and chooses rule (alternative) based on the current non-terminal FIRST set. If it contains an epsilon (rule is ...
- 53
1
vote
1
answer
1k
views
How to handle operator precedence in an LL(1) parser
I was writing an LL(1) parser for an expression grammar. I had the following grammar:
E -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> INT
However, this is left recursive and I removed ...
- 323
5
votes
1
answer
487
views
John Hughes' Deterministic LL(1) parsing with Arrow and errors
I wanted to write a parser based on John Hughes' paper Generalizing Monads to Arrows. When reading through and trying to reimplement his code I realized there were some things that didn't quite make ...
- 1,484