Question

编译原理一个文法的EBNF表示

原文法规则如下：
lexp →NUMBER| ( op lexp-seq )
op →+ | - | 
lexp -seq → lexp-seq lexp|lexp
最后是想让它EBNF规范：
我现在知道lexp -seq → lexp-seq lexp|lexp 变成lexp -seq →lexp{lexp}然后代入lexp →NUMBER| ( op lexp-seq )变成lexp →NUMBER| ( op lexp{lexp})接下来我就不会了，lexp →NUMBER| ( op lexp{lexp})这个文法既是左递归又是右递归，它该怎样表示消除自身的递归啊。。。{}表示0到多个重复，高手来解答下啊，万分感激！！！

Answer 1

首先
lexp-seq->lexp-seq lexp|lexp
消除左递归 得
lexp-seq->lexp q'
q'->lexp q'|空

解的ebnf为

lexp->NUMBER|(+|-|*)lexp{lexp}
就得
S->{NUMBER(+|-|*)}NUMBER
{}中间表示0次或以上