Changeset 3


Ignore:
Timestamp:
Oct 4, 2007, 1:58:38 PM (17 years ago)
Author:
george
Message:

Upraveno: Lexikální a syntaktická analýza.

Files:
5 edited

Legend:

Unmodified
Added
Removed
  • P0.grm

    r2 r3  
    1 p= b | '' | 'b' .
     1p=bcd | '' | 'b' .
  • PascalCompiler.dpr

    r1 r3  
    11program PascalCompiler;
     2
     3{%File 'P0.grm'}
    24
    35uses
  • Program.pas

    r2 r3  
    1 p= b | '' | 'b' .
     1p=bcd | '' | 'b' .
  • UMainForm.dfm

    r2 r3  
    1313  OldCreateOrder = False
    1414  Position = poDesigned
     15  WindowState = wsMaximized
    1516  OnCreate = FormCreate
    1617  OnDestroy = FormDestroy
     
    4445    Indent = 19
    4546    TabOrder = 2
    46     ExplicitWidth = 313
    47     ExplicitHeight = 441
    4847  end
    4948  object TreeView2: TTreeView
  • UMainForm.pas

    r2 r3  
    1111
    1212  TPathItem = record
     13  public
    1314    Rule: TGrammerRule;
    1415    ItemIndex: Integer;
     16    Affected: Boolean;
    1517    CharIndex: Integer;
    1618    procedure Assign(Source: TPathItem);
     
    3840
    3941  TProgramItem = class
    40   private
    4142  public
    4243    RuleBefore: TGrammerRule;
     
    5859
    5960  TGrammerItem = record
     61  private
     62    Parent: TGrammerRule;
     63    Processed: Boolean;
    6064  public
    6165    ItemType: TRuleItemType;
     
    7074  TGrammerRule = class
    7175  private
    72     Index: Integer;
    7376  public
    7477    Name: string;
    7578    RuleType: TRuleType;
    7679    Items: array of TGrammerItem;
     80    procedure ClearProcessed;
    7781    procedure AddTerminal(Character: Char; Optional, Repetition: Boolean);
    7882    procedure AddTerminalText(Text: string);
     
    8084    procedure ProcessCharacter(Character: Char);
    8185    procedure GetPossibleCharacters(Path: TGrammerPath;
    82       var Characters: TPossibleCharacters; UseIndex: Integer = 0; UseCharIndex: Integer = 0);
     86      var Characters: TPossibleCharacters; UseIndex: Integer = 0; UseCharIndex: Integer = -1);
    8387    constructor Create;
    8488  end;
     
    8993    TopRule: TGrammerRule;
    9094    constructor Create;
     95    procedure ClearProcessed;
    9196    procedure Parse(Text: string; var ParsedProgram: TProgram);
    9297    destructor Destroy; override;
     
    120125procedure TMainForm.Button1Click(Sender: TObject);
    121126begin
     127  SourceProgram.Free;
     128  SourceProgram := TProgram.Create;
    122129  Grammer.Parse(Memo1.Text, SourceProgram);
     130  ShowProgramTree(SourceProgram);
    123131end;
    124132
     
    128136  Digit, AlphabeticCharacter, Number, AlphaNumericCharacter,
    129137    Identifier, Assignment, Expression, RuleString, Rule, RuleList,
    130     AlternateOptions, OptionBlock, RepetitionBlock, GroupingBlock,
    131     AlternateOptionsSubBlock, Term, AllCharacters, WhiteSpace: TGrammerRule;
     138    OptionBlock, RepetitionBlock, GroupingBlock,
     139    Term, AllCharacters, WhiteSpace, Concatenation, ConcatenationBlock,
     140    Separation, SeparationBlock: TGrammerRule;
    132141  C: Char;
    133142  I: Integer;
     
    225234    Rules.Add(RuleString);
    226235
    227     AlternateOptions := TGrammerRule.Create;
    228     Expression := TGrammerRule.Create;
    229 
    230     AlternateOptionsSubBlock := TGrammerRule.Create;
    231     with AlternateOptionsSubBlock do begin
    232       Name := 'AlternateOptionsSubBlock';
    233       RuleType := rtSequence;
    234       AddRule(WhiteSpace, True, True);
    235       AddTerminal('|', False, False);
    236       AddRule(WhiteSpace, True, True);
    237       AddRule(AlternateOptions, True, True);
    238     end;
    239     Rules.Add(AlternateOptionsSubBlock);
     236    Concatenation := TGrammerRule.Create;
    240237
    241238    OptionBlock := TGrammerRule.Create;
     
    245242      AddTerminal('[', False, False);
    246243      AddRule(WhiteSpace, True, True);
    247       AddRule(Expression, False, False);
     244      AddRule(Concatenation, False, False);
    248245      AddRule(WhiteSpace, True, True);
    249246      AddTerminal(']', False, False);
     
    257254      AddTerminal('{', False, False);
    258255      AddRule(WhiteSpace, True, True);
    259       AddRule(Expression, False, False);
     256      AddRule(Concatenation, False, False);
    260257      AddRule(WhiteSpace, True, True);
    261258      AddTerminal('}', False, False);
     
    269266      AddTerminal('(', False, False);
    270267      AddRule(WhiteSpace, True, True);
    271       AddRule(Expression, False, False);
     268      AddRule(Concatenation, False, False);
    272269      AddRule(WhiteSpace, True, True);
    273270      AddTerminal(')', False, False);
     
    284281    Rules.Add(Term);
    285282
    286     with AlternateOptions do begin
    287       Name := 'AlternateOptions';
    288       RuleType := rtSequence;
    289       AddRule(Term, False, False);
    290       AddRule(AlternateOptionsSubBlock, True, True);
    291     end;
    292     Rules.Add(AlternateOptions);
    293 
     283    Expression := TGrammerRule.Create;
    294284    with Expression do begin
    295285      Name := 'Expression';
     
    298288      AddRule(OptionBlock, False, False);
    299289      AddRule(GroupingBlock, False, False);
    300       AddRule(AlternateOptions, False, False);
     290      AddRule(Term, False, False);
    301291    end;
    302292    Rules.Add(Expression);
     293
     294    ConcatenationBlock := TGrammerRule.Create;
     295    with ConcatenationBlock do begin
     296      Name := 'ConcatenationBlock';
     297      RuleType := rtSequence;
     298      AddRule(WhiteSpace, False, True);
     299      AddRule(Expression, False, False);
     300    end;
     301    Rules.Add(ConcatenationBlock);
     302
     303    with Concatenation do begin
     304      Name := 'Concatenation';
     305      RuleType := rtSequence;
     306      AddRule(Expression, False, False);
     307      AddRule(ConcatenationBlock, True, True);
     308    end;
     309    Rules.Add(Concatenation);
     310
     311    SeparationBlock := TGrammerRule.Create;
     312    with SeparationBlock do begin
     313      Name := 'SeparationBlock';
     314      RuleType := rtSequence;
     315      AddRule(WhiteSpace, True, True);
     316      AddTerminal('|', False, False);
     317      AddRule(WhiteSpace, True, True);
     318      AddRule(Concatenation, False, False);
     319    end;
     320    Rules.Add(SeparationBlock);
     321
     322    Separation := TGrammerRule.Create;
     323    with Separation do begin
     324      Name := 'Separation';
     325      RuleType := rtSequence;
     326      AddRule(Concatenation, False, False);
     327      AddRule(SeparationBlock, True, True);
     328    end;
     329    Rules.Add(Separation);
    303330
    304331    Rule := TGrammerRule.Create;
     
    311338      AddTerminal('=', False, False);
    312339      AddRule(WhiteSpace, True, True);
    313       AddRule(Expression, False, True);
     340      AddRule(Separation, False, False);
    314341      AddRule(WhiteSpace, True, True);
    315342      AddTerminal('.', False, False);
     
    353380  Items[High(Items)].Optional := Optional;
    354381  Items[High(Items)].Repetition := Repetition;
     382  Items[High(Items)].Parent := Self;
    355383end;
    356384
     
    362390  Items[High(Items)].Optional := Optional;
    363391  Items[High(Items)].Repetition := Repetition;
     392  Items[High(Items)].Parent := Self;
    364393end;
    365394
     
    371400end;
    372401
     402procedure TGrammerRule.ClearProcessed;
     403var
     404  I: Integer;
     405begin
     406  for I := 0 to High(Items) do with Items[I] do begin
     407    Processed := False;
     408  end;
     409end;
     410
    373411constructor TGrammerRule.Create;
    374412begin
     
    377415
    378416procedure TGrammerRule.GetPossibleCharacters(Path: TGrammerPath;
    379   var Characters: TPossibleCharacters; UseIndex: Integer = 0; UseCharIndex: Integer = 0);
    380 var
    381   I: Integer;
    382 begin
    383   Index := UseIndex;
     417  var Characters: TPossibleCharacters; UseIndex: Integer = 0; UseCharIndex: Integer = -1);
     418var
     419  I: Integer;
     420  NextItemIndex, NextCharIndex: Integer;
     421  NextRule: TGrammerRule;
     422  TempPath: TGrammerPath;
     423begin
    384424  SetLength(Path.Items, Length(Path.Items) + 1);
    385   Path.Items[High(Path.Items)].Rule := Self;
    386   Path.Items[High(Path.Items)].ItemIndex := UseIndex;
    387   Path.Items[High(Path.Items)].CharIndex := UseCharIndex;
     425  with Path.Items[High(Path.Items)] do begin
     426    Rule := Self;
     427    ItemIndex := UseIndex;
     428    CharIndex := UseCharIndex;
     429    Affected := True;
     430  end;
     431
    388432  case RuleType of
    389433    rtAlternative: begin
    390       for I := 0 to High(Items) do begin
    391         Path.Items[High(Path.Items)].ItemIndex := I;
    392         //Inc(Path.Items[High(Path.Items)].CharIndex);
    393         Items[I].GetPossibleCharacters(Path, Characters);
     434      if UseIndex > 0 then begin
     435        // Forward generation to upper item
     436        SetLength(Path.Items, Length(Path.Items) - 1);
     437        with Path.Items[High(Path.Items)] do begin
     438          NextItemIndex := ItemIndex;
     439          NextCharIndex := CharIndex;
     440          NextRule := Rule;
     441        end;
     442        SetLength(Path.Items, Length(Path.Items) - 1);
     443        NextRule.GetPossibleCharacters(Path, Characters, NextItemIndex + 1, NextCharIndex);
     444      end else begin
     445        // Generate alternatives
     446        for I := 0 to High(Items) do begin
     447          Path.Items[High(Path.Items)].ItemIndex := I;
     448          //Inc(Path.Items[High(Path.Items)].CharIndex);
     449          Items[I].GetPossibleCharacters(Path, Characters);
     450        end;
    394451      end;
    395452    end;
    396453    rtSequence: begin
    397       Path.Items[High(Path.Items)].ItemIndex := Index;
    398       //Inc(Path.Items[High(Path.Items)].CharIndex);
    399       Items[Index].GetPossibleCharacters(Path, Characters);
     454      TempPath.Assign(Path);
     455      if UseIndex >= Length(Items) then begin
     456        // Forward generation to upper item
     457        SetLength(Path.Items, Length(Path.Items) - 1);
     458        with Path.Items[High(Path.Items)] do begin
     459          NextItemIndex := ItemIndex;
     460          NextCharIndex := CharIndex;
     461          NextRule := Rule;
     462        end;
     463        SetLength(Path.Items, Length(Path.Items) - 1);
     464        NextRule.GetPossibleCharacters(Path, Characters, NextItemIndex + 1, NextCharIndex);
     465      end else begin
     466        Path.Items[High(Path.Items)].ItemIndex := UseIndex;
     467        Items[UseIndex].GetPossibleCharacters(Path, Characters);
     468      end;
     469      // Check repetition
     470      if (UseIndex > 0) and not Items[UseIndex - 1].Processed then
     471        if Items[UseIndex - 1].Repetition then begin
     472          TempPath.Items[High(TempPath.Items)].ItemIndex := UseIndex - 1;
     473          Items[UseIndex - 1].GetPossibleCharacters(TempPath, Characters);
     474        end;
    400475    end;
    401476  end;
     
    480555{ TGrammer }
    481556
     557procedure TGrammer.ClearProcessed;
     558var
     559  I: Integer;
     560begin
     561  for I := 0 to Rules.Count - 1 do with TGrammerRule(Rules[I]) do begin
     562    ClearProcessed;
     563  end;
     564end;
     565
    482566constructor TGrammer.Create;
    483567begin
     
    509593    Rule := TopRule;
    510594    ItemIndex := 0;
    511     CharIndex := 0;
     595    CharIndex := -1;
    512596  end;
    513597
     
    519603      SetLength(Path.Items, Length(Path.Items) - 1);
    520604      SetLength(Scope.Items, 0);
     605      ClearProcessed;
    521606      UseRule.GetPossibleCharacters(Path, Scope, UseIndex, UseCharIndex);
    522607      C := 0;
     
    524609        (Scope.Items[C].Character <> Text[I]) do Inc(C);
    525610      if C < Length(Scope.Items) then begin
    526         ParsedProgram.Insert(Scope.Items[C].RulePath, Scope.Items[C].Character);
     611        Path.Assign(Scope.Items[C].RulePath);
     612        for II := 0 to Length(Path.Items) - 1 do with Path.Items[II] do begin
     613          if Affected then Inc(CharIndex);
     614        end;
     615        ParsedProgram.Insert(Path, Scope.Items[C].Character);
     616        for II := 0 to Length(Path.Items) - 1 do with Path.Items[II] do begin
     617          Affected := False;
     618        end;
     619        //Path.Next;
    527620      end else begin
    528621        ExpectedCharacters := '';
    529622        for II := 0 to Length(Scope.Items) - 1 do
    530623          ExpectedCharacters := ExpectedCharacters + Scope.Items[II].Character;
     624        //raise Exception.Create('Parse error. Expected "' + ExpectedCharacters + '" but found "' + Text[I] + '".');
    531625        break;
    532         //raise Exception.Create('Parse error. Expected "' + ExpectedCharacters +
    533           //'" but found "' + Text[I] + '".');
    534626      end;
    535       Path.Assign(Scope.Items[C].RulePath);
    536       Path.Next;
    537627    end;
    538628  end;
     
    612702  Found: Boolean;
    613703  PathIndex: Integer;
    614   Index: Integer;
    615 begin
     704  NextItemIndex, NextCharIndex: Integer;
     705  NextRule: TGrammerRule;
     706begin
     707  Processed := True;
    616708  case ItemType of
    617709    itTerminal: begin
     
    619711      Characters.Items[High(Characters.Items)].Character := Character;
    620712      Characters.Items[High(Characters.Items)].RulePath.Assign(Path);
     713      with Characters.Items[High(Characters.Items)].RulePath do begin
     714        Inc(Items[High(Items)].ItemIndex);
     715      end;
    621716    end;
    622717    itNonterminal: begin
     
    625720  end;
    626721  if Optional then begin
    627     PathIndex := High(Path.Items);
    628     Found := False;
    629     while not Found and (PathIndex >= 0) do begin
    630       with Path.Items[PathIndex] do begin
    631         //if High(Path.Items) = PathIndex then
    632         Index := ItemIndex + 1;
    633         // else Index := ItemIndex;
    634 
    635         if Index < Length(Rule.Items) then begin
    636           SetLength(Path.Items, PathIndex + 1);
    637           Inc(Path.Items[PathIndex].ItemIndex);
    638           //Inc(Path.Items[PathIndex].CharIndex);
    639           Rule.Items[Index].GetPossibleCharacters(Path, Characters);
    640           Found := True;
    641         end else Dec(PathIndex);
    642       end;
    643     end;
     722        // Forward generation to upper item
     723        //SetLength(Path.Items, Length(Path.Items) - 1);
     724        with Path.Items[High(Path.Items)] do begin
     725          NextItemIndex := ItemIndex;
     726          NextCharIndex := CharIndex;
     727          NextRule := Rule;
     728        end;
     729        SetLength(Path.Items, Length(Path.Items) - 1);
     730        NextRule.GetPossibleCharacters(Path, Characters, NextItemIndex + 1, NextCharIndex);
    644731  end;
    645732end;
     
    665752    with Items[Index] do if Rule.Items[ItemIndex].Repetition then begin
    666753      Success := True;
    667       Inc(CharIndex);
     754      //Inc(CharIndex);
    668755    end else begin
    669756      if ((ItemIndex + 1) < Length(Rule.Items)) and (Rule.RuleType = rtSequence) then begin
    670757        Inc(ItemIndex);
    671         Inc(CharIndex);
     758        //Inc(CharIndex);
    672759        Success := True;
    673760      end else Dec(Index);
     
    684771  ItemIndex := Source.ItemIndex;
    685772  CharIndex := Source.CharIndex;
     773  Affected := Source.Affected;
    686774end;
    687775
Note: See TracChangeset for help on using the changeset viewer.