Reduces a bit the size of expressions AST

vsbenas / parser-gen

A parser generator in Lua using PEG syntax.

MIT License

49 stars 9 forks source link

This pull request makes two things: reduces a bit the size of expressions AST and fixes some small issues with operators associativity in the lua-parser.lua example.

For instance, return 2^3+1 was generating the following AST:

rule='chunk',
{
         rule='block',
         {
                  rule='retstat',
                  'return',
                  {
                           rule='explist',
                           {
                                    rule='exp',
                                    {
                                             rule='expOR',
                                             {
                                                      rule='expAND',
                                                      {
                                                               rule='expREL',
                                                               {
                                                                        rule='expBIT',
                                                                        {
                                                                                 rule='expCAT',
                                                                                 {
                                                                                          rule='expADD',
                                                                                          {
                                                                                                   rule='expMUL',
                                                                                                   {
                                                                                                            rule='expUNA',
                                                                                                            {
                                                                                                                     rule='expPOW',
                                                                                                                     {
                                                                                                                              rule='expTokens',
                                                                                                                              {
                                                                                                                                       rule='number',
                                                                                                                                       {
                                                                                                                                                rule='INT',
                                                                                                                                                '2',
                                                                                                                                       },
                                                                                                                              },
                                                                                                                     },
                                                                                                                     {
                                                                                                                              rule='operatorPower',
                                                                                                                              '^',
                                                                                                                     },
                                                                                                                     {
                                                                                                                              rule='expUNA',
                                                                                                                              {
                                                                                                                                       rule='expPOW',
                                                                                                                                       {
                                                                                                                                                rule='expTokens',
                                                                                                                                                {
                                                                                                                                                         rule='number',
                                                                                                                                                         {
                                                                                                                                                                  rule='INT',
                                                                                                                                                                  '3',
                                                                                                                                                         },
                                                                                                                                                },
                                                                                                                                       },
                                                                                                                              },
                                                                                                                     },
                                                                                                            },
                                                                                                   },
                                                                                          },
                                                                                          {
                                                                                                   rule='operatorAddSub',
                                                                                                   '+',
                                                                                          },
                                                                                          {
                                                                                                   rule='expMUL',
                                                                                                   {
                                                                                                            rule='expUNA',
                                                                                                            {
                                                                                                                     rule='expPOW',
                                                                                                                     {
                                                                                                                              rule='expTokens',
                                                                                                                              {
                                                                                                                                       rule='number',
                                                                                                                                       {
                                                                                                                                                rule='INT',
                                                                                                                                                '1',
                                                                                                                                       },
                                                                                                                              },
                                                                                                                     },
                                                                                                            },
                                                                                                   },
                                                                                          },
                                                                                 },
                                                                        },
                                                               },
                                                      },
                                             },
                                    },
                           },
                  },
         },
},

After faking a fold with repetition and removing extra nodes I got the following AST:

rule='chunk',
{
         rule='block',
         {
                  rule='retstat',
                  'return',
                  {
                           rule='explist',
                           {
                                    rule='exp',
                                    {
                                             rule='exp',
                                             {
                                                      rule='exp',
                                                      {
                                                               rule='exp',
                                                               {
                                                                        rule='expTokens',
                                                                        {
                                                                                 rule='number',
                                                                                 {
                                                                                          rule='INT',
                                                                                          '2',
                                                                                 },
                                                                        },
                                                               },
                                                               {
                                                                        rule='operatorPower',
                                                                        '^',
                                                               },
                                                               {
                                                                        rule='exp',
                                                                        {
                                                                                 rule='expTokens',
                                                                                 {
                                                                                          rule='number',
                                                                                          {
                                                                                                   rule='INT',
                                                                                                   '3',
                                                                                          },
                                                                                 },
                                                                        },
                                                               },
                                                      },
                                             },
                                             {
                                                      rule='operatorAddSub',
                                                      '+',
                                             },
                                             {
                                                      rule='expTokens',
                                                      {
                                                               rule='number',
                                                               {
                                                                        rule='INT',
                                                                        '1',
                                                               },
                                                      },
                                             },
                                    },
                           },
                  },
         },
},

Regarding operators associativity, you were using repetition for some rules that should associate to the right:

...
expCAT      <-  expADD (operatorStrcat expADD^ErrConcatExpr)* -- associate to the right
...
expPOW      <-  expTokens (operatorPower expUNA^ErrPowExpr)* -- associate to the right
...

So I just changed them to only use right recursion.

...
expCAT      <-  (expADD (operatorStrcat expCAT^ErrConcatExpr)?) -> fixexp
...
expPOW      <-  (expTokens (operatorPower expUNA^ErrPowExpr)?) -> fixexp
...

Not so much a mistake, as a special case for when we have a partial AST due to errors in the input, thanks for the contribution.

2017-09-19 10:56 GMT-04:00 Andre Murbach Maidl notifications@github.com:

Really great work!! Line 16 should be changed to

Thanks for applying my PR and fixing my mistake. I haven't gone through tests, sorry, and going back and forth between C and Lua sometimes makes my eyes not see this kind of silly mistake. :)

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/vsbenas/parser-gen/pull/3#issuecomment-330566858, or mute the thread https://github.com/notifications/unsubscribe-auth/AZe9q-_G5vZVJn-nRM9Kz1MeM5iyX24Wks5sj9YqgaJpZM4Pcb0e .

vsbenas / parser-gen

Reduces a bit the size of expressions AST #3