Mixing
LL(1) parsing conflict
I'm writing a LL(1) parser for a very simple grammar. Yet I've found conflicts when trying to build the parsing table.
I'm surprised since the grammar seems simple. I don't know if I have a problem with the parser or with my understanding of LL(1) parsing. Maybe the grammar is not LL(1) in the end.
The grammar is:
1: S -> begin list
2: list -> id listPrime
3: listPrime -> id listPrime
4: | ε
My code runs into two conflicts, both for deriving listPrime, one with the terminal symbol id and one with the EOF. In both cases rule 3 clashes against rule 4.
My computed FIRST and FOLLOW sets are:
first:
{ S: Set { 'begin' },
list: Set { 'id' },
listPrime: Set { 'id', 'eps' } },
follow:
{ S: Set { 'EOF' },
list: Set { 'EOF', 'id' },
listPrime: Set { 'EOF', 'id' } } }
parsing ll
asked Jan 2 at 22:55
dv1729dv1729
420317
add a comment |
I'm writing a LL(1) parser for a very simple grammar. Yet I've found conflicts when trying to build the parsing table.
I'm surprised since the grammar seems simple. I don't know if I have a problem with the parser or with my understanding of LL(1) parsing. Maybe the grammar is not LL(1) in the end.
The grammar is:
1: S -> begin list
2: list -> id listPrime
3: listPrime -> id listPrime
4: | ε
My code runs into two conflicts, both for deriving listPrime, one with the terminal symbol id and one with the EOF. In both cases rule 3 clashes against rule 4.
My computed FIRST and FOLLOW sets are:
first:
{ S: Set { 'begin' },
list: Set { 'id' },
listPrime: Set { 'id', 'eps' } },
follow:
{ S: Set { 'EOF' },
list: Set { 'EOF', 'id' },
listPrime: Set { 'EOF', 'id' } } }
parsing ll
asked Jan 2 at 22:55
dv1729dv1729
420317
add a comment |
I'm writing a LL(1) parser for a very simple grammar. Yet I've found conflicts when trying to build the parsing table.
I'm surprised since the grammar seems simple. I don't know if I have a problem with the parser or with my understanding of LL(1) parsing. Maybe the grammar is not LL(1) in the end.
The grammar is:
1: S -> begin list
2: list -> id listPrime
3: listPrime -> id listPrime
4: | ε
My code runs into two conflicts, both for deriving listPrime, one with the terminal symbol id and one with the EOF. In both cases rule 3 clashes against rule 4.
My computed FIRST and FOLLOW sets are:
first:
{ S: Set { 'begin' },
list: Set { 'id' },
listPrime: Set { 'id', 'eps' } },
follow:
{ S: Set { 'EOF' },
list: Set { 'EOF', 'id' },
listPrime: Set { 'EOF', 'id' } } }
parsing ll
asked Jan 2 at 22:55
dv1729dv1729
420317
I'm writing a LL(1) parser for a very simple grammar. Yet I've found conflicts when trying to build the parsing table.
I'm surprised since the grammar seems simple. I don't know if I have a problem with the parser or with my understanding of LL(1) parsing. Maybe the grammar is not LL(1) in the end.
The grammar is:
1: S -> begin list
2: list -> id listPrime
3: listPrime -> id listPrime
4: | ε
My code runs into two conflicts, both for deriving listPrime, one with the terminal symbol id and one with the EOF. In both cases rule 3 clashes against rule 4.
My computed FIRST and FOLLOW sets are:
first:
{ S: Set { 'begin' },
list: Set { 'id' },
listPrime: Set { 'id', 'eps' } },
follow:
{ S: Set { 'EOF' },
list: Set { 'EOF', 'id' },
listPrime: Set { 'EOF', 'id' } } }
parsing ll
parsing ll
asked Jan 2 at 22:55
dv1729dv1729
420317
asked Jan 2 at 22:55
dv1729dv1729
420317
asked Jan 2 at 22:55
dv1729dv1729
420317
asked Jan 2 at 22:55
dv1729dv1729
420317
asked Jan 2 at 22:55
dv1729dv1729
420317
420317
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.
answered Jan 3 at 16:54
ricirici
157k20138206
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54014244%2fll1-parsing-conflict%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.
answered Jan 3 at 16:54
ricirici
157k20138206
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
add a comment |
The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.
answered Jan 3 at 16:54
ricirici
157k20138206
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
add a comment |
The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.
answered Jan 3 at 16:54
ricirici
157k20138206
The grammar is LL(1). Your FOLLOW sets are computed incorrectly, which can easily be verified: there is no derivation in which list or listPrime is followed by a token other than EOF.
answered Jan 3 at 16:54
ricirici
157k20138206
answered Jan 3 at 16:54
ricirici
157k20138206
answered Jan 3 at 16:54
ricirici
157k20138206
answered Jan 3 at 16:54
ricirici
157k20138206
157k20138206
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
add a comment |
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
Thank you so much! I was stuck at this, after realizing that FOLLOW was wrong I was able to fix the bugs quickly
– dv1729
Jan 3 at 18:42
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54014244%2fll1-parsing-conflict%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
