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

cjaizss

原帖由 prolj 于 2009-2-3 12:06 发表
PLC 编译器？

A － AAx
－－－－－－－
A － aA'
----------------
A －AAx
－－－－－－
aA' － aA‘aA'x

这样可以么？我表达的不好，看看意思是不是那个意思。

aA' － aA‘aA'x
这已经扩展到0类语言了,不好拿来做编译器设计啊
如果写编译器,这里的语法我可以识别,前两个回帖已经说明了这个语言的意思,但实在不知道如何用BNF表示

prolj

哦，那样的话，Yacc描述不好直接拿出来。
to 楼下 递归下降可以分析这种语法。 semt semt termail，慢慢递归吧，总有结束的时候。
问楼下 PLC编译器是什么啊？T形图？生成什么啊？如果生成代码的话，sdcc在单片机里面用的很多啊。

[ 本帖最后由 prolj 于 2009-2-3 18:01 编辑 ]

liuzq71

____________________________________________________
QUOTE:
原帖由 prolj 于 2009-2-3 12:06 发表
PLC 编译器？

A － AAx
－－－－－－－
A － aA'
----------------
A －AAx
－－－－－－
aA' － aA‘aA'x

这样可以么？我表达的不好，看看意思是不是那个意思。
aA' － aA‘aA'x
这已经扩展到0类语言了,不好拿来做编译器设计啊
如果写编译器,这里的语法我可以识别,前两个回帖已经说明了这个语言的意思,但实在不知道如何用BNF表示
________________________________________________________________________


cjaizss版主:

这样的语法如何识别啊?能否详细点讲解一下,谢谢

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

cjaizss

原帖由 liuzq71 于 2009-2-3 17:46 发表
____________________________________________________
QUOTE:
原帖由 prolj 于 2009-2-3 12:06 发表
PLC 编译器？

A － AAx
－－－－－－－
A － aA'
----------------
A －AAx
－－－－－－
aA ...

原帖由 cjaizss 于 2009-2-2 20:45 发表
还找到一个规律,从左往右,依次为c|d和b计数,
b的计数永远是小于c|d的计数,
再加上刚才提到的,生成的语言中,c|d的总数比b的总数多一
并且,如果长度大于2,则以[cd]{2}开头
貌似满足上述的性质的所有语言就是这 ...

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

liuzq71

to :prolj (爱好者)

我是想做PLC(可编程逻辑控制器)的IL(指令表程序)的"编译器"(将IL转换成*.C文件),
但现在在这里没折了,大家请邦下忙,3Q

[ 本帖最后由 liuzq71 于 2009-2-3 21:37 编辑 ]

prolj

要求产生的代码可读性么？如果不要求，那就好办了。
写一个PLC 的 IL 的 paser ， 错误自己检查，生成 LLVM IR ，剩下的事情你就不用管了， LLVM 有一个现成的 C Backend ，这个 C Backend 生成的 C 代码完全正确，可以编译，但是可读性不太好。
我对 LLVM 比较熟 顺便送你一个tutorial http://llvm.org/docs/tutorial/

[ 本帖最后由 prolj 于 2009-2-3 22:35 编辑 ]

liuzq71

原帖由 prolj 于 2009-2-3 21:55 发表
要求产生的代码可读性么？如果不要求，那就好办了。
写一个PLC 的 IL 的 paser ， 错误自己检查，生成 LLVM IR ，剩下的事情你就不用管了， LLVM 有一个现成的 C Backend ，这个 C Backend 生成的 C 代码完全正 ...

谢谢prolj (爱好者) ,我还是想用通常编译的方式,

实际上就是下面的"产生式",我不会"消除左递归"
(其中大写的是终结符,小写的是非终结符),

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 ;

再请教下:
i -> i vi ;
i -> LD ID | LDI ID ;

和下面的是否等价?

i -> t { vi } ;
t -> LD ID | LDI ID ;

cjaizss

原帖由 liuzq71 于 2009-2-4 10:20 发表


谢谢prolj (爱好者) ,我还是想用通常编译的方式,

实际上就是下面的"产生式",我不会"消除左递归"
(其中大写的是终结符,小写的是非终结符),

i -> i  i  ANB ;
i -> i  i  ORB ;
i -> i  vi ;
i  ...

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

原帖由 liuzq71 于 2009-2-4 10:20 发表
i -> i vi ;
i -> LD ID | LDI ID ;

和下面的是否等价?

i -> t { vi } ;
t -> LD ID | LDI ID ;

区别就在于{ vi } 是只有一个 vi 元素的集合，vi 只是一个 vi 元素。同一个 vi，穿上MJ是他，脱了MJ还是他。非终结符我就不认识你了？所以，这个两个是一样的。

原帖由 cjaizss 于 2009-2-4 10:28 发表
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 ;
这个规则还是太麻烦.
另外,最后两组是等价的

这个规则我记得老师讲课的时候说是无法做到的。看来lz就是想得到BNF描述转化成Yacc代码。

to lz 何苦呢？手工分析 或者 递归下降（我知道是左递归，但是在现实中总不会无限递归的）都可以解决问题，非要Yacc不成？
另外，ANTLR 也许能“对付”这种语法，不要怕那是java的，他可以生成C或者C＋＋代码的分析器。http://www.antlr.org/

cjaizss

原帖由 prolj 于 2009-2-4 11:00 发表

区别就在于{ vi } 是只有一个 vi 元素的集合，vi 只是一个 vi 元素。同一个 vi，穿上MJ是他，脱了MJ还是他。非终结符我就不认识你了？所以，这个两个是一样的。


这个规则我记得老师讲课的时候说是无法做 ...

我怀疑也是无法做到,一下子又不知道怎么去证明,也没有去查计算理论、递归论等书（估计里面也不见得有现成的证明）
但是对于
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 ;
我还没有想好真正意义上的递归下降该怎么做
我把规则缩减一下，其实只要解决下述规则，上面这个规则就解决了
A->A A a
A->A b
A->c