line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Parse::Pyapp::Parser; |
2
|
1
|
|
|
1
|
|
20
|
use 5.006; |
|
1
|
|
|
|
|
3
|
|
|
1
|
|
|
|
|
38
|
|
3
|
1
|
|
|
1
|
|
5
|
use strict; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
361
|
|
4
|
|
|
|
|
|
|
our $VERSION = '0.01'; |
5
|
|
|
|
|
|
|
#use Data::Dumper; |
6
|
|
|
|
|
|
|
|
7
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
sub addrule { |
9
|
8
|
|
|
8
|
0
|
72
|
my $pkg = shift; |
10
|
8
|
|
|
|
|
13
|
my $lhs = shift; |
11
|
8
|
|
|
|
|
15
|
foreach (@_){ |
12
|
12
|
100
|
|
|
|
32
|
my $sub = pop @$_ if ref $_->[-1] eq 'CODE'; |
13
|
12
|
|
|
|
|
15
|
push @{$pkg->{grammar}->{$lhs}}, { rhs => $_, callback => $sub }; |
|
12
|
|
|
|
|
84
|
|
14
|
12
|
100
|
|
|
|
44
|
if(ref $sub eq 'CODE'){ |
15
|
1
|
|
|
|
|
4
|
$pkg->{rcb}->{join q/,/, $lhs, @{$_}[0..$#$_-1]} = $sub; |
|
1
|
|
|
|
|
6
|
|
16
|
|
|
|
|
|
|
} |
17
|
|
|
|
|
|
|
} |
18
|
|
|
|
|
|
|
} |
19
|
|
|
|
|
|
|
|
20
|
|
|
|
|
|
|
sub addlex { |
21
|
5
|
|
|
5
|
0
|
33
|
my $pkg = shift; |
22
|
5
|
|
|
|
|
10
|
my $lhs = shift; |
23
|
|
|
|
|
|
|
# lexical callback function |
24
|
5
|
100
|
|
|
|
17
|
$pkg->{lcb}->{$lhs} = pop @_ if( ref $_[-1] eq 'CODE' ); |
25
|
5
|
|
|
|
|
17
|
foreach (@_){ |
26
|
7
|
|
|
|
|
36
|
$pkg->{lexidx}->{$_->[0]}->{$lhs} = $_->[1]; |
27
|
7
|
|
|
|
|
9
|
push @{$pkg->{grammar}->{$lhs}}, { rhs => $_ }; |
|
7
|
|
|
|
|
32
|
|
28
|
|
|
|
|
|
|
} |
29
|
|
|
|
|
|
|
} |
30
|
|
|
|
|
|
|
|
31
|
|
|
|
|
|
|
sub start { |
32
|
1
|
50
|
|
1
|
0
|
12
|
die "Unknown symbol $_[1]\n" unless exists $_[0]->{grammar}->{$_[1]}; |
33
|
1
|
|
|
|
|
4
|
$_[0]->{start} = $_[1]; |
34
|
|
|
|
|
|
|
} |
35
|
|
|
|
|
|
|
|
36
|
1
|
|
|
1
|
|
5
|
use B::Deparse; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
1468
|
|
37
|
|
|
|
|
|
|
|
38
|
|
|
|
|
|
|
sub stringify { |
39
|
0
|
|
|
0
|
0
|
0
|
my $pkg = shift; |
40
|
0
|
|
|
|
|
0
|
my $grammar; |
41
|
0
|
|
|
|
|
0
|
my $deparse = B::Deparse->new(); |
42
|
0
|
|
|
|
|
0
|
foreach my $lhs (keys %{$pkg->{grammar}}){ |
|
0
|
|
|
|
|
0
|
|
43
|
0
|
|
|
|
|
0
|
my $sum = 0; |
44
|
0
|
|
|
|
|
0
|
$grammar .= |
45
|
|
|
|
|
|
|
join q//, |
46
|
|
|
|
|
|
|
"$lhs : \n\t", |
47
|
|
|
|
|
|
|
join( qq/\n\t | \n\t/, |
48
|
|
|
|
|
|
|
map { |
49
|
0
|
|
|
|
|
0
|
my $body; |
50
|
0
|
0
|
|
|
|
0
|
if(ref( $_->{callback}) eq 'CODE'){ |
51
|
0
|
|
|
|
|
0
|
$body = $deparse->coderef2text($_->{callback}); |
52
|
0
|
|
|
|
|
0
|
$body =~ s/^(.+)$/\t$1/mg; |
53
|
0
|
|
|
|
|
0
|
$body = "\n$body"; |
54
|
|
|
|
|
|
|
} |
55
|
0
|
|
|
|
|
0
|
join q/ /, grep{$_} |
|
0
|
|
|
|
|
0
|
|
56
|
0
|
|
|
|
|
0
|
@{$_->{rhs}}[0..$#{$_->{rhs}}-1], |
|
0
|
|
|
|
|
0
|
|
57
|
|
|
|
|
|
|
"[".$_->{rhs}->[-1]."]", |
58
|
|
|
|
|
|
|
$body; |
59
|
|
|
|
|
|
|
} |
60
|
0
|
|
|
|
|
0
|
@{$pkg->{grammar}->{$lhs}})."\n\t;\n", |
61
|
|
|
|
|
|
|
$/ |
62
|
|
|
|
|
|
|
; |
63
|
|
|
|
|
|
|
} |
64
|
|
|
|
|
|
|
$grammar |
65
|
0
|
|
|
|
|
0
|
} |
66
|
|
|
|
|
|
|
|
67
|
|
|
|
|
|
|
sub toCNF { |
68
|
1
|
50
|
|
1
|
0
|
6
|
die unless caller eq __PACKAGE__; |
69
|
1
|
|
|
|
|
2
|
my $pkg = shift; |
70
|
1
|
|
|
|
|
2
|
my $maxsym; |
71
|
1
|
|
|
|
|
2
|
do{ |
72
|
3
|
|
|
|
|
3
|
$maxsym = 0; |
73
|
3
|
|
|
|
|
5
|
foreach my $lhs (keys %{$pkg->{grammar}}){ |
|
3
|
|
|
|
|
12
|
|
74
|
32
|
|
|
|
|
37
|
foreach (@{$pkg->{grammar}->{$lhs}}){ |
|
32
|
|
|
|
|
61
|
|
75
|
50
|
100
|
|
|
|
56
|
if(@{$_->{rhs}} > 3){ |
|
50
|
|
|
|
|
145
|
|
76
|
5
|
100
|
|
|
|
7
|
$maxsym = @{$_->{rhs}} if(@{$_->{rhs}} > $maxsym); |
|
3
|
|
|
|
|
5
|
|
|
5
|
|
|
|
|
15
|
|
77
|
5
|
|
|
|
|
12
|
$pkg->addrule("%%".$pkg->{symcount}, [splice(@{$_->{rhs}}, 1, -1, "%%".$pkg->{symcount}), 1]); |
|
5
|
|
|
|
|
27
|
|
78
|
5
|
|
|
|
|
20
|
$pkg->{symcount}++; |
79
|
|
|
|
|
|
|
} |
80
|
|
|
|
|
|
|
} |
81
|
|
|
|
|
|
|
} |
82
|
|
|
|
|
|
|
}while($maxsym > 3); |
83
|
|
|
|
|
|
|
|
84
|
|
|
|
|
|
|
# building rules' index |
85
|
1
|
|
|
|
|
2
|
foreach my $lhs (keys %{$pkg->{grammar}}){ |
|
1
|
|
|
|
|
5
|
|
86
|
13
|
|
|
|
|
16
|
foreach (@{$pkg->{grammar}->{$lhs}}){ |
|
13
|
|
|
|
|
27
|
|
87
|
19
|
|
|
|
|
32
|
$pkg->{rulidx }->{join q/,/,$lhs, @{$_->{rhs}}[0..$#{$_->{rhs}}-1]} = $_->{rhs}->[-1]; |
|
19
|
|
|
|
|
118
|
|
|
19
|
|
|
|
|
35
|
|
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
} |
90
|
|
|
|
|
|
|
|
91
|
|
|
|
|
|
|
|
92
|
|
|
|
|
|
|
} |
93
|
|
|
|
|
|
|
|
94
|
|
|
|
|
|
|
|
95
|
|
|
|
|
|
|
sub visit { |
96
|
1
|
|
|
1
|
0
|
4
|
my $pkg = shift; |
97
|
1
|
|
|
|
|
4
|
$pkg->{var} = {}; |
98
|
1
|
|
|
|
|
6
|
$pkg->{tree} = {}; |
99
|
1
|
|
|
|
|
3
|
@{$pkg->{nonterm}} = (); |
|
1
|
|
|
|
|
6
|
|
100
|
1
|
|
|
|
|
12
|
$pkg->_visit(join( q/,/, 0, $pkg->{lastidx}, $pkg->{start})); |
101
|
|
|
|
|
|
|
} |
102
|
|
|
|
|
|
|
|
103
|
|
|
|
|
|
|
sub _visit { |
104
|
16
|
|
|
16
|
|
30
|
my ($pkg, $key) = @_; |
105
|
|
|
|
|
|
|
|
106
|
16
|
|
|
|
|
60
|
my @L = split /,/, $key; |
107
|
16
|
|
|
|
|
53
|
my $root = (split /,/,$key)[-1]; |
108
|
16
|
|
|
|
|
85
|
my @R = split /,/, $pkg->{bp}->{$key}; |
109
|
|
|
|
|
|
|
|
110
|
16
|
100
|
66
|
|
|
110
|
if(!defined $pkg->{bp}->{$key} && $L[0] == $L[1]){ |
111
|
8
|
100
|
|
|
|
27
|
if(ref($pkg->{lcb}->{$root}) eq 'CODE'){ |
112
|
1
|
|
|
|
|
3
|
$pkg->{lhs} = $root; |
113
|
1
|
|
|
|
|
619
|
$pkg->{lcb}->{$root}->($pkg, $pkg->{token}->[$L[0]]); |
114
|
|
|
|
|
|
|
} |
115
|
8
|
|
|
|
|
29
|
return; |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
|
118
|
|
|
|
|
|
|
# left |
119
|
8
|
|
|
|
|
46
|
$pkg->_visit(join( q/,/, $L[0], $R[0], $R[1])); |
120
|
|
|
|
|
|
|
|
121
|
|
|
|
|
|
|
# right |
122
|
8
|
100
|
|
|
|
43
|
$pkg->_visit(join( q/,/, $R[0]+1, $L[1], $R[2])) if $R[2]; |
123
|
|
|
|
|
|
|
|
124
|
|
|
|
|
|
|
# root |
125
|
8
|
100
|
|
|
|
38
|
if($root !~ /^%%/o){ |
126
|
4
|
|
|
|
|
6
|
$pkg->{pos} = [ $root, $R[1], @{$pkg->{nonterm}} ]; |
|
4
|
|
|
|
|
18
|
|
127
|
4
|
100
|
|
|
|
11
|
if(ref($pkg->{rcb}->{join q/,/, @{$pkg->{pos}}}) eq 'CODE'){ |
|
4
|
|
|
|
|
36
|
|
128
|
2
|
|
|
|
|
8
|
$pkg->{lhs} = $root; |
129
|
2
|
|
|
|
|
12
|
$pkg->{rcb}->{join q/,/, @{$pkg->{pos}}}->($pkg, @{$pkg->{token}}[$L[0]..$L[1]]); |
|
2
|
|
|
|
|
14
|
|
|
2
|
|
|
|
|
10
|
|
130
|
|
|
|
|
|
|
} |
131
|
4
|
|
|
|
|
20
|
@{$pkg->{nonterm}} = (); |
|
4
|
|
|
|
|
11
|
|
132
|
4
|
|
|
|
|
7
|
@{$pkg->{pos}} = (); |
|
4
|
|
|
|
|
15
|
|
133
|
|
|
|
|
|
|
} |
134
|
|
|
|
|
|
|
else{ |
135
|
4
|
|
|
|
|
8
|
unshift @{$pkg->{nonterm}}, grep{$_!~/^%%/o} $R[1], $R[2]; |
|
4
|
|
|
|
|
11
|
|
|
8
|
|
|
|
|
32
|
|
136
|
|
|
|
|
|
|
# print @{$pkg->{nonterm}},$/; |
137
|
|
|
|
|
|
|
} |
138
|
|
|
|
|
|
|
} |
139
|
|
|
|
|
|
|
|
140
|
|
|
|
|
|
|
|
141
|
|
|
|
|
|
|
sub parse($@) { |
142
|
1
|
|
|
1
|
0
|
8
|
my $pkg = shift; |
143
|
1
|
|
|
|
|
8
|
$pkg->toCNF; |
144
|
|
|
|
|
|
|
|
145
|
1
|
|
|
|
|
2
|
my @nont = keys %{$pkg->{grammar}}; |
|
1
|
|
|
|
|
8
|
|
146
|
|
|
|
|
|
|
|
147
|
1
|
|
|
|
|
25
|
$pkg->{lastidx} = $#_; |
148
|
1
|
|
|
|
|
5
|
$pkg->{token} = \@_; |
149
|
|
|
|
|
|
|
|
150
|
|
|
|
|
|
|
# probability matrix |
151
|
1
|
|
|
|
|
3
|
$pkg->{pi} = undef; |
152
|
|
|
|
|
|
|
# back pointers |
153
|
1
|
|
|
|
|
2
|
$pkg->{bp} = undef; |
154
|
|
|
|
|
|
|
|
155
|
|
|
|
|
|
|
#################### |
156
|
|
|
|
|
|
|
# base case |
157
|
|
|
|
|
|
|
#################### |
158
|
1
|
|
|
|
|
4
|
foreach my $i (0..$#_){ |
159
|
8
|
|
|
|
|
11
|
foreach (keys %{$pkg->{grammar}}){ |
|
8
|
|
|
|
|
25
|
|
160
|
104
|
100
|
|
|
|
272
|
$pkg->{pi}->{"$i,$i,$_"} = $pkg->{lexidx}->{$_[$i]}->{$_} if $pkg->{lexidx}->{$_[$i]}->{$_}; |
161
|
|
|
|
|
|
|
} |
162
|
|
|
|
|
|
|
} |
163
|
|
|
|
|
|
|
|
164
|
|
|
|
|
|
|
#################### |
165
|
|
|
|
|
|
|
# recursive case |
166
|
|
|
|
|
|
|
#################### |
167
|
1
|
|
|
|
|
4
|
foreach my $span (0..$#_){ |
168
|
8
|
|
|
|
|
52
|
foreach my $begin (0..$#_-$span){ |
169
|
36
|
|
|
|
|
76
|
my $end = $begin + $span; |
170
|
36
|
|
|
|
|
102
|
foreach my $m ($begin..$end){ |
171
|
120
|
|
|
|
|
175
|
foreach my $A (@nont){ |
172
|
1560
|
|
|
|
|
2465
|
foreach my $B (@nont){ |
173
|
20280
|
|
|
|
|
27682
|
foreach my $C (@nont){ |
174
|
263640
|
|
|
|
|
937260
|
my $prob = $pkg->{pi}->{"$begin,$m,$B"} * |
175
|
|
|
|
|
|
|
$pkg->{pi}->{join q/,/,$m+1,$end,$C} * |
176
|
|
|
|
|
|
|
$pkg->{rulidx}->{join q/,/, $A, $B, $C}; |
177
|
263640
|
100
|
66
|
|
|
629628
|
if($prob && $prob > $pkg->{pi}->{"$begin,$end,$A"}){ |
178
|
9
|
|
|
|
|
48
|
$pkg->{pi}->{"$begin,$end,$A"} = $prob; |
179
|
9
|
|
|
|
|
53
|
$pkg->{bp}->{"$begin,$end,$A"} = "$m,$B,$C"; |
180
|
|
|
|
|
|
|
} |
181
|
|
|
|
|
|
|
} |
182
|
|
|
|
|
|
|
######################################## |
183
|
|
|
|
|
|
|
# for a single right hand derivation |
184
|
|
|
|
|
|
|
######################################## |
185
|
|
|
|
|
|
|
|
186
|
20280
|
100
|
|
|
|
62962
|
if($pkg->{rulidx}->{join q/,/, $A, $B}){ |
187
|
240
|
|
|
|
|
802
|
my $prob = $pkg->{pi}->{"$begin,$m,$B"} * $pkg->{rulidx}->{join q/,/, $A, $B}; |
188
|
240
|
100
|
100
|
|
|
976
|
if($prob && $prob > $pkg->{pi}->{"$begin,$end,$A"}){ |
189
|
10
|
|
|
|
|
44
|
$pkg->{pi}->{"$begin,$end,$A"} = $prob; |
190
|
10
|
|
|
|
|
52
|
$pkg->{bp}->{"$begin,$end,$A"} = "$begin,$B"; |
191
|
|
|
|
|
|
|
} |
192
|
|
|
|
|
|
|
} |
193
|
|
|
|
|
|
|
} |
194
|
|
|
|
|
|
|
} |
195
|
|
|
|
|
|
|
} |
196
|
|
|
|
|
|
|
} |
197
|
|
|
|
|
|
|
} |
198
|
1
|
50
|
|
|
|
16
|
return unless ($pkg->{bp}->{join(q/,/,0,$pkg->{lastidx},$pkg->{start})}); |
199
|
1
|
|
|
|
|
26
|
$pkg->visit; |
200
|
1
|
|
|
|
|
14
|
1; |
201
|
|
|
|
|
|
|
} |
202
|
|
|
|
|
|
|
|
203
|
|
|
|
|
|
|
|
204
|
|
|
|
|
|
|
|
205
|
|
|
|
|
|
|
|
206
|
|
|
|
|
|
|
1; |
207
|
|
|
|
|
|
|
|
208
|
|
|
|
|
|
|
__END__ |