% (find-angg "LATEX/2010luayacc.tex")
% (find-dn4ex "edrx08.sty")
% (find-angg ".emacs.templates" "s2008a")
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010luayacc.tex && latex    2010luayacc.tex"))
% (defun c () (interactive) (find-zsh "cd ~/LATEX/ && ~/dednat4/dednat41 2010luayacc.tex && pdflatex 2010luayacc.tex"))
% (eev "cd ~/LATEX/ && Scp 2010luayacc.{dvi,pdf} edrx@angg.twu.net:slow_html/LATEX/")
% (defun d () (interactive) (find-dvipage "~/LATEX/2010luayacc.dvi"))
% (find-dvipage "~/LATEX/2010luayacc.dvi")
% (find-pspage  "~/LATEX/2010luayacc.ps")
% (find-pspage  "~/LATEX/2010luayacc.pdf")
% (find-xpdfpage "~/LATEX/2010luayacc.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvipdf         2010luayacc.pdf 2010luayacc.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o 2010luayacc.ps 2010luayacc.dvi")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 600 -P pk -o 2010luayacc.ps 2010luayacc.dvi && ps2pdf 2010luayacc.ps 2010luayacc.pdf")
% (find-zsh0 "cd ~/LATEX/ && dvips -D 300 -o tmp.ps tmp.dvi")
% (find-pspage  "~/LATEX/tmp.ps")
% (ee-cp "~/LATEX/2010luayacc.pdf" (ee-twupfile "LATEX/2010luayacc.pdf") 'over)
% (ee-cp "~/LATEX/2010luayacc.pdf" (ee-twusfile "LATEX/2010luayacc.pdf") 'over)
% (find-twusfile     "LATEX/" "2010luayacc")
% http://angg.twu.net/LATEX/2010luayacc.pdf

\documentclass[oneside]{book}
\usepackage[latin1]{inputenc}
\usepackage{edrx08}       % (find-dn4ex "edrx08.sty")
%L process "edrx08.sty"  -- (find-dn4ex "edrx08.sty")
\input edrxheadfoot.tex   % (find-dn4ex "edrxheadfoot.tex")
\begin{document}

\input 2010luayacc.dnt

%*
% (eedn4-51-bounded)

%Index of the slides:
%\msk
% To update the list of slides uncomment this line:
%\makelos{tmp.los}
% then rerun LaTeX on this file, and insert the contents of "tmp.los"
% below, by hand (i.e., with "insert-file"):
% (find-fline "tmp.los")
% (insert-file "tmp.los")

The language:

$\begin{array}{ccc}
N &\to& 2 \;|\; 3 \;|\; 4 \;|\; 5 \\
M &\to& N \;|\; N*M \\
A &\to& M \;|\; A+M \\
 \end{array}
$

\bsk

The parse tree for ``\verb!2*3*4+5*6!''

(the subscripts indicate order of production):

\def\ptok      #1#2#3{\underbrace{\mathstrut#1}_{#2_{#3}}}
\def\ptok      #1#2#3{\underbrace{\mathstrut{\tt #1}}_{#2_{#3}}}
\def\pprodone  #1#2#3{\underbrace{#1}_{#2_{#3}}}
\def\pprodtwo  #1#2#3#4{\underbrace{#1#2}_{#3_{#4}}}
\def\pprodthree#1#2#3#4#5{\underbrace{#1\;#2\;#3}_{#4_{#5}}}

$$
{\pprodthree
 {\pprodone
  {\pprodthree
   {\ptok{2}{N}{1}}
   {\ptok{*}{*}{2}}
   {\pprodthree
    {\ptok{3}{N}{3}}
    {\ptok{*}{*}{4}}
    {\pprodone
     {\ptok{4}{N}{5}}
     {M}{7}}
    {M}{8}}
   {M}{9}}
  {A}{10}}
 {\ptok{+}{+}{6}}
 {\pprodthree
  {\ptok{5}{N}{11}}
  {\ptok{*}{*}{12}}
  {\pprodone
   {\ptok{6}{N}{13}}
   {M}{14}}
  {M}{15}}
 {A}{16}}
$$

\msk

\newsavebox{\myboxunordered}
\newsavebox{\myboxordered}
\newsavebox{\myboxshort}

\setbox0=\hbox{%
\begin{minipage}[c]{5.0cm}
\par \verb! _1: 0 1 N!
\par \verb! _2: 1 2 *!
\par \verb! _3: 2 3 N!
\par \verb! _4: 3 4 *!
\par \verb! _5: 4 5 N!
\par \verb! _6: 5 6 +!
\par \verb! _7: _5 N->M!
\par \verb! _8: _3 _4 _7 N*M->M!
\par \verb! _9: _1 _2 _8 N*M->M!
\par \verb!_10: _9 M->A!
\par \verb!_11: 6 7 N!
\par \verb!_12: 7 8 *!
\par \verb!_13: 8 9 N!
\par \verb!_14: _13 N->M!
\par \verb!_15: _11 _12 _14 N*M->M!
\par \verb!_16: _10 _6 _15 A+M->A!
\end{minipage}%
}
\savebox{\myboxunordered}{\copy0}

\setbox0=\hbox{%
\begin{minipage}[c]{5.0cm}
\par \verb!  _1: 0 1 N!
\par \verb!  _2: 1 2 *!
\par \verb!   _3: 2 3 N!
\par \verb!   _4: 3 4 *!
\par \verb!    _5: 4 5 N!
\par \verb!   _7: _5 N->M!
\par \verb!  _8: _3 _4 _7 N*M->M!
\par \verb! _9: _1 _2 _8 N*M->M!
\par \verb!_10: _9 M->A!
\par \verb!_6: 5 6 +!
\par \verb!  _11: 6 7 N!
\par \verb!  _12: 7 8 *!
\par \verb!   _13: 8 9 N!
\par \verb!  _14: _13 N->M!
\par \verb! _15: _11 _12 _14 N*M->M!
\par \verb!_16: _10 _6 _15 A+M->A!
\end{minipage}%
}
\savebox{\myboxordered}{\copy0}

\setbox0=\hbox{%
\begin{minipage}[c]{2.5cm}
\par \verb!   0 1 N!
\par \verb!   1 2 *!
\par \verb!    2 3 N!
\par \verb!    3 4 *!
\par \verb!     4 5 N!
\par \verb!    N->M!
\par \verb!   N*M->M!
\par \verb!  N*M->M!
\par \verb! M->A!
\par \verb! 5 6 +!
\par \verb!  6 7 N!
\par \verb!  7 8 *!
\par \verb!   8 9 N!
\par \verb!  N->M!
\par \verb! N*M->M!
\par \verb!A+M->A!
\end{minipage}%
}
\savebox{\myboxshort}{\copy0}

\def\foobox#1#2{\begin{tabular}{l} #1 \\ \fbox{\usebox{#2}}\end{tabular}}

\foobox{Unordered output (original):}{\myboxunordered}
\foobox{Reordered:}{\myboxordered}
\foobox{Shortened:}{\myboxshort}

\newpage


The program (foo2.y):

{\myttchars
\footnotesize
\begin{verbatim}
%{
#include <stdio.h> /* for printf */
int nline = 0;     /* global */
#define PPROD1(d1,dd, pstr)       \
  printf("_%d: _%d "pstr"\n", ++nline, d1); \
  dd = nline;
#define PPROD2(d1,d2,dd, pstr)    \
  printf("_%d: _%d _%d "pstr"\n", ++nline, d1, d2); \
  dd = nline;
#define PPROD3(d1,d2,d3,dd, pstr) \
  printf("_%d: _%d _%d _%d "pstr"\n", ++nline, d1, d2, d3); \
  dd = nline;
#define TOK1(tstr, tok) \
  printf("_%d: %d %d "tstr"\n", ++nline, yypos, yypos+1); \
  ++yypos; yylval.nline = nline; return tok;
%}
%union {
  int nline;
}
%token <nline> N '+' '*'
%type  <nline> A M

%% /* The grammar follows.  */
A:    M        { PPROD1($1, $$,           "M->A"); }
    | A '+' M  { PPROD3($1, $2, $3, $$, "A+M->A"); }
;
M:    N        { PPROD1($1, $$,           "N->M"); }
    | N '*' M  { PPROD3($1, $2, $3, $$, "N*M->M"); }
;
/* End of grammar.  */
%%

/* Called by yyparse on error.
*/
void yyerror (char const *msg) {
  printf ("%s\n", msg);
}
char  yylex_input[] = "2*3*4+5*6";
char *yylex_ptr = yylex_input;
int   yypos = 0;
int yylex (void) {
  int c = yylex_input[yypos];
  if (c == EOF) { return 0; }
  if (c == '*') { TOK1("*", '*'); }
  if (c == '+') { TOK1("+", '+'); }
  if ('0' <= c && c <= '9') { TOK1("N", N); }
  /* no error-handling code yet */
}
int main (void) {
  return yyparse();
}
\end{verbatim}
}




%*

\end{document}

% Local Variables:
% coding:           raw-text-unix
% ee-anchor-format: "«%s»"
% End: