helm/DEVEL/mathml_editor/doc/spec.tex

   1 \documentclass[10pt]{article}
   2
   3 \usepackage{a4wide}
   4 \usepackage{palatino}
   5 \usepackage{euler}
   6 \usepackage{amssymb}
   7 \usepackage{stmaryrd}
   8 \usepackage{wasysym}
   9
  10 \title{\EdiTeX: a MathML Editor Based on \TeX{} Syntax\\\small Description and Formal Specification}
  11 \author{Paolo Marinelli\\Luca Padovani\\\small\{{\tt pmarinel},{\tt lpadovan}\}{\tt @cs.unibo.it}\\\small Department of Computer Science\\\small University of Bologna}
  12 \date{}
  13
  14 \newcommand{\EdiTeX}{Edi\TeX}
  15
  16 \newcommand{\tmap}[1]{\llbracket#1\rrbracket}
  17 \newcommand{\tadvance}{\vartriangle}
  18 \newcommand{\tnext}{\rhd}
  19 \newcommand{\G}{\texttt{g}}
  20 \newcommand{\PNODE}{\texttt{p}}
  21 \newcommand{\SNODE}{\texttt{s}}
  22 \newcommand{\INODE}{\texttt{i}}
  23 \newcommand{\NNODE}{\texttt{n}}
  24 \newcommand{\ONODE}{\texttt{o}}
  25 \newcommand{\CNODE}{\texttt{c}}
  26 \newcommand{\TABLE}{\texttt{table}}
  27 \newcommand{\SP}{\texttt{sp}}
  28 \newcommand{\SB}{\texttt{sb}}
  29 \newcommand{\CELL}{\texttt{cell}}
  30 \newcommand{\ROW}{\texttt{row}}
  31 \newcommand{\SLDROP}{\blacktriangleleft}
  32 \newcommand{\NLDROP}{\vartriangleleft}
  33 \newcommand{\RDROP}{\vartriangleright}
  34
  35 \begin{document}
  36
  37 \maketitle
  38
  39 \section{Introduction}
  40
  41 MathML~\cite{MathML1,MathML2,MathML2E} is an XML application for the
  42 representation of mathematical expressions. As most XML applications,
  43 MathML is unsuitable to be hand-written, except for the simplest
  44 cases, because of its verbosity. In fact, the MathML specification
  45 explicitly states that
  46 \begin{quote}
  47 ``While MathML is human-readable, it is anticipated that, in all but
  48 the simplest cases, authors will use equation editors, conversion
  49 programs, and other specialized software tools to generate MathML''
  50 \end{quote}
  51
  52 The statement about human readability of MathML is already too strong,
  53 as the large number of mathematical symbols, operators, and
  54 diacritical marks that are used in mathematical notation cause MathML
  55 documents to make extensive use of Unicode characters that typically
  56 are not in the ``visible'' range of common text editors. Such
  57 characters may appear as entity references, whose name indicates
  58 somehow the kind of symbol used, or character references or they are
  59 directly encoded in the document encoding scheme (for instance,
  60 UTF-8).
  61
  62 It is thus obvious that authoring MathML documents assumes the
  63 assistance of dedicated tools. As of today, such tools can be
  64 classified into two main categories:
  65 \begin{enumerate}
  66   \item WYSIWYG (What You See Is What You Get) editors that allow the
  67     author to see the formatted document on the screen as it is
  68     composed;
  69   \item conversion tools that generate MathML markup from different
  70     sources, typically other markup languages for scientific
  71     documents, such as \TeX.
  72 \end{enumerate}
  73
  74 While the former tools are certainly more appealing, especially to the
  75 unexperienced user, as they give a direct visual feedback, the
  76 existance of tools in the second category takes into account the large
  77 availability of existing documents in \TeX{} format, and also the fact
  78 that experienced or ``lazy'' users may continue to prefer the use of a
  79 markup language other than MathML for editing, and generate MathML
  80 only as a final step of the authoring process. The ``laziness'' is not
  81 really intended as a way of being reluctant towards a new technology,
  82 but rather as a justified convincement that WYSIWYG editors are ``nice
  83 to look at'' but after all they may slow down the authoring process.
  84 WYSIWYG editors often involve the use of menus, palettes of symbols,
  85 and, in general, an extensive use of the pointing device (the mouse)
  86 for completing most operations. The use of shortcuts is of little
  87 help, as it implies very soon a challenging exercise for the fingers
  88 and the mind. Moreover, authors \emph{cannot improve} their authoring
  89 speed with time.  On the other side, the gap between the syntax of any
  90 markup language for mathematics and mathematical notation may be
  91 relevant, especially for large, non-trivial formulas and authoring is
  92 a re-iterated process in which the author repeadtedly types the markup
  93 in the editor, compiles, and looks at the result inside a pre-viewer.
  94
  95 \EdiTeX{} tries to synthesize the ``best of both worlds'' in a single
  96 tool. The basic idea is that of creating a WYSIWYG editor in which
  97 editing is achieved by typing \TeX{} markup as the author would do in
  98 a text editor. The \TeX{} markup is tokenized and parsed on-the-fly
  99 and a corresponding MathML representation is created and
 100 displayed. This way, the author can see the rendered document as it
 101 changes. The advantages of this approach can be summarized as follows:
 102 \begin{itemize}
 103   \item the document is rendered concurrently with the editing, the
 104     user has an immediate feedback hence it is easier to spot errors;
 105   \item the author types in a concrete (and likely familiar) syntax
 106     improving the editing speed;
 107   \item the usual WYSIWYG mechanisms are still available. In
 108     particular, it is possible to select \emph{visually} a fragment of
 109     the document that needs re-editing, or that was left behind for
 110     subsequent editing.
 111 \end{itemize}
 112
 113 \paragraph{The Name of the Game:} there is no reference to MathML in
 114 the name ``\EdiTeX.'' In fact, the architecture of the editor is not
 115 tied to MathML markup. Although we focus on MathML editing, by
 116 changing a completely modularized component of the editor it is
 117 virtually possible to generate any other markup language.
 118
 119 \paragraph{Acknowledgments.} Stephen M. Watt and Igor Rodionov for
 120 their work on the \TeX{} to MathML conversion tool; Stan Devitt for an
 121 illuminating discussion about the architecture of \TeX{} to XML
 122 conversion tools; Claudio Sacerdoti Coen for the valuable feedback and
 123 uncountable bug reports.
 124
 125 \section{Architecture}
 126
 127 \section{Customization}
 128
 129 \subsection{Short and Long Identifiers}
 130
 131 \subsection{The Dictionary}
 132
 133 \subsection{Stylesheets and Trasformations}
 134
 135 \subsection{Rendering}
 136
 137 \section{XML Representation of \TeX{} Markup}
 138
 139 \section{Tokens}
 140
 141 The following tokens are defined:
 142
 143 \begin{tabular}{lllp{0.5\textwidth}}
 144   \textbf{\TeX{}} & \textbf{Notation} & \textbf{Node} & \textbf{Description} \\
 145 \hline
 146   \verb+{+ & $\mathrm{begin}$ & \texttt{g} & Beginning of a group \\
 147   \verb+}+ & $\mathrm{end}$ & & End of a group \\
 148   \verb+$+ & $\$$ & \texttt{math} & Math shift \\ %$ \\
 149   & &  & End-of-line \\
 150   \verb+#+$i$ & $p(i)$ & \texttt{p} & Parameter \\
 151   \verb+^+ & $\uparrow$ & \texttt{sp} & Superscript \\
 152   \verb+_+ & $\downarrow$ & \texttt{sb} & Subscript \\
 153   & $\square$ & & Space-like character that can be ignored \\
 154   & $s$ & \texttt{s} & Space-like character that may be significant \\
 155   letter & $i(v)$ & \texttt{i} & Identifier $v$ \\
 156   digit & $n(v)$ & \texttt{n} & Number $v$ \\
 157   other & $o(v)$ & \texttt{o} & Other character or operator $v$ \\
 158   \verb+~+ & $\sim$ & & Active character \\
 159   \verb+%+ & $\%$ & & Comment \\
 160   control & $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$ & \texttt{c} &
 161     Control sequence $v$ that expects the $\alpha_1,\dots,\alpha_n$ sequence of tokens. \\
 162   backspace & $\vartriangleleft$ & & \\
 163   backspace & $\blacktriangleleft$ & & \\
 164 \end{tabular}
 165
 166 %% Some tokens are mapped directly into nodes of the TML tree. The following functions shows
 167 %% the mapping:
 168
 169 \begin{tabular}{r@{\quad$=$\quad}l}
 170   $\tmap{\{}$ & \verb+g+ \\
 171   $\tmap{p(i)}$ & \verb+p[@index=+$i$\verb+]+ \\
 172   $\tmap{p_l(i)}$ & \verb+p[@index=+$i$\verb+][@left-open='1']+ \\
 173   $\tmap{p_r(i)}$ & \verb+p[@index=+$i$\verb+][@right-open='1']+ \\
 174   $\tmap{s}$ & \verb+s+ \\
 175   $\tmap{\uparrow}$ & \verb+sp+ \\
 176   $\tmap{\downarrow}$ & \verb+sb+ \\
 177   $\tmap{i(v)}$ & \verb+i[@value=+$v$\verb+]+ \\
 178   $\tmap{n(v)}$ & \verb+n[@value=+$v$\verb+]+ \\
 179   $\tmap{o(v)}$ & \verb+o[@value=+$v$\verb+]+ \\
 180   $\tmap{c(v)\langle\alpha_1,\dots,\alpha_n\rangle}$ & \verb+c[@name=+$v$\verb+][^+$\tmap{\alpha_1}\cdots\tmap{\alpha_n}$\verb+$]+\\
 181 \end{tabular}
 182 %$
 183
 184 \section{Description and Semantics of the Pattern Language}
 185
 186 %% \begin{eqnarray*}
 187 %%   \mathit{NodeTest} & ::= & \mathtt{*} \\
 188 %%   & | & \mathit{ElementType} \\
 189 %%   & | & \mathtt{<}~\mathit{ElementTypePattern}~\mathtt{>} \\[1ex]
 190 %%   \mathit{ElementTypePattern} & ::= & \mathtt{*} \\
 191 %%   & | & \mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^* \\
 192 %%   & | & \mathtt{!}\mathit{ElementType}~(\mathtt{|}~\mathit{ElementType})^*\\[1ex]
 193 %%   \mathit{NodePattern} & ::= & \mathit{NodeTest}~\mathit{AttributeQualifier}^*\\[1ex]
 194 %%   \mathit{AttributeQualifier} & ::= & \mathtt{[@}\mathit{AttributeTest}\mathtt{]}\\
 195 %%   & | & \mathtt{[!@}\mathit{AttributeTest}\mathtt{]}\\[1ex]
 196 %%   \mathit{AttributeTest} & ::= & \mathit{AttributeName} \\
 197 %%   & | & \mathit{AttributeName}\mathtt{='}\mathit{Text}\mathtt{'}
 198 %% \end{eqnarray*}
 199
 200 \begin{table}
 201 \[
 202 \begin{array}{rcl@{\hspace{3em}}rcl@{\hspace{3em}}rcl}
 203   C &::=& Q\verb+/+       & Q &::=& T                                          & P &::=& P' \\
 204   &|& Q\verb+//+          & &|& Q\verb+[@+n\verb+=+v\verb+]+                   & &|& \verb+^+P'\\
 205   &|& \verb+(+C\verb+)+   & &|& Q\verb+[!@+n\verb+=+v\verb+]+                  & &|& P'\verb+$+\\%$
 206   &|& (\alpha\verb+=+C)   & &|& Q\verb+[@+n\verb+]+                            & &|& \verb+^+P'\verb+$+\\%$
 207   &|& C_1 \verb+&+ C_2    & &|& Q\verb+[+P\verb+]+                             & & &\\
 208   &|& C_1 \verb+|+ C_2    & & &                                                & P' &::=& P''\\
 209   &|& C\verb.+.           & T &::=& N                                          & &|& P''\verb+#+P''\\
 210   &|& C\verb+*+           & &|& C N                                            & & &\\
 211   &|& C\verb+?+           & & &                                                & P'' &::=& \\
 212   &|& C_1~C_2             & N &::=& \verb+<*>+                                 & &|& T\;P''\\
 213   &|& \verb+!+C           & &|& \verb+<+n_1\verb+|+\cdots\verb+|+n_2\verb+>+   & & &\\
 214   & &                     & &|& \verb+<!+n_1\verb+|+\cdots\verb+|+n_2\verb+>+  & & &\\
 215 \end{array}
 216 \]
 217 \caption{Syntax of the pattern language. $n$, $n_i$ denote names, $v$
 218 denotes a string enclosed in single or double quotes}
 219 \end{table}
 220
 221
 222 \section{Insert Rules}
 223
 224 \paragraph{Begin Group:} $\{$
 225
 226 \begin{description}
 227   \item{\verb+table/cursor+}\\
 228    create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
 229     append the cursor to the \texttt{g} node, append the \texttt{g} node to the \texttt{cell} node,
 230     append the \texttt{cell} node to the \texttt{row} node, append the \texttt{row} node to the
 231     \texttt{c} node
 232   \item{\verb+cursor+} \\ create a \texttt{g} node, replace the cursor with the new \texttt{g} node,
 233     append the cursor to the new \texttt{g} node
 234 \end{description}
 235
 236 % CASE: c/g[!@id]/cursor
 237
 238 % CASE: c/cursor
 239
 240 % ELSE:
 241
 242 % do_begin:
 243 % CASE: c[@table='1']/cursor
 244 % ELSE:
 245 %   create a g node with id, replace the cursor with the fresh g and append
 246 %   the cursor as only child of it
 247
 248 \paragraph{End Group:} $\}$
 249
 250 \begin{description}
 251   \item{\verb+g[@id]/cursor+}\\
 252   remove the cursor, put $\tadvance$ after the \texttt{g} node
 253   \item{\verb+row/cell/g/cursor+}\\
 254   remove the cursor, put $\tadvance$ after the \texttt{row} node
 255   \item{\verb+math/g[!@id]/cursor+}\\
 256   ?
 257   \item{\verb+cursor+}\\
 258   error ?
 259 \end{description}
 260
 261 \paragraph{Math Shift:} $\$$
 262
 263 \begin{description}
 264   \item{\verb+tex/cursor+}\\
 265   create a \texttt{math} node, create a \texttt{g} node, append the \texttt{g} node
 266     as child of the \texttt{math} node, append the cursor as child of the \texttt{g} node
 267   \item{\verb+math[@display='1']/g[!@id][*#]/cursor+}\\
 268   append the cursor as last child of the \texttt{math} node
 269   \item{\verb+math/g[!@id][*#]/cursor+}\\
 270   remove the cursor
 271   \item{\verb+math[!display='1']/g[!@id]/cursor+}\\
 272   set \verb+display='1'+ in the \texttt{math} node
 273   \item{\verb+math/g[!@id]+}\\
 274   append the cursor after the \texttt{math} node
 275   \item{\verb+math/cursor+}\\
 276   remove the cursor
 277   \item{\verb+cursor+} \\
 278   error ?
 279 \end{description}
 280
 281 % do_shift:
 282 % CASE: tex/cursor
 283 %   create a math node. create a g node. append g as child of math.
 284 %   append the cursor as child of g
 285 % CASE: math[@display='1']/g[!@id][*#]/cursor
 286 %   append the cursor as last child of math
 287 % CASE: math/g[!@id][*#]/cursor
 288 %   remove the cursor. Editing is done
 289 % CASE: math[!display='1']/g[!@id]/cursor
 290 %   set the display attribute to '1'
 291 % CASE: math/g[!@id]
 292 %   append the cursor after math (?)
 293 % CASE: math/cursor
 294 %   remove the cursor. Editing is done
 295 % ELSE:
 296 %   error
 297
 298 \paragraph{Align:} $\&$
 299
 300 \begin{description}
 301   \item{\verb+g[@id]/cursor+}\\
 302   create a \texttt{row} node, create a \texttt{cell} node, create a \texttt{g} node,
 303     append the cursor to the new \texttt{g} node, append the \texttt{cell} node to the
 304     the \texttt{row} node ?
 305   \item{\verb+row/cell/g/cursor+}\\
 306   create the \texttt{g} node, create the \texttt{cell} node, append the cursor
 307     as child of the new \texttt{g} node, append the new \texttt{g} node to the new
 308     \texttt{cell} node after the old \texttt{cell} node
 309   \item{\verb+cursor+}\\
 310   error
 311 \end{description}
 312
 313 % do_align:
 314 % CASE: g[@id]/cursor
 315 %   create a row node. create a cell node. create a g node. append the
 316 %   cursor to g, append the g to cell, append the cell to row, ???
 317 % CASE: row/cell/g/cursor
 318 %   create a g node. create a cell node. appent the cursor to g,
 319 %   append the g to cell, insert the new cell after the existing cell
 320 % ELSE:
 321 %   error
 322
 323 \paragraph{End-of-line:}
 324
 325 % do_eol:
 326 %   ignored
 327
 328 \paragraph{Parameter:} $p(i)$
 329 % do_parameter:
 330 %   ignored
 331
 332 \paragraph{Superscript:} $\uparrow$
 333
 334 \begin{description}
 335   \item{\verb+<g|p>[^#]/cursor+}\\
 336   create a \SP{} node, create a \G{} node, replace the cursor with the \SP{} node,
 337     append the \G{} node as first child of the \SP{} node, append the cursor as last
 338     child of the \SP{} node
 339   \item{\verb+<g|p>[*#]/cursor+}\\
 340   create a \SP{} node, replace \texttt{*} with the \SP{} node, append \texttt{*} to
 341     the \SP{} node, append cursor to the \SP{} node
 342   \item{\verb+sp[^*#$][!@over='1']/cursor+}\\ %$
 343   set \verb+over='1'+ in the \SP{} node
 344   \item{\verb+sp[^*#$][@over='1']/cursor+}\\ %$
 345   error
 346   \item{\verb+cursor+}\\
 347   error ?
 348 \end{description}
 349 % do_superscript:
 350 % CASE: g[^#]/cursor
 351 %   create sp node. create g node, replace cursor with sp, append g to sp, append cursor to sp
 352 % CASE: g[*#]/cursor
 353 %   create sp node, replace * with sp, append * to sp, append cursor to sp
 354 % CASE: sp[^*#$][!@over='1']/cursor
 355 %   set over='1' in sp node
 356 % CASE: sp[^*#$][@over='1']/cursor
 357 %   error
 358 % ELSE:
 359 %   error ?
 360
 361 \paragraph{Subscript:} $\downarrow$
 362
 363 \begin{description}
 364   \item{\verb+<g|p>[^#]/cursor+}\\
 365   create a \SB{} node, create a \G{} node, replace the cursor with the \SB{} node,
 366     append the \G{} node as first child of the \SB{} node, append the cursor as last
 367     child of the \SB{} node
 368   \item{\verb+<g|p>[*#]/cursor+}\\
 369   create a \SB{} node, replace \texttt{*} with the \SB{} node, append \texttt{*} to
 370     the \SB{} node, append cursor to the \SB{} node
 371   \item{\verb+sb[^*#$][!@under='1']/cursor+}\\ %$
 372   set \verb+under='1'+ in the \SB{} node
 373   \item{\verb+sb[^*#$][@under='1']/cursor+}\\ %$
 374   error
 375   \item{\verb+cursor+}\\
 376   error ?
 377 \end{description}
 378 % do_subscript:
 379 % CASE: g[^#]/cursor
 380 %   create sb node. create g node, replace cursor with sb, append g to sb, append cursor to sb
 381 % CASE: g[*#]/cursor
 382 %   create sb node, replace * with sb, append * to sb, append cursor to sb
 383 % CASE: sb[^*#$][!@under='1']/cursor
 384 %   set over='1' in sb node
 385 % CASE: sb[^*#$][@under='1']/cursor
 386 %   error
 387 % ELSE:
 388 %   error ?
 389
 390 \paragraph{Ignorable space:} $\square$
 391
 392 % do_ignorable_space:
 393 %   do nothing?
 394
 395 \paragraph{Space:} $s$
 396
 397 \begin{description}
 398   \item{\verb+cursor+}\\
 399   create \SNODE{} node, replace cursor with the \SNODE{} node, append
 400   $\tadvance$ after \SNODE{} node
 401 \end{description}
 402
 403 % do_space
 404 %   create s node, replace cursor with s, append \advance after s
 405
 406 \paragraph{Identifier:} $i(v)$
 407
 408 \begin{description}
 409   \item{\verb+cursor+}\\
 410   create an \INODE{}, set \verb+value=+$v$ in the \INODE{}, replace
 411   cursor with \INODE{}, append $\tadvance$ after the \INODE{} node
 412 \end{description}
 413
 414 % do_identifier
 415 %   create i node, replace cursor with i, append \advance after i
 416
 417 \paragraph{Number:} $n(v)$
 418
 419 \begin{description}
 420   \item{\verb+cursor+}\\
 421   create an \NNODE{}, set \verb+value=+$v$ in the \NNODE{}, replace
 422   cursor with \NNODE{}, append $\tadvance$ after the \NNODE{} node
 423 \end{description}
 424
 425 % do_number
 426 %   create n node, replace cursor with n, append \advance after n
 427
 428 \paragraph{Apostrophe:} $o({}')$
 429
 430 \begin{description}
 431   \item{\verb+<g/p>[(sp[*#$]/g[o[@name='prime']$])#]/cursor+}\\
 432   create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
 433     append the \ONODE{} to the innermost \G{} node
 434   \item{\verb+<g|p>[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor+}\\
 435   create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
 436     append the \ONODE{} to the innermost \G{} node
 437   \item{\verb+<g|p>[*#]/cursor+}\\
 438   create a \ONODE{} node, set \verb+name='prime'+ in the \ONODE{},
 439     create a \SP{} node, create a \G{} node, replace \texttt{*} with \SP{} node,
 440     append the new \G{} node to the \SP{} node, append the \ONODE{}
 441     node to the new \G{} node
 442   \item{\verb+<g|p>[^#]/cursor+}\\
 443   error?
 444   \item{\verb+cursor+}\\
 445   cursor is not in a group, error?
 446 \end{description}
 447
 448 % do_apostrophe
 449 % CASE: g[(sp[^*#$]/g[o[@name='prime']$])#]/cursor
 450 %   append a new o[@name='prime'] node to the inner g node
 451 % CASE: g[(sb[^sp[^*#$]/g[o[@name='prime']]$])#]/cursor
 452 %   append a new o[@name='prime'] node to the inner g node
 453 % CASE: g[*#]/cursor
 454 %   create sp node, create g node, replace * with sp, append * to sp, append g to sp,
 455 %   append a new o[@name='prime'[ node to the new g node
 456 % CASE: g[^#]/cursor
 457 %   error?
 458 % ELSE:
 459 %   cursor is not in a group, error?
 460
 461 \paragraph{Other:} $o(v)$
 462
 463 create an \ONODE{}, set \verb+value=+$v$ in the \ONODE{}, replace
 464 cursor with \ONODE{}, append $\tadvance$ after the \ONODE{} node
 465
 466 % do_other
 467 %   create o node, replace cursor with o, append \advance after o
 468
 469 \paragraph{Active:} $\sim$
 470
 471 % do_active:
 472 %   ignored ???
 473
 474 \paragraph{Comment:} $\%$
 475
 476 % do_comment:
 477 %   ignored ???
 478
 479 \paragraph{Begin Environment:} $c(\mathtt{begin})\langle\alpha_1,\dots,\alpha_n\rangle$
 480
 481 \paragraph{End Environment:} $c(\mathtt{end})\langle\rangle$
 482
 483 \paragraph{Left Delimiter:} $c(\mathtt{left})\langle\alpha\rangle$
 484
 485 \paragraph{Right Delimiter:} $c(\mathtt{right})\langle\alpha\rangle$
 486
 487 \paragraph{Carriage-Return:} $c(\mathtt{cr})\langle\rangle$
 488
 489 \begin{description}
 490   \item{\verb+row/cell/g/cursor+}\\
 491   create a \ROW{} node, create a \CELL{} node, create a \G{}
 492     node, append the cursor to the new \G{} node, append the new \G{}
 493     node to the new \CELL{} node, append the new \CELL{} node to the
 494     new \ROW{} node, insert the new \ROW{} node after the old \ROW{} node
 495   \item{\verb+cursor+}\\
 496   ignored?
 497 \end{description}
 498
 499 % do_cr:
 500 % CASE: row/cell/g/cursor
 501 %   create row node, create cell node, create g node,
 502 %   append cursor to g, append g to cell, append cell to row,
 503 %   insert new row after old row
 504 % ELSE:
 505 %   ignored ???
 506
 507 \paragraph{Macro:} $c(v)\langle\alpha_1,\dots,\alpha_n\rangle$
 508
 509 \begin{description}
 510   \item{\verb+<p|g>/cursor+}\\
 511   create a \CNODE{} node with the children corresponding to the pattern
 512   $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
 513   the new \CNODE{} node. put $\tnext$ as the first child of the new
 514   \CNODE{} node
 515
 516   \item{\verb+*/cursor+}\\
 517   create a \CNODE{} node with the children corresponding to the pattern
 518   $\tmap{\alpha_1}$,\dots,$\tmap{\alpha_n}$, replace the cursor with
 519   the new \CNODE{} node, put $\tnext$ as the first child of the new
 520   \CNODE{} node. If $n\ne0$ emit a warning (the macro has arguments but
 521   but the context wouldn't normally allow them to be entered)
 522 \end{description}
 523
 524 % do_macro:
 525 % CASE: g/cursor
 526 %   create a c node with children corresponding to the pattern of the macro
 527 %   append \nextparam as first child of the macro
 528
 529 \section{Left Drop Rules}
 530
 531 \paragraph{Normal Left Drop:} $\NLDROP$
 532
 533 \begin{description}
 534
 535   \item{\verb+cursor+}\\
 536   replace the cursor with the $\NLDROP$.
 537
 538 \end{description}
 539
 540 \paragraph{Special Left Drop:} $\SLDROP$
 541
 542 \begin{description}
 543
 544   \item{\verb+cursor+}\\
 545   replace the cursor with the $\SLDROP$.
 546
 547 \end{description}
 548
 549 \section{Right Drop Rules}
 550
 551 \begin{description}
 552
 553   \item{\verb+cursor+}\\
 554   replace the cursor with the $\RDROP$.
 555
 556 \end{description}
 557
 558 \section{$\varepsilon$-rules}
 559
 560 \paragraph{Nromal Left Drop}
 561
 562 \begin{description}
 563
 564   \item{\verb+math/g[^#]/+$\NLDROP$}\\
 565   repalce the $\NLDROP$ with the cursor.
 566
 567   %**************************************************************************************
 568   %****************************** epsilon-rules with \NLDROP ****************************
 569   %**************************************************************************************
 570
 571   %**************  \NLDROP has neither preceding nor following nodes ********************
 572
 573   \item{\verb+math[^#$]/+$\NLDROP$}\\
 574   replace the $\NLDROP$ with the cursor.
 575
 576   \item{\verb+g[^#$]/+$\NLDROP$}\\
 577   replace the \G{} node with the $\NLDROP$.
 578
 579   % this rule is overridden by the two ones below
 580   \item{\verb+c/p[^#$]/+$\NLDROP$}\\
 581   remove the $\NLDROP$ and insert it before the \PNODE{} node.
 582
 583   \item{\verb+c[p[@left-open='1'][*]#$]/p[@right-open='1'][^#$]/+$\NLDROP$}\\
 584   replace the \CNODE{} node with the content of the first \PNODE{} node and insert the $\NLDROP$ after this content
 585
 586   \item{\verb+c[p[@left-open='1'][!*]#$]/p[@right-open='1'][^#$]/+$\NLDROP$}\\
 587   replace the \CNODE{} node with the $\NLDROP$.
 588
 589   \item{\verb+c[^#][!p(*)]/+$\NLDROP$}\\
 590   replace the \CNODE{} node with the $\NLDROP$.
 591
 592   \item{\verb+cell[^#$]/+$\NLDROP$}\\
 593   replace the cell with the $\NLDROP_n$.
 594
 595   \item{\verb+table[^#$]/+$\NLDROP$}\\
 596   replace the \TABLE{} node with the $\NLDROP$.
 597
 598   %************************* \NLDROP has at least one preceding node *********************
 599
 600   % general rules
 601
 602   % this rule should also handles the case where the \NLDROP is the third (and last) child of a script.
 603   \item{\verb+*[*#]/+$\NLDROP$}\\
 604   remove the $\NLDROP$ and append it as the last child of its ex preceding brother.
 605
 606   % this rule overrides the one above
 607   \item{\verb+*[(i|n|o|s|c[!*])#]/+$\NLDROP$}\\
 608   remove the $\NLDROP$ and replace the token with the $\NLDROP_n$.
 609
 610   % special rules
 611
 612   \item{\verb+<sp|sb>[^*#$]+/$\NLDROP$}\\
 613   replace the script node with its first child and insert the $\NLDROP$ after it.
 614
 615   % this rule overrides the one above.
 616   \item{\verb+<sp|sb>[^g[!@id][!*]#$]/+$\NLDROP$}\\
 617   replace the script with the cursor.
 618
 619   % this rule overrides the one above
 620   \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']++\verb+o[@name='prime']$]]#]/+$\NLDROP$}\\
 621   remove the last \ONODE{} node and replace the $\NLDROP$ with the cursor.%$\NLDROP_n$.
 622
 623   \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']$]]#]/+$\NLDROP$}\\
 624   replace the script with its first child and replace the $\NLDROP$ with the cursor.%$\NLDROP_n$.
 625
 626   \item{\verb+c[(i|n|o|s|c[!*])#]/+$\NLDROP$}\\
 627   move the $\NLDROP$ before the delimiter.
 628
 629   % this rule is true for both right-open and parameterized macros.
 630   \item{\verb+c[p#]/+$\NLDROP$}\\
 631   move the $\NLDROP$ into the \PNODE{} node.
 632
 633   %**************** \NLDROP has no preceding nodes, but has following nodes **************
 634
 635   % general rule
 636   \item{\verb+*[^#*]/+$\NLDROP$}\\
 637   remove the $\NLDROP$ and insert it before its parent.
 638
 639   % special rules
 640
 641   % this rule is applicable to all macros.
 642   \item{\verb+c[^#][p[*]]/+$\NLDROP$}\\
 643   remove the $\NLDROP$ and insert it before the \CNODE{} node.
 644
 645 \end{description}
 646
 647 \paragraph{Special Left Drop}
 648
 649 \begin{description}
 650
 651   %********************************************************************************************************
 652   %************************************ epsilon-rules with \SLDROP ****************************************
 653   %********************************************************************************************************
 654
 655   \item{\verb+math/+$\SLDROP$}\\
 656   replace the $\SLDROP$ with the cursor.
 657
 658   \item{\verb+math/g[^#]/+$\NLDROP$}\\
 659   replace the $\NLDROP$ with the cursor.
 660
 661   %************************ \SLDROP has neither preceding nor following nodes *****************************
 662
 663   \item{\verb+g[^#$]/+$\SLDROP$}\\
 664   replace the \G{} node with the cursor.
 665
 666   \item{\verb+c[p[@left-open='1'][*]#$]/p[@right-open='1'][^#$]/+$\SLDROP$}\\
 667   replace the \CNODE{} node with the content of the first \PNODE{} node and insert the cursor after this content
 668
 669   \item{\verb+c[p[@left-open='1'][!*]#$]/p[@right-open='1'][^#$]/+$\SLDROP$}\\
 670   replace the \CNODE{} node with the cursor.
 671
 672   \item{\verb+c/p[^#$]/+$\SLDROP$}\\
 673   remove the $\SLDROP$ and insert it before the \PNODE{} node.
 674
 675   \item{\verb+c[^#][!p(*)]/+$\SLDROP$}\\
 676   replace the \CNODE{} node with the cursor.
 677
 678   \item{\verb+cell[^#$]/+$\SLDROP$}\\
 679   replace the cell with the $\NLDROP_n$.
 680
 681   \item{\verb+table[^#$]/+$\SLDROP$}\\
 682   replace the \TABLE{} node with the cursor.
 683
 684   %*********************** \SLDROP has at least one preceding node ***********************************
 685
 686   \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']++\verb+o[@name='prime']$]]#]/+$\SLDROP$}\\
 687   remove the last \ONODE{} node and replace the $\SLDROP$ with the cursor.
 688
 689   \item{\verb+*[sp[!@id][^*g[!@id][^o[@name='prime']$]]#]/+$\SLDROP$}\\
 690   replace the script with its first child and replace the $\SLDROP$ with the cursor.%$\NLDROP_n$.
 691
 692   \item{\verb+<sp|sb>[^g[!@id][!*]#$]/+$\SLDROP$}\\
 693   replace the script with the cursor.
 694
 695   % this rule is overridden by the three rules above.
 696   \item{\verb+<sp|sb>[^*#$]+/$\SLDROP$}\\
 697   replace the script node with its first child and insert the cursor after it.
 698
 699   \item{\verb+c[(i|n|o|s|c[!*])#]/+$\SLDROP$}\\
 700   remove the $\SLDROP$ and insert the cursor before the delimiter.
 701
 702   \item{\verb+c[p#(i|n|o|s|c[!*])]/+$\SLDROP$}\\
 703   remove the $\SLDROP$ and insert the cursor into the \PNODE{} node.
 704
 705   \item{\verb+c[p[@right-open='1']#]+}\\
 706   remove the $\SLDROP$ and append the curor as last child of the \PNODE{} node.
 707
 708   % this rule is overridden by the two ones above.
 709   \item{\verb+c[p#]/+$\SLDROP$}\\
 710   move the $\SLDROP$ into the \PNODE{} node.
 711
 712   \item{\verb+*[(i|n|o|s|c[!*])#]/+$\SLDROP$}\\
 713   remove the $\SLDROP$ and replace the token with the cursor.
 714
 715   \item{\verb+*[table#]/+$\SLDROP$}\\
 716   remove the $\SLDROP$ and append the $\NLDROP_n$ as the last child of the \TABLE{} node.
 717
 718   \item{\verb+*[c#]/+$\SLDROP$}\\
 719   move the $\SLDROP$ into the \CNODE{} node.
 720
 721   \item{\verb+*[g#]/+$\SLDROP$}\\
 722   remove the $\SLDROP$ and append the cursor as the last child of the \G{} node.
 723
 724   %********** \SLDROP has no preceding node, but has following ones **************
 725
 726   \item{\verb+c[^#p][p(*)]/+$\SLDROP$}\\
 727   remove the $\SLDROP$ and insert the cursor before the \CNODE{} node.
 728
 729   % general rule
 730   \item{\verb+*[^#*]/+$\SLDROP$}\\
 731   remove the $\SLDROP$ and insert the cursor before its parent.
 732
 733 \end{description}
 734
 735 \paragraph{Normalize Left Drop}
 736
 737 \begin{description}
 738
 739   %****************************************************************************************
 740   %***************************** epsilon-rules with \NLDROP_n *****************************
 741   %****************************************************************************************
 742
 743   \item{\verb+*[*#]/+$\NLDROP_n$}\\
 744   replace the $\NLDROP_n$ with the cursor.
 745
 746   \item{\verb+row[cell#]/+$\NLDROP_n$}\\
 747   remove the $\NLDROP_n$ and append the cursor as the last child of the \CELL{} node.
 748
 749   \item{\verb+row[^#$]/+$\NLDROP_n$}\\
 750   replace the \ROW{} node with the $\NLDROP_n$
 751
 752   \item{\verb+table[row#]/+$\NLDROP_n$}\\
 753   remove the $\NLDROP_n$ and append it as last child of the \ROW{} node.
 754
 755   \item{\verb+table[^#$]/+$\NLDROP_n$}\\
 756   replace the \TABLE{} with the cursor.%$\NLDROP_n$.
 757
 758   \item{\verb+g[@id][^#$]/+$\NLDROP_n$}\\
 759   replace the \G{} node with the $\NLDROP_n$.
 760
 761   \item{$\NLDROP_n$}\\
 762   replace the $\NLDROP_n$ with the cursor.
 763
 764 \end{description}
 765
 766 \paragraph{Right Drop}
 767
 768 \begin{description}
 769
 770   %************************* \RDROP has at least a following node ****************************************
 771
 772   \item{\verb+c[#(i|n|o|s|c[!*])]/+$\RDROP$}\\
 773   remove the $\RDROP$ and append it after the delimiter
 774
 775   \item{\verb+*[#(i|n|o|s|c[!*])]/+$\RDROP$}\\
 776   remove the token and replace the $\RDROP$ with the cursor $\RDROP_n$.
 777
 778   % this rule is overridden by those ones above.
 779   \item{\verb+*[#*]/+$\RDROP$}\\
 780   remove the $\RDROP$ and append it as the first child of the following node.
 781
 782   %************************** \RDROP has neither following nor preceding nodes ******************************
 783
 784   \item{\verb+c[#$][!p[*]]/+$\RDROP$}\\
 785   replace the \CNODE{} with the $\RDROP$.
 786
 787   \item{\verb+p[^#$]/+$\RDROP$}\\
 788   move the $\RDROP$ after the \PNODE{} node.
 789
 790   \item{\verb+g[^#$]/+$\RDROP$}\\
 791   replace the \G{} node with the $\RDROP$.
 792
 793 \end{description}
 794
 795 \paragraph{Normalize Right Drop}
 796
 797 \begin{description}
 798
 799   % at the moment it's the only rule, defined for this symbol.
 800   \item{\verb+g[@id][^#$]/+$\RDROP_n$}\\
 801   replace the \G{} node with the $\RDROP_n$.
 802
 803   \item{$\RDROP_n$}\\
 804   replace the $\RDROP$ with the cursor.
 805
 806 \end{description}
 807
 808 \paragraph{Advance}
 809
 810 \begin{description}
 811   \item{\verb+g/+$\tadvance$}\\
 812   replace $\tadvance$ with the cursor
 813
 814   \item{\verb+p[#$]/+$\tadvance$}\\ %$
 815   put $\tadvance$ after the \PNODE{} node
 816
 817   \item{\verb+c[#p]/+$\tadvance$} \\
 818   remove $\tadvance$, put the cursor as first child of the \PNODE{} node
 819
 820   \item{\verb+c[#*]/+$\tadvance$} \\ %$
 821   replace $\tadvance$ with the cursor
 822
 823   \item{\verb+c[#$]/+$\tadvance$} \\ %$
 824   move $\tadvance$ after the \CNODE{} node
 825 \end{description}
 826
 827 \paragraph{Next Parameter}
 828
 829 \paragraph{Next Token}
 830
 831 %% \begin{description}
 832 %%   \item{\verb+c[#p]/+$\tnext$} \\
 833 %% \end{description}
 834
 835 % g[@id]/(c[#$][@right-open]/g[!@id][#$]/)+cursor  }   let p = cursor.parent() in remove; advance(p)
 836
 837 % c/g[!@id]/cursor
 838 % c/cursor
 839 % */cursor  {   let g = new group in replace
 840
 841 % g[@id][^#$]/cursor  <=   cursor.parent().replace(cursor)
 842 % g[@id][^#$]/cursor  <-   cursor
 843 % (!g[@id][^#$])[A#B]/(g[@id][^#$]/)+cursor  <-  (!g[@id][^#$])[A#B]/cursor
 844
 845 \clearpage
 846 \appendix
 847 \section{Semantics of the Regular Context Language}
 848
 849 \newcommand{\CSEM}[2]{\mathcal{C}\llbracket#1\rrbracket#2}
 850 \newcommand{\QSEM}[2]{\mathcal{Q}\llbracket#1\rrbracket#2}
 851 \newcommand{\TSEMUP}[2]{\mathcal{T}^\uparrow\llbracket#1\rrbracket#2}
 852 \newcommand{\TSEMDOWN}[2]{\mathcal{T}_\downarrow\llbracket#1\rrbracket#2}
 853 \newcommand{\NSEM}[2]{\mathcal{N}\llbracket#1\rrbracket#2}
 854 \newcommand{\PSEM}[2]{\mathcal{P}\llbracket#1\rrbracket#2}
 855 \newcommand{\PPSEM}[2]{\mathcal{P'}\llbracket#1\rrbracket(#2)}
 856 \newcommand{\PARENT}[1]{\mathit{parent}(#1)}
 857 \newcommand{\CHILDREN}[1]{\mathit{children}(#1)}
 858 \newcommand{\ANCESTORS}[1]{\mathit{ancestors}(#1)}
 859 \newcommand{\DESCENDANTS}[1]{\mathit{descendants}(#1)}
 860 \newcommand{\HASATTRIBUTE}[2]{\mathit{hasAttribute}(#1,#2)}
 861 \newcommand{\HASNOATTRIBUTE}[2]{\mathit{hasNoAttribute}(#1,#2)}
 862 \newcommand{\ATTRIBUTE}[2]{\mathit{attribute}(#1,#2)}
 863 \newcommand{\ISELEMENT}[1]{\mathit{isElement}(#1)}
 864 \newcommand{\NAME}[1]{\mathit{name}(#1)}
 865 \newcommand{\PREV}[1]{\mathit{prev}(#1)}
 866 \newcommand{\NEXT}[1]{\mathit{next}(#1)}
 867
 868 \[
 869 \begin{array}{rcl}
 870   \CSEM{.}{x} &=& \{x\}\\
 871   \CSEM{..}{x} &=& \PARENT{x}\\
 872   \CSEM{/}{x} &=& \CHILDREN{x}\\
 873   \CSEM{q}{x} &=& \{x_1\mid x_1\in\{x\} \wedge \QSEM{q}{x_1}\}\\
 874   \CSEM{(c)}{x} &=& \CSEM{c}{x}\\
 875   \CSEM{\alpha(c)}{x} &=& \CSEM{c}{x}, \mbox{bind $\alpha$ to $x$}\\
 876   \CSEM{c_1\&c_2}{x} &=& \CSEM{c_1}{x} \cap \CSEM{c_2}{x}\\
 877   \CSEM{c_1\mid c_2}{x} &=& \CSEM{c_1}{x} \cup \CSEM{c_2}{x}\\
 878   \CSEM{c+}{x} &=& \CSEM{c}{x} \cup \CSEM{c+}{\CSEM{c}{x}}\\
 879   \CSEM{c?}{x} &=& \CSEM{.\mid c}{x}\\
 880   \CSEM{c*}{x} &=& \CSEM{{c+}?}{x}\\
 881   \CSEM{c_1\;c_2}{x} &=& \CSEM{c_2}{\CSEM{c_1}{x}}\\[3ex]
 882   \QSEM{\langle*\rangle}{x} &=& \ISELEMENT{x}\\
 883   \QSEM{\langle!*\rangle}{x} &=& \neg\QSEM{\langle*\rangle}{x}\\
 884   \QSEM{\langle n_1\mid\cdots\mid n_k\rangle}{x} &=& \exists i\in\{1,\dots,k\}:\NAME{x}=n_i\\
 885   \QSEM{\langle !n_1\mid\cdots\mid n_k\rangle}{x} &=& \neg\QSEM{\langle n_1\mid\cdots\mid n_k\rangle}{x}\\
 886   \QSEM{q[@n]}{x} &=& \QSEM{q}{x} \wedge \HASATTRIBUTE{x}{n}\\
 887   \QSEM{q[!@n]}{x} &=& \QSEM{q}{x} \wedge \HASNOATTRIBUTE{x}{n}\\
 888   \QSEM{q[@n=v]}{x} &=& \QSEM{q}{x} \wedge \ATTRIBUTE{x}{n}= v\\
 889   \QSEM{q[!@n=v]}{x} &=& \QSEM{q}{x} \wedge \ATTRIBUTE{x}{n}\ne v\\
 890   \QSEM{q[p]}{x} &=& \QSEM{q}{x} \wedge \PSEM{p}{x}\\
 891   \QSEM{q[!p]}{x} &=& \QSEM{q}{x} \wedge \neg\PSEM{p}{x}\\[3ex]
 892   \PSEM{p_1\#p_2}{x} &=& \PPSEM{p_1}{*,x}\wedge\PPSEM{p_2}{x,*}\\
 893   \PSEM{\cent p_1\#p_2}{x} &=& \PPSEM{p_1}{\cent,x}\wedge\PPSEM{p_2}{x,*}\\
 894   \PSEM{p_1\#p_2\$}{x} &=& \PPSEM{p_1}{*,x}\wedge\PPSEM{p_2}{x,\$}\\
 895   \PSEM{\cent p_1\#p_2\$}{x} &=& \PPSEM{p_1}{\cent,x}\wedge\PPSEM{p_2}{x,\$}\\[3ex]
 896   \PPSEM{}{*,x} &=& \mathit{true}\\
 897   \PPSEM{}{\cent,x} &=& \PREV{x}=\emptyset\\
 898   \PPSEM{}{x,*} &=& \mathit{true}\\
 899   \PPSEM{}{x,\$} &=& \NEXT{x}=\emptyset\\
 900   \PPSEM{p\;c}{\alpha,x} &=& \CSEM{c}{\PREV{x}}\ne\emptyset\wedge\PPSEM{p}{\alpha,\PREV{x}}\\
 901   \PPSEM{c\;p}{x,\alpha} &=& \CSEM{c}{\NEXT{x}}\ne\emptyset\wedge\PPSEM{p}{\NEXT{x},\alpha}\\
 902 \end{array}
 903 \]
 904
 905 \end{document}