Multi-tape S-attributed grammars

We extend now this formalism in order to use a ``m-tape'' alphabet.

Definition 4   ($m$-tape index)
A m-tape index $\vec{\imath}$ is a vector of $\mathbb{Z} ^m$. the notation $\vec{\imath} ^{(k)}$ will denote the k-th tape. We shall say that a m-tape index $\vec{\imath}$ is inferior to a m-tape index $\vec{\jmath}$ if this order stands on every tape, and we shall denote this relation by $\vec{\imath} \leq \vec{\jmath}$.

The $m$-tape index $\vec{1}$ has the value 1 on all tapes. The sum of two $m$-tapes indexes $\vec{\imath}_1$ and $\vec{\mbox{\it\i}}_2$ is a $m$-tape index $\vec{\jmath}$ defined by $\vec{\jmath}^{(k)} = \vec{\imath}_1^{(k)} + \vec{\imath}_2^{(k)}$. Thus, $\vec{\imath} \leq \vec{\jmath}$ also means $\vec{\imath} - \vec{\jmath} \leq 0$.

Definition 5   ($m$-tape input string)
Given m alphabet $\Sigma ^{(i)} \; (1 \leq i \leq m)$, a $m$-tape input string is a vector of $m$ strings $(a^{(1)}_{\vec{1}^{(1)}} \cdots a^{(1)}_{\vec{n}^{(1)}}, \cdots ,a^{(m)}_{\vec{m}^{(m)}}$ $\cdots a^{(m)}_{\vec{n}^{(m)}})$, where each string $a^{(i)}_{\vec{1}^{(i)}} \cdots a^{(i)}_{\vec{n}^{(i)}}$ belongs to $\big( \Sigma ^{(i)} \big) ^{\star}$. We shall denote the set of such defined input strings by $\langle \Sigma ^{\star} \rangle = \bigotimes _{i= 1 \cdots n} \Sigma^{(i)^\star}$. As a shorthand, any m-tape input string $\big(a^{(1)}_{\vec{1}^{(1)}} \cdots a^{(1)}_{\vec{n}^{(1)}}, \cdots ,a^{(m)}_{\vec{m}^{(m)}} \cdots a^{(m)}_{\vec{n}^{(m)}}\big)$ may be denoted by $a_{\vec{1}} \cdots a_{\vec{n}}$. Substrings of $a_{\vec{1}} \cdots a_{\vec{n}}$ will be denoted by $a_{\vec{\imath}} \cdots a_{\vec{\jmath}} = \big(a^{(1)}_{\vec{\imath}^{(1)}} \... ...a^{(1)}_{\vec{\jmath}^{(1)}}, \cdots ,a^{(m)}_{\vec{\mbox{\it\i}}^{(m)}} \cdots$ $a^{(m)}_{\vec{\jmath}^{(m)}}\big)$ with the usual conventions that $\vec{1} \leq \vec{\imath}$, $\vec{\jmath} \leq \vec{n}$ and, if $\vec{\imath}^{(k)} > \vec{\jmath}^{(k)}$, $a^{(k)}_{\vec{\imath}^{(k)}} \cdots a^{(k)}_{\vec{\jmath}^{(k)}} = \varepsilon$.

Example 2 (abba,dcd)   is a 2-tape input string on $\Sigma ^{(1)} = {a,b}$ and $\Sigma ^{(2)} = {c,d}$. We shall also write this 2-tape input string as ${a \atop d}{b \atop c}{b \atop d}{a \atop}$, which a somewhat more natural notation in the context of alignments. This 2-tape input string $a_{\overrightarrow{\left( 1 \atop 1 \right)}} \cdots a_{\overrightarrow{\left( 4 \atop 3 \right)}} = {a \atop d}{b \atop c}{b \atop d}{a \atop}$ has a 2-tape input string $a_{\overrightarrow{\left( 2 \atop 1 \right)}} \cdots a_{\overrightarrow{\left( 3 \atop 2 \right)}} = {b \atop d}{b \atop c}$.

Definition 6   ($m$-tape alphabet)
A $m$-tape alphabet $\Sigma$ is a product of $m$ alphabets $\Sigma ^{(i)}$ augmented with the empty string: $\Sigma = \bigotimes _{i = 1 \cdots m} (\Sigma ^{(i)} \cup \{ \varepsilon \} )$.

Definition 7   ($m$-tape alignment)
An element $a_1 \cdots a_l$ of the free monoid $\Sigma ^{\star}$, generated by formal concatenation of $m$-tape elements of $\Sigma$, is called a $m$-tape alignment of length $l$. The empty alignment of $\Sigma ^{\star}$ is denoted by $\varepsilon$.

Definition 8   ( $\varepsilon$-deletion)
Given any $m$-tape alignment $a_1 \cdots a_l$, we get a $m$-tape input string $a_{\vec{1}} \cdots a_{\vec{n}}$ by concatenation of symbols of the projection of $a_1 \cdots a_l$ on every tape.

$$\begin{array}{rcl} \Sigma ^{\star} & \rightarrow & \langle \... ...ots a_{\vec{l}} = \langle a_1 \cdots a_l \rangle\\ \end{array}$$

Example 3   The 2-tape input string ${a \atop d}{b \atop c}{b \atop d}{a \atop}$ may be defined as an $\varepsilon$-deletion of the alignments $\left\langle \left[ \varepsilon \atop b \right] \left[ a \atop \varepsilon \right] \left[ b \atop \varepsilon \right] \left[ b \atop c \right] \right.$ $\left. \left[ a \atop d \right]\right\rangle$ or $\left\langle \left[ a \atop \varepsilon \right] \left[ b\atop d \right] \left... ...ight] \left[ b \atop \varepsilon \right] \left[ a \atop d \right] \right\rangle$.

Once the $m$-tape alphabets and strings have been defined, we naturally extend a context-free grammar into a $m$-tape context-free grammar.

Definition 9   ($m$-tape context-free grammar) A $m$-tape context-free grammar $G = (V_T,V_N,P,S)$ is classical context-free grammar such that $V_T$ is a subset of a $m$-tape alphabet.

Notice that in $m$-tape case, $L(G)$ is not the set of derivable strings but the set of $\varepsilon$-deleted such strings.

Example 4   The following toy MTCFG will align two properly parenthesized strings interspersed with a's:

$$S \rightarrow \left[ {( \atop (} \right] S \left[ {) \atop )} \ri... ...arepsilon} \right] \big\vert \left[ {\varepsilon \atop a} \right] \big\vert SS$$

In this MTSAG, the structure defined by parentheses must be the same on both tapes, but substrings of $a$ may be aligned with gaps (denoted with $\varepsilon$).

Then, as in mono-tape case, a $m$-tape context-free grammar can be extended into a $m$-tape S-attributed grammar by addition of attributes and functions to compute the non-terminal attributes.

Definition 10   ($m$-tape S-attributed grammar) A $m$-tape S-attributed grammaris denoted by $G = (V_T,V_N,P,S,{\cal A},S_{\cal A},F_P)$. It is an extension of a $m$-tape context-free grammar $G = (V_T,V_N,P,S)$, where an attribute $x \in {\cal A}$ is attached to each symbol $X \in V$ and a string of attributes $\lambda \in {\cal A}^{\star}$ to each string $\alpha \in V ^{\star}$. $S_{\cal A}$ is a function from $V_T$ to ${\cal A}$ assigning attributes to terminals. $F_P$ is a set of functions from ${\cal A}^{\star}$ to ${\star A}$. A function $f_{A \rightarrow \alpha}$ is in $F_P$ iff $A \rightarrow \alpha$ is in P.