Newbie question

Oct 24, 2014 at 3:37 PM
I'm trying to define a grammar for a simple language:

zero or more a's followed by zero or more b's

The following code functions very well for this:
NonTerminal PROGRAM = new NonTerminal("PROGRAM");
NonTerminal ALIST = new NonTerminal("AS");
NonTerminal BLIST = new NonTerminal("BS");

ALIST.Rule = MakeStarRule(ALIST, ToTerm("a"));
BLIST.Rule = MakeStarRule(BLIST, ToTerm("b"));
PROGRAM.Rule = ALIST + BLIST;

this.Root = PROGRAM;
Now I need to change the grammar so that every a and b should be on a new line and there can be empty lines in between.

Whatever I try, I keep getting reduce-conflicts...

Please help,
Simon
Coordinator
Oct 26, 2014 at 6:54 PM
MakeStarRule allows specifying delimiter inside, try using NewLine with it. Most likely your problem comes from joining two STAR rules - each allows empty list as implementation, so an empty file has multiple interpretations - like Empty Alist or Empty BList, or both. Try to remove ambiguity by altering rules
Oct 27, 2014 at 5:45 PM
Thanks!

I added the delimiter, but it didn't work straight away. I looked in the code for MakeStarRule and added a modified call to MakeListRule.
NonTerminal PROGRAM = new NonTerminal("PROGRAM");
NonTerminal ALIST = new NonTerminal("AS");
NonTerminal BLIST = new NonTerminal("BS");

ALIST.Rule = MakeListRule(ALIST, NewLinePlus, ToTerm("a"), TermListOptions.StarList | TermListOptions.AllowTrailingDelimiter | TermListOptions.AllowEmpty);
BLIST.Rule = MakeListRule(BLIST, NewLinePlus, ToTerm("b"), TermListOptions.StarList | TermListOptions.AllowTrailingDelimiter | TermListOptions.AllowEmpty);
PROGRAM.Rule = ALIST + BLIST;

this.Root = PROGRAM;
It parses ok now, but there are 2 shift-reduce conflicts.
Shift-reduce conflict. State S0, lookaheads [LF]. Selected shift as preferred action.
Shift-reduce conflict. State S3, lookaheads [LF]. Selected shift as preferred action.
I've tried adding some PreferShiftHere()'s but I'm not sure where to put them.

Any tips?
Coordinator
Oct 27, 2014 at 5:53 PM
I don't think this kind of grammar (with multiple empty lines in between) fits pure LALR algorithm, it might be difficult to express this in BNF in a simple way.
I would suggest a bit simpler approach. Define the grammar as sequence of lines that are either A or B or empty. Program is a list of lines. This grammar allows mixing A and Bs in any order. Then hook to Reduced event of LineList non-terminal and check in code that the order is correct - A's are before B's.
Essentially you define grammar for less restrictive simpler language, but then enforce extra rule after parsing, by validating the parse tree.
Oct 27, 2014 at 5:55 PM
Thanks, I'll try that!