← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/AddIns/Misc/Reports/Irony/CompilerServices/LALR/ParserControlData.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/AddIns/Misc/Reports/Irony/CompilerServices/LALR/ParserControlData.cs
 
1
#region License
 
2
/* **********************************************************************************
 
3
 * Copyright (c) Roman Ivantsov
 
4
 * This source code is subject to terms and conditions of the MIT License
 
5
 * for Irony. A copy of the license can be found in the License.txt file
 
6
 * at the root of this distribution. 
 
7
 * By using this source code in any fashion, you are agreeing to be bound by the terms of the 
 
8
 * MIT License.
 
9
 * You must not remove this notice from this software.
 
10
 * **********************************************************************************/
 
11
#endregion
 
12
 
 
13
using System;
 
14
using System.Collections.Generic;
 
15
using System.Text;
 
16
 
 
17
 
 
18
namespace Irony.Compiler.Lalr {
 
19
  // ParserControlData is a container for all information used by LALR Parser in input processing.
 
20
  // The state graph entry is InitialState state; the state graph encodes information usually contained 
 
21
  // in what is known in literature as transiton/goto tables.
 
22
  // The graph is built from the language grammar by ParserControlDataBuilder instance. 
 
23
  // See Dragon book or other book on compilers on details of LALR parsing and parsing tables construction. 
 
24
 
 
25
  public class ParserControlData {
 
26
    public Grammar Grammar;
 
27
    public NonTerminal AugmentedRoot;
 
28
    public ParserState InitialState;
 
29
    public ParserState FinalState;
 
30
    public readonly ParserStateList States = new ParserStateList();
 
31
    
 
32
    public bool AnalysisCanceled;  //True if grammar analysis was canceled due to errors
 
33
 
 
34
    public ParserControlData(Grammar grammar) {
 
35
      Grammar = grammar;
 
36
    }
 
37
  }
 
38
 
 
39
 
 
40
  public enum ParserActionType {
 
41
    Shift,
 
42
    Reduce,
 
43
    Operator,  //shift or reduce depending on operator associativity and precedence
 
44
  }
 
45
 
 
46
  public partial class ParserState {
 
47
    public readonly string Name;
 
48
    public readonly ActionRecordTable Actions = new ActionRecordTable();
 
49
    public readonly LRItemList Items = new LRItemList();
 
50
 
 
51
    public ParserState(string name, LRItem item) {
 
52
      Name = name;
 
53
      Items.Add(item);
 
54
    }
 
55
    public ParserState(string name, LR0ItemList coreItems) {
 
56
      Name = name;
 
57
      foreach (LR0Item coreItem in coreItems)
 
58
        Items.Add(new LRItem(this, coreItem));
 
59
    }
 
60
    public override string ToString() {
 
61
      return Name;
 
62
    }
 
63
  }//class
 
64
 
 
65
  public class ParserStateList : List<ParserState> { }
 
66
  public class ParserStateTable : Dictionary<string, ParserState> { } //hash table
 
67
 
 
68
  public class ActionRecord {
 
69
    public string Key;
 
70
    public ParserActionType ActionType = ParserActionType.Shift;
 
71
    public ParserState NewState;
 
72
    public readonly ProductionList ReduceProductions = new ProductionList(); //may be more than one, in case of conflict
 
73
    public readonly LRItemList ShiftItems = new LRItemList();
 
74
    public bool ConflictResolved; 
 
75
 
 
76
    internal ActionRecord(string key, ParserActionType type, ParserState newState, Production reduceProduction) {
 
77
      this.Key = key;
 
78
      this.ActionType = type;
 
79
      this.NewState = newState; 
 
80
      if (reduceProduction != null)
 
81
        ReduceProductions.Add(reduceProduction);
 
82
    }
 
83
    public ActionRecord CreateDerived(ParserActionType type, Production reduceProduction) {
 
84
      return new ActionRecord(this.Key, type, this.NewState, reduceProduction);
 
85
    }
 
86
 
 
87
    public Production Production { 
 
88
      get {return ReduceProductions.Count > 0? ReduceProductions[0] : null;}
 
89
    }
 
90
    public NonTerminal NonTerminal {
 
91
      get { return Production == null? null: Production.LValue; }
 
92
    }
 
93
    public int PopCount {
 
94
      get { return Production.RValues.Count;}
 
95
    }
 
96
    public bool HasConflict() {
 
97
      // This function is used by parser to determine if it needs to call OnActionConflict method in Grammar.
 
98
      // Even if conflict is resolved, we still need to return true to force parser to invoke method.
 
99
      // This is necessary to make parser work properly in situation like this: in c#, the "<" symbol is 
 
100
      // both operator symbol and opening brace for type parameter. When used purely as operator symbol, 
 
101
      //  it is involved in shift/reduced conflict resolved by operator precedence. Still, before parser starts 
 
102
      // acting based on precedence, a custom grammar method should decide - is it really an operator or type parameter
 
103
      // bracket.
 
104
      //if (ConflictResolved) return false; -- this should be commented out
 
105
      return ShiftItems.Count > 0 && ReduceProductions.Count > 0 ||
 
106
        ReduceProductions.Count > 1; 
 
107
    }
 
108
    public override string ToString() {
 
109
      string result = ActionType.ToString();
 
110
      if (ActionType == ParserActionType.Reduce && ReduceProductions.Count > 0)
 
111
        result += " on " + ReduceProductions[0];
 
112
      return result;
 
113
    }
 
114
 
 
115
  }//class ActionRecord
 
116
 
 
117
  public class ActionRecordTable : Dictionary<string, ActionRecord> { }
 
118
 
 
119
  public class LRItem {
 
120
    public readonly ParserState State;
 
121
    public readonly LR0Item Core;
 
122
    public readonly LRItemList PropagateTargets = new LRItemList(); //used for lookaheads propagation
 
123
    public readonly StringSet Lookaheads = new StringSet();
 
124
    public readonly StringSet NewLookaheads = new StringSet();
 
125
    public LRItem(ParserState state, LR0Item core) {
 
126
      State = state;
 
127
      Core = core;
 
128
    }
 
129
    public override string ToString() {
 
130
      return Core.ToString() + "  LOOKAHEADS: " + TextUtils.Cleanup(Lookaheads.ToString(" "));
 
131
    }
 
132
  }//LRItem class
 
133
 
 
134
  public class LRItemList : List<LRItem> { }
 
135
 
 
136
 
 
137
}//namespace