726 \begin{center} |
726 \begin{center} |
727 $b ::= S \mid Z \; \;\; |
727 $b ::= S \mid Z \; \;\; |
728 bs ::= [] \mid b:bs |
728 bs ::= [] \mid b:bs |
729 $ |
729 $ |
730 \end{center} |
730 \end{center} |
731 They are just a string of bits, the names $S$ and $Z$ here are quite arbitrary, we can use 0 and 1 or any other set of binary symbols to substitute them. They are a compact form of parse trees. |
731 They are just a string of bits, the names $S$ and $Z$ here are quite arbitrary, we can use 0 and 1 or any other set of binary symbols to substitute them. Bit-codes(or bit-sequences) are a compact form of parse trees. |
732 Here is how values and bit-codes are related: |
732 Here is how values and bit-codes are related: |
733 Bitcodes are essentially incomplete values. |
733 Bitcodes are essentially incomplete values. |
734 This can be straightforwardly seen in the following transformation: |
734 This can be straightforwardly seen in the following transformation: |
735 \begin{center} |
735 \begin{center} |
736 \begin{tabular}{lcl} |
736 \begin{tabular}{lcl} |
737 $\textit{code}(\Empty)$ & $\dn$ & $[]$\\ |
737 $\textit{code}(\Empty)$ & $\dn$ & $[]$\\ |
738 $\textit{code}(\Char\,c)$ & $\dn$ & $[]$\\ |
738 $\textit{code}(\Char\,c)$ & $\dn$ & $[]$\\ |
739 $\textit{code}(\Left\,v)$ & $\dn$ & $\Z :: code(v)$\\ |
739 $\textit{code}(\Left\,v)$ & $\dn$ & $\Z :: code(v)$\\ |
740 $\textit{code}(\Right\,v)$ & $\dn$ & $\S :: code(v)$\\ |
740 $\textit{code}(\Right\,v)$ & $\dn$ & $\S :: code(v)$\\ |
741 $\textit{code}(\Seq\,v_1\,v_2)$ & $\dn$ & $code(v_1) \,@\, code(v_2)$\\ |
741 $\textit{code}(\Seq\,v_1\,v_2)$ & $\dn$ & $code(v_1) \,@\, code(v_2)$\\ |
742 $\textit{code}(\Stars\,[])$ & $\dn$ & $[\S]$\\ |
742 $\textit{code}(\Stars\,[])$ & $\dn$ & $[\Z]$\\ |
743 $\textit{code}(\Stars\,(v\!::\!vs))$ & $\dn$ & $\Z :: code(v) \;@\; |
743 $\textit{code}(\Stars\,(v\!::\!vs))$ & $\dn$ & $\S :: code(v) \;@\; |
744 code(\Stars\,vs)$ |
744 code(\Stars\,vs)$ |
745 \end{tabular} |
745 \end{tabular} |
746 \end{center} |
746 \end{center} |
747 where $\Z$ and $\S$ are arbitrary names for the bits in the |
747 Here code encodes a value into a bit-sequence by converting Left into $\Z$, Right into $\S$, the start point of a non-empty star iteration into $\S$, and the border where a local star terminates into $\Z$. This conversion is apparently lossy, as it throws away the character information, and does not decode the boundary between the two operands of the sequence constructor. Moreover, with only the bitcode we cannot even tell whether the $\S$s and $\Z$s are for $\Left/\Right$ or $\Stars$. The reason for choosing this compact way of storing information is that the relatively small size of bits can be easily moved around. In order to recover the bitcode back into values, we will need the regular expression as the extra information and decode them back into value:\\ |
748 bitsequences. |
|
749 Here code encodes a value into a bitsequence by converting Left into $\Z$, Right into $\S$, the start point of a non-empty star iteration into $\S$, and the border where a local star terminates into $\Z$. This conversion is apparently lossy, as it throws away the character information, and does not decode the boundary between the two operands of the sequence constructor. Moreover, with only the bitcode we cannot even tell whether the $\S$s and $\Z$s are for $Left/Right$ or $Stars$. The reason for choosing this compact way of storing information is that the relatively small size of bits can be easily moved around during the lexing process. In order to recover the bitcode back into values, we will need the regular expression as the extra information and decode them back into value:\\ |
|
750 %\begin{definition}[Bitdecoding of Values]\mbox{} |
748 %\begin{definition}[Bitdecoding of Values]\mbox{} |
751 \begin{center} |
749 \begin{center} |
752 \begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
750 \begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
753 $\textit{decode}'\,bs\,(\ONE)$ & $\dn$ & $(\Empty, bs)$\\ |
751 $\textit{decode}'\,bs\,(\ONE)$ & $\dn$ & $(\Empty, bs)$\\ |
754 $\textit{decode}'\,bs\,(c)$ & $\dn$ & $(\Char\,c, bs)$\\ |
752 $\textit{decode}'\,bs\,(c)$ & $\dn$ & $(\Char\,c, bs)$\\ |