SQL解析器之求FIRST集

本人欲用自顶向下进行SQL的语法分析,在此之前必须进行推导式的FIRST和FOLLOW集的求解,在求解FIST集中要注意

  • 不能有左递归
  • 不能有循环递归,如A->B  B->C C->A,这样会造成分析的死循环

目前完成FIRST集的求解,终结符采用小写的一位字母和')','(','+','-'等,非终结符采用大写字母,如有必要可拓展终结符和非终结符

FIRST集求解算法

FIRST(α)的算法(α=x1x2xn):根据定义计算

根据定义计算

  由定义4.1 FIRST(α)={a|αaβ,aVTα,βV*},αε,则规定εFIRST(α)

  对每一文法符号XV 计算FIRST(X)

  (a) XVT,则FIRST(X){X}

  (b) XVN,且有产生式XaaVT aFIRST(X)

  (c) XVNX→ε,εFIRST(X)

   (d) XVNY1Y2YiVN,且有产生式XY1 Y2 Yn

Y1 Y2 Yi-1ε时,(其中1in),则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(1ji-12in), εFIRST(Xj), FIRST(α)=(FIRST(Xj)\{ε})FIRST(Xi)

  当所有FIRST(Xj)(1jn)都含有{ε}时,则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');
上一篇:数据结构之Trie树


下一篇:黑客炼金术士 Seeker:可以攻破 4G 摸到你短信,还要为朝阳群众提供谍战工具