编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

网站建设哪家好，找创新互联！专注于网页设计、网站建设、微信开发、小程序定制开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了乐平免费建站欢迎大家使用！

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。

在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。

对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。

我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。

进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S - aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S - aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:

定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A - ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。

那么对于 A - a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:

定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。

那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。

我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？

例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。

其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。

而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :

就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S - Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。

这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。

但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。

例如:

那么如何进行改造呢？

其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。

而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。

例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai - Ajβ 来判断是不是间接左递归，那如果有产生式 Ai - BAjβ 且 B - ε ,那么它是不是间接左递归呢？

间接地我们可以推出如果一个产生式 Ai - αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

编译原理实验二 LL(1)分析法

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

根据某一文法编制调试 LL(1)分析程序，以便对任意输入的符号串进行分析。

构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。

分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表，对输入符号串自上而下的分析过程。

对文法 的句子进行不含回溯的自上向下语法分析的充分必要条件是：

（1）文法不含左递归；

（2）对于文法中的每一个非终结符 的各个产生式的候选首符集两两不相交，即，若

Follow集合构造：

对于文法 的每个非终结符 构造 的算法是，连续使用下面的规则，直至每个 不再增大为止：

仅给出核心部分

(1) GrammerSymbol.java

(2) GrammerSymbols.java

(3) Grammer.java

(4) LL1Grammer.java

编译原理的LL(1)文法是什么意思？

L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将用最左到推倒，1表明只需向右看一个符号便可决定如何推倒即选择哪个产生式（规则）进行推导，类似也可以有LL（k）文法，也就是需要向前查看k个符号才能确定选用哪个产生式、、

关于LL（1）文法

(1)first(E)={(,i},first(D)={+,-,ε},first(T)={(,i},first(S)={*,/,ε}

first(F)={(,i}

follow(E)={#,)},follow(D)={#,)},follow(T)={+,-,#,)} follow(S)={+,-,#,)} follow(F)={*,/,+,-,#,)}

(2)select(E-TD)=FIRST(TD)={(,i}

SELECT(E-+TD)={+}

SELECT(E--TD)={-}

SELECT(E-ε)={#,)}

SELECT(T-FS)={(,i}

SELECT(S-*FS)={*}

SELECT(S-/FS)={/}

SELECT(S-ε)={+,-,#,)}

SELECT(F-(E))={(}

SELECT(F-i)={i}

预测分析表：

+ - * / （ ） i #

E -+TD --TD -TD -ε -TD -ε

D

T -FS -FS

S -ε -ε -*FS -/FS -(E) -ε -ε

F -i

(3)i/i-i的分析过程：

步骤 输入串 剩余串 移进或规约

1 # i/i-i#

2 #i /i-i# E-TD

3 #DT ......

...

剩余的只要按照书上的步骤填就行了。

高分求LL(1)语法分析设计原理与实现技术

#includestdio.h

#includeiostream.h

#includestring.h

#define Vtn 8

#define Vnn 5

#define Pn 10

#define Pmaxlen 20

#define MaxStLength 50

#define MaxStackDepth 50

char Vn[Vnn]={'E','e','T','t','F'};

char Vt[Vtn]={'i','+','-','*','/','(',')','$'};

char Pstr[Pn][Pmaxlen]=

{

"E-Te",

"e-+Te",

"e--Te",

"e-ε",

"T-Ft",

"t-*Ft",

"t-/Ft",

"t-ε",

"F-(E)",

"F-i"

};

int Prlen[Pn]={2,3,3,1,2,3,3,1,3,1};

int Pint[Pn][3]=

{

{102,101},

{1,102,101},

{2,102,101},

{-1},

{104,103},

{3,104,103},

{4,104,103},

{-1},

{5,100,6},

{0}

};

int analyseTable[Vnn][Vtn+1];

int analyseStack[MaxStackDepth+1];

int topAnalyse;

char st[MaxStLength];//要分析的符号串

/* ----------------------初始化----------------------------*/

void InitanalyseTable()

{

/*---预测分析表存放各个产生式的编号，-1表示找不到相匹配的产生式---*/

for(int i=0;iVnn;i++)

for(int j=0;jVtn;j++)

analyseTable[i][j]=-1;

analyseTable[0][0]=0;

analyseTable[0][5]=0;

analyseTable[1][1]=1;

analyseTable[1][2]=2;

analyseTable[1][6]=3;

analyseTable[1][7]=3;

analyseTable[2][0]=4;

analyseTable[2][5]=4;

analyseTable[3][1]=7;

analyseTable[3][2]=7;

analyseTable[3][3]=5;

analyseTable[3][4]=6;

analyseTable[3][6]=7;

analyseTable[3][7]=7;

analyseTable[4][0]=9;

analyseTable[4][5]=8;

}

void Init()

{

//分析栈的初始化

analyseStack[0]=7;//入栈

analyseStack[1]=100;//初始符入栈

topAnalyse=1;

//初始符号串

int i;

for(i = 0;i MaxStLength;i++)

st[i] = '\0';

}

void Pop()

{

topAnalyse--;

}

/*--------------------产生式入栈操作----------------------*/

void Push(int r)

{

int i,len;

Pop();

len=Prlen[r];

//为空时

if((len==1)(Pint[r][0]==-1))

return;

//不为空时

topAnalyse+=len;

for(i=0;ilen;i++)

analyseStack[topAnalyse-i]=Pint[r][i]; //逆序入栈

}

void ShowStack()

{

int i;

for(i =0;i=topAnalyse;i++)

{

if(analyseStack[i]=100)

printf("%c",Vn[analyseStack[i]-100]);

else

printf("%c", Vt[analyseStack[i]]);

}

}

/*----------------------返回表中的位置，-1表示未找到----------*/

int Index(char c)

{

int i=0;

while((iVtn)(c!= Vt[i]))

i++;

if((iVtn)(c==Vt[i])) return i;

else return -1;

}

void Identify()

{

int current,step,r;

printf("\n%s：\n\n", st);

step = 0;

current = 0;

printf("%d\t",step);

ShowStack();

printf("\t\t%s\t\t- -\n", st+current);

while(1)

{

if(analyseStack[topAnalyse]100)

{

if(Vt[analyseStack[topAnalyse]]==st[current])

{

Pop();

current++;

step++;

printf("%d\t",step);

ShowStack();

printf("\t\t%s\t\t出栈、后移\n", st+current);

}

else

{

printf("字符 %c 与字符 %c 不匹配!", Vt[analyseStack[topAnalyse]], st[current]);

printf("此串不符合此文法!\n");

return;

}

}

else

{

int n,m;

n=analyseStack[topAnalyse] - 100;

m=Index(st[current]);

if(m==-1)

{

printf(" %c 字符输入错误!" ,st[current]);

printf("此串不符合此文法!\n");

return;

}

r = analyseTable[n][m];

if( r!=-1)

{

Push(r);

step++;

printf("%d\t", step);

ShowStack();

printf("\t\t%s\t\t%s\n", st+current,Pstr[r]);

}

else

{

printf("无可用产生式，此串不是此文法的句子!\n");

return;

}

}

if(topAnalyse==0st[current]=='$') break;

}

}

///////////////////////////////////////////////////////////////////////////////////////////////////

void main()

{

InitanalyseTable();

while(1)

{

Init();

printf("请输入符号串(以$结束):");

int i=0;

char c;

c=getchar();

while(iMaxStLength)

{

if(c=='$')

{

st[i]='$';

break;

}

else if(c!=' 'c!='\n')

st[i++]=c;

c=getchar();

if(c=='\n')

{

printf("请以$结束：");

c=getchar();

}

}

if(iMaxStLength)

Identify();

else printf("输入的符号串超过规定长度");

}

}

网站栏目：ll1文法java代码的简单介绍
文章起源：http://myzitong.com/article/hhgsdh.html