\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsmath}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{theorem}{Theorem}
\newtheorem{example}{Example}
\newtheorem{condition}{Condition}
\newtheorem{proposition}{Proposition}

\newtheorem{lemma}{Lemma}
\usepackage{color}
\usepackage{comment}
\usepackage{calrsfs}
\usepackage{latexsym}
\usepackage{tikz}
\usepackage{tikz-qtree}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{titlesec}
\usepackage[colorlinks=true]{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=blue,
    urlcolor=blue
}
\usepackage{alltt}
\usepackage{ulem}
\def\st{\noindent}
\renewcommand\em{\it}
\renewcommand\emph{\textit}
\newcommand\red[1]{{\color{red}#1}}
\newcommand\blue[1]{{\color{blue}#1}}
\newcommand\cancelr[1]{{\color{red}\sout{#1}}}

% define subsubsubsection
\titleclass{\subsubsubsection}{straight}[\subsection]

\newcounter{subsubsubsection}[subsubsection]
\renewcommand\thesubsubsubsection{\thesubsubsection.\arabic{subsubsubsection}}
\renewcommand\theparagraph{\thesubsubsubsection.\arabic{paragraph}} % optional; useful if paragraphs are to be numbered

\titleformat{\subsubsubsection}
  {\normalfont\normalsize\bfseries}{\thesubsubsubsection}{1em}{}
\titlespacing*{\subsubsubsection}
{0pt}{3.25ex plus 1ex minus .2ex}{1.5ex plus .2ex}

\makeatletter
\renewcommand\paragraph{\@startsection{paragraph}{5}{\z@}%
  {3.25ex \@plus1ex \@minus.2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{6}{\parindent}%
  {3.25ex \@plus1ex \@minus .2ex}%
  {-1em}%
  {\normalfont\normalsize\bfseries}}
\def\toclevel@subsubsubsection{4}
\def\toclevel@paragraph{5}
\def\toclevel@paragraph{6}
\def\l@subsubsubsection{\@dottedtocline{4}{7em}{4em}}
\def\l@paragraph{\@dottedtocline{5}{10em}{5em}}
\def\l@subparagraph{\@dottedtocline{6}{14em}{6em}}
\makeatother

\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}



%\newcommmand{\red}[1]{\textcolor{red}{#1}}
%\renewcommand\red[1]{{\color{red}#1}}
%opening
\title{AST generator specification}
\author{Evgenii Balai}
\def\no{{\bf not}\;}
\begin{document}

\maketitle
\st

\tableofcontents
\section{Vocabulary}

\begin{itemize}
\item \textit{identifier} -  a sequence of alphanumeric or underscore characters starting with a letter.
\item \textit{numeral} - a sequence of characters used to represent a number. Numerals can be in one of the following forms:
\begin{enumerate}
\item $d_1\ldots d_k$
\item $d_1\ldots d_n.d_1\ldots d_m$
\end{enumerate}
possible preceded by a minus sign,
where each $d_i$ is a digit, $k > 0, n\ge 0$ and $m >0$.
\end{itemize}


\section{Input Specification}
The input consists of the following:
\begin{enumerate}
\item lexicon file (defined in section \ref{lf})
\item grammar file (defined in section \ref{gf}) 
\item source file (defined in section \ref{sf})
\end{enumerate}

\subsection{Lexicon file}\label{lf}

A lexicon file is an ASCII file that contains a specification of types of terminal symbols (\textit{lexems}) that may occur in a program file.
Each lexem type is declared as 
\begin{equation}\label{lexdef}
lexem\_type\_name = regex
\end{equation}
where $lexem\_type\_name$ is an identifier and $regex$ is a regular expression following python syntax\cite{pythonre} whose special characters are limited to $.$, $*$, $+$, $?$, $\{m\}$, $\{m,n\}$, $[]$, $\wedge$(only inside$[]$), $\backslash$,  or $|$.

We will say that statement (\ref{lexdef}) \textit{defines} a lexem type named $lexem\_type\_name$.

Lexicon file may contain multiple declarations of the form (\ref{lexdef}), one per line, where no lexem type name occurs in the left hand side of a statement more than once, and no lexem type name is a member of the set $\{id, num, space\}  $.

 
\subsection{Grammar File}\label{gf}
A grammar file is an ASCII file that contains a specification of non-terminals occurring in the produced abstract syntax tree as well as the desired structure of the tree. Every grammar file must be associated with a lexicon file. We will refer to the set of lexem type names defined in the file as $S_L$.  


Non-terminals are specified  by  statements of the form 

\begin{equation}\label{nontd}
nt(\beta_1~\ldots~\beta_m) ::= \alpha_1(\tau_1)~\ldots~\alpha_n(\tau_n) 
\end{equation}
where 
\begin{enumerate}
\item $nt$ is an identifier which is not a member of the set $\{id, num, space\}\cup S_L$ sometimes referred to as a \textit{non-terminal symbol}, or simply \textit{non-terminal};
\item $n\ge 1$;
\item each $\alpha_i$  is an identifier;
\item each $\tau_i$ is an identifier;
\item $\beta_1~\ldots~\beta_m$ ($m \ge 1$) is a sequence  where
 each  $\beta_1$  is an identifier and each $\beta_i$ for $i>1$ 
is in one of the following forms:
\begin{enumerate}
\item an identifier that is an element of the sequence   $\tau_1\ldots \tau_n$;
\item $f(c)$, where $f$ is a member of the set of identifiers $\{cut\_root\}$ and c is an element of  the sequence   $\tau_1\ldots \tau_n$.
If $f = cut\_root$, $c$ must not be a lexeme type name;
\end{enumerate} 
\item  if $\beta_i$ is of one of the forms $\tau_j$ or $f(\tau_j)$, then  $\tau_j$ must occur in the sequence  $\tau_1\ldots \tau_n$ exactly once;
\item if $\beta_1$ is of one of the forms $\tau_j$ or $f(\tau_j)$, then $m$ must be equal to $1$, otherwise $\beta_1$ is an identifier also referred to as \textit{a label}.
\end{enumerate}

An informal reading of the rule \ref{nontd} is given below.
\begin{enumerate}

\item  Suppose $\beta_1 \in \{\tau_1,...,\tau_m\}$ .
In this case $n = 1$, and the rule is of the form:

$$nt (\tau_i) ::= \alpha_1(\tau_1) ... \alpha_m(\tau_m)$$.

where $\tau_i \in \{\tau_1,\ldots,\tau_m\}$

The reading of the rule is:

An expression of type $nt$ with tree $\tau_i$ can be written by writing an expression of type $\alpha_1$ with tree $\tau_1$, followed by an expression of type $\alpha_2$ with tree $\tau_2$, \ldots, followed by an expression of type $\alpha_n$ with tree $\tau_n$.

For a terminal symbol $t$ the phrase \textit{expression of type $t$} should be understood as $t$ itself.

For example, the reading of the rule
$$T2(M) = T3(M)$$
is \textit{an expression of type $T2$ with tree $M$ can be written by writing an expression of type $T3$ with tree $M$.} 


\item  Suppose  $\beta_1 \not\in \{\tau_1,...,\tau_m\}$ .

In this case the reading is:

An expression of type $nt$ with the tree corresponding to the list $(\beta_1,...,\beta_n)$ (see section \ref{treesec}) can be written by writing an expression of type $\alpha_1$ with tree $\tau_1$, followed by an expression of type $\alpha_2$ with tree $\tau_2$, \ldots, followed by an expression of type $\alpha_n$ with tree $\tau_n$.

For example, the reading of the rule
$$T1(add~M1~M2)~::=~T2(M1)~add\_op(A)~T1(M2)$$
is \textit{an expression of type $T1$ with tree~$(add~M1~M2)$ can be written by writing an expression of type $T2$ with tree $M1$, followed by an expression of type $add\_op$ with tree $A$, followed by an expression of type $T1$ with tree $M2$.} 

\end{enumerate}


We allow a shorthand $\alpha$ that stands for $\alpha(\alpha)$ to be an element of the sequence on the right hand side of the statement (\ref{nontd}). 


We will refer to the sequence of statements of the form(2) as \textit{a grammar}, if each $\alpha_i$ is a  non-terminal  name occurring on the left hand side of another statement in the sequence, or a member of the set$\{id, num, space\}\cup S_L$ . The non-terminal symbols occurring in the statements of the grammar are referred to as the \textit{non-terminal symbols} (or the \textit{non-terminals}) \textit{of the grammar}. 
The non-terminal symbol occurring on the left hand side of the first statement of $G$ is referred to as the \textit{starting symbol of the grammar}. The members of $S_L$ are referred to as the \textit{terminal symbols} (or the \textit{terminals}) \textit{of the grammar}.  Both terminals and non-terminals of a grammar are referred to as \textit{symbols of the grammar}. 
Finally, the labels occurring in the statements of a grammar are referred to as the \textit{labels of the grammar}.

Let $G$ be a grammar.
We define a leveling function $|\ |$ of $G$ that maps non-terminals of $G$ onto a set of non-negative integers in the range [0..n].
A leveling function is called reasonable if for each statement of the form 
$$nt(\beta_1~\ldots~\beta_m) ::= \alpha_1(\tau_1)$$
such that  $\alpha_1$ is a non-terminal, $|nt|> |\alpha_1|$.
$G$ is called \textit{stratified}, if there exists a reasonable leveling of $G$.
  
A grammar file contains a stratified grammar, one  statement per line.

\subsection{Source File}\label{sf}
A source file is a file containing arbitrary collection of ASCII characters.

\subsection{Input Examples}\label{ie}
\subsubsection{Arithmetic Expression}
In this example we will define an arithmetic expression whose operands are integer numbers  by means of lexicon and grammar defined in sections \ref{lf} and \ref{gf} and give an example of an arithmetic expression that can be used as contents of a source file.

\subsubsubsection{Lexicon File}\label{alex}
\begin{verbatim}
num = -?([1-9][0-9]+|0)
add_op = \+|-
mult_op = :|\*
left_paren = \(
right_paren = \)
\end{verbatim} 
\subsubsubsection{Grammar File}\label{agram}

\begin{verbatim}
expr(T1) ::= T1
T1(T2) ::= T2
T1(add M1 M2) ::= T2(M1) add_op T1(M2)
T2(mult Op1 Op2) ::= T3(Op1) mult_op T2(Op2)
T2(T3) ::= T3
T3(expr) ::= left_paren expr right_paren
T3(num) ::= num   
\end{verbatim}
 
\subsubsubsection{Source File}\label{asf}
\begin{verbatim}
1+2*3
\end{verbatim}
\subsubsection{Chess Notation}
In this example we will define Algebraic Chess Notation \cite{chess} by means of lexicon and grammar defined in sections \ref{lf} and \ref{gf} and give an example of a game described in this notation. 
\subsubsubsection{Lexicon file}\label{clex}
\begin{verbatim}
figure = K|Q|R|B|N
file = [a-h]
rank = [1-8]
cell = [a-h][1-8]
capture_char = x
space = \s
dot = \.
en_passant = e\.p\.
natural_number = [1-9][0-9]+
move_id = [1-9][0-9]+\.
long_castling = 0-0-0
short_castling = 0-0
plus = \+
pound_sign = #
end = 1-0|1/2-1/2|0-1
\end{verbatim}
\subsubsubsection{Grammar file}\label{cgram}
\begin{verbatim}
game(game move_d) ::= move_d 
game(game move_d cut_root(G)) ::= move_d   game(G)
move_d(move move_id M1 M2) ::= move_id  move(M1) move(M2)
move_d(game_over  move_id move) ::= move_id move end
move_d(game_over  move_id checkmate) ::= move_id checkmate 
move(pawn_move cell) ::= cell
move(move figure_spec cell) ::= figure_spec cell
move(capture figure_spec cell) ::= figure_spec capture_char cell
move(pawn_capture file cell) ::= file capture_char cell
move(pawn_special_capture) ::= file capture_char cell en_passant
move(promotion cell figure) ::= cell figure
move(castling long_castling) ::= long_castling
move(castling short_castling) ::= short_castling
move(checkmate c) ::= checkmate(c)
move(check c) ::= check(c)
check(check move) ::= move plus
checkmate(checkmate move) ::= move pound_sign
figure_spec(fig figure) ::= figure
figure_spec(fig figure file) ::= figure file
figure_spec(fig figure rank) ::= figure rank
figure_spec(fig figure cell) ::= figure cell
\end{verbatim}

\subsubsubsection{Source File}\label{csf}
\begin{comment}
\begin{verbatim}

1. e4 c5 2. Nf3 d6 3. Bb5 Bd7 4. Bxd7 Qxd7 5. c4 Nc6 6. Nc3 Nf6 
7. 0-0 g6 8. d4 cxd4 9. Nxd4 Bg7 10. Nde2 Qe6  11. Nd5 Qxe4 
12. Nc7+ Kd7 13. Nxa8 Qxc4 14. Nb6+ axb6 15. Nc3 Ra8 16. a4 Ne4 
17. Nxe4 Qxe4 18. Qb3 f5 19. Bg5 Qb4 20. Qf7 Be5 21. h3 Rxa4 
22. Rxa4 Qxa4 23. Qxh7 Bxb2 24. Qxg6 Qe4 25. Qf7 Bd4 26. Qb3 f4 
27. Qf7 Be5 28. h4 b5 29. h5 Qc4 30. Qf5+ Qe6 31. Qxe6+ Kxe6 
32. g3 fxg3 33. fxg3 b4 34. Bf4 Bd4 
35. Kh1! b3 36. g4 Kd5 37. g5 e6 38. h6 Ne7 39. Rd1 e5 40. Be3 Kc4 
41. Bxd4 exd4 42. Kg2 b2 43. Kf3 Kc3 44. h7 Ng6 45. Ke4 Kc2 
46. Rh1 d3 47. Kf5 b1=Q 48. Rxb1 Kxb1 49. Kxg6 d2 50. h8=Q d1=Q 
51. Qh7 b5 52. Kf6 Kb2 53. Qh2 Ka1 54. Qf4 b4 55. Qxb4 Qf3+ 
56. Kg7 d5 57. Qd4 Kb1 58. g6 Qe4 59. Qg1 Kb2 60. Qf2+ Kc1 
61. Kf6 d4 62. g7 1-0 
\end{verbatim}
\end{comment}

\begin{verbatim}
1. e4 e5 2. Qh5 Nc6 3. Bc4 Nf6 4. Qxf7# 
\end{verbatim}

\section{Output specification}
The output is obtained in two steps
\begin{enumerate}
\item \textit{Lexing}.  \textit{Lexer Module} takes a source file and lexicon file and outputs a sequence of annotated lexemes as specified in section \ref{lex}.
\item \textit{Parsing}. \textit{Parser Module} takes an output of the lexer module and grammar file as an input and returns an abstract tree as specified in section \ref{pars}.
\end{enumerate}

\subsection{Lexing}\label{lex}
In addition to thee  set of lexeme types  declared in the lexicon file, denoted by $S_L$, we introduce two more lexemes: $id$, $num$ and $spaces$.  For each lexeme $l$, we define a regular expression $\mathcal{R}_L(l)$ as follows:

\begin{enumerate}
\item if $l \in S_L$, $\mathcal{R}_L(l) = expr$, where $expr$ is the regular expression  on the right hand side of the statement
$$l = expr$$
appearing in the lexicon file;
\item if $l$ is $id$, $\mathcal{R}_L(l)$ is 
                               $$[a-zA-Z]\backslash w^*$$
\item if $l$ is $num$, $\mathcal{R}_L(l)$ is  
                $$-?[1-9][0-9]* |-?0?\backslash.[0-9]+ | -?[1-9][0-9]*\backslash.[0-9]+$$ 
\item if $l$ is $spaces$, $\mathcal{R}_L(l)$ is  
                $$\backslash s+$$ 
\end{enumerate}


We will say that a string $S$ \textit{matches} a regular expression $E$ if $S$ is a member of the set of strings specified by  the python regular expression 
$$\wedge (E) \backslash Z $$
In other words, $S$ matches $E$ if the following python code prints \texttt{True}, when being run on a   python3.4 interpreter:
\begin{alltt}
import re
regex = re.compile(r"^\((E)\)\textbackslash{}Z")
print(regex.match("\(S\)") != None)
\end{alltt}

The symbols $\wedge$ and $\$$ are added to $E$ to ensure that the whole string, but not its prefix or suffix are matched. More details on  the syntax and semantics of python regular expressions can be found in \cite{pythonre}.

Let $I$ be the string that represents the contents of the input file. 
The \textit{lexing sequence} of $I$ with respect to the lexicon file $L$ is a sequence of pairs $(l_1,s_1),\ldots (l_n,s_n)$, such that:

\begin{enumerate}
\item each $l_i$ is a lexeme which is a member of the set $S_L \cup \{id,num\}$;
\item each $s_i$ is a string;
\item $s_1+\ldots+s_n$ = $I$ (where + denotes concatenation);
\item for each $1 \le i  \le n$, $s_i$ matches $\mathcal{R}_L(l_i)$;
\item for each $1 \le i \le n$, $s_i$ is the longest prefix of $s_i+\ldots+s_n$ such that $s_i$ matches  $\mathcal{R}_L(l)$ for some  $l \in  S_L \cup \{id,num\}$ 
\end{enumerate}


We will refer to each element of the lexing sequence as an \textit{annotated lexeme}.






\subsection{Parsing}\label{pars}
Given a sequence of annotated lexemes  $(l_1,s_1),\ldots, (l_n,s_n)$ and a grammar $G$  the goal of parsing is to produce an abstract syntax tree  as defined in this section. 

\subsection{Abstract Syntax Trees for a  Grammar}

 We say that $T$ is \textit{an abstract syntax tree for a grammar $G$} if $T$ is a finite rooted ordered\footnote{A finite tree  is \textit{ordered} if the children of each node of the tree are pairwise distinct and totally ordered. That is, we can define a correspondence between the children of a node $V$ of the tree and the set of natural numbers \{1,\ldots,\ldots,$n$\}, and refer to the children of $V$  as $1^{st}, 2^{nd}, \ldots, n^{th}$ child of $V$.}  tree  whose non-leaf nodes are labeled by  labels of $G$ and whose leafs are labeled by terminals of $G$.  

Let $T_1$ and $T_2$ be two trees of $G$. We say $T_1$ is a \textit{subtree} of $T_2$ if the following three conditions hold:

\begin{enumerate}
\item the root of $T_2$ is a node of $T_1$;
\item the nodes of $T_2$  different from $r$ are the descendants of $r$ in $T_1$;
\item every edge of $T_2$ is an edge of $T_1$.
\end{enumerate}

\begin{example}\label{ex1}
Consider the tree $T$ shown below\footnote{The children of nodes in the tree are shown from left to right according to their order.} :
\begin{center}
\Tree [.$add$ $(num,1)$ [.$mult$ $(num,2)$  $(num,3)$ ]  [.$mult$ $(num,4)$  $(num,5)$ ]]   
\end{center}

The tree $T$ has 8 subtrees: $T$ itself, the five trees containing only one node which is a leaf of $T$ and two trees rooted at the nodes labeled by $mult$ shown below:

\begin{center}
\Tree [.$mult$ $(num,2)$  $(num,3)$ ]    \Tree [.$mult$ $(num,4)$  $(num,5)$ ]  
\end{center}

 
\end{example}
If $T$ is an abstract tree of $G$, by $cut\_root$ we define a sequence of trees i-th of which is rooted at i-th child of the root of $T$.

\begin{example}
If $T$ is a tree given in example \ref{ex1}, $cut\_root$ is a sequence of three trees shown below (from left to right):
\begin{center}
\Tree [.$(num,1)$ ]  \Tree [.$mult$ $(num,2)$  $(num,3)$ ]  \Tree [.$mult$ $(num,4)$  $(num,5)$ ]
 \end{center}
\end{example}
 

\subsection{Parsing output specification}

Let $G$ be a stratified grammar with a symbol $S$,  $(l_1,s_1),\ldots, (l_n,s_n)$ be a lexing sequence denoted by $L$, $b$ and $e$ be two natural numbers such that $1 \le b \le e \le n$.


 By $R_{G,L}(S,b,e)$ we denote an abstract syntax tree for $G$ satisfying one of the following two conditions: 
\begin{enumerate}
\item if $b = e$ and $S$ is  $l_b$, 
 $R_{G,L}(S,b,e)$ contains only one node labeled by $(l_b, s_b)$

 
\item if S is a non-terminal of $G$, and there is a statement in $G$ of the form 
$$ S(\beta_1 \ldots \beta_m) = \alpha_1(\tau_1) \ldots  \alpha_n(\tau_n)  $$
where 
\begin{itemize}
\item $l_b \dots l_e = l^1_1,l^1_2 \ldots l^1_{k_1} \ldots l^n_1 \ldots l^n_{k_n}$ for some  $1 \le k_1,\ldots,k_n \le (e-b+1)$,
\item for each $1\le i \le n$ there exists a tree denoted by $$R_{G,L}(\alpha_i,k_1+ \ldots + k_{i-1}+1, k_1+ \ldots + k_{i})$$
\end{itemize}
then
\begin{itemize}
\item if $\beta_1 = \tau_j$ for some $ 1\le j \le n$, then

  $R_{G,L}(S,b,e)$ is $R_{G,L}(\alpha_j,k_1+ \ldots + k_{j-1}+1, k_1+ \ldots + k_{j})$  

\item if $\beta_1 \not= \tau_j$ and  $\beta_1 \not= cut\_root(\tau_j)$   for all $ 1\le j \le n$, 

  then $R_{G,L}(S,b,e)$ is a tree whose root $r$ is labeled by $\beta_1$ and the tree $T_i$ whose root is the $i^{th}$ child of $r$ is obtained as follows:
 \begin{enumerate}
 \item Let $f:\{2..m\} \to \{1..n\}$ be a function such that for any $j \in \{2..m\}$ $\beta_j = \tau_{f(j)}$ or  $\beta_j = cut\_root(\tau_{f(j)})$.
 \item For each $1\le j \le n$ let $A_j$ be an abstract syntax tree denoted by $R(\alpha_j,k_1+ \ldots + k_{j-1}+1, k_1+ \ldots + k_{j})$
 \item Let $c:\{2..m\} \to \mathbb{N}$ be a function defined as follows:

\[
c(u) = 
\begin{cases}
             1,& \beta_u \in \{\tau_1 \dots \tau_n\} \\
  \text{the number of children of the root of } T_{f(u)},          & \text{otherwise}
\end{cases}
\]
\item Let $p$ be the largest number in the range $[1..m]$ such that $$c(2) + \ldots + c(p) < i$$
\item if $\beta_{p+1}$ is of the form $cut\_root(\tau_j)$, $T_i$ is the $(i - (c(2) + \ldots + c(p)))^{th}$ child of $A_p$;
      otherwise $T_i$ is $A_p$

 \end{enumerate}
 \end{itemize}
 \end{enumerate}

We will refer  $R_{G,L}(S,b,e)$ as  an abstract syntax tree of $G$ \textit{matching the lexing sequence $l_b, \ldots, l_e$ on $S$}. 
The result of the parsing is defined to be the abstract syntax tree matching the lexing sequence $l_1, \ldots, l_n$ on the starting symbol of $G$.  


\subsection{Trees Representation}\label{treesec}
Let $T$ be an abstract syntax tree .
In the implementation, $T$ is  represented as follows:
\begin{enumerate}
\item if $T$ is empty, it is represented by an empty list;
\item if $T$ consists of only one node labeled by $l$, it is represented the label $l$;
\item if a tree consists of more then one node, it is represented by the list $[r,t_1,\ldots,t_n]$, where $r$ is a label of the root of $T$ and  $t_i$ is the representation of the subtree of $T$ rooted at $i^{th}$ child of $T$ 
\end{enumerate}

\subsection{Examples}
\subsubsection{Arithmetic Expression Tree}

The lexing sequence for the  lexicon file given in section \ref{alex} and source file given in section \ref{asf} is:
\begin{verbatim}
(num '1'), (add_op, '+'), (num, '2'), (mult_op,'*'), (num, '3') 
\end{verbatim}

Given the grammar file in section \ref{agram}, the corresponding abstract syntax tree is represented by the list:
\begin{verbatim}
[add, (num,'1'),[mult,(num,'2'),(num,'3')]]
\end{verbatim}
\subsubsection{Chess Game Tree}

The lexing sequence for the  lexicon file given in section \ref{clex} and source file given in section \ref{csf} is:

\begin{verbatim}
(move_id, '1.'), (spaces, ' ') (cell, 'e4'), (spaces, ' '), 
(cell, 'e5'), (spaces, ' '), (move_id, '2.'), (spaces, ' '), 
(figure, 'Q'), (cell, 'h5'), (space, ' '), (figure, 'B'),
(cell, 'c6'), (spaces, ' '), (move_id, '3.'), (spaces, ' '), 
(figure, 'B'), (cell, 'c4'), (spaces, ' '),  (figure, 'N'), 
(cell, 'f6'), (spaces, ' '), (move_id, '4.'), (spaces, ' '), 
(figure, 'Q'), (capture_char, 'x'), (cell, 'f7'),  
(pound_sign, '#')
\end{verbatim} 

\st
Given the grammar file in section \ref{cgram}, the corresponding abstract syntax tree  is represented by the list\footnote{All lexemes annotated as spaces are dropped from the lexing sequence before parsing is done}:

\begin{verbatim}
[ game,
      [move, [(move_id '1.')], [pawn_move [(cell 'e4')] ], 
                                [pawn_move [(cell 'e5')] ] ],
       
      [move, [(move_id '2.')], [move [fig [(figure 'Q')]] 
                                     [(cell 'h5')] ], 
                                     [move, [fig [(figure 'N')]], 
                                     [(cell 'c6')]]],
           
      [move, [(move_id '3.')], [move [fig [(figure 'B')]],
                                               [(cell 'c4')] ], 
                                         [move, [fig [(figure 'N') ]], 
                                         [(cell 'f6')]]],
               
      [checkmate   [move, [(move_id '4.')],
                                       [capture [fig [(figure 'Q')] ], 
                                       [(cell 'f7')] ] ] ]
               
]
\end{verbatim}



   
\bibliography{mylib}
\bibliographystyle{plain}
\end{document}
