Class: Lrama::States

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Report::Duration
Defined in:
lib/lrama/states.rb,
lib/lrama/states/item.rb

Overview

States is passed to a template file

“Efficient Computation of LALR(1) Look-Ahead Sets”

https://dl.acm.org/doi/pdf/10.1145/69622.357187

Defined Under Namespace

Classes: Item

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Report::Duration

enable, enabled?, #report_duration

Constructor Details

#initialize(grammar, trace_state: false) ⇒ States

Returns a new instance of States.



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/lrama/states.rb', line 21

def initialize(grammar, trace_state: false)
  @grammar = grammar
  @trace_state = trace_state

  @states = []

  # `DR(p, A) = {t ∈ T | p -(A)-> r -(t)-> }`
  #   where p is state, A is nterm, t is term.
  #
  # `@direct_read_sets` is a hash whose
  # key is [state.id, nterm.token_id],
  # value is bitmap of term.
  @direct_read_sets = {}

  # Reads relation on nonterminal transitions (pair of state and nterm)
  # `(p, A) reads (r, C) iff p -(A)-> r -(C)-> and C =>* ε`
  #   where p, r are state, A, C are nterm.
  #
  # `@reads_relation` is a hash whose
  # key is [state.id, nterm.token_id],
  # value is array of [state.id, nterm.token_id].
  @reads_relation = {}

  # `Read(p, A) =s DR(p, A) ∪ ∪{Read(r, C) | (p, A) reads (r, C)}`
  #
  # `@read_sets` is a hash whose
  # key is [state.id, nterm.token_id],
  # value is bitmap of term.
  @read_sets = {}

  # `(p, A) includes (p', B) iff B -> βAγ, γ =>* ε, p' -(β)-> p`
  #   where p, p' are state, A, B are nterm, β, γ is sequence of symbol.
  #
  # `@includes_relation` is a hash whose
  # key is [state.id, nterm.token_id],
  # value is array of [state.id, nterm.token_id].
  @includes_relation = {}

  # `(q, A -> ω) lookback (p, A) iff p -(ω)-> q`
  #   where p, q are state, A -> ω is rule, A is nterm, ω is sequence of symbol.
  #
  # `@lookback_relation` is a hash whose
  # key is [state.id, rule.id],
  # value is array of [state.id, nterm.token_id].
  @lookback_relation = {}

  # `Follow(p, A) =s Read(p, A) ∪ ∪{Follow(p', B) | (p, A) includes (p', B)}`
  #
  # `@follow_sets` is a hash whose
  # key is [state.id, rule.id],
  # value is bitmap of term.
  @follow_sets = {}

  # `LA(q, A -> ω) = ∪{Follow(p, A) | (q, A -> ω) lookback (p, A)`
  #
  # `@la` is a hash whose
  # key is [state.id, rule.id],
  # value is bitmap of term.
  @la = {}
end

Instance Attribute Details

#includes_relation ⇒ Object (readonly)

Returns the value of attribute includes_relation.



19
20
21
 
# File 'lib/lrama/states.rb', line 19

def includes_relation
  @includes_relation
end

#lookback_relation ⇒ Object (readonly)

Returns the value of attribute lookback_relation.



19
20
21
 
# File 'lib/lrama/states.rb', line 19

def lookback_relation
  @lookback_relation
end

#reads_relation ⇒ Object (readonly)

Returns the value of attribute reads_relation.



19
20
21
 
# File 'lib/lrama/states.rb', line 19

def reads_relation
  @reads_relation
end

#states ⇒ Object (readonly)

Returns the value of attribute states.



19
20
21
 
# File 'lib/lrama/states.rb', line 19

def states
  @states
end

Instance Method Details

#compute ⇒ Object 



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/lrama/states.rb', line 82

def compute
  # Look Ahead Sets
  report_duration(:compute_lr0_states) { compute_lr0_states }
  report_duration(:compute_direct_read_sets) { compute_direct_read_sets }
  report_duration(:compute_reads_relation) { compute_reads_relation }
  report_duration(:compute_read_sets) { compute_read_sets }
  report_duration(:compute_includes_relation) { compute_includes_relation }
  report_duration(:compute_lookback_relation) { compute_lookback_relation }
  report_duration(:compute_follow_sets) { compute_follow_sets }
  report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }

  # Conflicts
  report_duration(:compute_conflicts) { compute_conflicts }

  report_duration(:compute_default_reduction) { compute_default_reduction }
end

#compute_ielr ⇒ Object 



99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/lrama/states.rb', line 99

def compute_ielr
  report_duration(:split_states) { split_states }
  report_duration(:compute_direct_read_sets) { compute_direct_read_sets }
  report_duration(:compute_reads_relation) { compute_reads_relation }
  report_duration(:compute_read_sets) { compute_read_sets }
  report_duration(:compute_includes_relation) { compute_includes_relation }
  report_duration(:compute_lookback_relation) { compute_lookback_relation }
  report_duration(:compute_follow_sets) { compute_follow_sets }
  report_duration(:compute_look_ahead_sets) { compute_look_ahead_sets }
  report_duration(:compute_conflicts) { compute_conflicts }

  report_duration(:compute_default_reduction) { compute_default_reduction }
end

#direct_read_sets ⇒ Object 



121
122
123
124
125
 
# File 'lib/lrama/states.rb', line 121

def direct_read_sets
  @direct_read_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#follow_sets ⇒ Object 



133
134
135
136
137
 
# File 'lib/lrama/states.rb', line 133

def follow_sets
  @follow_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#la ⇒ Object 



139
140
141
142
143
 
# File 'lib/lrama/states.rb', line 139

def la
  @la.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#read_sets ⇒ Object 



127
128
129
130
131
 
# File 'lib/lrama/states.rb', line 127

def read_sets
  @read_sets.transform_values do |v|
    bitmap_to_terms(v)
  end
end

#reporter ⇒ Object 



113
114
115
 
# File 'lib/lrama/states.rb', line 113

def reporter
  StatesReporter.new(self)
end

#rr_conflicts_count ⇒ Object 



149
150
151
 
# File 'lib/lrama/states.rb', line 149

def rr_conflicts_count
  @rr_conflicts_count ||= @states.flat_map(&:rr_conflicts).count
end

#sr_conflicts_count ⇒ Object 



145
146
147
 
# File 'lib/lrama/states.rb', line 145

def sr_conflicts_count
  @sr_conflicts_count ||= @states.flat_map(&:sr_conflicts).count
end

#states_count ⇒ Object 



117
118
119
 
# File 'lib/lrama/states.rb', line 117

def states_count
  @states.count
end