-
Notifications
You must be signed in to change notification settings - Fork 1
/
How-to-rewrite-EBNF-into-BNF.htm
85 lines (78 loc) · 1.53 KB
/
How-to-rewrite-EBNF-into-BNF.htm
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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf8" />
<title>How to rewrite EBNF into BNF</title>
</head>
<body>
<table><tr><td style="vertical-align:top;">
<h1>How to rewrite EBNF into BNF</h1>
</td><td style="vertical-align:top;">
<a href="http://stackoverflow.com/questions/2466484/converting-ebnf-to-bnf">EBNF -> BNF</a>
<br />
<a href="http://stackoverflow.com/questions/14922242/how-to-convert-bnf-to-ebnf">BNF -> EBNF</a>
</td></tr></table>
EBNF have 3 additional constructs:
<br />
- repetitions
<br />
- optional parts
<br />
- alternatives
<h2>Repetitions</h2>
Can be replaced with additional recursive rule
<br />
<br />
A := B, { C }, D ; (* repetition of C *)
<br />
can be replaced with
<br />
A0 := ;
<br />
A0 := C, A0; // supplementary rule, which express repetition through tail recursion
<br />
A1 := B, A0, D; (* final rule = A *)
<br />
<br />
I don't know the reason, why { } mean 0 to many repetitions instead of 1 to many.
<h2>Optional parts</h2>
A := B, [ C ], D ; (* C is optional *)
<br />
replaced with 2 rules
<br />
A1 := B, D ;
<br />
A1 := B, C, D ;
<br />
<br />
What if there N optional parts (and 2<sup>N</sup> variants of their presence)?
<br />
A := B, [ C ], [ D ], [ E ], [ F ], G ;
<br />
A0 := ;
<br />
A0 := C;
<br />
A1 := ;
<br />
A1 := D;
<br />
A2 := ;
<br />
A2 := E;
<br />
A3 := ;
<br />
A3 := F;
<br />
A4 := B, A0, A1, A2, A3, G; (* final rule = A *)
<h2>Alternatives</h2>
A := B | C;
<br />
replaced with N rules - one for each alternative branch:
<br />
A1 := B;
<br />
A1 := C;
</body>
</html>