[Commit] mint/doc architecture.fig, NONE, 1.1 architecture.pstex, NONE, 1.1 architecture.pstex_t, NONE, 1.1 fig1.fig, 1.1, NONE mintsec.tex, NONE, 1.1

Emma Kuo commit at keithp.com
Mon Nov 29 11:59:09 PST 2004


Committed by: ekuo

Update of /local/src/CVS/mint/doc
In directory home.keithp.com:/tmp/cvs-serv4789

Added Files:
	architecture.fig architecture.pstex architecture.pstex_t 
	mintsec.tex 
Removed Files:
	fig1.fig 
Log Message:


--- NEW FILE: architecture.fig ---
#FIG 3.2
Portrait
Center
Inches
Letter  
100.00
Single
-2
1200 2
6 5203 3039 5718 3586
6 5258 3155 5663 3470
4 0 0 50 0 4 10 0.0000 2 150 405 5258 3275 lexing\001
4 0 0 50 0 4 10 0.0000 2 120 330 5258 3470 table\001
-6
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 5203 3039 5718 3039 5718 3586 5203 3586 5203 3039
-6
6 3000 2636 7080 2786
4 0 0 50 0 4 10 0.0000 2 120 930 6150 2756 MINT runtime\001
4 0 0 50 0 4 10 0.0000 2 120 645 5107 2756 table files\001
4 0 0 50 0 4 10 0.0000 2 150 1530 3000 2756 parser/lexer generator\001
-6
6 5200 4037 5715 4585
6 5202 4138 5712 4483
4 0 0 50 0 4 10 0.0000 2 120 330 5202 4483 table\001
4 0 0 50 0 4 10 0.0000 2 150 510 5202 4258 parsing\001
-6
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 5200 4037 5715 4037 5715 4585 5200 4585 5200 4037
-6
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 4655 3296 5203 3296
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 4655 4295 5203 4295
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 5718 3296 6266 3296
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 5718 4295 6266 4295
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 6620 3586 6620 4037
2 1 0 1 0 7 50 0 -1 6.000 0 0 -1 1 0 4
	1 1 2.00 51.54 103.08
	 3560 3747 3689 3747 3689 3296 3914 3296
2 1 0 1 0 7 50 0 -1 6.000 0 0 -1 1 0 4
	1 1 2.00 51.54 103.08
	 3560 3844 3689 3844 3689 4295 3914 4295
2 1 0 1 0 7 50 0 -1 6.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 2432 3779 2819 3779
2 4 1 1 0 7 50 0 -1 4.000 0 0 3 0 0 5
	 4816 4810 4816 2813 2593 2813 2593 4810 4816 4810
2 4 1 1 0 7 50 0 -1 4.000 0 0 3 0 0 5
	 7275 4800 7275 2813 6000 2813 6000 4800 7275 4800
2 4 1 1 0 7 50 0 -1 4.000 0 0 3 0 0 5
	 5850 4800 5850 2813 4977 2813 4977 4800 5850 4800
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 7548 3300 7009 3300
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 2819 3554 3560 3554 3560 4101 2819 4101 2819 3554
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 3914 3039 4655 3039 4655 3586 3914 3586 3914 3039
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 3914 4037 4655 4037 4655 4585 3914 4585 3914 4037
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 6266 3039 7007 3039 7007 3586 6266 3586 6266 3039
2 2 0 1 0 7 50 0 -1 4.000 0 0 -1 0 0 5
	 6266 4037 7007 4037 7007 4585 6266 4585 6266 4037
2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 0 2
	1 1 2.00 51.54 103.08
	 7009 4275 7557 4275
4 0 0 50 0 4 10 0.0000 2 120 600 1800 3900 grammar\001
4 0 0 50 0 4 10 0.0000 2 150 345 1800 3750 input\001
4 0 0 50 0 4 10 0.0000 2 150 690 7596 4315 parse tree\001
4 0 0 50 0 4 10 0.0000 2 120 435 2850 4022 parser\001
4 0 0 50 0 4 10 0.0000 2 120 600 2850 3872 grammar\001
4 0 0 50 0 4 10 0.0000 2 120 375 2850 3722 MINT\001
4 0 0 50 0 4 10 0.0000 2 120 330 3975 3260 lexer\001
4 0 0 50 0 4 10 0.0000 2 150 675 3975 3455 generator\001
4 0 0 50 0 4 10 0.0000 2 120 435 3975 4243 parser\001
4 0 0 50 0 4 10 0.0000 2 150 675 3975 4438 generator\001
4 0 0 50 0 4 10 0.0000 2 120 330 6471 3372 lexer\001
4 0 0 50 0 4 10 0.0000 2 120 435 6419 4341 parser\001
4 0 0 50 0 4 10 0.0000 2 150 795 7592 3355 input string\001

--- NEW FILE: architecture.pstex ---
%!PS-Adobe-2.0 EPSF-2.0
%%Title: architecture.pstex
%%Creator: fig2dev Version 3.2 Patchlevel 4
%%CreationDate: Mon Nov 29 11:09:16 2004
%%For: emma at kyo (,,,)
%%BoundingBox: 0 0 397 132
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
newpath 0 132 moveto 0 0 lineto 397 0 lineto 397 132 lineto closepath clip newpath
-108.0 289.3 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
10 setmiterlimit
0 slj 0 slc
 0.06000 0.06000 sc
%
% Fig objects follow
%
% 
% here starts figure with depth 50
% Polyline
7.500 slw
n 5203 3039 m 5718 3039 l 5718 3586 l 5203 3586 l
 cp gs col0 s gr 
% Polyline
n 5200 4037 m 5715 4037 l 5715 4585 l 5200 4585 l
 cp gs col0 s gr 
% Polyline
gs  clippath
5218 3321 m 5218 3270 l 5067 3270 l 5171 3296 l 5067 3321 l cp
eoclip
n 4655 3296 m
 5203 3296 l gs col0 s gr gr

% arrowhead
15.000 slw
n 5067 3321 m 5171 3296 l 5067 3270 l 5067 3321 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
5218 4320 m 5218 4269 l 5067 4269 l 5171 4295 l 5067 4320 l cp
eoclip
n 4655 4295 m
 5203 4295 l gs col0 s gr gr

% arrowhead
15.000 slw
n 5067 4320 m 5171 4295 l 5067 4269 l 5067 4320 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
6281 3321 m 6281 3270 l 6130 3270 l 6234 3296 l 6130 3321 l cp
eoclip
n 5718 3296 m
 6266 3296 l gs col0 s gr gr

% arrowhead
15.000 slw
n 6130 3321 m 6234 3296 l 6130 3270 l 6130 3321 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
6281 4320 m 6281 4269 l 6130 4269 l 6234 4295 l 6130 4320 l cp
eoclip
n 5718 4295 m
 6266 4295 l gs col0 s gr gr

% arrowhead
15.000 slw
n 6130 4320 m 6234 4295 l 6130 4269 l 6130 4320 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
6594 4052 m 6645 4052 l 6645 3901 l 6620 4005 l 6594 3901 l cp
eoclip
n 6620 3586 m
 6620 4037 l gs col0 s gr gr

% arrowhead
15.000 slw
n 6594 3901 m 6620 4005 l 6645 3901 l 6594 3901 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
3929 3321 m 3929 3270 l 3778 3270 l 3882 3296 l 3778 3321 l cp
eoclip
n 3560 3747 m 3689 3747 l 3689 3296 l
 3914 3296 l gs col0 s gr gr

% arrowhead
15.000 slw
n 3778 3321 m 3882 3296 l 3778 3270 l 3778 3321 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
3929 4320 m 3929 4269 l 3778 4269 l 3882 4295 l 3778 4320 l cp
eoclip
n 3560 3844 m 3689 3844 l 3689 4295 l
 3914 4295 l gs col0 s gr gr

% arrowhead
15.000 slw
n 3778 4320 m 3882 4295 l 3778 4269 l 3778 4320 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
gs  clippath
2834 3804 m 2834 3753 l 2683 3753 l 2787 3779 l 2683 3804 l cp
eoclip
n 2432 3779 m
 2819 3779 l gs col0 s gr gr

% arrowhead
15.000 slw
n 2683 3804 m 2787 3779 l 2683 3753 l 2683 3804 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
 [60] 0 sd
n 2638 2813 m 2593 2813 2593 4765 45 arcto 4 {pop} repeat
  2593 4810 4771 4810 45 arcto 4 {pop} repeat
  4816 4810 4816 2858 45 arcto 4 {pop} repeat
  4816 2813 2638 2813 45 arcto 4 {pop} repeat
 cp gs col0 s gr  [] 0 sd
% Polyline
 [60] 0 sd
n 6045 2813 m 6000 2813 6000 4755 45 arcto 4 {pop} repeat
  6000 4800 7230 4800 45 arcto 4 {pop} repeat
  7275 4800 7275 2858 45 arcto 4 {pop} repeat
  7275 2813 6045 2813 45 arcto 4 {pop} repeat
 cp gs col0 s gr  [] 0 sd
% Polyline
 [60] 0 sd
n 5022 2813 m 4977 2813 4977 4755 45 arcto 4 {pop} repeat
  4977 4800 5805 4800 45 arcto 4 {pop} repeat
  5850 4800 5850 2858 45 arcto 4 {pop} repeat
  5850 2813 5022 2813 45 arcto 4 {pop} repeat
 cp gs col0 s gr  [] 0 sd
% Polyline
gs  clippath
6994 3274 m 6994 3325 l 7144 3325 l 7041 3300 l 7144 3274 l cp
eoclip
n 7548 3300 m
 7009 3300 l gs col0 s gr gr

% arrowhead
15.000 slw
n 7144 3274 m 7041 3300 l 7144 3325 l 7144 3274 l  cp gs 0.00 setgray ef gr  col0 s
% Polyline
7.500 slw
n 2819 3554 m 3560 3554 l 3560 4101 l 2819 4101 l
 cp gs col0 s gr 
% Polyline
n 3914 3039 m 4655 3039 l 4655 3586 l 3914 3586 l
 cp gs col0 s gr 
% Polyline
n 3914 4037 m 4655 4037 l 4655 4585 l 3914 4585 l
 cp gs col0 s gr 
% Polyline
n 6266 3039 m 7007 3039 l 7007 3586 l 6266 3586 l
 cp gs col0 s gr 
% Polyline
n 6266 4037 m 7007 4037 l 7007 4585 l 6266 4585 l
 cp gs col0 s gr 
% Polyline
gs  clippath
7572 4300 m 7572 4249 l 7421 4249 l 7525 4275 l 7421 4300 l cp
eoclip
n 7009 4275 m
 7557 4275 l gs col0 s gr gr

% arrowhead
15.000 slw
n 7421 4300 m 7525 4275 l 7421 4249 l 7421 4300 l  cp gs 0.00 setgray ef gr  col0 s
% here ends figure;
$F2psEnd
rs
showpage

--- NEW FILE: architecture.pstex_t ---
\begin{picture}(0,0)%
\includegraphics{architecture.pstex}%
\end{picture}%
\setlength{\unitlength}{3947sp}%
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset at font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(6607,2186)(1801,-3983)
\put(5259,-2436){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}lexing}%
}}}}
\put(5259,-2631){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}table}%
}}}}
\put(6151,-1917){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}MINT runtime}%
}}}}
\put(5108,-1917){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}table files}%
}}}}
\put(3001,-1917){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parser/lexer generator}%
}}}}
\put(5203,-3644){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}table}%
}}}}
\put(5203,-3419){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parsing}%
}}}}
\put(1801,-3061){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}grammar}%
}}}}
\put(1801,-2911){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}input}%
}}}}
\put(7597,-3476){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parse tree}%
}}}}
\put(2851,-3183){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parser}%
}}}}
\put(2851,-3033){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}grammar}%
}}}}
\put(2851,-2883){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}MINT}%
}}}}
\put(3976,-2421){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}lexer}%
}}}}
\put(3976,-2616){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}generator}%
}}}}
\put(3976,-3404){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parser}%
}}}}
\put(3976,-3599){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}generator}%
}}}}
\put(6472,-2533){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}lexer}%
}}}}
\put(6420,-3502){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}parser}%
}}}}
\put(7593,-2516){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{12.0}{\sfdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}input string}%
}}}}
\end{picture}%

--- fig1.fig DELETED ---

--- NEW FILE: mintsec.tex ---
%+ MINT [James, Emma]
%  + Design
%    + LOLA/FLO-style split between generator + lexer and
%      between generator + parser [fig]
%    + Lexer and parser isolated in libraries + Generates Canonical
%    LR(1) parsers + Produces ASTs
%  + Implementation
%    + Code base + Bootstrapping
%  + Achieving goals

\section{MINT}

\subsection{Design}

There are three elements in the design of MINT that differentiate it
from traditional parser and lexer generators such as YACC and LEX.

First, MINT implements a canonical LR(1) parser rather than SLR or
LALR.  Processor speeds and memory capacities have grown enough in the
twenty years since parsing techniques were first developed that it was
deemed unecessary to implement a more complex algorithm in order to
achieve a (possibly modest) table size reduction.

Second, rather than targetting a specific output language such as C,
MINT generates language independent lexing and parsing tables, which
can then be loaded by lexer/parser libraries (the MINT runtime)
implemented in the desired target language.

Third, MINT does not allow one to execute arbitary actions during the
parsing of input. Instead, MINT constructs an abstract syntax
tree. Grammar rules may additionally allow the special action of
changing the lexer state (also known as start condition in flex-like
parser generators.) This restriction on actions is due to the
difficulty of specifying arbitrary actions when the target language is
unknown, as it is in the MINT architecture.

\begin{figure*}[htbp]
\begin{center}
\input{architecture.pstex_t}
\caption{MINT Architecture}
\label{figure:architecture}
\end{center}
\end{figure*}

The design of MINT is split into two main sections: the MINT parser
and lexer generator, implemented in Nickle, and the MINT runtime,
which is currently implemented in Nickle but may be extended to other
languages. The output parsing and lexing tables are generated in a
simple line-oriented ASCII format that is easily parsed. Other formats
such as XML were considered, but dismissed as overly complicated for
this initial proof-of-concept application. Additionally, since the
lexer passes tokens to the parser, they need to agree on a standard
set of token specifications.

As stated above, MINT generates an abstract syntax tree after
successfully parsing a string. The advantage of this is that MINT can
generate parsers targetting arbitrary back-ends written in multiple
languages.

\subsection{Implementation}

The lexer generator uses Thompson's construction and an NFA to DFA
conversion to create the lexing table. Minimum-state DFA and table
compaction methods were not used.

The lexer is a standard DFA based algorithm with three enhancements:
lexer states (aka ``start conditions''), lookahead patterns, and
arbitrary size character sets. Because no code generation is performed
at at lexer generation time, the lexer cannot perform arbitrary
actions upon a rule match. The only allowed actions are to return a
token or ``none.'' Additionally the lexer may change its own state
upon matching a lexeme.

MINT implements lexer states that are similar to the ``start
condition'' present in FLEX. At any point in time, the lexer is in one
and only one state. Lexer matching rules only match if the lexer is in
the correct state. Rules may match in more than one state. This is
typically used to implement different modes of lexing-- for example,
string mode, or comment mode. The lexer's state may be changed
internally, by the lexer's own rule actions, or externally by a call
from the parser.

Lookahead patterns are implemented subject to the same restrictions as
for FLEX. That is, lookahead patterns such as ``ab*/b'' are not
allowed. Finally, the lexer can handle character sets of arbitrary
size, and this should be particularly useful with Unicode. Because a
lookup table would grow impractically large with such a large
character set, MINT's lexer implements the lexing table as an
adjacency list and transitions are matched based on character ranges.

The LR(1) parser generator algorithm is taken straight from the
classic text by Aho, Sethi, and Ullman. We decided to implement LR(1)
as opposed to SLR or LALR due to the simplicity of this algorithm and
the fact that memory sizes are large enough now that the compactness
of the tables is not so much of an issue. [cite table size statistics
for different algorithms] The parser generator is additionally
augmented with precedence rules to resolve shift/reduce conflicts.


\subsection{Achieving goals}

MINT was able to generate parsers for the regular expression and BNF
syntaxes fairly easily. Attempting to generate a parse table for a
small Nickle subset proved to be more difficult, however.




More information about the Commit mailing list