Reversing a List from a Context-Free Grammar

Question

Let's say I have a struct_declaration_list of the following type. How do I reverse it?

struct_declaration_list
    : struct_declaration
    | struct_declaration_list struct_declaration
    ;

P.S. Sorry I don't know the exact name of this kind of list so I can't search. I just have this grammar.

What do you mean by "reverse"? Could you give some examples? — svick, Nov 21, 2014 at 14:23
@svick Probably too late. I've got a similar confusion as OP. My interpretation of "reverse" is that: given a grammar rule (such as the one in the Q) that defines the order of evaluation in the form of self-recursion, how to obtain a sequential list where elements are in the order of the defined order of evaluation. — DannyNiu, Mar 24 at 9:24

babou · Accepted Answer · 2014-11-21 17:23:20Z

Your question is not very precise. I assume you want the list of struct_declaration to start from the other end in the parse tree.

Your grammar gives you a struct_declaration_list that looks like

         SDL
        /   \
      SDL    SD
     /   \
   SDL   SD
  /   \
SDL   SD
 |
SD

If you reverse the order in the second part of the rule, you reverse "the pointers" in the list, which may be understood as reversing the order.

struct_declaration_list
    : struct_declaration
    | struct_declaration struct_declaration_list
    ;

Then the parse tree looks like:

   SDL
  /   \
 SD   SDL
     /   \
    SD   SDL
        /   \
       SD   SDL
             |
            SD

The left-to-right order of SD is in both cases that of their occurrence in the input string (the program).

This would flip the order of evaluation if the rule is intended as a self-recursion definition. I've added a comment under OP explaining my interpretation of the problem OP's facing. — DannyNiu, Mar 24 at 9:27

1 Answer 1