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
|
<head>
<link href="../favicon.ico" rel="shortcut icon" type="image/x-icon"/>
<link href="../style.css" rel="stylesheet"/>
<title>Specification: BQN grammar</title>
</head>
<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../index.html">BQN</a> / <a href="index.html">spec</a></div>
<h1 id="specification-bqn-grammar"><a class="header" href="#specification-bqn-grammar">Specification: BQN grammar</a></h1>
<p>BQN's grammar is given below. Terms are defined in a <a href="https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form">BNF</a> variant. However, handling special names properly is possible but difficult in BNF, so they are explained in text along with the block grammar.</p>
<p>The symbols <code><span class='Value'>s</span></code>, <code><span class='Function'>F</span></code>, <code><span class='Modifier'>_m</span></code>, and <code><span class='Modifier2'>_c_</span></code> are identifier tokens with subject, function, 1-modifier, and 2-modifier classes respectively. Similarly, <code><span class='Value'>sl</span></code>, <code><span class='Function'>Fl</span></code>, <code><span class='Modifier'>_ml</span></code>, and <code><span class='Modifier2'>_cl_</span></code> refer to literals and primitives of those classes. While names in the BNF here follow the identifier naming scheme, this is informative only: syntactic roles are no longer used after parsing and cannot be inspected in a running program.</p>
<p>A program is a list of statements. Almost all statements are expressions. Namespace export statements, and valueless results stemming from <code><span class='Nothing'>ยท</span></code>, or <code><span class='Value'>๐จ</span></code> in a monadic block function, can be used as statements but not expressions.</p>
<pre><span class='Function'>PROGRAM</span> <span class='Function'>=</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Function'>STMT</span> <span class='Separator'>โ</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>STMT</span> <span class='Separator'>โ</span><span class='Head'>?</span>
<span class='Function'>STMT</span> <span class='Function'>=</span> <span class='Function'>EXPR</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Function'>|</span> <span class='Function'>EXPORT</span>
<span class='Separator'>โ</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='String'>"โ"</span> <span class='Function'>|</span> <span class='String'>","</span> <span class='Function'>|</span> <span class='Function'>LF</span> <span class='Function'>|</span> <span class='Function'>CR</span> <span class='Paren'>)</span><span class='Function'>+</span>
<span class='Function'>EXPR</span> <span class='Function'>=</span> <span class='Value'>subExpr</span> <span class='Function'>|</span> <span class='Function'>FuncExpr</span> <span class='Function'>|</span> <span class='Modifier'>_m1Expr</span> <span class='Function'>|</span> <span class='Modifier2'>_m2Expr_</span>
<span class='Function'>EXPORT</span> <span class='Function'>=</span> <span class='Function'>LHS_ELT</span><span class='Head'>?</span> <span class='String'>"โ"</span>
</pre>
<p>Here we define the "atomic" forms of functions and modifiers, which are either single tokens or enclosed in paired symbols. Stranded lists with <code><span class='Ligature'>โฟ</span></code>, which binds more tightly than any form of execution, are also included.</p>
<pre><span class='Function'>ANY</span> <span class='Function'>=</span> <span class='Value'>atom</span> <span class='Function'>|</span> <span class='Function'>Func</span> <span class='Function'>|</span> <span class='Modifier'>_mod1</span> <span class='Function'>|</span> <span class='Modifier2'>_mod2_</span>
<span class='Modifier2'>_mod2_</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Value'>atom</span> <span class='String'>"."</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Modifier2'>_c_</span> <span class='Function'>|</span> <span class='Modifier2'>_cl_</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Modifier2'>_m2Expr_</span> <span class='String'>")"</span> <span class='Function'>|</span> <span class='Modifier2'>_blMod2_</span>
<span class='Modifier'>_mod1</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Value'>atom</span> <span class='String'>"."</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Modifier'>_m</span> <span class='Function'>|</span> <span class='Modifier'>_ml</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Modifier'>_m1Expr</span> <span class='String'>")"</span> <span class='Function'>|</span> <span class='Modifier'>_blMod1</span>
<span class='Function'>Func</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Value'>atom</span> <span class='String'>"."</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>F</span> <span class='Function'>|</span> <span class='Function'>Fl</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Function'>FuncExpr</span> <span class='String'>")"</span> <span class='Function'>|</span> <span class='Function'>BlFunc</span>
<span class='Value'>atom</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Value'>atom</span> <span class='String'>"."</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Value'>s</span> <span class='Function'>|</span> <span class='Value'>sl</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Value'>subExpr</span> <span class='String'>")"</span> <span class='Function'>|</span> <span class='Value'>blSub</span> <span class='Function'>|</span> <span class='Value'>array</span>
<span class='Value'>array</span> <span class='Function'>=</span> <span class='String'>"โจ"</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Paren'>(</span> <span class='Function'>EXPR</span> <span class='Separator'>โ</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>EXPR</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='String'>"โฉ"</span>
<span class='Function'>|</span> <span class='String'>"["</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Function'>EXPR</span> <span class='Separator'>โ</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>EXPR</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>"]"</span>
<span class='Value'>subject</span> <span class='Function'>=</span> <span class='Value'>atom</span> <span class='Function'>|</span> <span class='Function'>ANY</span> <span class='Paren'>(</span> <span class='String'>"โฟ"</span> <span class='Function'>ANY</span> <span class='Paren'>)</span><span class='Function'>+</span>
</pre>
<p>Starting at the highest-order objects, modifiers have simple syntax. In most cases the syntax for <code><span class='Gets'>โ</span></code> and <code><span class='Gets'>โฉ</span></code> is the same, but only <code><span class='Gets'>โฉ</span></code> can be used for modified assignment. The export arrow <code><span class='Gets'>โ</span></code> can be used in the same ways as <code><span class='Gets'>โ</span></code>, but it can also be used at the beginning of a header to force a namespace result, or with no expression on the right in an <code><span class='Function'>EXPORT</span></code> statement.</p>
<pre><span class='Function'>ASGN</span> <span class='Function'>=</span> <span class='String'>"โ"</span> <span class='Function'>|</span> <span class='String'>"โ"</span> <span class='Function'>|</span> <span class='String'>"โฉ"</span>
<span class='Modifier2'>_m2Expr_</span> <span class='Function'>=</span> <span class='Modifier2'>_mod2_</span>
<span class='Function'>|</span> <span class='Modifier2'>_c_</span> <span class='Function'>ASGN</span> <span class='Modifier2'>_m2Expr_</span>
<span class='Modifier'>_m1Expr</span> <span class='Function'>=</span> <span class='Modifier'>_mod1</span>
<span class='Function'>|</span> <span class='Modifier'>_m</span> <span class='Function'>ASGN</span> <span class='Modifier'>_m1Expr</span>
</pre>
<p>Functions can be formed by applying modifiers, or with trains. Modifiers are left-associative, so that the left operand (<code><span class='Function'>Operand</span></code>) can include modifier applications but the right operand (<code><span class='Value'>subject</span> <span class='Function'>|</span> <span class='Function'>Func</span></code>) cannot. Trains are right-associative, but bind less tightly than modifiers. Assignment is not allowed in the top level of a train: it must be parenthesized.</p>
<pre><span class='Function'>Derv</span> <span class='Function'>=</span> <span class='Function'>Func</span>
<span class='Function'>|</span> <span class='Function'>Operand</span> <span class='Modifier'>_mod1</span>
<span class='Function'>|</span> <span class='Function'>Operand</span> <span class='Modifier2'>_mod2_</span> <span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Function'>Func</span> <span class='Paren'>)</span>
<span class='Function'>Operand</span> <span class='Function'>=</span> <span class='Value'>subject</span>
<span class='Function'>|</span> <span class='Function'>Derv</span>
<span class='Function'>Fork</span> <span class='Function'>=</span> <span class='Function'>Derv</span>
<span class='Function'>|</span> <span class='Function'>Operand</span> <span class='Function'>Derv</span> <span class='Function'>Fork</span> <span class='Comment'># 3-train
</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Function'>Derv</span> <span class='Function'>Fork</span> <span class='Comment'># 2-train
</span><span class='Function'>Train</span> <span class='Function'>=</span> <span class='Function'>Fork</span>
<span class='Function'>|</span> <span class='Function'>Derv</span> <span class='Function'>Fork</span> <span class='Comment'># 2-train
</span><span class='Function'>FuncExpr</span> <span class='Function'>=</span> <span class='Function'>Train</span>
<span class='Function'>|</span> <span class='Function'>F</span> <span class='Function'>ASGN</span> <span class='Function'>FuncExpr</span>
</pre>
<p>Subject expressions consist mainly of function application. We also define nothing-statements, which have very similar syntax to subject expressions but do not permit assignment. They can be used as an <code><span class='Function'>STMT</span></code> or in place of a left argument.</p>
<pre><span class='Value'>arg</span> <span class='Function'>=</span> <span class='Value'>subject</span>
<span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>Derv</span> <span class='Value'>subExpr</span>
<span class='Value'>nothing</span> <span class='Function'>=</span> <span class='String'>"ยท"</span>
<span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>Derv</span> <span class='Value'>nothing</span>
<span class='Value'>subExpr</span> <span class='Function'>=</span> <span class='Value'>arg</span>
<span class='Function'>|</span> <span class='Value'>lhs</span> <span class='Function'>ASGN</span> <span class='Value'>subExpr</span>
<span class='Function'>|</span> <span class='Value'>lhs</span> <span class='Function'>Derv</span> <span class='String'>"โฉ"</span> <span class='Value'>subExpr</span><span class='Head'>?</span> <span class='Comment'># Modified assignment
</span></pre>
<p>The target of subject assignment can be compound to allow for destructuring. List and namespace assignment share the nodes <code><span class='Value'>lhsList</span></code> and <code><span class='Value'>lhsStr</span></code> and cannot be completely distinguished until execution. The term <code><span class='Value'>sl</span></code> in <code><span class='Function'>LHS_SUB</span></code> is used for header inputs below: as an additional rule, it cannot be used in the <code><span class='Value'>lhs</span></code> term of a <code><span class='Value'>subExpr</span></code> node.</p>
<pre><span class='Function'>NAME</span> <span class='Function'>=</span> <span class='Value'>s</span> <span class='Function'>|</span> <span class='Function'>F</span> <span class='Function'>|</span> <span class='Modifier'>_m</span> <span class='Function'>|</span> <span class='Modifier2'>_c_</span>
<span class='Function'>LHS_SUB</span> <span class='Function'>=</span> <span class='String'>"ยท"</span> <span class='Function'>|</span> <span class='Value'>lhsList</span> <span class='Function'>|</span> <span class='Value'>lhsArray</span> <span class='Function'>|</span> <span class='Value'>sl</span>
<span class='Function'>LHS_ANY</span> <span class='Function'>=</span> <span class='Function'>NAME</span> <span class='Function'>|</span> <span class='Function'>LHS_SUB</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Function'>LHS_ELT</span> <span class='String'>")"</span>
<span class='Function'>LHS_ATOM</span> <span class='Function'>=</span> <span class='Function'>LHS_ANY</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Value'>lhsStr</span> <span class='String'>")"</span>
<span class='Function'>LHS_ELT</span> <span class='Function'>=</span> <span class='Function'>LHS_ANY</span> <span class='Function'>|</span> <span class='Value'>lhsStr</span>
<span class='Function'>LHS_ENTRY=</span> <span class='Function'>LHS_ELT</span> <span class='Function'>|</span> <span class='Value'>lhs</span> <span class='String'>"โ"</span> <span class='Function'>NAME</span>
<span class='Value'>lhsStr</span> <span class='Function'>=</span> <span class='Function'>LHS_ATOM</span> <span class='Paren'>(</span> <span class='String'>"โฟ"</span> <span class='Function'>LHS_ATOM</span> <span class='Paren'>)</span><span class='Function'>+</span>
<span class='Value'>lhsList</span> <span class='Function'>=</span> <span class='String'>"โจ"</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Paren'>(</span> <span class='Function'>LHS_ENTRY</span> <span class='Separator'>โ</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>LHS_ENTRY</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='String'>"โฉ"</span>
<span class='Value'>lhsArray</span> <span class='Function'>=</span> <span class='String'>"["</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Paren'>(</span> <span class='Function'>LHS_ELT</span> <span class='Separator'>โ</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>LHS_ELT</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='String'>"]"</span>
<span class='Value'>lhsComp</span> <span class='Function'>=</span> <span class='Function'>LHS_SUB</span> <span class='Function'>|</span> <span class='Value'>lhsStr</span> <span class='Function'>|</span> <span class='String'>"("</span> <span class='Value'>lhs</span> <span class='String'>")"</span>
<span class='Value'>lhs</span> <span class='Function'>=</span> <span class='Value'>s</span> <span class='Function'>|</span> <span class='Value'>lhsComp</span>
</pre>
<p>A header looks like a name for the thing being headed, or its application to inputs (possibly twice in the case of modifiers). As with assignment, it is restricted to a simple form with no extra parentheses. The full list syntax is allowed for arguments. A plain name is called a label and can be used for a block with or without arguments. First we define headers <code><span class='Function'>IMM_HEAD</span></code> that include no arguments.</p>
<pre><span class='Value'>headW</span> <span class='Function'>=</span> <span class='Value'>lhs</span> <span class='Function'>|</span> <span class='String'>"๐จ"</span>
<span class='Value'>headX</span> <span class='Function'>=</span> <span class='Value'>lhs</span> <span class='Function'>|</span> <span class='String'>"๐ฉ"</span>
<span class='Function'>HeadF</span> <span class='Function'>=</span> <span class='Value'>lhs</span> <span class='Function'>|</span> <span class='Function'>F</span> <span class='Function'>|</span> <span class='String'>"๐"</span> <span class='Function'>|</span> <span class='String'>"๐ฝ"</span>
<span class='Function'>HeadG</span> <span class='Function'>=</span> <span class='Value'>lhs</span> <span class='Function'>|</span> <span class='Function'>F</span> <span class='Function'>|</span> <span class='String'>"๐"</span> <span class='Function'>|</span> <span class='String'>"๐พ"</span>
<span class='Function'>FuncLab</span> <span class='Function'>=</span> <span class='Function'>F</span> <span class='Function'>|</span> <span class='String'>"๐"</span>
<span class='Function'>Mod1Lab</span> <span class='Function'>=</span> <span class='Modifier'>_m</span> <span class='Function'>|</span> <span class='String'>"_๐ฃ"</span>
<span class='Function'>Mod2Lab</span> <span class='Function'>=</span> <span class='Modifier2'>_c_</span> <span class='Function'>|</span> <span class='String'>"_๐ฃ_"</span>
<span class='Function'>FuncName</span> <span class='Function'>=</span> <span class='Function'>FuncLab</span>
<span class='Function'>Mod1Name</span> <span class='Function'>=</span> <span class='Function'>HeadF</span> <span class='Function'>Mod1Lab</span>
<span class='Function'>Mod2Name</span> <span class='Function'>=</span> <span class='Function'>HeadF</span> <span class='Function'>Mod2Lab</span> <span class='Function'>HeadG</span>
<span class='Function'>LABEL</span> <span class='Function'>=</span> <span class='Function'>FuncLab</span> <span class='Function'>|</span> <span class='Function'>Mod1Lab</span> <span class='Function'>|</span> <span class='Function'>Mod2Lab</span>
<span class='Function'>IMM_HEAD</span> <span class='Function'>=</span> <span class='Function'>LABEL</span> <span class='Function'>|</span> <span class='Function'>FuncName</span> <span class='Function'>|</span> <span class='Function'>Mod1Name</span> <span class='Function'>|</span> <span class='Function'>Mod2Name</span>
</pre>
<p>There are some extra possibilities for a header that specifies arguments. As a special rule, a monadic function header specifically can omit the function when the argument is not just a name (as this would conflict with a subject label). Additionally, an inference header doesn't affect evaluation of the function, but describes how an inferred property (<a href="inferred.html#undo">Undo</a>) should be computed. Here <code><span class='String'>"ห"</span></code> and <code><span class='String'>"โผ"</span></code> are both specific instances of the <code><span class='Modifier'>_ml</span></code> token.</p>
<pre><span class='Function'>ARG_HEAD</span> <span class='Function'>=</span> <span class='Function'>LABEL</span>
<span class='Function'>|</span> <span class='Value'>headW</span><span class='Head'>?</span> <span class='Function'>IMM_HEAD</span> <span class='String'>"โผ"</span><span class='Head'>?</span> <span class='Value'>headX</span>
<span class='Function'>|</span> <span class='Value'>headW</span> <span class='Function'>IMM_HEAD</span> <span class='String'>"ห"</span> <span class='String'>"โผ"</span> <span class='Value'>headX</span>
<span class='Function'>|</span> <span class='Function'>FuncName</span> <span class='String'>"ห"</span><span class='Head'>?</span> <span class='String'>"โผ"</span>
<span class='Function'>|</span> <span class='Value'>lhsComp</span>
</pre>
<p>A block is written with braces. It contains bodies, which are lists of statements, separated by semicolons. Multiple bodies can handle different cases, as determined by headers and predicates. A header is written before its body with a separating colon, and an expression other than the last in a body can be made into a predicate by following it with the separator-like <code><span class='Head'>?</span></code>.</p>
<p>An <code><span class='Function'>I_CASE</span></code>, <code><span class='Function'>A_CASE</span></code>, or <code><span class='Function'>S_CASE</span></code> is called a <em>general case</em> or <em>general body</em> if it has no header or predicate, or, more formally, it doesn't directly include a <code><span class='String'>":"</span></code> token and its <code><span class='Function'>BODY</span></code> node doesn't use the <code><span class='Function'>EXPR</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>"?"</span> <span class='Separator'>โ</span><span class='Head'>?</span></code> case. A program must satisfy some additional rules regarding general cases, but these are not needed to resolve the grammar and shouldn't strictly be considered part of it. First, no general body can appear before a body that isn't general in a block. Second, a <code><span class='Function'>IMM_BLK</span></code> or <code><span class='Value'>blSub</span></code> can directly contain at most one general body and an <code><span class='Function'>ARG_BLK</span></code> at most two (these are monadic and dyadic cases).</p>
<pre><span class='Function'>BODY</span> <span class='Function'>=</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>(</span> <span class='Function'>STMT</span> <span class='Separator'>โ</span> <span class='Function'>|</span> <span class='Function'>EXPR</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>"?"</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>STMT</span> <span class='Separator'>โ</span><span class='Head'>?</span>
<span class='Function'>I_CASE</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Function'>IMM_HEAD</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>":"</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>BODY</span>
<span class='Function'>A_CASE</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Function'>ARG_HEAD</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>":"</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>BODY</span>
<span class='Function'>S_CASE</span> <span class='Function'>=</span> <span class='Paren'>(</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='Value'>s</span> <span class='Separator'>โ</span><span class='Head'>?</span> <span class='String'>":"</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>BODY</span>
<span class='Function'>IMM_BLK</span> <span class='Function'>=</span> <span class='String'>"{"</span> <span class='Paren'>(</span> <span class='Function'>I_CASE</span> <span class='String'>";"</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>I_CASE</span> <span class='String'>"}"</span>
<span class='Function'>ARG_BLK</span> <span class='Function'>=</span> <span class='String'>"{"</span> <span class='Paren'>(</span> <span class='Function'>A_CASE</span> <span class='String'>";"</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>A_CASE</span> <span class='String'>"}"</span>
<span class='Value'>blSub</span> <span class='Function'>=</span> <span class='String'>"{"</span> <span class='Paren'>(</span> <span class='Function'>S_CASE</span> <span class='String'>";"</span> <span class='Paren'>)</span><span class='Value'>*</span> <span class='Function'>S_CASE</span> <span class='String'>"}"</span>
<span class='Function'>BlFunc</span> <span class='Function'>=</span> <span class='Function'>ARG_BLK</span>
<span class='Modifier'>_blMod1</span> <span class='Function'>=</span> <span class='Function'>IMM_BLK</span> <span class='Function'>|</span> <span class='Function'>ARG_BLK</span>
<span class='Modifier2'>_blMod2_</span> <span class='Function'>=</span> <span class='Function'>IMM_BLK</span> <span class='Function'>|</span> <span class='Function'>ARG_BLK</span>
</pre>
<p>Three additional rules apply to blocks, allowing the ambiguous grammar above to be disambiguated. They are shown in the table below. First, each block type allows the special names in its row to be used as the given token types within <code><span class='Function'>BODY</span></code> terms (not headers). Except for the spaces labelled "None", each of these four columns is cumulative, so that a given entry also includes all the entries above it. Second, a block can't contain one of the tokens from the "label" column of a different row. Third, each <code><span class='Function'>BlFunc</span></code>, <code><span class='Modifier'>_blMod1</span></code>, and <code><span class='Modifier2'>_blMod2_</span></code> term <em>must</em> contain one of the names on, and not above, the corresponding row (including the "label" column).</p>
<table>
<thead>
<tr>
<th>Term</th>
<th><code><span class='Value'>s</span></code></th>
<th><code><span class='Function'>F</span></code></th>
<th><code><span class='Modifier'>_m</span></code></th>
<th><code><span class='Modifier2'>_c_</span></code></th>
<th>label</th>
</tr>
</thead>
<tbody>
<tr>
<td><code><span class='Value'>blSub</span></code>, <code><span class='Function'>PROGRAM</span></code></td>
<td>None</td>
<td>None</td>
<td>None</td>
<td>None</td>
<td>None</td>
</tr>
<tr>
<td><code><span class='Function'>BlFunc</span></code></td>
<td><code><span class='Value'>๐จ๐ฉ๐ค</span></code></td>
<td><code><span class='Function'>๐๐๐</span></code></td>
<td></td>
<td></td>
<td><code><span class='Function'>FuncLab</span></code></td>
</tr>
<tr>
<td><code><span class='Modifier'>_blMod1</span></code></td>
<td><code><span class='Value'>๐๐ฃ</span></code></td>
<td><code><span class='Function'>๐ฝ</span></code></td>
<td><code><span class='Modifier'>_๐ฃ</span></code></td>
<td></td>
<td><code><span class='Function'>Mod1Lab</span></code></td>
</tr>
<tr>
<td><code><span class='Modifier2'>_blMod2_</span></code></td>
<td><code><span class='Value'>๐</span></code></td>
<td><code><span class='Function'>๐พ</span></code></td>
<td>None</td>
<td><code><span class='Modifier2'>_๐ฃ_</span></code></td>
<td><code><span class='Function'>Mod2Lab</span></code></td>
</tr>
</tbody>
</table>
<p>The rules for special names can be expressed in BNF by making many copies of all expression rules above. For each "level", or row in the table, a new version of every rule should be made that allows that level but not higher ones, and another version should be made that requires exactly that level. The values themselves should be included in <code><span class='Value'>s</span></code>, <code><span class='Function'>F</span></code>, <code><span class='Modifier'>_m</span></code>, and <code><span class='Modifier2'>_c_</span></code> for these copies. Then the "allowed" rules are made simply by replacing the terms they contain (excluding <code><span class='Value'>blSub</span></code> and so on) with the same "allowed" versions, and "required" rules are constructed using both "allowed" and "required" rules. For every part of a production rule, an alternative should be created that requires the relevant name in that part while allowing it in the others. For example, the definition of <code><span class='Value'>arg</span></code> as <code><span class='Value'>subject</span> <span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject</span> <span class='Function'>|</span> <span class='Value'>nothing</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>Derv</span> <span class='Value'>subExpr</span></code> would be transformed to</p>
<pre><span class='Value'>arg_req1</span> <span class='Function'>=</span> <span class='Value'>subject_req1</span>
<span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject_req1</span> <span class='Function'>|</span> <span class='Value'>nothing_req1</span> <span class='Paren'>)</span> <span class='Function'>Derv_allow1</span> <span class='Value'>subExpr_allow1</span>
<span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject_allow1</span> <span class='Function'>|</span> <span class='Value'>nothing_allow1</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>Derv_req1</span> <span class='Value'>subExpr_allow1</span>
<span class='Function'>|</span> <span class='Paren'>(</span> <span class='Value'>subject_allow1</span> <span class='Function'>|</span> <span class='Value'>nothing_allow1</span> <span class='Paren'>)</span><span class='Head'>?</span> <span class='Function'>Derv_allow1</span> <span class='Value'>subExpr_req1</span>
</pre>
<p>Quite tedious. The explosion of rules is partly due to the fact that the block-typing rule falls into a weaker class of grammars than the other rules. Most of BQN is <a href="https://en.wikipedia.org/wiki/Deterministic_context-free_grammar">deterministic context-free</a> but block-typing is not, only context-free. Fortunately block typing does not introduce the parsing difficulties that can be present in a general context-free grammar, and it can easily be performed in linear time: after <a href="token.html">scanning</a> but before parsing, move through the source code maintaining a stack of the current top-level set of braces. Whenever a colon or special name is encountered, annotate that set of braces to indicate that it is present. When a closing brace is encountered and the top brace is popped off the stack, the type is needed if there was no colon, and can be found based on which names were present. One way to present this information to the parser is to replace the brace tokens with new tokens that indicate the type.</p>
|
