next up previous
Next: Bibliography Up: A multi-tape S-attributed grammar's Previous: S-attributed context-free grammars

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

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.

\Sigma ^{\star} & \rightarrow & \langle \...
...ots a_{\vec{l}} = \langle a_1
\cdots a_l \rangle\\

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[ b \atop \varepsilon \right]
\left[ a \atop d \right]

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:

$\displaystyle 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.

next up previous
Next: Bibliography Up: A multi-tape S-attributed grammar's Previous: S-attributed context-free grammars
Jerome Waldispuhl 2002-12-18