开发者

How to remove Left recursive in this ANTLR grammar?

开发者 https://www.devze.com 2023-02-19 08:58 出处:网络
I am trying to parse CSP(Communicating Sequential Processes) CSP Reference Manual. I have defined following grammar rules.

I am trying to parse CSP(Communicating Sequential Processes) CSP Reference Manual. I have defined following grammar rules.

assignment
    : IDENT '=' processExpression
    ;
processExpression
    :   ( STOP
        | SKIP
       开发者_JAVA技巧 | chaos
        | prefix
        | prefixWithValue
        | seqComposition
        | interleaving
        | externalChoice

        ....

seqComposition
    :   processExpression ';' processExpression
    ;
interleaving
    :   processExpression '|||' processExpression
    ;
externalChoice
    :   processExpression '[]' processExpression
        ;

Now ANTLR reports that

seqComposition 
interleaving
externalChoice

are left recursive . Is there any way to remove this or I should better used Bison Flex for this type of grammar. (There are many such rules)


Define a processTerm. Then write rules looking like

assignment
    : IDENT '=' processExpression
    ;
processTerm
    :   ( STOP
        | SKIP
        | chaos
        | prefix
        ...
processExpression
    :   ( processTerm
        | processTerm ';' processExpression
        | processTerm '|||' processExpression
        | processTerm '[]' processExpression

        ....

If you want to have things like seqComposition still defined, I think that would be OK as well. But you need to make sure that the parsing of processExpansion is going to always consume more text as you proceed through your rules.


Read the guide to removing left recursion in on the ANTLR wiki. It helped me a lot.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号