下面的"产生式"如何"消除左递归"?谢谢

prolj

原帖由 cjaizss 于 2009-2-4 11:45 发表

我怀疑也是无法做到,一下子又不知道怎么去证明,也没有去查计算理论、递归论等书（估计里面也不见得有现成的证明）
但是对于
i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  vi ;
i -> LD  ID  |  LDI  I ...

你都把伪码给出来了还想怎么递归干啥？那个对应的递归就是 semt semt termianl ，前面两个 semt 慢慢递归，总有变成 terminal 的时候。 当然要是非设计一种无限递归的语言，我也没办法。
我记得 ANTLR 的bbs上有人说过 AAa 这样的语法，好像可以被 ANTLR 描述，只是 ANTRL 默认生成 java代码，用C/C++的模板可以生成C/C++代码，这一点和 Lemon 是一样的。

cjaizss

原帖由 prolj 于 2009-2-4 13:23 发表

你都把伪码给出来了还想怎么递归干啥？那个对应的递归就是 semt semt termianl ，前面两个 semt 慢慢递归，总有变成 terminal 的时候。 当然要是非设计一种无限递归的语言，我也没办法。
我记得 AN ...

呵呵,那个伪码只可以用来处理
A->A A b
A->c
却不可以处理
A->A A b
A->A c
A->d

liuzq71

   .....

(这里只是个例子,其中最里层的语句行并不一定是这样的组合规律,但最里层的一定是以ＬＤ ...或LDI ...这一行语句开头的)
这是 ＩＬ语言的输入部分语句的结构,它象汇编一样,每行一句,前面是指令,后面跟０个或几个操作数,结构好象是块一样,块中又可包含块,可以是无限的包含,大侠们是否可以邦我归纳一下,重新邦我写出产生式,谢谢!

"前面的"我写的产生式是否正确?

[ 本帖最后由 liuzq71 于 2009-2-4 17:29 编辑 ]

prolj

这个问题强大，留着，以后有时间再说，我先干别的，等待答案。

liuzq71

(其中大写的是终结符,小写的是非终结符),

i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  vi ;
i -> LD  ID  |  LDI  ID ;
vi -> OR ID | ORI ID | vo ;
vo -> AND  ID | ANI  ID ;

这些产生式是否可以用"自底向上分析"的方法写分析程序?看来"递归下降分析法"是悬了

prolj

说句题外话，lz 的毕业设计老师如果是关老师的话，这个问题可以去问姚老师，她喜欢推自动机，或者去计算机系问王老师。实在不行用上一界的“论文”看看，他这个题目给学生做了好几年了。
BNF 都没有，怎么 Yacc 啊？
无论怎么分析，分析出来就行了，分析不了的别总在分析器上下文章，想想语法怎么改。PLC 编译器那么成熟，就没有开源的？google一下看有现成代码么？

cjaizss

想到
A->AAb
A->Ac
A->d
怎么解决了
过会写出伪码

cjaizss

A->AAb
A->d
已经解决了
而
A->AAb
A->Ac
A->d
中的c永远出现在d或者c之后,而且可以有任意多

cjaizss

于是,
A->A A b
A->A c
A->d
伪码:
if(输入!=d) {
     语言不接受
     结束
}
if(输入结束) {
    语言接受
   结束
}
while(输入==c);
if(输入!=d) {
     语言不接受
     结束
}
d_count=2
b_count=0
last=d
while(输入没结束) {
    if(d_count<=b_count) {
          语言不接受
       结束
    }
    x=输入
    if(x==d)
              d_count++
    else if(x==b)
             b_count++
    else if(x!=c || (x==c  & last!=c|d)){      
            语言不接受  //该语言不接受bcd之外的字符
        结束
   }
     last=x
}
if(d_count==b_count+1) {
     语言接受
} else {
    语言不接受
}

liuzq71

to:prolj (爱好者)
感谢您的建议,
只是PLC的指令表程序的编译器,我网上找了几个月了,从没看到说到点子上的,收费论文也弄了N多篇,没用,基本东插一段西插一段是抄袭的多,
我是想用编译的方法来识别分析它,做一个实用的编译器,硬件早弄好了,单片机方面的编程也没什么问题了,现在就卡在这上位机上,呵呵,还是希望继续得到您的帮助,谢谢

to:
cjaizss,真的是万分的感谢!

您的意思是,这一伪码就是非终结符A的函数A()的实现部分么?
您的这一伪码,是不是自顶向下分析中的"递归下降分析法"?还是其它,我的#23楼的图中的程序的语法,是不是可以用"递归下降分析法"分析?还是要用"LR(1)"?
编译原理方面,我是菜鸟,希望继续得到您的帮助,谢谢!

A()
{
   if(输入!=d) {
     语言不接受
     结束
}
if(输入结束) {
    语言接受
   结束
}
while(输入==c);
if(输入!=d) {
     语言不接受
     结束
}
d_count=2
b_count=0
last=d
while(输入没结束) {
    if(d_count<=b_count) {
          语言不接受
       结束
    }
    x=输入
    if(x==d)
              d_count++
    else if(x==b)
             b_count++
    else if(x!=c || (x==c  & last!=c|d)){      
            语言不接受  //该语言不接受bcd之外的字符
        结束
   }
     last=x
}
if(d_count==b_count+1) {
     语言接受
} else {
    语言不接受
}
}

[ 本帖最后由 liuzq71 于 2009-2-5 11:44 编辑 ]