SQL解析器之求FIRST集

本人欲用自顶向下进行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)。

　 (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');

秒客网

SQL解析器之求FIRST集

相关文章