Home My Page Projects Code Snippets Project Openings SML/NJ Bugs
Summary Activity Tracker Lists

[#170] Bogus "Left recursion" error message from ML-Antlr

Date:
2016-10-13 17:48
Priority:
3
State:
Open
Submitted by:
Bug Submitter (webuser)
Assigned to:
John Reppy (jhr)
Machine Architecture:
None
Operating System:
Generic Unix
Component:
ML-ANTLR
Resolution:
None
Severity:
Major
OS Version:
SML/NJ Version:
110.80
Keywords:
ml-lpt
URL:
Transcript (of reproduction):
<jhr@dhcp-10-135-11-128> ml-antlr dangling-else.grm [ml-antlr: parsing dangling-else.grm] [ml-antlr: checking grammar] 2 nonterminals 4 productions Left recursion detected: E -> E ...
Source (for reproduction):
%token : IF ("if") | THEN ("then") | ELSE ("else") | SKIP ("skip") | ID ; %start S; S : "if" ID "then" S E | "skip" ; E : "else" S | (* empty *) ;
Summary:
Bogus "Left recursion" error message from ML-Antlr

Detailed description
ML-Antlr reports a left recursion, where there is no such
problem. There is a problem that the grammar is not LL(k)
and it appears that the generated parser may not work on
valid input.
Additional comments:
It looks like the generated parser would fail on the input

if X then skip

because the function for the E nonterminal fails if the
first token is not "else".

Submitted via web form by John Reppy <jhr@cs.uchicago.edu>

Comments:

No Comments Have Been Posted

Attached Files:

Changes

Field Old Value Date By
assigned_tonone2016-10-24 13:07jhr
detailsML-Antlr reports a left recursion, where there is no such problem. There is a problem that the grammar is not LL(k) and it appears that the generated parser may not work on valid input. Additional comments: It looks like the generated parser would fail on the input if X then skip because the function for the E nonterminal fails if the first token is not "else". Submitted via web form by John Reppy <jhr@cs.uchicago.edu> 2016-10-24 13:07jhr
Transcript (of reproduction)<jhr@dhcp-10-135-11-128> ml-antlr dangling-else.grm [ml-antlr: parsing dangling-else.grm] [ml-antlr: checking grammar] 2 nonterminals 4 productions Left recursion detected: E -> E ... 2016-10-24 13:07jhr
Source (for reproduction)%token : IF ("if") | THEN ("then") | ELSE ("else") | SKIP ("skip") | ID ; %start S; S : "if" ID "then" S E | "skip" ; E : "else" S | (* empty *) ; 2016-10-24 13:07jhr