1 \documentclass[10pt]{article}
9 \title{A MathML Editor Based on \TeX{} Syntax\\Formal Specification}
10 \author{Paolo Marinelli\\Luca Padovani\\\small\{{\tt pmarinel},{\tt lpadovan}\}{\tt @cs.unibo.it}\\\small Department of Computer Science\\\small University of Bologna}
13 \newcommand{\tmap}[1]{\llbracket#1\rrbracket}
14 \newcommand{\tadvance}{\vartriangle}
15 \newcommand{\tnext}{\rhd}
16 \newcommand{\G}{\texttt{g}}
17 \newcommand{\PNODE}{\texttt{p}}
18 \newcommand{\SNODE}{\texttt{s}}
19 \newcommand{\INODE}{\texttt{i}}
20 \newcommand{\NNODE}{\texttt{n}}
21 \newcommand{\ONODE}{\texttt{o}}
22 \newcommand{\CNODE}{\texttt{c}}
23 \newcommand{\TABLE}{\texttt{table}}
24 \newcommand{\SP}{\texttt{sp}}
25 \newcommand{\SB}{\texttt{sb}}
26 \newcommand{\CELL}{\texttt{cell}}
27 \newcommand{\ROW}{\texttt{row}}
28 \newcommand{\SLDROP}{\blacktriangleleft}
29 \newcommand{\SLDSCRIPT}{\blacktriangleleft_{s}}
30 \newcommand{\NLDROP}{\vartriangleleft}
31 \newcommand{\RGROUP}{\vartriangleleft_{rg}}
32 \newcommand{\NLDGP}{\vartriangleleft_{g}}
33 \newcommand{\NLDSCRIPT}{\vartriangleleft_{s}}
34 \newcommand{\NLDMACRO}{\vartriangleleft_{c}}
35 \newcommand{\NLDTABLE}{\vartriangleleft_{t}}
43 The following tokens are defined:
45 \begin{tabular}{lllp{0.5\textwidth}}
46 \textbf{\TeX{}} & \textbf{Notation} & \textbf{Node} & \textbf{Description} \\
48 \verb+{+ & $\mathrm{begin}$ & \texttt{g} & Beginning of a group \\
49 \verb+}+ & $\mathrm{end}$ & & End of a group \\
50 \verb+$+ & $\$$ & \texttt{math} & Math shift \\ %$ \\
52 \verb+#+$i$ & $p(i)$ & \texttt{p} & Parameter \\
53 \verb+^+ & $\uparrow$ & \texttt{sp} & Superscript \\
54 \verb+_+ & $\downarrow$ & \texttt{sb} & Subscript \\
55 & $\square$ & & Space-like character that can be ignored \\
56 & $s$ & \texttt{s} & Space-like character that may be significant \\
57 letter & $i(v)$ & \texttt{i} & Identifier $v$ \\
58 digit & $n(v)$ & \texttt{n} & Number $v$ \\
59 other & $o(v)$ & \texttt{o} & Other character or operator $v$ \\
60 \verb+~+ & $\sim$ & & Active character \\
61 \verb+%+ & $\%$ & & Comment \\
62 control & $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$ & \texttt{c} &
63 Control sequence $v$ that expects the $\alpha_1,\dots,\alpha_n$ sequence of tokens. \\
64 backspace & $\vartriangleleft$ & & \\
65 backspace & $\blacktriangleleft$ & & \\
68 %% Some tokens are mapped directly into nodes of the TML tree. The following functions shows
71 \begin{tabular}{r@{\quad$=$\quad}l}
72 $\tmap{\{}$ & \verb+g+ \\
73 $\tmap{p(i)}$ & \verb+p[@index=+$i$\verb+]+ \\
74 $\tmap{p_l(i)}$ & \verb+p[@index=+$i$\verb+][@left-open='1']+ \\
75 $\tmap{p_r(i)}$ & \verb+p[@index=+$i$\verb+][@right-open='1']+ \\
76 $\tmap{s}$ & \verb+s+ \\
77 $\tmap{\uparrow}$ & \verb+sp+ \\
78 $\tmap{\downarrow}$ & \verb+sb+ \\
79 $\tmap{i(v)}$ & \verb+i[@value=+$v$\verb+]+ \\
80 $\tmap{n(v)}$ & \verb+n[@value=+$v$\verb+]+ \\
81 $\tmap{o(v)}$ & \verb+o[@value=+$v$\verb+]+ \\
82 $\tmap{c(v)\langle\alpha_1,\dots,\alpha_n\rangle}$ & \verb+c[@name=+$v$\verb+][^+$\tmap{\alpha_1}\cdots\tmap{\alpha_n}$\verb+$]+\\
86 %% \section{Description and Semantics of the Pattern Language}
89 %% \mathit{NodeTest} & ::= & \mathtt{*} \\
90 %% & | & \mathit{ElementType} \\
91 %% & | & \mathtt{<}~\mathit{ElementTypePattern}~\mathtt{>} \\[1ex]
92 %% \mathit{ElementTypePattern} & ::= & \mathtt{*} \\
93 %% & | & \mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^* \\
94 %% & | & \mathtt{!}\mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^*\\[1ex]
95 %% \mathit{NodePattern} & ::= & \mathit{NodeTest}~\mathit{AttributeQualifier}^*\\[1ex]
96 %% \mathit{AttributeQualifier} & ::= & \mathtt{[@}\mathit{AttributeTest}\mathtt{]}\\
97 %% & | & \mathtt{[!@}\mathit{AttributeTest}\mathtt{]}\\[1ex]
98 %% \mathit{AttributeTest} & ::= & \mathit{AttributeName} \\
99 %% & | & \mathit{AttributeName}\mathtt{='}\mathit{Text}\mathtt{'}
102 \section{Insert Rules}
104 \paragraph{Begin Group:} $\{$
107 \item{\verb+table/cursor+}\\
108 create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
109 append the cursor to the \texttt{g} node, append the \texttt{g} node to the \texttt{cell} node,
110 append the \texttt{cell} node to the \texttt{row} node, append the \texttt{row} node to the
112 \item{\verb+cursor+} \\ create a \texttt{g} node, replace the cursor with the new \texttt{g} node,
113 append the cursor to the new \texttt{g} node
116 % CASE: c/g[!@id]/cursor
123 % CASE: c[@table='1']/cursor
125 % create a g node with id, replace the cursor with the fresh g and append
126 % the cursor as only child of it
128 \paragraph{End Group:} $\}$
131 \item{\verb+g[@id]/cursor+}\\
132 remove the cursor, put $\tadvance$ after the \texttt{g} node
133 \item{\verb+row/cell/g/cursor+}\\
134 remove the cursor, put $\tadvance$ after the \texttt{row} node
135 \item{\verb+math/g[!@id]/cursor+}\\
137 \item{\verb+cursor+}\\
141 \paragraph{Math Shift:} $\$$
144 \item{\verb+tex/cursor+}\\
145 create a \texttt{math} node, create a \texttt{g} node, append the \texttt{g} node
146 as child of the \texttt{math} node, append the cursor as child of the \texttt{g} node
147 \item{\verb+math[@display='1']/g[!@id][*#]/cursor+}\\
148 append the cursor as last child of the \texttt{math} node
149 \item{\verb+math/g[!@id][*#]/cursor+}\\
151 \item{\verb+math[!display='1']/g[!@id]/cursor+}\\
152 set \verb+display='1'+ in the \texttt{math} node
153 \item{\verb+math/g[!@id]+}\\
154 append the cursor after the \texttt{math} node
155 \item{\verb+math/cursor+}\\
157 \item{\verb+cursor+} \\
163 % create a math node. create a g node. append g as child of math.
164 % append the cursor as child of g
165 % CASE: math[@display='1']/g[!@id][*#]/cursor
166 % append the cursor as last child of math
167 % CASE: math/g[!@id][*#]/cursor
168 % remove the cursor. Editing is done
169 % CASE: math[!display='1']/g[!@id]/cursor
170 % set the display attribute to '1'
172 % append the cursor after math (?)
174 % remove the cursor. Editing is done
178 \paragraph{Align:} $\&$
181 \item{\verb+g[@id]/cursor+}\\
182 create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
183 append the cursor to the new \texttt{g} node, append the \texttt{cell} node to the
184 the \texttt{row} node ?
185 \item{\verb+row/cell/g/cursor+}\\
186 create the \texttt{g} node, create the \texttt{cell} node, append the cursor
187 as child of the new \texttt{g} node, append the new \texttt{g} node to the new
188 \texttt{cell} node after the old \texttt{cell} node
189 \item{\verb+cursor+}\\
194 % CASE: g[@id]/cursor
195 % create a row node. create a cell node. create a g node. append the
196 % cursor to g, append the g to cell, append the cell to row, ???
197 % CASE: row/cell/g/cursor
198 % create a g node. create a cell node. appent the cursor to g,
199 % append the g to cell, insert the new cell after the existing cell
203 \paragraph{End-of-line:}
208 \paragraph{Parameter:} $p(i)$
212 \paragraph{Superscript:} $\uparrow$
215 \item{\verb+<g|p>[^#]/cursor+}\\
216 create a \SP{} node, create a \G{} node, replace the cursor with the \SP{} node,
217 append the \G{} node as first child of the \SP{} node, append the cursor as last
218 child of the \SP{} node
219 \item{\verb+<g|p>[*#]/cursor+}\\
220 create a \SP{} node, replace \texttt{*} with the \SP{} node, append \texttt{*} to
221 the \SP{} node, append cursor to the \SP{} node
222 \item{\verb+sp[^*#$][!@over='1']/cursor+}\\ %$
223 set \verb+over='1'+ in the \SP{} node
224 \item{\verb+sp[^*#$][@over='1']/cursor+}\\ %$
226 \item{\verb+cursor+}\\
231 % create sp node. create g node, replace cursor with sp, append g to sp, append cursor to sp
233 % create sp node, replace * with sp, append * to sp, append cursor to sp
234 % CASE: sp[^*#$][!@over='1']/cursor
235 % set over='1' in sp node
236 % CASE: sp[^*#$][@over='1']/cursor
241 \paragraph{Subscript:} $\downarrow$
244 \item{\verb+<g|p>[^#]/cursor+}\\
245 create a \SB{} node, create a \G{} node, replace the cursor with the \SB{} node,
246 append the \G{} node as first child of the \SB{} node, append the cursor as last
247 child of the \SB{} node
248 \item{\verb+<g|p>[*#]/cursor+}\\
249 create a \SB{} node, replace \texttt{*} with the \SB{} node, append \texttt{*} to
250 the \SB{} node, append cursor to the \SB{} node
251 \item{\verb+sb[^*#$][!@under='1']/cursor+}\\ %$
252 set \verb+under='1'+ in the \SB{} node
253 \item{\verb+sb[^*#$][@under='1']/cursor+}\\ %$
255 \item{\verb+cursor+}\\
260 % create sb node. create g node, replace cursor with sb, append g to sb, append cursor to sb
262 % create sb node, replace * with sb, append * to sb, append cursor to sb
263 % CASE: sb[^*#$][!@under='1']/cursor
264 % set over='1' in sb node
265 % CASE: sb[^*#$][@under='1']/cursor
270 \paragraph{Ignorable space:} $\square$
272 % do_ignorable_space:
275 \paragraph{Space:} $s$
278 \item{\verb+cursor+}\\
279 create \SNODE{} node, replace cursor with the \SNODE{} node, append
280 $\tadvance$ after \SNODE{} node
284 % create s node, replace cursor with s, append \advance after s
286 \paragraph{Identifier:} $i(v)$
289 \item{\verb+cursor+}\\
290 create an \INODE{}, set \verb+value=+$v$ in the \INODE{}, replace
291 cursor with \INODE{}, append $\tadvance$ after the \INODE{} node
295 % create i node, replace cursor with i, append \advance after i
297 \paragraph{Number:} $n(v)$
300 \item{\verb+cursor+}\\
301 create an \NNODE{}, set \verb+value=+$v$ in the \NNODE{}, replace
302 cursor with \NNODE{}, append $\tadvance$ after the \NNODE{} node
306 % create n node, replace cursor with n, append \advance after n
308 \paragraph{Apostrophe:} $o({}')$
311 \item{\verb+<g/p>[(sp[*#$]/g[o[@name='prime']$])#]/cursor+}\\
312 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
313 append the \ONODE{} to the innermost \G{} node
314 \item{\verb+<g|p>[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor+}\\
315 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
316 append the \ONODE{} to the innermost \G{} node
317 \item{\verb+<g|p>[*#]/cursor+}\\
318 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
319 create a \SP{} node, create a \G{} node, replace \texttt{*} with \SP{} node,
320 append the new \G{} node to the \SP{} node, append the \ONODE{}
321 node to the new \G{} node
322 \item{\verb+<g|p>[^#]/cursor+}\\
324 \item{\verb+cursor+}\\
325 cursor is not in a group, error?
329 % CASE: g[(sp[^*#$]/g[o[@name='prime']$])#]/cursor
330 % append a new o[@name='prime'] node to the inner g node
331 % CASE: g[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor
332 % append a new o[@name='prime'] node to the inner g node
334 % create sp node, create g node, replace * with sp, append * to sp, append g to sp,
335 % append a new o[@name='prime'[ node to the new g node
339 % cursor is not in a group, error?
341 \paragraph{Other:} $o(v)$
343 create an \ONODE{}, set \verb+value=+$v$ in the \ONODE{}, replace
344 cursor with \ONODE{}, append $\tadvance$ after the \ONODE{} node
347 % create o node, replace cursor with o, append \advance after o
349 \paragraph{Active:} $\sim$
354 \paragraph{Comment:} $\%$
359 \paragraph{Begin Environment:} $c(\mathtt{begin})\langle\alpha_1,\dots,\alpha_n\rangle$
361 \paragraph{End Environment:} $c(\mathtt{end})\langle\rangle$
363 \paragraph{Left Delimiter:} $c(\mathtt{left})\langle\alpha\rangle$
365 \paragraph{Right Delimiter:} $c(\mathtt{right})\langle\alpha\rangle$
367 \paragraph{Carriage-Return:} $c(\mathtt{cr})\langle\rangle$
370 \item{\verb+row/cell/g/cursor+}\\
371 create a \ROW{} node, create a \CELL{} node, create a \G{}
372 node, append the cursor to the new \G{} node, append the new \G{}
373 node to the new \CELL{} node, append the new \CELL{} node to the
374 new \ROW{} node, insert the new \ROW{} node after the old \ROW{} node
375 \item{\verb+cursor+}\\
380 % CASE: row/cell/g/cursor
381 % create row node, create cell node, create g node,
382 % append cursor to g, append g to cell, append cell to row,
383 % insert new row after old row
387 \paragraph{Macro:} $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$
390 \item{\verb+<p|g>/cursor+}\\
391 create a \CNODE{} node with the children corresponding to the pattern
392 $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
393 the new \CNODE{} node. put $\tnext$ as the first child of the new
396 \item{\verb+*/cursor+}\\
397 create a \CNODE{} node with the children corresponding to the pattern
398 $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
399 the new \CNODE{} node, put $\tnext$ as the first child of the new
400 \CNODE{} node. If $n\ne0$ emit a warning (the macro has arguments but
401 but the context wouldn't normally allow them to be entered)
406 % create a c node with children corresponding to the pattern of the macro
407 % append \nextparam as first child of the macro
409 \section{Left Drop Rules}
411 \paragraph{Normal Left Drop:} $\NLDROP$
415 \item{\verb+cursor+}\\
416 replace the cursor with the $\NLDROP$.
420 \paragraph{Special Left Drop:} $\SLDROP$
424 %*******************************************************************************************************
425 %************** rules handling the case in which the cursor has a preceding node ***********************
426 %*******************************************************************************************************
428 %************** cursor's parent is a group or a parameter (a p node)
430 \item{\verb+<g|p>[(i|n|o|s|c[!*])#]/cursor+}\\
433 \item{\verb+<g|p>[g#]/cursor+}\\
434 remove the cursor and append it to the \G{} node.
436 \item{\verb+<g|p>[<sp|sb>#]cursor+}\\
437 remove the cursor and append the $\SLDSCRIPT$
439 \item{\verb+<g|p>[c[p[@right-open="1"]$]#]/cursor+}\\
440 remove the cursor and append the it to the \PNODE{} node.
442 % remember to add the rules handling the primes
444 %*************************************************************************************************
445 %*********** rules handling the case in which the cursor has no preceding nodes ******************
446 %*************************************************************************************************
448 \item{\verb+g[@id][^#$]/cursor+}\\
449 replace the \G{} node with the cursor.
453 \section{Right Drop Rules}
455 \section{$\varepsilon$-rules}
457 \paragraph{Nromal Left Drop}
461 %**************************************************************************************
462 %****************************** epsilon-rules with \NLDROP ****************************
463 %**************************************************************************************
465 %***************************** \NLDROP has no preceding nodes *************************
467 \item{\verb+math[^#$]/+$\NLDROP$}\\
468 replace the $\NLDROP$ with the cursor.
470 \item{\verb+g[^#$]/+$\NLDROP$}\\
471 replace the \G{} node with the $\NLDROP$.
473 % this rule overrides the rule above
474 \item{\verb+math/g[^#$]/+$\NLDROP$}\\
475 replace the $\NLDROP$ with the cursor.
477 \item{\verb+c/p[^#$]/+$\NLDROP$}\\
478 remove the $\NLDROP$ and insert it before the \PNODE{} node.
480 \item{\verb+cell[^#$]/+$\NLDROP$}\\
481 replace the cell with the $\NLDROP_n$.
483 \item{\verb+table[^#$]/+$\NLDROP$}\\
484 replace the \TABLE{} node with the $\NLDROP$.
486 \item{\verb+c[p[@left-open='1'][*]#$]/p[@right-open='1'][^#$]/+$\NLDROP$}\\
487 replace the \CNODE{} node with the content of the first \PNODE{} node and insert the $\NLDROP$ after this content
489 \item{\verb+c[p[@left-open='1'][!*]#$]/p[@right-open='1'][^#$]/+$\NLDROP$}\\
490 replace the \CNODE{} node with the $\NLDROP$.
492 \item{\verb+c[^#][!p(*)]/+$\NLDROP$}\\
493 replace the \CNODE{} node with the $\NLDROP$.
495 %************************* \NLDROP has at least one preceding node *********************
499 % this rule should also handles the case where the \NLDROP is the third (and last) child of a script.
500 \item{\verb+*[*#]/+$\NLDROP$}\\
501 remove the $\NLDROP$ and append it as the last child of its ex preceding brother.
503 % this rule overrides the one above
504 \item{\verb+*[<i|n|o|s>#]/+$\NLDROP$}\\
505 remove the $\NLDROP$ and replace the token with the $\NLDROP_n$.
509 \item{\verb+<sp|sb>[^*#$]+/$\NLDROP$}\\
510 replace the script node with its first child and insert the $\NLDROP$ after it.
512 % this rule overrides the one above.
513 \item{\verb+<sp|sb>[^g[!@id][!*]#$]/+$\NLDROP$}\\
514 replace the script with the cursor.
516 % this rule overrides the one above
517 \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']++\verb+o[@name='prime']$]]#]/+$\NLDROP$}\\
518 remove the last \ONODE{} node and replace the $\NLDROP$ with the %$\NLDROP_n$.
520 \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']$]]#]/+$\NLDROP$}\\
521 replace the script with its first child and replace the $\NLDROP$ with the cursor.%$\NLDROP_n$.
523 \item{\verb+c[(i|n|o|s|c[!*])#]/+$\NLDROP$}\\
524 move the $\NLDROP$ before the delimiter.
526 % this rule is true for both right-open and parameterized macros.
527 \item{\verb+c[p#]/+$\NLDROP$}\\
528 move the $\NLDROP$ into the \PNODE{} node.
530 %****************************************************************************************
531 %***************************** epsilon-rules with \NLDROP_n *****************************
532 %****************************************************************************************
534 \item{\verb+*[*#]/+$\NLDROP_n$}\\
535 replace the $\NLDROP_n$ with the cursor.
537 \item{\verb+row[cell#]/+$\NLDROP_n$}\\
538 remove the $\NLDROP_n$ and append the cursor as the last child of the \CELL{} node.
540 \item{\verb+row[^#$]/+$\NLDROP_n$}\\
541 replace the \ROW{} node with the $\NLDROP_n$
543 \item{\verb+table[row#]/+$\NLDROP_n$}\\
544 remove the $\NLDROP_n$ and append it as last child of the \ROW{} node.
546 \item{\verb+table[^#$]/+$\NLDROP_n$}\\
547 replace the \texttt{table} with the cursor.$\NLDROP_n$.
549 \item{\verb+g[@id][^#$]/+$\NLDROP_n$}\\
550 replace the \G{} node with the $\NLDROP_n$.
554 \paragraph{Special Left Drop}
563 \item{\verb+g/+$\tadvance$}\\
564 replace $\tadvance$ with the cursor
566 \item{\verb+p[#$]/+$\tadvance$}\\ %$
567 put $\tadvance$ after the \PNODE{} node
569 \item{\verb+c[#p]/+$\tadvance$} \\
570 remove $\tadvance$, put the cursor as first child of the \PNODE{} node
572 \item{\verb+c[#*]/+$\tadvance$} \\ %$
573 replace $\tadvance$ with the cursor
575 \item{\verb+c[#$]/+$\tadvance$} \\ %$
576 move $\tadvance$ after the \CNODE{} node
579 \paragraph{Next Parameter}
581 \paragraph{Next Token}
583 %% \begin{description}
584 %% \item{\verb+c[#p]/+$\tnext$} \\
587 % g[@id]/(c[#$][@right-open]/g[!@id][#$]/)+cursor } let p = cursor.parent() in remove; advance(p)
591 % */cursor { let g = new group in replace
593 % g[@id][^#$]/cursor <= cursor.parent().replace(cursor)
594 % g[@id][^#$]/cursor <- cursor
595 % (!g[@id][^#$])[A#B]/(g[@id][^#$]/)+cursor <- (!g[@id][^#$])[A#B]/cursor