本人欲用自顶向下进行SQL的语法分析，在此之前必须进行推导式的FIRST和FOLLOW集的求解，在求解FIST集中要注意
- 不能有左递归
- 不能有循环递归，如A->B B->C C->A,这样会造成分析的死循环
目前完成FIRST集的求解，终结符采用小写的一位字母和')','(','+','-'等，非终结符采用大写字母，如有必要可拓展终结符和非终结符
FIRST集求解算法
求FIRST(α)的算法（α=x1x2…xn）：根据定义计算
① 根据定义计算
由定义4.1 FIRST(α)={a|αaβ,a∈VT，α,β∈V*},若αε,则规定ε∈FIRST(α)
对每一文法符号X∈V 计算FIRST(X)：
(a) 若X∈VT，则FIRST(X)＝{X}。
(b) 若X∈VN，且有产生式X→a…，a∈VT， 则 a∈FIRST(X)。
(c) 若X∈VN，X→ε,则ε∈FIRST(X)。
(d) 若X∈VN；Y1，Y2，…，Yi∈VN，且有产生式X→Y1 Y2 … Yn；
当Y1 Y2 … Yi-1都ε时，(其中1≤i≤n)，则FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)的所有非{ε}元素
和FIRST(Yi)都包含在FIRST(X)中。
(e) 当(d)中所有Yiε,(i=1,2,… n)，则 FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}
反复使用上述(b)～(e)步直到每个符号的FIRST集合不再增大为止。
求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。
若符号串α∈V*，α=X1 X2 … Xn,当X1不能ε,则置FIRST(α)= FIRST(X1)。
若对任何j(1≤j≤i-1，2≤i≤n), ε∈FIRST(Xj), 则FIRST(α)=(FIRST(Xj)\{ε})∪FIRST(Xi)
当所有FIRST(Xj)(1≤j≤n)都含有{ε}时，则FIRST(α)=(FIRST(Xj))∪{ε}
代码采用递归求解：
//获得FIRST集
function TSCanner.GetFirst(s: TStringList): TStringList;
var
i,j,k:Integer;
sTemp,MyRes:string;
Data:PFirst;
s1:PChar;
sList,slTemp1:TStringList;
procedure GetAllProduction(sNoTerminate:string;sList:TStringList;var Res:TStringList);
var
i,j:Integer;
s1:string;
begin
for i:=0 to sList.Count-1 do
begin
j :=Pos(FInfer,sList[i]);
if j>0 then
begin
if Trim(MidStr(sList[i],1,j-1))=Trim(sNoTerminate) then
Res.Add(sList[i]);
end;
end;
end;
procedure GetOne(str:string);
var
i,j:integer;
s1,s2,sTemp:string;
slTemp1:TStringList;
begin
slTemp1 :=TStringList.Create;
GetAllProduction(str,s,slTemp1);
For i :=0 to slTemp1.Count-1 do
begin
sTemp :=Trim(slTemp1[i]);
j :=Pos(FInfer,sTemp);
if (j>0) then
begin
s1 :=Copy(sTemp,j+Length(FInfer),1);
s2 :=Copy(sTemp,j+Length(FInfer),2);
if (InTerminate(s1)) then
begin
if not OneInOther(s1,sTemp) then
MyRes :=MyRes+s1+ ',';
end
else if (s2='ε') then
begin
if not OneInOther(s2,sTemp) then
MyRes :=MyRes+s2+','
end
else if InNoTerminate(s1) then
begin
GetOne(s1);
//此处可用一堆栈保存非终结符，有新的非终结符则入栈，入栈前查看栈内是否已有此非终结符
//如有则会导致死循环，报错退出
end;
end;
end;
slTemp1.Free;
end;
begin
sList :=TStringList.Create;
Result :=TStringList.Create;
//slTemp1 :=TStringList.Create;
try
GetAllNoTerminate(s,sList);
for i:=0 to sList.Count -1 do
begin
//获取所有sList[i]推导的产生式 如A->a或A->BCa
MyRes :='';
GetOne(sList[i]);
if Trim(MyRes)<>'' then
Delete(MyRes,Length(MyRes),1);
New(Data);
Data^.Name :=sList[i];
Data^.Value :=MyRes;
Result.AddObject(Data^.Name,TObject(Data));
end;
finally
sList.Free;
//slTemp1.Free;
end;
end;
其中结构体、终结符和非终结符定义如下
1 PFirst=^TFirst;
2 TFirst=record
3 Name:string;
4 Value:string;
5 end;
6
7 PFollow=^TFollow;
8 TFollow=record
9 Name:string;
10 Value:string;
11 end;
12
13 const
14 arrTerminate:array[1..31] of string=('a','b','c','d','e','f','g','h','i','j','k',
15 'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',')','(','+','-','ε');
16 arrNoTerminate:array[1..26] of string=('A','B','C','D','E','F','G','H','I','J','K',
17 'L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');
