+ -
当前位置:首页 → 问答吧 → minic编译器设计,关于LL(1)文法

minic编译器设计,关于LL(1)文法

时间:2011-12-16

来源:互联网

大概文法要实现的句子就是这样:

0个或多个函数声明
一个函数实体

文法为(其中$为空)
program -> fun_declares fun
fun_declares -> fun_declare 
fun_declares -> $
fun_decalre -> type id ( optparams ) ; fun_declare1 
fun_declare1 -> fun_declare ;
fun_declare1 -> $
optparams -> params | $
params -> param , params | param 
param -> type | type id
fun -> type id ( optparams ) { body }
body -> stmts
stmts -> .....

这个文法不是LL1的主要是因为
select(fun_declares -> fun_declare)
select(fun_declares -> $)
有相交的元素。

抽出其中主要的部分,我把它写成这个样子了:
S->AB
A->pq|$
B->pr
分析时
select(A->pq) = p;
select(A->$) = p;
冲突了。
可能表达不太好,能理解就好了。那这个应该怎么改才是LL1文法?
先谢过各位了!

作者: kaiyuan_ky   发布时间: 2011-12-16

我提个小建议。

在我学习编译原理的时候,LL分析是一带而过的,我不知道你是因为课程需要,还是自己需要。

如果是自己需要,我强烈建议不要在LL上做过多的研究,应该把精力放在LR(1)上,以及对此算法的实现上的优化上。

作者: sinservice   发布时间: 2011-12-16

据我对LL的理解,这种算法主要是需要避免左递归的情况,至于你说的:

-------
select(fun_declares -> fun_declare)
select(fun_declares -> $)
有相交的元素。

抽出其中主要的部分,我把它写成这个样子了:
S->AB
A->pq|$
B->pr
--------

我没有看懂。

作者: sinservice   发布时间: 2011-12-16

引用 2 楼 sinservice 的回复:

据我对LL的理解,这种算法主要是需要避免左递归的情况,至于你说的:

-------
select(fun_declares -> fun_declare)
select(fun_declares -> $)
有相交的元素。

抽出其中主要的部分,我把它写成这个样子了:
S->AB
A->pq|$
B->pr
--------

我没有看懂。

你看啊
1.program -> fun_declares fun
2.fun_declares -> fun_declare 
3.fun_declares -> $
4.fun->type id ...
用标号表示产生式:
select(2)= FIRST(fun_declare) = {int,long};
select(3) = FOLLOW(fun_declares) = FIRST(fun) = {int,long};
冲突了。
至于我变成那样,可以理解:
1.S->AB program -> fun_declares fun
2.A->pq fun_declares->fun_declare //这个fun_declare的first集={int,long};
3.A->$ fun_declares->$
4.B->pr fun->type id ... //这个fun的first集={int,long}
这样
select(2) = {p};
select(3) = {p};
冲突。
就是这个意思,不知我有没有说明白

作者: kaiyuan_ky   发布时间: 2011-12-16

引用 1 楼 sinservice 的回复:

我提个小建议。

在我学习编译原理的时候,LL分析是一带而过的,我不知道你是因为课程需要,还是自己需要。

如果是自己需要,我强烈建议不要在LL上做过多的研究,应该把精力放在LR(1)上,以及对此算法的实现上的优化上。

这个是编译原理课程设计。LR(1)还没讲完,自己看了看,有点麻烦。

作者: kaiyuan_ky   发布时间: 2011-12-16