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{\NLDROP}{\vartriangleleft}
30 \newcommand{\RGROUP}{\vartriangleleft_{rg}}
31 \newcommand{\NLDGP}{\vartriangleleft_{g}}
32 \newcommand{\NLDSCRIPT}{\vartriangleleft_{s}}
33 \newcommand{\NLDMACRO}{\vartriangleleft_{c}} % at the moment it's not used.
41 The following tokens are defined:
43 \begin{tabular}{lllp{0.5\textwidth}}
44 \textbf{\TeX{}} & \textbf{Notation} & \textbf{Node} & \textbf{Description} \\
46 \verb+{+ & $\mathrm{begin}$ & \texttt{g} & Beginning of a group \\
47 \verb+}+ & $\mathrm{end}$ & & End of a group \\
48 \verb+$+ & $\$$ & \texttt{math} & Math shift \\ %$ \\
50 \verb+#+$i$ & $p(i)$ & \texttt{p} & Parameter \\
51 \verb+^+ & $\uparrow$ & \texttt{sp} & Superscript \\
52 \verb+_+ & $\downarrow$ & \texttt{sb} & Subscript \\
53 & $\square$ & & Space-like character that can be ignored \\
54 & $s$ & \texttt{s} & Space-like character that may be significant \\
55 letter & $i(v)$ & \texttt{i} & Identifier $v$ \\
56 digit & $n(v)$ & \texttt{n} & Number $v$ \\
57 other & $o(v)$ & \texttt{o} & Other character or operator $v$ \\
58 \verb+~+ & $\sim$ & & Active character \\
59 \verb+%+ & $\%$ & & Comment \\
60 control & $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$ & \texttt{c} &
61 Control sequence $v$ that expects the $\alpha_1,\dots,\alpha_n$ sequence of tokens. \\
62 backspace & $\vartriangleleft$ & & \\
63 backspace & $\blacktriangleleft$ & & \\
66 %% Some tokens are mapped directly into nodes of the TML tree. The following functions shows
69 \begin{tabular}{r@{\quad$=$\quad}l}
70 $\tmap{\{}$ & \verb+g+ \\
71 $\tmap{p(i)}$ & \verb+p[@index=+$i$\verb+]+ \\
72 $\tmap{p_l(i)}$ & \verb+p[@index=+$i$\verb+][@left-open='1']+ \\
73 $\tmap{p_r(i)}$ & \verb+p[@index=+$i$\verb+][@right-open='1']+ \\
74 $\tmap{s}$ & \verb+s+ \\
75 $\tmap{\uparrow}$ & \verb+sp+ \\
76 $\tmap{\downarrow}$ & \verb+sb+ \\
77 $\tmap{i(v)}$ & \verb+i[@value=+$v$\verb+]+ \\
78 $\tmap{n(v)}$ & \verb+n[@value=+$v$\verb+]+ \\
79 $\tmap{o(v)}$ & \verb+o[@value=+$v$\verb+]+ \\
80 $\tmap{c(v)\langle\alpha_1,\dots,\alpha_n\rangle}$ & \verb+c[@name=+$v$\verb+][^+$\tmap{\alpha_1}\cdots\tmap{\alpha_n}$\verb+$]+\\
84 %% \section{Description and Semantics of the Pattern Language}
87 %% \mathit{NodeTest} & ::= & \mathtt{*} \\
88 %% & | & \mathit{ElementType} \\
89 %% & | & \mathtt{<}~\mathit{ElementTypePattern}~\mathtt{>} \\[1ex]
90 %% \mathit{ElementTypePattern} & ::= & \mathtt{*} \\
91 %% & | & \mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^* \\
92 %% & | & \mathtt{!}\mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^*\\[1ex]
93 %% \mathit{NodePattern} & ::= & \mathit{NodeTest}~\mathit{AttributeQualifier}^*\\[1ex]
94 %% \mathit{AttributeQualifier} & ::= & \mathtt{[@}\mathit{AttributeTest}\mathtt{]}\\
95 %% & | & \mathtt{[!@}\mathit{AttributeTest}\mathtt{]}\\[1ex]
96 %% \mathit{AttributeTest} & ::= & \mathit{AttributeName} \\
97 %% & | & \mathit{AttributeName}\mathtt{='}\mathit{Text}\mathtt{'}
100 \section{Insert Rules}
102 \paragraph{Begin Group:} $\{$
105 \item{\verb+table/cursor+}\\
106 create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
107 append the cursor to the \texttt{g} node, append the \texttt{g} node to the \texttt{cell} node,
108 append the \texttt{cell} node to the \texttt{row} node, append the \texttt{row} node to the
110 \item{\verb+cursor+} \\ create a \texttt{g} node, replace the cursor with the new \texttt{g} node,
111 append the cursor to the new \texttt{g} node
114 % CASE: c/g[!@id]/cursor
121 % CASE: c[@table='1']/cursor
123 % create a g node with id, replace the cursor with the fresh g and append
124 % the cursor as only child of it
126 \paragraph{End Group:} $\}$
129 \item{\verb+g[@id]/cursor+}\\
130 remove the cursor, put $\tadvance$ after the \texttt{g} node
131 \item{\verb+row/cell/g/cursor+}\\
132 remove the cursor, put $\tadvance$ after the \texttt{row} node
133 \item{\verb+math/g[!@id]/cursor+}\\
135 \item{\verb+cursor+}\\
139 \paragraph{Math Shift:} $\$$
142 \item{\verb+tex/cursor+}\\
143 create a \texttt{math} node, create a \texttt{g} node, append the \texttt{g} node
144 as child of the \texttt{math} node, append the cursor as child of the \texttt{g} node
145 \item{\verb+math[@display='1']/g[!@id][*#]/cursor+}\\
146 append the cursor as last child of the \texttt{math} node
147 \item{\verb+math/g[!@id][*#]/cursor+}\\
149 \item{\verb+math[!display='1']/g[!@id]/cursor+}\\
150 set \verb+display='1'+ in the \texttt{math} node
151 \item{\verb+math/g[!@id]+}\\
152 append the cursor after the \texttt{math} node
153 \item{\verb+math/cursor+}\\
155 \item{\verb+cursor+} \\
161 % create a math node. create a g node. append g as child of math.
162 % append the cursor as child of g
163 % CASE: math[@display='1']/g[!@id][*#]/cursor
164 % append the cursor as last child of math
165 % CASE: math/g[!@id][*#]/cursor
166 % remove the cursor. Editing is done
167 % CASE: math[!display='1']/g[!@id]/cursor
168 % set the display attribute to '1'
170 % append the cursor after math (?)
172 % remove the cursor. Editing is done
176 \paragraph{Align:} $\&$
179 \item{\verb+g[@id]/cursor+}\\
180 create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
181 append the cursor to the new \texttt{g} node, append the \texttt{cell} node to the
182 the \texttt{row} node ?
183 \item{\verb+row/cell/g/cursor+}\\
184 create the \texttt{g} node, create the \texttt{cell} node, append the cursor
185 as child of the new \texttt{g} node, append the new \texttt{g} node to the new
186 \texttt{cell} node after the old \texttt{cell} node
187 \item{\verb+cursor+}\\
192 % CASE: g[@id]/cursor
193 % create a row node. create a cell node. create a g node. append the
194 % cursor to g, append the g to cell, append the cell to row, ???
195 % CASE: row/cell/g/cursor
196 % create a g node. create a cell node. appent the cursor to g,
197 % append the g to cell, insert the new cell after the existing cell
201 \paragraph{End-of-line:}
206 \paragraph{Parameter:} $p(i)$
210 \paragraph{Superscript:} $\uparrow$
213 \item{\verb+<g|p>[^#]/cursor+}\\
214 create a \SP{} node, create a \G{} node, replace the cursor with the \SP{} node,
215 append the \G{} node as first child of the \SP{} node, append the cursor as last
216 child of the \SP{} node
217 \item{\verb+<g|p>[*#]/cursor+}\\
218 create a \SP{} node, replace \texttt{*} with the \SP{} node, append \texttt{*} to
219 the \SP{} node, append cursor to the \SP{} node
220 \item{\verb+sp[^*#$][!@over='1']/cursor+}\\ %$
221 set \verb+over='1'+ in the \SP{} node
222 \item{\verb+sp[^*#$][@over='1']/cursor+}\\ %$
224 \item{\verb+cursor+}\\
229 % create sp node. create g node, replace cursor with sp, append g to sp, append cursor to sp
231 % create sp node, replace * with sp, append * to sp, append cursor to sp
232 % CASE: sp[^*#$][!@over='1']/cursor
233 % set over='1' in sp node
234 % CASE: sp[^*#$][@over='1']/cursor
239 \paragraph{Subscript:} $\downarrow$
242 \item{\verb+<g|p>[^#]/cursor+}\\
243 create a \SB{} node, create a \G{} node, replace the cursor with the \SB{} node,
244 append the \G{} node as first child of the \SB{} node, append the cursor as last
245 child of the \SB{} node
246 \item{\verb+<g|p>[*#]/cursor+}\\
247 create a \SB{} node, replace \texttt{*} with the \SB{} node, append \texttt{*} to
248 the \SB{} node, append cursor to the \SB{} node
249 \item{\verb+sb[^*#$][!@under='1']/cursor+}\\ %$
250 set \verb+under='1'+ in the \SB{} node
251 \item{\verb+sb[^*#$][@under='1']/cursor+}\\ %$
253 \item{\verb+cursor+}\\
258 % create sb node. create g node, replace cursor with sb, append g to sb, append cursor to sb
260 % create sb node, replace * with sb, append * to sb, append cursor to sb
261 % CASE: sb[^*#$][!@under='1']/cursor
262 % set over='1' in sb node
263 % CASE: sb[^*#$][@under='1']/cursor
268 \paragraph{Ignorable space:} $\square$
270 % do_ignorable_space:
273 \paragraph{Space:} $s$
276 \item{\verb+cursor+}\\
277 create \SNODE{} node, replace cursor with the \SNODE{} node, append
278 $\tadvance$ after \SNODE{} node
282 % create s node, replace cursor with s, append \advance after s
284 \paragraph{Identifier:} $i(v)$
287 \item{\verb+cursor+}\\
288 create an \INODE{}, set \verb+value=+$v$ in the \INODE{}, replace
289 cursor with \INODE{}, append $\tadvance$ after the \INODE{} node
293 % create i node, replace cursor with i, append \advance after i
295 \paragraph{Number:} $n(v)$
298 \item{\verb+cursor+}\\
299 create an \NNODE{}, set \verb+value=+$v$ in the \NNODE{}, replace
300 cursor with \NNODE{}, append $\tadvance$ after the \NNODE{} node
304 % create n node, replace cursor with n, append \advance after n
306 \paragraph{Apostrophe:} $o({}')$
309 \item{\verb+<g/p>[(sp[*#$]/g[o[@name='prime']$])#]/cursor+}\\
310 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
311 append the \ONODE{} to the innermost \G{} node
312 \item{\verb+<g|p>[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor+}\\
313 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
314 append the \ONODE{} to the innermost \G{} node
315 \item{\verb+<g|p>[*#]/cursor+}\\
316 create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
317 create a \SP{} node, create a \G{} node, replace \texttt{*} with \SP{} node,
318 append the new \G{} node to the \SP{} node, append the \ONODE{}
319 node to the new \G{} node
320 \item{\verb+<g|p>[^#]/cursor+}\\
322 \item{\verb+cursor+}\\
323 cursor is not in a group, error?
327 % CASE: g[(sp[^*#$]/g[o[@name='prime']$])#]/cursor
328 % append a new o[@name='prime'] node to the inner g node
329 % CASE: g[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor
330 % append a new o[@name='prime'] node to the inner g node
332 % create sp node, create g node, replace * with sp, append * to sp, append g to sp,
333 % append a new o[@name='prime'[ node to the new g node
337 % cursor is not in a group, error?
339 \paragraph{Other:} $o(v)$
341 create an \ONODE{}, set \verb+value=+$v$ in the \ONODE{}, replace
342 cursor with \ONODE{}, append $\tadvance$ after the \ONODE{} node
345 % create o node, replace cursor with o, append \advance after o
347 \paragraph{Active:} $\sim$
352 \paragraph{Comment:} $\%$
357 \paragraph{Begin Environment:} $c(\mathtt{begin})\langle\alpha_1,\dots,\alpha_n\rangle$
359 \paragraph{End Environment:} $c(\mathtt{end})\langle\rangle$
361 \paragraph{Left Delimiter:} $c(\mathtt{left})\langle\alpha\rangle$
363 \paragraph{Right Delimiter:} $c(\mathtt{right})\langle\alpha\rangle$
365 \paragraph{Carriage-Return:} $c(\mathtt{cr})\langle\rangle$
368 \item{\verb+row/cell/g/cursor+}\\
369 create a \ROW{} node, create a \CELL{} node, create a \G{}
370 node, append the cursor to the new \G{} node, append the new \G{}
371 node to the new \CELL{} node, append the new \CELL{} node to the
372 new \ROW{} node, insert the new \ROW{} node after the old \ROW{} node
373 \item{\verb+cursor+}\\
378 % CASE: row/cell/g/cursor
379 % create row node, create cell node, create g node,
380 % append cursor to g, append g to cell, append cell to row,
381 % insert new row after old row
385 \paragraph{Macro:} $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$
388 \item{\verb+<p|g>/cursor+}\\
389 create a \CNODE{} node with the children corresponding to the pattern
390 $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
391 the new \CNODE{} node. put $\tnext$ as the first child of the new
394 \item{\verb+*/cursor+}\\
395 create a \CNODE{} node with the children corresponding to the pattern
396 $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
397 the new \CNODE{} node, put $\tnext$ as the first child of the new
398 \CNODE{} node. If $n\ne0$ emit a warning (the macro has arguments but
399 but the context wouldn't normally allow them to be entered)
404 % create a c node with children corresponding to the pattern of the macro
405 % append \nextparam as first child of the macro
407 \section{Left Drop Rules}
409 \paragraph{Normal Left Drop:} $\NLDROP$
413 % in the rules below, a token is either an i node, an n node, an o node, an s node or an empty c node.
414 % an empty c node is either an undefined macro or an empty macro. These c node are handled as they actually were
415 % tokens (i, n, o, s).
416 % An important observation is: a sequence of groups with id, in which every group has one and only one child and where
417 % the last group contains the cursor, is equivalent to the cursor (Is it clear?). For example:
418 % <g id="id1"><g id="id2">...<g id="idn"><cursor/></g>...</g></g> is equivalent to:
421 %************************************************************************************************************
422 %************************** there is at least one node preceding the cursor *********************************
423 %************************************************************************************************************
425 %************************** cursor's parent is a group or a parameter (p node).
427 \item{\verb+<g|p>[(i|n|o|s|c[!*])#]/(g[@id][^#$]/++\verb+)?cursor+}\\
428 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and replace the token with the cursor.
430 \item{\verb+g[@id][(i|n|o|s|c[!*])#]/(g[@id][^#$]/++\verb+)?cursor+}\\
431 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and replace the token with the $\RGROUP$.
433 \item{\verb+<g|p>[g#]/(g[@id][^#$]/++\verb+)?cursor+}\\
434 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and append $\NLDGP$ to the \G{} node preceding the cursor.
436 \item{\verb+<g|p>[<sp|sb>#]/(g[@id][^#$]/++\verb+)?cursor+}\\
437 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and append the $\NLDSCRIPT$ to script node.
439 \item{\verb+<g|p>[c[p[@right-open="1"]$]#]/(g[@id][^#$]/++\verb+)?cursor+}\\
440 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and apeend the $\NLDGP$ to the \PNODE{} node.
442 % we don't have this kind of macro
443 %\item{\verb+<g|p>[c[^p[@left-open="1"]$]#]/(g[@id][^#$]/++\verb+)?cursor+}\\
445 \item{\verb+<g|p>[c[p[!@left-open="1"][!@right-open="1"](c[!*]|i|n|o|s)*$]#]/(g[@id][^#$]/++\verb+)?cursor+}\\
446 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and append the $\NLDGP$ to the \PNODE{} node.
448 \item{\verb+*[sp[^*g[!@id][^o[@name="prime"]$]]#]/(g[@id][^#$]/++\verb+)?cursor+}\\
449 replace (if present) the sequence of \G{} nodes with attribute \texttt{id} with the cursor and replace the \SP{} node with its first child.
451 \item{\verb+*[sp[^*g[!@id][^o[@name="prime"]++\verb+o[@name="prime"]$]]#]/(g[@id][^#$]/++\verb+)?cursor+}\\
452 replace (if present) the sequence of \G{} nodes with attribute \texttt{id} with the cursor and remove the last \ONODE{}, which is \G{} node's child.
454 %************************************ cursor's parent is a script
456 \item{\verb+<g|p>/<sp|sb>[(i|n|o|s|c[!*])#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
457 remove replace the script with the cursor.
459 \item{\verb+g[@id]/<sp|sb>[(i|n|o|s|c[!*])#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
460 replace the script with the $\RGROUP$.
462 \item{\verb+<sp|sb>[g#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
463 repalce the script with it's first child (the \G{} node) and append the $\NLDGP$ to it.
465 \item{\verb+<sp|sb>[^c[p[@right-open="1"]$]#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
466 remove the cursor (and eventually the sequence of \G{} nodes with attribute \texttt{id}) and append the $\NLDGP$ to the \PNODE{} node.
468 % we don't have a macro of this kind
469 %\item{\verb+<sp|sb>[^c[^p[@left-open="1"]$]#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
471 \item{\verb+<sp|sb>[^c[p[!@left-open="1"][!@right-open="1"](c[!*]|i|n|o|s)*$]#$]/(g[@id][^#$]/++\verb+)?cursor+}\\
472 replace the script with the \CNODE{} node and append the $\NLDGP$ to the \PNODE{} node.
476 \paragraph{Special Left Drop:} $\SLDROP$
480 %*******************************************************************************************************
481 %************** rules handling the case in which the cursor has a preceding node ***********************
482 %*******************************************************************************************************
484 %*************************************************************************************************
485 %*********** rules handling the case in which the cursor has no preceding nodes ******************
486 %*************************************************************************************************
490 \section{Right Drop Rules}
492 \section{$\varepsilon$-rules}
494 \paragraph{Nromal Left Drop}
498 %********************* epsilon rules concerning the rgreplace_father ********************
500 \item{\verb+(g[@id][^#$]/++\verb+)+$\RGROUP$}\\
501 replace the whole fragment with the cursor.
503 \item{\verb+*[!@id]/+$\RGROUP$}\\
504 replace the $\RGROUP$ with the cursor.
506 \item{\verb+g[@id][*#]/+$\RGROUP$}\\
507 replace the $\RGROUP$ with the cursor
509 \item{\verb+g[@id][#*]/+$\RGROUP$}\\
510 replace the $\RGROUP$ with the cursor.
511 % maybe it's not the correct action
515 \paragraph{Special Left Drop}
524 \item{\verb+g/+$\tadvance$}\\
525 replace $\tadvance$ with the cursor
527 \item{\verb+p[#$]/+$\tadvance$}\\ %$
528 put $\tadvance$ after the \PNODE{} node
530 \item{\verb+c[#p]/+$\tadvance$} \\
531 remove $\tadvance$, put the cursor as first child of the \PNODE{} node
533 \item{\verb+c[#*]/+$\tadvance$} \\ %$
534 replace $\tadvance$ with the cursor
536 \item{\verb+c[#$]/+$\tadvance$} \\ %$
537 move $\tadvance$ after the \CNODE{} node
540 \paragraph{Next Parameter}
542 \paragraph{Next Token}
544 %% \begin{description}
545 %% \item{\verb+c[#p]/+$\tnext$} \\
548 % g[@id]/(c[#$][@right-open]/g[!@id][#$]/)+cursor } let p = cursor.parent() in remove; advance(p)
552 % */cursor { let g = new group in replace
554 % g[@id][^#$]/cursor <= cursor.parent().replace(cursor)
555 % g[@id][^#$]/cursor <- cursor
556 % (!g[@id][^#$])[A#B]/(g[@id][^#$]/)+cursor <- (!g[@id][^#$])[A#B]/cursor