-
Notifications
You must be signed in to change notification settings - Fork 2
/
yacc.py
1844 lines (1553 loc) · 65.9 KB
/
yacc.py
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
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#-----------------------------------------------------------------------------
# ply: yacc.py
#
# Author: David M. Beazley ([email protected])
# Department of Computer Science
# University of Chicago
# Chicago, IL 60637
#
# Copyright (C) 2001, David M. Beazley
#
# $Header$
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2.1 of the License, or (at your option) any later version.
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
#
# See the file COPYING for a complete copy of the LGPL.
#
#
# This implements an LR parser that is constructed from grammar rules defined
# as Python functions. Roughly speaking, this module is a cross between
# John Aycock's Spark system and the GNU bison utility.
#
# Disclaimer: This is a work in progress. SLR parsing seems to work fairly
# well and there is extensive error checking. LALR(1) is in progress. The
# rest of this file is a bit of a mess. Please pardon the dust.
#
# The current implementation is only somewhat object-oriented. The
# LR parser itself is defined in terms of an object (which allows multiple
# parsers to co-exist). However, most of the variables used during table
# construction are defined in terms of global variables. Users shouldn't
# notice unless they are trying to define multiple parsers at the same
# time using threads (in which case they should have their head examined).
#-----------------------------------------------------------------------------
__version__ = "1.3"
#-----------------------------------------------------------------------------
# === User configurable parameters ===
#
# Change these to modify the default behavior of yacc (if you wish)
#-----------------------------------------------------------------------------
yaccdebug = 1 # Debugging mode. If set, yacc generates a
# a 'parser.out' file in the current directory
debug_file = 'parser.out' # Default name of the debugging file
tab_module = 'parsetab' # Default name of the table module
default_lr = 'SLR' # Default LR table generation method
error_count = 3 # Number of symbols that must be shifted to leave recovery mode
import re, types, sys, cStringIO, md5, os.path
# Exception raised for yacc-related errors
class YaccError(Exception): pass
#-----------------------------------------------------------------------------
# === LR Parsing Engine ===
#
# The following classes are used for the LR parser itself. These are not
# used during table construction and are independent of the actual LR
# table generation algorithm
#-----------------------------------------------------------------------------
# This class is used to hold non-terminal grammar symbols during parsing.
# It normally has the following attributes set:
# .type = Grammar symbol type
# .value = Symbol value
# .lineno = Starting line number
# .endlineno = Ending line number (optional, set automatically)
class YaccSymbol:
def __str__(self): return self.type
def __repr__(self): return str(self)
# This class is a wrapper around the objects actually passed to each
# grammar rule. Index lookup and assignment actually assign the
# .value attribute of the underlying YaccSymbol object.
# The lineno() method returns the line number of a given
# item (or 0 if not defined). The linespan() method returns
# a tuple of (startline,endline) representing the range of lines
# for a symbol.
class YaccSlice:
def __init__(self,s):
self.slice = s
self.pbstack = []
def __getitem__(self,n):
return self.slice[n].value
def __setitem__(self,n,v):
self.slice[n].value = v
def lineno(self,n):
return getattr(self.slice[n],"lineno",0)
def linespan(self,n):
startline = getattr(self.slice[n],"lineno",0)
endline = getattr(self.slice[n],"endlineno",startline)
return startline,endline
def pushback(self,n):
if n <= 0:
raise ValueError, "Expected a positive value"
if n > (len(self.slice)-1):
raise ValueError, "Can't push %d tokens. Only %d are available." % (n,len(self.slice)-1)
for i in range(0,n):
self.pbstack.append(self.slice[-i-1])
# The LR Parsing engine. This is defined as a class so that multiple parsers
# can exist in the same process. A user never instantiates this directly.
# Instead, the global yacc() function should be used to create a suitable Parser
# object.
class Parser:
def __init__(self,magic=None):
# This is a hack to keep users from trying to instantiate a Parser
# object directly.
if magic != "xyzzy":
raise YaccError, "Can't instantiate Parser. Use yacc() instead."
# Reset internal state
self.productions = None # List of productions
self.errorfunc = None # Error handling function
self.action = { } # LR Action table
self.goto = { } # LR goto table
self.require = { } # Attribute require table
self.method = "Unknown LR" # Table construction method used
def errok(self):
self.errorcount = 0
def restart(self):
del self.statestack[:]
del self.symstack[:]
sym = YaccSymbol()
sym.type = '$'
self.symstack.append(sym)
self.statestack.append(0)
def parse(self,input=None,lexer=None,debug=0):
lookahead = None # Current lookahead symbol
lookaheadstack = [ ] # Stack of lookahead symbols
actions = self.action # Local reference to action table
goto = self.goto # Local reference to goto table
prod = self.productions # Local reference to production list
pslice = YaccSlice(None) # Slice object passed to grammar rules
pslice.parser = self # Parser object
self.errorcount = 0 # Used during error recovery
# If no lexer was given, we will try to use the lex module
if not lexer:
import lex as lexer
pslice.lexer = lexer
# If input was supplied, pass to lexer
if input:
lexer.input(input)
# Tokenize function
get_token = lexer.token
statestack = [ ] # Stack of parsing states
self.statestack = statestack
symstack = [ ] # Stack of grammar symbols
self.symstack = symstack
errtoken = None # Err token
# The start state is assumed to be (0,$)
statestack.append(0)
sym = YaccSymbol()
sym.type = '$'
symstack.append(sym)
while 1:
# Get the next symbol on the input. If a lookahead symbol
# is already set, we just use that. Otherwise, we'll pull
# the next token off of the lookaheadstack or from the lexer
if not lookahead:
if not lookaheadstack:
lookahead = get_token() # Get the next token
else:
lookahead = lookaheadstack.pop()
if not lookahead:
lookahead = YaccSymbol()
lookahead.type = '$'
if debug:
print "%-20s : %s" % (lookahead, [xx.type for xx in symstack])
# Check the action table
s = statestack[-1]
ltype = lookahead.type
t = actions.get((s,ltype),None)
if t is not None:
if t > 0:
# shift a symbol on the stack
if ltype == '$':
# Error, end of input
print "yacc: Parse error. EOF"
return
statestack.append(t)
symstack.append(lookahead)
lookahead = None
# Decrease error count on successful shift
if self.errorcount > 0:
self.errorcount -= 1
continue
if t < 0:
# reduce a symbol on the stack, emit a production
p = prod[-t]
pname = p.name
plen = p.len
# Get production function
sym = YaccSymbol()
sym.type = pname # Production name
sym.value = None
if plen:
targ = symstack[-plen-1:]
targ[0] = sym
try:
sym.lineno = targ[1].lineno
sym.endlineno = getattr(targ[-1],"endlineno",targ[-1].lineno)
except AttributeError:
sym.lineno = 0
del symstack[-plen:]
del statestack[-plen:]
else:
sym.lineno = 0
targ = [ sym ]
pslice.slice = targ
pslice.pbstack = []
# Call the grammar rule with our special slice object
p.func(pslice)
# Validate attributes of the resulting value attribute
# if require:
# try:
# t0 = targ[0]
# r = Requires.get(t0.type,None)
# t0d = t0.__dict__
# if r:
# for field in r:
# tn = t0
# for fname in field:
# try:
# tf = tn.__dict__
# tn = tf.get(fname)
# except StandardError:
# tn = None
# if not tn:
# print "%s:%d: Rule %s doesn't set required attribute '%s'" % \
# (p.file,p.line,p.name,".".join(field))
# except TypeError,LookupError:
# print "Bad requires directive " % r
# pass
# If there was a pushback, put that on the stack
if pslice.pbstack:
lookaheadstack.append(lookahead)
for _t in pslice.pbstack:
lookaheadstack.append(_t)
lookahead = None
symstack.append(sym)
statestack.append(goto[statestack[-1],pname])
continue
if t == 0:
n = symstack[-1]
return getattr(n,"value",None)
if t == None:
# We have some kind of parsing error here. To handle this,
# we are going to push the current token onto the tokenstack
# and replace it with an 'error' token. If there are any synchronization
# rules, they may catch it.
#
# In addition to pushing the error token, we call call the user defined p_error()
# function if this is the first syntax error. This function is only called
# if errorcount == 0.
if not self.errorcount:
self.errorcount = error_count
errtoken = lookahead
if errtoken.type == '$':
errtoken = None # End of file!
if self.errorfunc:
global errok,token,restart
errok = self.errok # Set some special functions available in error recovery
token = get_token
restart = self.restart
tok = self.errorfunc(errtoken)
del errok, token, restart # Delete special functions
if not self.errorcount:
# User must have done some kind of panic mode recovery on their own. The returned token
# is the next lookahead
lookahead = tok
errtoken = None
continue
else:
if errtoken:
if hasattr(errtoken,"lineno"): lineno = lookahead.lineno
else: lineno = 0
if lineno:
print "yacc: Syntax error at line %d, token=%s" % (lineno, errtoken.type)
else:
print "yacc: Syntax error, token=%s" % errtoken.type
else:
print "yacc: Parse error in input. EOF"
return
else:
self.errorcount = error_count
# case 1: the statestack only has 1 entry on it. If we're in this state, the
# entire parse has been rolled back and we're completely hosed. The token is
# discarded and we just keep going.
if len(statestack) <= 1 and lookahead.type != '$':
lookahead = None
errtoken = None
# Nuke the pushback stack
del lookaheadstack[:]
continue
# case 2: the statestack has a couple of entries on it, but we're
# at the end of the file. nuke the top entry and generate an error token
# Start nuking entries on the stack
if lookahead.type == '$':
# Whoa. We're really hosed here. Bail out
return
if lookahead.type != 'error':
sym = symstack[-1]
if sym.type == 'error':
# Hmmm. Error is on top of stack, we'll just nuke input
# symbol and continue
lookahead = None
continue
t = YaccSymbol()
t.type = 'error'
if hasattr(lookahead,"lineno"):
t.lineno = lookahead.lineno
t.value = lookahead
lookaheadstack.append(lookahead)
lookahead = t
else:
symstack.pop()
statestack.pop()
continue
# Call an error function here
raise RuntimeError, "yacc: internal parser error!!!\n"
# -----------------------------------------------------------------------------
# === Parser Construction ===
#
# The following functions and variables are used to implement the yacc() function
# itself. This is pretty hairy stuff involving lots of error checking,
# construction of LR items, kernels, and so forth. Although a lot of
# this work is done using global variables, the resulting Parser object
# is completely self contained--meaning that it is safe to repeatedly
# call yacc() with different grammars in the same application.
# -----------------------------------------------------------------------------
# -----------------------------------------------------------------------------
# validate_file()
#
# This function checks to see if there are duplicated p_rulename() functions
# in the parser module file. Without this function, it is really easy for
# users to make mistakes by cutting and pasting code fragments (and it's a real
# bugger to try and figure out why the resulting parser doesn't work). Therefore,
# we just do a little regular expression pattern matching of def statements
# to try and detect duplicates.
# -----------------------------------------------------------------------------
def validate_file(filename):
base,ext = os.path.splitext(filename)
if ext != '.py': return 1 # No idea. Assume it's okay.
try:
f = open(filename)
lines = f.readlines()
f.close()
except IOError:
return 1 # Oh well
# Match def p_funcname(
fre = re.compile(r'\s*def\s+(p_[a-zA-Z_0-9]*)\(')
counthash = { }
linen = 1
noerror = 1
for l in lines:
m = fre.match(l)
if m:
name = m.group(1)
prev = counthash.get(name)
if not prev:
counthash[name] = linen
else:
print "%s:%d: Function %s redefined. Previously defined on line %d" % (filename,linen,name,prev)
noerror = 0
linen += 1
return noerror
# This function looks for functions that might be grammar rules, but which don't have the proper p_suffix.
def validate_dict(d):
for n,v in d.items():
if n[0:2] == 'p_' and isinstance(v,types.FunctionType): continue
if n[0:2] == 't_': continue
if n[0:2] == 'p_':
print "yacc: Warning. '%s' not defined as a function" % n
if isinstance(v,types.FunctionType) and v.func_code.co_argcount == 1:
try:
doc = v.__doc__.split(" ")
if doc[1] == ':':
print "%s:%d: Warning. Possible grammar rule '%s' defined without p_ prefix." % (v.func_code.co_filename, v.func_code.co_firstlineno,n)
except StandardError:
pass
# -----------------------------------------------------------------------------
# === GRAMMAR FUNCTIONS ===
#
# The following global variables and functions are used to store, manipulate,
# and verify the grammar rules specified by the user.
# -----------------------------------------------------------------------------
# Initialize all of the global variables used during grammar construction
def initialize_vars():
global Productions, Prodnames, Prodmap, Terminals
global Nonterminals, First, Follow, Precedence, LRitems
global Errorfunc, Signature, Requires
Productions = [None] # A list of all of the productions. The first
# entry is always reserved for the purpose of
# building an augmented grammar
Prodnames = { } # A dictionary mapping the names of nonterminals to a list of all
# productions of that nonterminal.
Prodmap = { } # A dictionary that is only used to detect duplicate
# productions.
Terminals = { } # A dictionary mapping the names of terminal symbols to a
# list of the rules where they are used.
Nonterminals = { } # A dictionary mapping names of nonterminals to a list
# of rule numbers where they are used.
First = { } # A dictionary of precomputed FIRST(x) symbols
Follow = { } # A dictionary of precomputed FOLLOW(x) symbols
Precedence = { } # Precedence rules for each terminal. Contains tuples of the
# form ('right',level) or ('nonassoc', level) or ('left',level)
LRitems = [ ] # A list of all LR items for the grammar. These are the
# productions with the "dot" like E -> E . PLUS E
Errorfunc = None # User defined error handler
Signature = md5.new() # Digital signature of the grammar rules, precedence
# and other information. Used to determined when a
# parsing table needs to be regenerated.
Requires = { } # Requires list
# File objects used when creating the parser.out debugging file
global _vf, _vfc
_vf = cStringIO.StringIO()
_vfc = cStringIO.StringIO()
# -----------------------------------------------------------------------------
# class Production:
#
# This class stores the raw information about a single production or grammar rule.
# It has a few required attributes:
#
# name - Name of the production (nonterminal)
# prod - A list of symbols making up its production
# number - Production number.
#
# In addition, a few additional attributes are used to help with debugging or
# optimization of table generation.
#
# file - File where production action is defined.
# lineno - Line number where action is defined
# func - Action function
# prec - Precedence level
# lr_next - Next LR item. Example, if we are ' E -> E . PLUS E'
# then lr_next refers to 'E -> E PLUS . E'
# lr_index - LR item index (location of the ".") in the prod list.
# len - Length of the production (number of symbols on right hand side)
# -----------------------------------------------------------------------------
class Production:
def __init__(self,**kw):
for k,v in kw.items():
setattr(self,k,v)
self.lr_index = -1
self.lr0_added = 0 # Flag indicating whether or not added to LR0 closure
self.usyms = [ ]
def __str__(self):
if self.prod:
s = "%s -> %s" % (self.name," ".join(self.prod))
else:
s = "%s -> <empty>" % self.name
return s
def __repr__(self):
return str(self)
# Compute lr_items from the production
def lr_item(self,n):
if n > len(self.prod): return None
p = Production()
p.name = self.name
p.prod = list(self.prod)
p.number = self.number
p.lr_index = n
p.prod.insert(n,".")
p.prod = tuple(p.prod)
p.len = len(p.prod)
p.usyms = self.usyms
# Precompute list of productions immediately following
try:
p.lrafter = Prodnames[p.prod[n+1]]
except (IndexError,KeyError),e:
p.lrafter = []
try:
p.lrbefore = p.prod[n-1]
except IndexError:
p.lrbefore = None
return p
class MiniProduction:
pass
# Utility function
def is_identifier(s):
for c in s:
if not (c.isalnum() or c == '_'): return 0
return 1
# -----------------------------------------------------------------------------
# add_production()
#
# Given an action function, this function assembles a production rule.
# The production rule is assumed to be found in the function's docstring.
# This rule has the general syntax:
#
# name1 ::= production1
# | production2
# | production3
# ...
# | productionn
# name2 ::= production1
# | production2
# ...
# -----------------------------------------------------------------------------
def add_production(f,file,line,prodname,syms):
if Terminals.has_key(prodname):
print "%s:%d: Illegal rule name '%s'. Already defined as a token." % (file,line,prodname)
return -1
if prodname == 'error':
print "%s:%d: Illegal rule name '%s'. error is a reserved word." % (file,line,prodname)
return -1
if not is_identifier(prodname):
print "%s:%d: Illegal rule name '%s'" % (file,line,prodname)
return -1
for s in syms:
if not is_identifier(s) and s != '%prec':
print "%s:%d: Illegal name '%s' in rule '%s'" % (file,line,s, prodname)
return -1
# See if the rule is already in the rulemap
map = "%s -> %s" % (prodname,syms)
if Prodmap.has_key(map):
m = Prodmap[map]
print "%s:%d: Duplicate rule %s." % (file,line, m)
print "%s:%d: Previous definition at %s:%d" % (file,line, m.file, m.line)
return -1
p = Production()
p.name = prodname
p.prod = syms
p.file = file
p.line = line
p.func = f
p.number = len(Productions)
Productions.append(p)
Prodmap[map] = p
if not Nonterminals.has_key(prodname):
Nonterminals[prodname] = [ ]
# Add all terminals to Terminals
i = 0
while i < len(p.prod):
t = p.prod[i]
if t == '%prec':
try:
precname = p.prod[i+1]
except IndexError:
print "%s:%d: Syntax error. Nothing follows %%prec." % (p.file,p.line)
return -1
prec = Precedence.get(precname,None)
if not prec:
print "%s:%d: Nothing known about the precedence of '%s'" % (p.file,p.line,precname)
return -1
else:
p.prec = prec
del p.prod[i]
del p.prod[i]
continue
if Terminals.has_key(t):
Terminals[t].append(p.number)
# Is a terminal. We'll assign a precedence to p based on this
if not hasattr(p,"prec"):
p.prec = Precedence.get(t,('right',0))
else:
if not Nonterminals.has_key(t):
Nonterminals[t] = [ ]
Nonterminals[t].append(p.number)
i += 1
if not hasattr(p,"prec"):
p.prec = ('right',0)
# Set final length of productions
p.len = len(p.prod)
p.prod = tuple(p.prod)
# Calculate unique syms in the production
p.usyms = [ ]
for s in p.prod:
if s not in p.usyms:
p.usyms.append(s)
# Add to the global productions list
try:
Prodnames[p.name].append(p)
except KeyError:
Prodnames[p.name] = [ p ]
return 0
# Given a raw rule function, this function rips out its doc string
# and adds rules to the grammar
def add_function(f):
line = f.func_code.co_firstlineno
file = f.func_code.co_filename
error = 0
if f.func_code.co_argcount > 1:
print "%s:%d: Rule '%s' has too many arguments." % (file,line,f.__name__)
return -1
if f.func_code.co_argcount < 1:
print "%s:%d: Rule '%s' requires an argument." % (file,line,f.__name__)
return -1
if f.__doc__:
# Split the doc string into lines
pstrings = f.__doc__.splitlines()
lastp = None
dline = line
for ps in pstrings:
dline += 1
p = ps.split()
if not p: continue
try:
if p[0] == '|':
# This is a continuation of a previous rule
if not lastp:
print "%s:%d: Misplaced '|'." % (file,dline)
return -1
prodname = lastp
if len(p) > 1:
syms = p[1:]
else:
syms = [ ]
else:
prodname = p[0]
lastp = prodname
assign = p[1]
if len(p) > 2:
syms = p[2:]
else:
syms = [ ]
if assign != ':' and assign != '::=':
print "%s:%d: Syntax error. Expected ':'" % (file,dline)
return -1
e = add_production(f,file,dline,prodname,syms)
error += e
except StandardError:
print "%s:%d: Syntax error in rule '%s'" % (file,dline,ps)
error -= 1
else:
print "%s:%d: No documentation string specified in function '%s'" % (file,line,f.__name__)
return error
# Cycle checking code (Michael Dyck)
def compute_reachable():
'''
Find each symbol that can be reached from the start symbol.
Print a warning for any nonterminals that can't be reached.
(Unused terminals have already had their warning.)
'''
Reachable = { }
for s in Terminals.keys() + Nonterminals.keys():
Reachable[s] = 0
mark_reachable_from( Productions[0].prod[0], Reachable )
for s in Nonterminals.keys():
if not Reachable[s]:
print "yacc: Symbol '%s' is unreachable." % s
def mark_reachable_from(s, Reachable):
'''
Mark all symbols that are reachable from symbol s.
'''
if Reachable[s]:
# We've already reached symbol s.
return
Reachable[s] = 1
for p in Prodnames.get(s,[]):
for r in p.prod:
mark_reachable_from(r, Reachable)
# -----------------------------------------------------------------------------
# compute_terminates()
#
# This function looks at the various parsing rules and tries to detect
# infinite recursion cycles (grammar rules where there is no possible way
# to derive a string of only terminals).
# -----------------------------------------------------------------------------
def compute_terminates():
'''
Raise an error for any symbols that don't terminate.
'''
Terminates = {}
# Terminals:
for t in Terminals.keys():
Terminates[t] = 1
Terminates['$'] = 1
# Nonterminals:
# Initialize to false:
for n in Nonterminals.keys():
Terminates[n] = 0
# Then propagate termination until no change:
while 1:
some_change = 0
for (n,pl) in Prodnames.items():
# Nonterminal n terminates iff any of its productions terminates.
for p in pl:
# Production p terminates iff all of its rhs symbols terminate.
for s in p.prod:
if not Terminates[s]:
# The symbol s does not terminate,
# so production p does not terminate.
p_terminates = 0
break
else:
# didn't break from the loop,
# so every symbol s terminates
# so production p terminates.
p_terminates = 1
if p_terminates:
# symbol n terminates!
if not Terminates[n]:
Terminates[n] = 1
some_change = 1
# Don't need to consider any more productions for this n.
break
if not some_change:
break
some_error = 0
for (s,terminates) in Terminates.items():
if not terminates:
if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
# s is used-but-not-defined, and we've already warned of that,
# so it would be overkill to say that it's also non-terminating.
pass
else:
print "yacc: Infinite recursion detected for symbol '%s'." % s
some_error = 1
return some_error
# -----------------------------------------------------------------------------
# verify_productions()
#
# This function examines all of the supplied rules to see if they seem valid.
# -----------------------------------------------------------------------------
def verify_productions(cycle_check=1):
error = 0
for p in Productions:
if not p: continue
for s in p.prod:
if not Prodnames.has_key(s) and not Terminals.has_key(s) and s != 'error':
print "%s:%d: Symbol '%s' used, but not defined as a token or a rule." % (p.file,p.line,s)
error = 1
continue
unused_tok = 0
# Now verify all of the tokens
if yaccdebug:
_vf.write("Unused terminals:\n\n")
for s,v in Terminals.items():
if s != 'error' and not v:
print "yacc: Warning. Token '%s' defined, but not used." % s
if yaccdebug: _vf.write(" %s\n"% s)
unused_tok += 1
# Print out all of the productions
if yaccdebug:
_vf.write("\nGrammar\n\n")
for i in range(1,len(Productions)):
_vf.write("Rule %-5d %s\n" % (i, Productions[i]))
unused_prod = 0
# Verify the use of all productions
for s,v in Nonterminals.items():
if not v:
p = Prodnames[s][0]
print "%s:%d: Warning. Rule '%s' defined, but not used." % (p.file,p.line, s)
unused_prod += 1
if unused_tok == 1:
print "yacc: Warning. There is 1 unused token."
if unused_tok > 1:
print "yacc: Warning. There are %d unused tokens." % unused_tok
if unused_prod == 1:
print "yacc: Warning. There is 1 unused rule."
if unused_prod > 1:
print "yacc: Warning. There are %d unused rules." % unused_prod
if yaccdebug:
_vf.write("\nTerminals, with rules where they appear\n\n")
ks = Terminals.keys()
ks.sort()
for k in ks:
_vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Terminals[k]])))
_vf.write("\nNonterminals, with rules where they appear\n\n")
ks = Nonterminals.keys()
ks.sort()
for k in ks:
_vf.write("%-20s : %s\n" % (k, " ".join([str(s) for s in Nonterminals[k]])))
if (cycle_check):
compute_reachable()
error += compute_terminates()
# error += check_cycles()
return error
# -----------------------------------------------------------------------------
# build_lritems()
#
# This function walks the list of productions and builds a complete set of the
# LR items. The LR items are stored in two ways: First, they are uniquely
# numbered and placed in the list _lritems. Second, a linked list of LR items
# is built for each production. For example:
#
# E -> E PLUS E
#
# Creates the list
#
# [E -> . E PLUS E, E -> E . PLUS E, E -> E PLUS . E, E -> E PLUS E . ]
# -----------------------------------------------------------------------------
def build_lritems():
for p in Productions:
lastlri = p
lri = p.lr_item(0)
i = 0
while 1:
lri = p.lr_item(i)
lastlri.lr_next = lri
if not lri: break
lri.lr_num = len(LRitems)
LRitems.append(lri)
lastlri = lri
i += 1
# In order for the rest of the parser generator to work, we need to
# guarantee that no more lritems are generated. Therefore, we nuke
# the p.lr_item method. (Only used in debugging)
# Production.lr_item = None
# -----------------------------------------------------------------------------
# add_precedence()
#
# Given a list of precedence rules, add to the precedence table.
# -----------------------------------------------------------------------------
def add_precedence(plist):
plevel = 0
error = 0
for p in plist:
plevel += 1
try:
prec = p[0]
terms = p[1:]
if prec != 'left' and prec != 'right' and prec != 'nonassoc':
print "yacc: Invalid precedence '%s'" % prec
return -1
for t in terms:
if Precedence.has_key(t):
print "yacc: Precedence already specified for terminal '%s'" % t
error += 1
continue
Precedence[t] = (prec,plevel)
except:
print "yacc: Invalid precedence table."
error += 1
return error
# -----------------------------------------------------------------------------
# augment_grammar()
#
# Compute the augmented grammar. This is just a rule S' -> start where start
# is the starting symbol.
# -----------------------------------------------------------------------------
def augment_grammar(start=None):
if not start:
start = Productions[1].name
Productions[0] = Production(name="S'",prod=[start],number=0,len=1,prec=('right',0),func=None)
Productions[0].usyms = [ start ]
Nonterminals[start].append(0)
# -------------------------------------------------------------------------
# first()
#
# Compute the value of FIRST1(beta) where beta is a tuple of symbols.
#
# During execution of compute_first1, the result may be incomplete.
# Afterward (e.g., when called from compute_follow()), it will be complete.
# -------------------------------------------------------------------------
def first(beta):
# We are computing First(x1,x2,x3,...,xn)
result = [ ]
for x in beta:
x_produces_empty = 0