Skip to main content

Table 1 Results of mechanical proof procedure. Number of shift-reduce (SR) and reduce-reduce (RR) conflicts when feeding example grammars G1 to G8 into parser generator MSTA. A 0/0 entry indicates a successful proof of non-ambiguity. Note that for increasing k, the number of conflicts may remain constant or even grow before it goes down to 0/0.

From: Effective ambiguity checking in biosequence analysis

Grammar

k

SR/RR conflicts

G1

1

24/12

G1

2

70/36

G1

3

195/99

G2

1

25/13

G2

2

59/37

G2

3

165/98

G3

1–3

4/0

G3

4

16/0

G3

5

0/0

G4

1

0/0

G5

1

0/0

G6

1

0/0

G7

1–6

5/0

G7

7

0/0

G8

1

0/0