去除左递归的问题

landker

请教有关C语法的问题

1、对于C语言语法里的 declarator 和 abstract_declarator，以及其相关的direct_declarator 和 direct_abstract_declarator 的C语言语法如下：

=============================================================================================
1）declarator
        : pointer direct_declarator
        | direct_declarator
        ;

2）direct_declarator
        : IDENTIFIER
        | '(' declarator ')'
        | direct_declarator '[' constant_expression ']'
        | direct_declarator '[' ']'
        | direct_declarator '(' parameter_type_list ')'
        | direct_declarator '(' identifier_list ')'
        | direct_declarator '(' ')'
        ;

3）abstract_declarator
        : pointer
        | direct_abstract_declarator
        | pointer direct_abstract_declarator
        ;

4）direct_abstract_declarator
        : '(' abstract_declarator ')'
        | '[' ']'
        | '[' constant_expression ']'
        | direct_abstract_declarator '[' ']'
        | direct_abstract_declarator '[' constant_expression ']'
        | '(' ')'
        | '(' parameter_type_list ')'
        | direct_abstract_declarator '(' ')'
        | direct_abstract_declarator '(' parameter_type_list ')'
        ;

============================================================================================


2、对于以上4条语法，在去左递归后，变为如下：
============================================================================================
1）declarator不存在左递归

2）direct_declarator        : IDENTIFIER R
                        | '(' declarator ')' R
                        ;

                R        : '[' constant_expression ']' R
                        | '[' ']' R
                        | '(' parameter_type_list ')' R
                        | '(' identifier_list ')' R
                        | '(' ')' R
                        | Ɛ
                        ;                                       

3）abstract_declarator不存在左递归，但为了方便分析，转换为如下：

abstract_declarator        : A B
                        ;

                A        : pointer
                        | Ɛ
                        ;

                B        : direct_abstract_declarator
                        | Ɛ
                        ;

4）direct_abstract_declarator        : '(' abstract_declarator ')' R
                                | '[' ']' R
                                | '[' constant_expression ']' R
                                | '(' ')' R
                                | '(' parameter_type_list ')' R
                                                                ;

                        R         : '[' ']' R
                                | '[' constant_expression ']' R
                                | '(' parameter_type_list ')' R
                                | '(' ')' R
                                | Ɛ
                                ;       
============================================================================================


3、问题

1）对于上面第2中的2）、4）的“去左递归”的转换是否正确？

landker

回复 1# landker

ding
   

cjaizss

回复 1# landker
正确

duanlin

2）

direct_declarator
  : IDENTIFIER
  | '(' declarator ')'
  | IDENTIFIER R
  | '(' declarator ')' R
  ;

R
  : '[' constant_expression ']'
  | '[' ']'
  | '(' parameter_type_list ')'
  | '(' identifier_list ')'
  | '(' ')'
  | '[' constant_expression ']' R
  | '[' ']' R
  | '(' parameter_type_list ')' R
  | '(' identifier_list ')' R
  | '(' ')' R
  ;

让规则R不可匹配空规则，这样写还对么？