AI 助理
备案控制台
开发者社区 云计算 文章 正文

follow集的求解

2011-08-28 705
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 根据定义计算 对文法中每一 A∈VN 计算 FOLLOW(A) (a) 设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里"#"为句子句号)。 (b) 若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(B)中。

根据定义计算

对文法中每一 A∈VN 计算 FOLLOW(A)

(a) 设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里"#"为句子句号)。

(b) 若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(B)中。

    如果β =>ε则把FOLLOW(A)也加入FOLLOW(B)中。

(c) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。

 

或：

(a)对文法开始符号S，令#∈FOLLOW(S)。

(b)若B→αAβ是一个产生式，则令FIRST(β)-{ε}属于FOLLOW(A)；

(c)若B→αA是一个产生式，或B→αAβ是一个产生式且有ε∈FOLLOW(β)，

则令FOLLOW(B)是FOLLOW(A)的子集。即把FOLLOW(B)的所有元素加入到FOLLOW(A)中。

(d)反复使用(b)直到每个非终结符的 FOLLOW集合不再增加为止。

 

     根据以上分析求FOLLOW集要依赖于FIRST集的求解，因为上一篇已经求出FIRST集，但里面的一些函数应该可以共享给FOLLOW集的求解，所以相应的需要修改FIRST集的求法，下面为修改后的FIRST集解法和FOLLOW集解法的定义部分，其中FInfer为推导符,可以为->或→，arrTerminate为终结符集，arrNoTerminate为非终结符集：

    

 1 TSCanner = class(TObject)
 2   private
 3     FInfer, FStart: string;
 4   public
 5     MyNoTerminate: TStringList;
 6     MyToken: TToken;
 7     function ScanSQL(str: string): Boolean;
 8     function Pro_Process(str: string): string;
 9     function DeleteBlankLines(str: string; buf: PChar): Boolean;
10     function SplitString(const Source, ch: string): TStringList;
11     function UpdateAllKey(sWords: string): string;
12     function GetAllToken(sWords: string): string;
13     function InTerminate(s: string): Boolean; //是否为终结符
14     function InNoTerminate(s: string): Boolean; //是否为非终结符
15 
16     procedure GetAllNoTerminate(sContent: TStringList; var Res: TStringList);
17     function OneInOther(s, str: string): Boolean; //s字符串是否在str中
18     function DeleteOne(s, str: string):string;    //在串str中删除s，避免重复
19     function GetFirst(s: TStringList): TStringList;
20     procedure GetFirstAllProduction(sNoTerminate: string; sList: TStringList; var Res: TStringList);
21     function GetFirstOne(str: string; slt: TStringList): string;     //获得一个非终结符的First集
22 
23     function GetFollow(s: TStringList): TStringList;
24     procedure GetFollowAllProduction(sNoTerminate: string; sList: TStringList; var Res: TStringList);
25     function GetFollowOne(str: string; slt: TStringList): string;  //获得一个非终结符的Follow集
26     function CanToEmpty(str: string; slt: TStringList): Boolean;   //str是否能推导出ε
27 
28 
29     constructor Create(sInFer: string);
30     destructor Destroy; override;
31     property Infer: string read FInfer write FInfer;
32   end;
33 
34 const
35   arrTerminate: array[1..32] of string = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
36     'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ')', '(', '+', '-', '*', 'ε');
37   arrNoTerminate: array[1..26] of string = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K',
38     'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z');
39   SQLKey: array[1..28] of Tkey = (
40     (Content: 'SELECT'; Key: 'S01'),
41     (Content: 'WHEN'; Key: 'S02'),
42     (Content: 'DISTINCT'; Key: 'S03'),
43     (Content: 'FROM'; Key: 'S04'),
44     (Content: 'WHERE'; Key: 'S05'),
45     (Content: 'LEFT JOIN'; Key: 'S06'),
46     (Content: 'LEFT OUTER JOIN'; Key: 'S07'),
47     (Content: 'RIGHT JOIN'; Key: 'S08'),
48     (Content: 'RIGHT OUTER JOIN'; Key: 'S09'),
49     (Content: 'INNER JOIN'; Key: 'S10'),
50     (Content: 'FULL JOIN'; Key: 'S11'),
51     (Content: 'HAVING'; Key: 'S12'),
52     (Content: 'ASC'; Key: 'S13'),
53     (Content: 'DESC'; Key: 'S14'),
54     (Content: 'CASE'; Key: 'S15'),
55     (Content: 'END'; Key: 'S16'),
56     (Content: 'ELSE'; Key: 'S17'),
57     (Content: 'ON'; Key: 'S18'),
58     (Content: 'UNION'; Key: 'S19'),
59     (Content: 'UNION ALL'; Key: 'S20'),
60     (Content: 'AS'; Key: 'S21'),
61     (Content: 'ORDER BY'; Key: 'S22'),
62     (Content: 'GOURP BY'; Key: 'S23'),
63     (Content: 'IN'; Key: 'S24'),
64     (Content: 'OR'; Key: 'S25'),
65     (Content: 'AND'; Key: 'S26'),
66     (Content: 'THEN'; Key: 'S27'),
67     (Content: 'LIKE'; Key: 'S28')
68     );

实现部分

function TSCanner.CanToEmpty(str: string; slt: TStringList): Boolean;
var
  i, j: Integer;
  sTemp, s1, s2: string;
begin
  Result := False;
for i := 0 to slt.Count - 1 do
begin
    sTemp := Trim(slt[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 s2 = 'ε' then
begin
        Result := True;
        Break;
end
else if InNoTerminate(s1) then
begin
        Result := CanToEmpty(s1, slt);
end
else if InTerminate(s1) then
        Result :=False;
end;
end;
end;

constructor TSCanner.Create(sInFer: string);
begin
  MyToken := TToken.Create;
  FInfer := sInFer;
end;

function TSCanner.DeleteBlankLines(str: string; buf: PChar): Boolean;
var
  sTemp: string;
  i, j, iLen, kFlag: Integer;
  old_c, cur_c: Char;
  bComment: Boolean;
begin
  Result := False;
  bComment := False;

  sTemp := Pro_Process(str);
  iLen := Length(sTemp);
  j := 1;
  i := 0;
  kFlag := 0;
  cur_c := sTemp[j];
while j <= iLen do
begin
case bComment of
      false:
begin
if ((old_c = '/') and (cur_c = '*')) then
begin
            i := i - 1;
            bComment := True;
end
else if ((old_c = '/') and (cur_c = '/')) then
begin
            i := i - 1;
            kFlag := 1; //状态1为"//"注视状态
end
else
begin
if kFlag = 1 then
begin
              j := j + 1;
              old_c := cur_c;
              cur_c := str[j];
              Continue;
end
else if (kFlag = 2) then
begin
              kFlag := 0;
              buf[i] := ' ';
              buf[i + 1] := cur_c;
              i := i + 2;
end
else
begin
              buf[i] := cur_c;
              i := i + 1;
end;
end;
//ShowMessage(buf);
end;
      True:
begin
if (old_c = '*') and (cur_c = '/') then
            bComment := False
else if cur_c = #10 then
begin
if kFlag = 1 then
begin
              kFlag := 0;
              bComment := False;
end;
end;
end;
end;
    j := j + 1;
    old_c := cur_c;
    cur_c := sTemp[j];
end;
//i := i + 1;
  buf[i] := '#';
  Result := True;
end;

function TSCanner.DeleteOne(s, str: string): string;
var
  sliTemp: TStringList;
begin
  sliTemp := TStringList.Create;
  sliTemp.Delimiter := ',';
  sliTemp.CommaText := str;
if sliTemp.IndexOf(s) >= 0 then
begin
    sliTemp.Delete(sliTemp.IndexOf(s));
end;
  Result :=sliTemp.CommaText;
  sliTemp.Free;
end;

destructor TSCanner.destroy;
begin
inherited;
  MyToken.Free;
end;

procedure TSCanner.GetAllNoTerminate(sContent: TStringList; var Res: TStringList);
var
  iCou, Cou, i, j: Integer;
  sTemp: string;
begin
  Cou := sContent.Count;
  Res.Clear;
for iCou := 0 to Cou - 1 do
begin
    i := Pos(FInfer, sContent[iCou]);
if (i = 0) then Exit;

if i > 0 then
begin
      sTemp := Copy(Trim(sContent[icou]), 1, i - (Length(FInfer)) + 1);
if Res.IndexOf(sTemp) < 0 then
        Res.Add(sTemp);
end;
end;
end;

function TSCanner.GetAllToken(sWords: string): string;
var
  i, j: Integer;
  slTemp: TStringList;
  sTemp: string;
  bTemp: Boolean;
begin
  slTemp := TStringList.Create;
  sTemp := sWords;
  bTemp := False;
for j := Low(SQLKey) to High(SQLKEY) do
    sTemp := StringReplace(sTemp, SQLKey[j].Content, SQLKey[j].Key, [rfReplaceAll]);
  slTemp.CommaText := sTemp;
  sTemp := '';
for i := 0 to slTemp.Count - 1 do
begin
    bTemp := False;
for j := Low(SQLKey) to High(SQLKEY) do
begin
if SQLKey[j].Key = slTemp[i] then
begin
        bTemp := True;
        MyToken.Add(SQLKey[j].Key + '=' + SQLKey[j].Content);
        sTemp := sTemp + SQLKey[j].Key;
        Break;
end;
end;
if not bTemp then
      sTemp := sTemp + slTemp[i];
end;
  slTemp.Free;
  Result := sTemp;
end;

//获得FIRST集
function TSCanner.GetFirst(s: TStringList): TStringList;
var
  i, j, k: Integer;
  sTemp, FFirst: string;
  Data: PFirst;
  s1: PChar;
  sList, slTemp1: TStringList;
begin
  sList := TStringList.Create;
  FStart := 'E';
  Result := TStringList.Create;
try
    GetAllNoTerminate(s, sList);
for i := 0 to sList.Count - 1 do
begin
//获取所有sList[i]推导的产生式 如A->a或A->BCa
      FFirst := '';
      FFirst := GetFirstOne(sList[i], s);
if Trim(FFirst) <> '' then
        Delete(FFirst, Length(FFirst), 1);
      New(Data);
      Data^.Name := sList[i];
      Data^.Value := FFirst;
      Result.AddObject(Data^.Name, TObject(Data));
end;
finally
    sList.Free;
//slTemp1.Free;
end;
end;

//获得FOLLOW集
procedure TSCanner.GetFirstAllProduction(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;

function TSCanner.GetFirstOne(str: string; slt: TStringList): string;
var
  i, j: integer;
  s1, s2, sTemp,sFirst,sFollow: string;
  slTemp1: TStringList;
begin
  slTemp1 := TStringList.Create;
  Result := '';
  GetFirstAllProduction(str, slt, 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
          Result := Result + s1 + ',';
end
else if (s2 = 'ε') then
begin
if not OneInOther(s2, sTemp) then
          Result := Result + s2 + ','
end
else if InNoTerminate(s1) then
begin
        Result := GetFirstOne(s1, slt);         
end;
end;
end;
  slTemp1.Free;
end;

function TSCanner.GetFollow(s: TStringList): TStringList;
var
  i, j, k: Integer;
  sTemp, FFollow: string;
  Data: PFirst;
  s1: PChar;
  sList, slTemp1: TStringList;

begin
  sList := TStringList.Create;
  FStart := 'E';
  Result := TStringList.Create;
try
    GetAllNoTerminate(s, sList);
for i := 0 to sList.Count - 1 do
begin
//获取所有sList[i]推导的产生式 如A->a或A->BCa
      FFollow := '';
      FFollow := FFollow + GetFollowOne(sList[i], s);
if Trim(FFollow) <> '' then
        Delete(FFollow, Length(FFollow), 1);
      New(Data);
      Data^.Name := sList[i];
      Data^.Value := FFollow;
      Result.AddObject(Data^.Name, TObject(Data));
end;
finally
    sList.Free;
//slTemp1.Free;
end;
end;

procedure TSCanner.GetFollowAllProduction(sNoTerminate: string;
  sList: TStringList; var Res: TStringList);
var
  i, j: Integer;
  s1: string;
  s2, s3: string;
begin
for i := 0 to sList.Count - 1 do
begin
    j := Pos(FInfer, sList[i]);
if j > 0 then
begin
      s2 := Trim(MidStr(sList[i], j + 1, Length(sList[i]) - j));
      s3 := Trim(sNoTerminate);
if Pos(s3, s2) > 0 then
begin
        Res.Add(sList[i]);
end;
end;
end;
end;

function TSCanner.GetFollowOne(str: string; slt: TStringList): string;
var
  i, j, k,l: integer;
  s1, s2, s3, sTemp,sFirst,sFollow: string;
  slTemp1,slTemp2: TStringList;
begin
  slTemp1 := TStringList.Create;
  Result := '';
if str = FStart then
    Result := '#,';
  GetFollowAllProduction(str, slt, 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, 1, 1);
//s2 := Copy(sTemp, j + Length(FInfer), 2);
      k := Pos(str, sTemp);
if k > 0 then
begin
        s3 := Copy(sTemp, k + 1, Length(sTemp) - k);
if (InTerminate(s3)) then
begin
if not OneInOther(s3, Result) then
begin
            Result := Result + s3 + ',';
end;
end
else if s3 = '' then
begin
          Result := Result + GetFollowOne(s1, slt);
end
else if InNoTerminate(s3) then
begin
if not OneInOther(s3,Result) then
begin
            sFirst :=GetFirstOne(s3, slt);
            slTemp2 :=TStringList.Create;
            slTemp2.CommaText :=sFirst;
for l:=0 to slTemp2.Count -1 do
begin
if not OneInOther(slTemp2[l],Result) then
                Result := Result + slTemp2[l]+',';
end;
            slTemp2.Free;
end;
if Pos('ε',Result)>0 then
begin
            sFollow := GetFollowOne(s3, slt);
            slTemp2 :=TStringList.Create;
            slTemp2.CommaText :=sFollow;
for l:=0 to slTemp2.Count -1 do
begin
if not OneInOther(slTemp2[l],Result) then
                Result := Result + slTemp2[l]+',';
end;
            slTemp2.Free;
end;
end;
end;
end;
end;
if OneInOther('ε',Result) then
begin
    Result :=DeleteOne('ε',Result);
end;
  slTemp1.Free;
end;

function TSCanner.InNoTerminate(s: string): Boolean;
var
  i: integer;
begin
  Result := False;
for i := Low(arrNoTerminate) to High(arrNoTerminate) do
begin
if s = arrNoTerminate[i] then
begin
      Result := True;
      Break;
end;
end;
end;

function TSCanner.InTerminate(s: string): Boolean;
var
  i: Integer;
begin
  Result := False;
for i := Low(arrTerminate) to High(arrTerminate) do
begin
if s = arrTerminate[i] then
begin
      Result := True;
      Break;
end;
end;
end;

function TSCanner.OneInOther(s, str: string): Boolean;
var
  sliTemp: TStringList;
begin
  Result := False;
  sliTemp := TStringList.Create;
  sliTemp.Delimiter := ',';
  sliTemp.CommaText := str;
if sliTemp.IndexOf(s) >= 0 then
    Result := True;
  sliTemp.Free;
end;

实际的测试界面如下：

 

孤独的猫董
目录
相关文章
fanstuck
|
机器学习/深度学习 算法 数据挖掘
马尔科夫链（Markov Chain, MC）算法详解及Python实现
马尔科夫链（Markov Chain, MC）算法详解及Python实现
fanstuck
7976 1
马尔科夫链（Markov Chain, MC）算法详解及Python实现
俄罗斯刺沙蓬
|
7月前
|
vr&ar C++
B. Fake Plastic Trees(贪心+dp)
B. Fake Plastic Trees(贪心+dp)
俄罗斯刺沙蓬
37 0
算精通
|
机器学习/深度学习 自然语言处理 算法
逆向最大匹配(Backward Maximum Matching)
逆向最大匹配(Backward Maximum Matching)是一种分词算法。它的工作原理与正向最大匹配相反,即从字符串结尾开始查找。
算精通
273 1
算精通
|
机器学习/深度学习 自然语言处理 算法
正向最大匹配(Forward Maximum Matching)
正向最大匹配(Forward Maximum Matching)是一种查找文本字符串中词语的算法。
算精通
480 1
小磊数学建模
|
算法
2022小美赛B题The Genetic Process of Sequences序列的遗传过程思路分享
2022小美赛B题The Genetic Process of Sequences序列的遗传过程思路分享
小磊数学建模
2709 1
2022小美赛B题The Genetic Process of Sequences序列的遗传过程思路分享
皮卡丘敲级可爱
最优化学习 牛顿法（Newton’s method）
最优化学习 牛顿法（Newton’s method）
皮卡丘敲级可爱
127 0
最优化学习 牛顿法（Newton’s method）
pzf3zdekdh6es
|
Ubuntu Java Linux
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
pzf3zdekdh6es
2327 0
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
LightOf
AtCoder Beginner Contest 223 D - Restricted Permutation（建图 思维 构造 拓扑排序）
AtCoder Beginner Contest 223 D - Restricted Permutation（建图 思维 构造 拓扑排序）
LightOf
132 0
zzqwtc
|
人工智能 BI
Educational Codeforces Round 103 C - Longest Simple Cycle (思维 + 贪心)
笔记
zzqwtc
83 0
LightOf
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
AtCoder Beginner Contest 214 D.Sum of Maximum Weights (思维 并查集)
LightOf
120 0