1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
|
require "lrama/report"
module Lrama
# Parser for parse.y, generates a grammar
class Parser
include Lrama::Report::Duration
T = Lrama::Lexer::Token
class TokenScanner
def initialize(tokens)
@tokens = tokens
@index = 0
end
def current_token
@tokens[@index]
end
def current_type
current_token && current_token.type
end
def next
token = current_token
@index += 1
return token
end
def consume(*token_types)
if token_types.include?(current_type)
token = current_token
self.next
return token
end
return nil
end
def consume!(*token_types)
consume(*token_types) || (raise "#{token_types} is expected but #{current_type}. #{current_token}")
end
def consume_multi(*token_types)
a = []
while token_types.include?(current_type)
a << current_token
self.next
end
raise "No token is consumed. #{token_types}" if a.empty?
return a
end
def eots?
current_token.nil?
end
end
def initialize(text)
@text = text
end
def parse
report_duration(:parse) do
lexer = Lexer.new(@text)
grammar = Grammar.new
process_prologue(grammar, lexer)
parse_bison_declarations(TokenScanner.new(lexer.bison_declarations_tokens), grammar)
parse_grammar_rules(TokenScanner.new(lexer.grammar_rules_tokens), grammar)
process_epilogue(grammar, lexer)
grammar.prepare
grammar.compute_nullable
grammar.validate!
grammar
end
end
private
def process_prologue(grammar, lexer)
grammar.prologue_first_lineno = lexer.prologue.first[1] if lexer.prologue.first
grammar.prologue = lexer.prologue.map(&:first).join
end
def process_epilogue(grammar, lexer)
grammar.epilogue_first_lineno = lexer.epilogue.first[1] if lexer.epilogue.first
grammar.epilogue = lexer.epilogue.map(&:first).join
end
def parse_bison_declarations(ts, grammar)
precedence_number = 0
while !ts.eots? do
case ts.current_type
when T::P_expect
ts.next
grammar.expect = ts.consume!(T::Number).s_value
when T::P_define
ts.next
# Ignore
ts.consume_multi(T::Ident)
when T::P_printer
lineno = ts.current_token.line
ts.next
code = ts.consume!(T::User_code)
code = grammar.build_code(:printer, code)
ident_or_tags = ts.consume_multi(T::Ident, T::Tag)
grammar.add_printer(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
when T::P_lex_param
ts.next
code = ts.consume!(T::User_code)
code = grammar.build_code(:lex_param, code)
grammar.lex_param = code.token_code.s_value
when T::P_parse_param
ts.next
code = ts.consume!(T::User_code)
code = grammar.build_code(:parse_param, code)
grammar.parse_param = code.token_code.s_value
when T::P_initial_action
ts.next
code = ts.consume!(T::User_code)
code = grammar.build_code(:initial_action, code)
ts.consume(T::Semicolon)
grammar.initial_action = code
when T::P_union
lineno = ts.current_token.line
ts.next
code = ts.consume!(T::User_code)
code = grammar.build_code(:union, code)
ts.consume(T::Semicolon)
grammar.set_union(code, lineno)
when T::P_token
# %token tag? (ident number? string?)+
#
# * ident can be char, e.g. '\\', '\t', '\13'
# * number is a token_id for term
#
# These are valid token declaration (from CRuby parse.y)
#
# %token END_OF_INPUT 0 "end-of-input"
# %token <id> '\\' "backslash"
# %token tSP "escaped space"
# %token tUPLUS 132 "unary+"
# %token tCOLON3 ":: at EXPR_BEG"
# %token tSTRING_DBEG tSTRING_DVAR tLAMBEG tLABEL_END
#
#
# See: https://www.gnu.org/software/bison/manual/html_node/Symbol-Decls.html
ts.next
opt_tag = ts.consume(T::Tag)
while (id = ts.consume(T::Ident, T::Char)) do
opt_number = ts.consume(T::Number)
opt_string = ts.consume(T::String)
# Can replace 0 (EOF)
grammar.add_term(
id: id,
alias_name: opt_string && opt_string.s_value,
token_id: opt_number && opt_number.s_value,
tag: opt_tag,
replace: true,
)
end
when T::P_type
# %type tag? (ident|char|string)+
#
# See: https://www.gnu.org/software/bison/manual/html_node/Symbol-Decls.html
ts.next
opt_tag = ts.consume(T::Tag)
while (id = ts.consume(T::Ident, T::Char, T::String)) do
grammar.add_type(
id: id,
tag: opt_tag
)
end
when T::P_nonassoc
# %nonassoc (ident|char|string)+
ts.next
while (id = ts.consume(T::Ident, T::Char, T::String)) do
sym = grammar.add_term(id: id)
grammar.add_nonassoc(sym, precedence_number)
end
precedence_number += 1
when T::P_left
# %left (ident|char|string)+
ts.next
while (id = ts.consume(T::Ident, T::Char, T::String)) do
sym = grammar.add_term(id: id)
grammar.add_left(sym, precedence_number)
end
precedence_number += 1
when T::P_right
# %right (ident|char|string)+
ts.next
while (id = ts.consume(T::Ident, T::Char, T::String)) do
sym = grammar.add_term(id: id)
grammar.add_right(sym, precedence_number)
end
precedence_number += 1
when nil
# end of input
raise "Reach to end of input within declarations"
else
raise "Unexpected token: #{ts.current_token}"
end
end
end
def parse_grammar_rules(ts, grammar)
while !ts.eots? do
parse_grammar_rule(ts, grammar)
end
end
# TODO: Take care of %prec of rule.
# If %prec exists, user code before %prec
# is NOT an action. For example "{ code 3 }" is NOT an action.
#
# keyword_class { code 2 } tSTRING '!' keyword_end { code 3 } %prec "="
def parse_grammar_rule(ts, grammar)
# LHS
lhs = ts.consume!(T::Ident_Colon) # class:
lhs.type = T::Ident
rhs = parse_grammar_rule_rhs(ts, grammar)
grammar.add_rule(lhs: lhs, rhs: rhs, lineno: rhs.first ? rhs.first.line : lhs.line)
while true do
case ts.current_type
when T::Bar
# |
bar_lineno = ts.current_token.line
ts.next
rhs = parse_grammar_rule_rhs(ts, grammar)
grammar.add_rule(lhs: lhs, rhs: rhs, lineno: rhs.first ? rhs.first.line : bar_lineno)
when T::Semicolon
# ;
ts.next
break
when T::Ident_Colon
# Next lhs can be here because ";" is optional.
# Do not consume next token.
break
when nil
# end of input can be here when ";" is omitted
break
else
raise "Unexpected token: #{ts.current_token}"
end
end
end
def parse_grammar_rule_rhs(ts, grammar)
a = []
prec_seen = false
code_after_prec = false
while true do
# TODO: Srting can be here
case ts.current_type
when T::Ident
# keyword_class
raise "Ident after %prec" if prec_seen
a << ts.current_token
ts.next
when T::Char
# '!'
raise "Char after %prec" if prec_seen
a << ts.current_token
ts.next
when T::P_prec
# %prec tPLUS
#
# See: https://www.gnu.org/software/bison/manual/html_node/Contextual-Precedence.html
ts.next
prec_seen = true
precedence_id = ts.consume!(T::Ident, T::String, T::Char)
precedence_sym = grammar.find_symbol_by_id!(precedence_id)
a << precedence_sym
when T::User_code
# { code } in the middle of rhs
if prec_seen
raise "Multiple User_code after %prec" if code_after_prec
code_after_prec = true
end
code = ts.current_token
grammar.build_references(code)
a << code
ts.next
when T::Bar
# |
break
when T::Semicolon
# ;
break
when T::Ident_Colon
# Next lhs can be here because ";" is optional.
break
when nil
# end of input can be here when ";" is omitted
break
else
raise "Unexpected token: #{ts.current_token}"
end
end
return a
end
end
end
|