Can I use assigned actions to create different parse rules that have common prefix?

[luan-xiaokun]

Hi guys, I'm here for help, again.

My problem is that, the language I'm working on has two integer types: the normal integer type int and the bounded integer type int lbound=Expression '..' ubound=Expression, and there is also the array type, which can be declared by int[] or (int 0 .. 1)[3]. The parentheses for array of bounded integer should be necessary since there may be something like a[0] in the upper bound expression and we cannot tell whether such a last pair of brackets belongs to the upper bound expression or the array type without the parentheses (please correct me if there is a way to do so).

Therefore, I think that the normal integer type and the bounded integer type should be declared as different parse rules so that I can write the array type parse rule. If I use different parse rules for these two integer types, then I get an error for common prefix in these two rules since the underlying algorithm is LL(k), and if I use the assigned actions to fix the error, then it will end up only one parse rule with different semantic types.

Is there any way to solve this problem? Or is this a case that the LL(k) algorithm cannot handle?

PS: in this language, variable declaration is in the form of Id: Type, not in the C style Type Id

[msujew]

Hey @luan-xiaokun,

The parentheses for array of bounded integer should be necessary since there may be something like a[0] in the upper bound expression and we cannot tell whether such a last pair of brackets belongs to the upper bound expression or the array type without the parentheses

You're right, such an expression always requires parentheses to split the upper bound expression from the array declaration part.

Is there any way to solve this problem? Or is this a case that the LL(k) algorithm cannot handle?

The way I'm imagining your grammar/language to look like, I don't believe that LL(k) is able to handle your language without resorting to assigned actions. Even increasing k wouldn't help (note that this is possible by supplying a maxLookahead in the parser config, see here).

However, I could be wrong. Do you mind sharing a snippet of what you already have? It might be possible to do this, if your grammar doesn't look the way I imagine it to llok.

[luan-xiaokun]

Thanks for your reply!

The following is a subset of the rules I've written, currently the grammar allows something like int 0 .. 1[3]. The complete langium grammar file is available at here.

entry Program:
    (Expression ':' Type ';')*;

Expression:
    name=ID
    | value=(INT | REAL | CHAR | BOOL | NULL)
    | '[' values+=Expression (',' values+=Expression)? ']';

Type infers Type:
    (PrimitiveType | BracketType)
    ({infer ListType} '[' (capacity=Expression)? ']')*
;

BracketType infers Type:
    '(' Type ({infer TupleType.types+=current} ',' types+=Type)* ')';

interface PrimitiveType {
    name: 'int' | 'real' | 'char' | 'bool' | string;
}

interface BoundedIntType extends PrimitiveType {
    lbound: Expression;
    ubound: Expression;
}

PrimitiveType returns PrimitiveType:
    {BoundedIntType} BoundedIntType |
    name=('int' | 'real' | 'char' | 'bool' | NULL);

BoundedIntType returns BoundedIntType:
    name='int' lbound=Expression '..' ubound=Expression;

Another problem with the complete grammar file I discovered recently is that array declaration like int[3] is not correctly parsed because I also allow the use list construct in the expressions, so the parser thinks that the [3] is a lower bound for a bounded integer and says that it is expecting .. and an upper bound. Although this problem seems irrelevant to the issue at hand, I'd like to ask for your help here in case my frequent help-seeking bothers others. If this question is typical and may be helpful to others, I am also willing to start another discussion.

By the way, the roadmap for Q4 mentioned that an ALL(*) extension for Chevrotain has been merged, (thanks for your great work!) I'm not familiar with compilers, so I'm curious if the ALL(*) extension can handle such case?