Are %shift modifiers still supported to resolve ambiguities?

[mewmew]

From my understanding of http://textmapper.org/documentation.html#grammar-ambiguities, %shift modifiers may be used to resolve shift/reduce ambiguities in grammars.

From the example, I tried to derive a minimal working grammar. However, when I tried to generate the parser using Textmapper, I got the following error:

$ textmapper shiftreduce.tm 
shiftreduce.tm,34: input: 'if' '(' Expr ')' Stmt
shift/reduce conflict (next: 'else')
    IfStmt : 'if' '(' Expr ')' Stmt

conflicts: 1 shift/reduce and 0 reduce/reduce
lalr: 0.019s, text: 0.105s, parser: 18 states, 0KB

From https://github.com/mewspring/foo/blob/427ecc6ddb2a95906cea7570c5b28c33abc26544/shiftreduce/shiftreduce.tm#L33:

IfStmt
	: 'if' '(' Expr ')' Stmt %shift 'else'
	| 'if' '(' Expr ')' Stmt 'else' Stmt
;

Is that the correct syntax for using %shift modifiers, and if so, why is there a shift/reduce error being reported?

If I remove 'if' '(' Expr ')' Stmt %shift 'else' from the grammar, Textmapper is able to successfully produce both lexers and parsers.

Edit: this is on version v0.9.22 of Textmapper.

u@x1 ~> textmapper --version
textmapper v0.9.22/java build 2018

[mewmew]

The specific ambiguity I'm trying to figure out how to deal with is described in llir/llvm#40.

I've tried quite a few different approaches to resolve the ambiguity by making changes to the grammar, but so far, I've been unsuccessful to find a working approach. Any feedback would be much appreciated, as my "usual" approaches don't seem to work this time.

The core issue boils down to the fact that LLVM IR has a lost of optional fields and attributes, as already discussed in other issues.

In particular, what I would like to do, is to enable Align in ReturnAttribute and FuncAttribute.

# NOTE: FuncAttribute should contain Align. However, using LALR(1) this
# produces a reduce/reduce conflict as the global attributes of
# GlobalDecl and GlobalDef also contains Align.

%interface FuncAttribute;

# TODO: Figure out how to enable Align in FuncAttribute again.

FuncAttribute -> FuncAttribute
	: AttrString
	| AttrPair
	# not used in attribute groups.
	| AttrGroupID
	# used in functions.
	#| Align # NOTE: removed to resolve reduce/reduce conflict, see above.
	# used in attribute groups.
	| AlignPair
	| AlignStack
	| AlignStackPair
	| AllocSize
	| FuncAttr
;

ReturnAttribute -> ReturnAttribute
	# TODO: Figure out how to re-enable without getting these errors in FuncHeader:
	#    - two unnamed fields share the same type `AttrPair`: ReturnAttribute -vs- FuncAttribute
	#    - `AttrPair` occurs in both named and unnamed fields
	#    - `ReturnAttrs` cannot be nullable, since it precedes FuncAttrs
	#: AttrString
	#| AttrPair
	#| Align
	: Dereferenceable
	| ReturnAttr
;

The GlobalDecl production rule optionally contains both Align (as a comma separated global attribute (',' Align)?) and FuncAttribute and is defined as follows:

GlobalDecl -> GlobalDecl
	: Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? (',' Align)? Metadata=(',' MetadataAttachment)+? FuncAttrs=(',' FuncAttribute)+?
;

And, Align is simply defined as:

Align -> Align
	: 'align' N=UintLit
;

Initially when I try to update the grammar I get ll.tm,816: Align occurs in both named and unnamed fields. This is easily resolved by assigning a name; i.e. Align=(',' Align)?.

At this point, I get the error ll.tm,816: Align cannot be nullable, since it precedes FuncAttrs which seem to be related to #25.

Now, this is usually where I try to break up use of optional non-terminals in production rules into 2^n alternatives, where n is the number of optional non-terminals that are part of the conflict.

While not pretty, the following approach was used successfully with Gocc:

From ll.bnf:

GlobalDecl
	: GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType OptCommaAttachedMDList                                    << astx.NewGlobalDecl($0, $3, $4, $5, $6) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Align OptCommaAttachedMDList                          << astx.NewGlobalDecl($0, $3, $4, $5, $8) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Comdat OptCommaAttachedMDList                         << astx.NewGlobalDecl($0, $3, $4, $5, $8) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Comdat "," Align OptCommaAttachedMDList               << astx.NewGlobalDecl($0, $3, $4, $5, $10) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Section OptCommaAttachedMDList                        << astx.NewGlobalDecl($0, $3, $4, $5, $8) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Section "," Align OptCommaAttachedMDList              << astx.NewGlobalDecl($0, $3, $4, $5, $10) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Section "," Comdat OptCommaAttachedMDList             << astx.NewGlobalDecl($0, $3, $4, $5, $10) >>
	| GlobalIdent "=" ExternLinkage GlobalOptions Immutable ConcreteType "," Section "," Comdat "," Align OptCommaAttachedMDList   << astx.NewGlobalDecl($0, $3, $4, $5, $12) >>
;

I've tried to apply similar techniques using Textmapper, but so far to no vail.

This is what I tried:

GlobalDecl -> GlobalDecl
	: Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)?
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? FuncAttrs=(',' FuncAttribute)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Metadata=(',' MetadataAttachment)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Metadata=(',' MetadataAttachment)+ FuncAttrs=(',' FuncAttribute)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Align=(',' Align)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Align=(',' Align)+ FuncAttrs=(',' FuncAttribute)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Align=(',' Align)+ Metadata=(',' MetadataAttachment)+
	| Name=GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable ContentType=Type (',' Section)? (',' Comdat)? Align=(',' Align) Metadata=(',' MetadataAttachment)+ FuncAttrs=(',' FuncAttribute)+
;

Which results in the following error:

ll.tm,816: `Align` cannot be nullable, since it precedes FuncAttrs
ll.tm,829: `Align` occurs in both named and unnamed fields
ll.tm,820: input: TopLevelEntity_optlist GlobalIdent '=' ExternLinkage Preemptionopt Visibilityopt DLLStorageClassopt ThreadLocalopt UnnamedAddropt AddrSpaceopt ExternallyInitializedopt Immutable Type ',' Align
reduce/reduce conflict (next: eoi, global_ident_tok, local_ident_tok, comdat_name_tok, metadata_name_tok, metadata_id_tok, 'attributes', 'declare', 'define', 'module', 'source_filename', 'target', 'uselistorder_bb', 'uselistorder')
    list_of_','_and_1_elements2 : ',' Align
    FuncAttribute : Align

conflicts: 8 shift/reduce and 9 reduce/reduce
lalr: 0.332s, text: 0.592s, parser: 2228 states, 229KB

Any thoughts? Is there something obvious I'm missing, or is this grammar especially tricky since it contains so many optional attributes?

Kindly,
Robin