Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Construction of LR(k) parsers with application to Algol 68 Ramer, David Robert 1973

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1973_A6_7 R34_4.pdf [ 6.91MB ]
Metadata
JSON: 831-1.0052015.json
JSON-LD: 831-1.0052015-ld.json
RDF/XML (Pretty): 831-1.0052015-rdf.xml
RDF/JSON: 831-1.0052015-rdf.json
Turtle: 831-1.0052015-turtle.txt
N-Triples: 831-1.0052015-rdf-ntriples.txt
Original Record: 831-1.0052015-source.json
Full Text
831-1.0052015-fulltext.txt
Citation
831-1.0052015.ris

Full Text

r  CONSTRUCTION  OF LR (k)  WITH APPLICATION  PARSERS TO  ALGOL 68  by DAVID ROBERT RAMER B.Sc., U n i v e r s i t y o f B r i t i s h C o l u m b i a ,  A t h e s i s submitted  in partial  o f tohe r e q u i r e m e n t s Master in  fulfillment  f o r the degree o f  of Science  t h e Department of  Computer  Science  we a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the required standard  THE UNIVERSITY  OF BRITISH  August,  1971  1973  COLUMBIA  In presenting  this thesis in partial  fulfilment of the  requirements for  an advanced degree at the University of B r i t i s h Columbia, I agree that the Library shall make i t freely available for reference  and  study.  I further agree that permission for extensive copying of this thesis for scholarly purposes may by his representatives.  be granted by the Head of my  Department or  It is understood that copying or publication  of this thesis for financial gain shall not be allowed without written  permission.  Department of  Computer Science  The University of B r i t i s h Columbia Vancouver 8, Canada  Date  A ,i t 9 , 11g  S  1973  my  ii  ABSTRACT The  purpose  implementation recovery  as  of t h i s  thesis  i s  to  report  on  the  arad u s e o f t h e LR (k) p a r s i n g t e c h n i q u e applied  t o t h e c o m p u t e r programming  study,  with  error  language  ALGOL  68. The  LR (k)  automatic The  parsing  technique  construction  of  parsers  m e t h o d o l o g y p r o v i d e d by De  classes  o f LR (k) grammars.  translator  The  parsing  cannot  of having  translator  method  implemented  The p r a c t i c a l  error  of  grammars. for  implementation  recovery  An e r r o r  f o r ALGOL 68.  a string  a l l  of the  for  any  parsing  recovery technique i s  T h i s technique uses the process  to  determine  o f symbols n o t i n t h e language,  o f symbols i n the language. LR (k)  parsing  technique  technique are applied  t o ALGOL 68  techniques  construction  programming  i s  t o a i d i n the d e c i s i o n  t h e t r a n s f o r m a t i o n from  The  powerful  f o r context free  Remer  be o v e r s t a t e d .  and d e m o n s t r a t e d  to a s t r i n g  a  k t o 15.  necessity  technique provided  limits  is  in  the  languages.  and of  and  the  prove  error  to  compilers  be for  recovery practical computer  iii  TABLE OF CONTENTS INTRODUCTION  .....  1  CHAPTER 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8  1 - THEORY AND IMPLEMENTATION .4 N o t a t i o n and D e f i n i t i o n s .4 LR (k) Grammars 7 C h a r a c t e r i s t i c F i n i t e S t a t e M a c h i n e s ..............9 LR (0) Grammars and DPDA's .........................13 SLR (k) Grammars and L o o k a h e a d .....................21 LALR (k) Grammars 42 LR (k) Grammars and S t a t e - s p l i t t i n g ................46 Empty P r o d u c t i o n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52  CHAPTER 2.1 2.2 2.3 2.4  2 - PARSER GENERATOR IMPLEMENTATION . . . . . . . . . . . . . . . 55 The P a r s e r ........................................55 Further Optimizations 58 I n p u t o f CFG *...60 O u t p u t .<> .........6 3  CHAPTER 3.1 3.2 3.3  3 - ERROR RECOVERY Some I d e a s E r r o r Recovery Algorithm R e s u l t s Obtained  64 64 .......................... .....75  CHAPTER 4 - ALGOL 68 IMPLEMENTATION .......................83 4.1 The Grammar .......................................83 4.2 The C o m p i l e r ............86 CONCLUSION BIBLIOGRAPHY APPENDIX  ,....,...,90 . . ...  .,,...,...,.,......,91 .,  .......92  iv  L I S T OF FIGURES Figures 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 3.1 3.2 3.3 3.4  Example o f a CFSM ........................12 CFSM f o r LR{0) grammar 18 DPDA f o r L R ( 0 ) grammar ..................19 B a s i s S e t s o f CFSM f o r SLR(1) grammar . . . . . . . . . . . 26 Symbol T r a n s i t i o n s o f f i g u r e 1.4 . . . . . . . . . . . . . . . . 28 N o n t e r m i n a l T r a n s i t i o n L i s t s o f f i g u r e 1.4 ......29 L o o k a h e a d s y m b o l s e t f o r s t a t e 14 . . . . . . . . . . . . . . . 30 Symbol t a b l e e n t r y f o r s t a t e 14 o f DPDA .........30 L o o k a h e a d (k=1) symbol s e t f o r s t a t e 24 .........31 L o o k a h e a d (k=2) s y m b o l s e t f o r s t a t e 24 .........31 DPDA f o r SLR{2) grammar ..32 B a s i s S e t s o f CFSM f o r LALR (2) grammar ..........36 Symbol T r a n s i t i o n s o f f i g u r e 1.12 . . . . . . . . . . . . . . . 39 N o n t e r m i n a l T r a n s i t i o n L i s t s o f f i g u r e 1.12 .....40 L o o k a h e a d s y m b o l s e t f o r s t a t e 19 . . . . . . . . » . 4 1 L o o k a h e a d symbol s e t f o r s t a t e 21 ...............41 L o o k a h e a d s y m b o l s e t f o r s t a t e 24 ...............41 S t a t e S o u r c e L i s t s o f f i g u r e 1.12 ...............44 L o o k a h e a d s y m b o l s e t f o r s t a t e 19 ...............45 L o o k a h e a d s y m b o l s e t f o r s t a t e 21 ...............45 L o o k a h e a d s y m b o l s e t f o r s t a t e 24 ...............45 CFSM o f LR(1) grammar ,,.,,48 S t a t e S o u r c e L i s t s o f f i g u r e 1.22 .........49 L o o k a h e a d (k=1) symbol s e t f o r s t a t e 6 ..........49 L o o k a h e a d (k=2) s y m b o l s e t f o r s t a t e 6 ..........49 M o d i f i e d CFSM o f LR{1) grammar . . . . . . . . . . . . . . . . . . 50 S t a t e S o u r c e L i s t s o f f i g u r e 1.26 ...,,,..,,....,51 L o o k a h e a d s y m b o l s e t f o r s t a t e 6 ................52 L o o k a h e a d s y m b o l s e t f o r s t a t e 18 ...............52 CFSM f o r SLR(1) grammar , 53 DPDA o f f i g u r e 1.30 54 F1 and F2 f o r ALGOL 68 i m p l e m e n t a t i o n ....,.,..,,71 E v a l u a t i o n r e s u l t s o f 1 s t s y n t a c t i c e r r o r .,...,.77 E v a l u a t i o n r e s u l t s o f 2nd s y n t a c t i c e r r o r .......79 E v a l u a t i o n r e s u l t s o f 3 r d s y n t a c t i c e r r o r .....,,79  ACKNOWLEDGEMENT I would l i k e for  his assistance  NRC f o r t h e i r  t o t h a n k my s u p e r v i s o r . i n this  financial  research.  Dr.  J.  E.  L.  Peck,  I am a l s o g r a t e f u l t o t h e  support f o r t h i s  project.  1  INTRODUCTION  In the  writing  writer  program the in  i s faced  which  same  compilers  will  f o r c o m p u t e r programming  with the t a s k p a r s e any  of  constructing  languages, a  computer  g i v e n sentence i n the language.  t i m e i t must d e t e r m i n e t h e s e m a n t i c s o f t h a t  o r d e r t h a t i t may  construct  a  be  parser  executed.  To  facilitate  sentence  this,  g e n e r a t o r , i . e . , a computer  we  program  when g i v e n a c o n t e x t f r e e grammar  (CFG)  g e n e r a t e s a program  to perform a s y n t a c t i c  The  parse  to  free of  parsing  tables  type of context f r e e  restricted context  and/or  the  a  languages discussed  c l a s s o f LR(k)  grammars.  The  method  method  (technique).  to  parse  the  t i m e t o p a r s e any  of  The  the  parse.  by  a  i s known a s an  i s linearly  be  LR(k)  syntactic  is  t o a top-down method.  sentence i s d i r e c t l y  which,  will  described  method used  may  language,  here  performing  parsing  a sentence i n the language  LR(k)  classed The  time  bounded, i . e . ,  proportional  to  the  of the sentence.  Knuth grammars  [KJ and  first De  technique  work r e p o r t e d  herein  Remer  construction  formally  Remer  construction  De  languages  s e n t e n c e i n an LR (k) l a n g u a g e  as a bottom-up method a s opposed  length  describing  At  later  the n o t i o n of  presented  a  us  translators  on t h a t  with for  done by De  the  LR(k)  practical  o f t r a n s l a t o r s f o r LR (k) grammars.  i s based  provides of  [D]  introduced  The  Remer.  methodology  for  the  LR (k) grammars w i t h p r o o f o f  2  correctness  of the  application. LR(k)  De  to  a  Remer  is  and  us is  a  adapted  found  t o be L R ( k ) ,  grammars De  method  LR(k) .  too  translator the  The  powerful  error  recovery  i s necessary  symbols  not i n the  tables not  recovery  i n the  language  Theoretically,  of  the  LR(k)  grammar.  translator  technique  w i t h empty  complete  grammar.  with  the w r i t e r  translator  our  enhanced  no  practical  to the s i z e limit  for  and of  is  s e t of with  a  Error  a string  translator  o f symbols i n the  limit  own.  the author.  to transform a s t r i n g  is  a  where a d e c i s i o n  encounters  the  as  of a l l the  some o f  is  p r o v i d e d by  I t uses  a string  the  model  of  productions.  have n o t made use  translator  language.  However,  under  i f t h e grammar i s  failure  the  De  in  r e p l a c e d them  translator  there  the  Remer's m e t h o d o l o g y , t h e c l a s s  when t h e  into  of  increased.  s y m b o l w h i c h i s a member o f a l a r g e  resultant  p r o v i d e d by  complexity  of  be  symbols.  the  complexity  to  one  As  i s the complexity  m o d i f i c a t i o n a l l o w s an i n c r e a s e i n s p e e d on  of  simple  One  made  complexity  t h e grammar i s ambiguous.  t h o u g h we  model and  by  a r e LR (0) , SLR (k) o r  to i n c l u d e those  model  use  From  which  the  o f De  interpreter  f e a t u r e s of t h i s  by  to  e.g.,  extended  Remer p r o v i d e s a  table-driven  so  with  its  names.  and  terminates  application  is  LR(k)  method  the  In our  hierarchy  discovered,  However, not  the h i e r a r c h i a l  c o n s t r u c t i o n of the  shows  construction  demonstrates  most complex t h e y  or lookahead  grammar  computation  provides t h i s  the  LR (k) , LALR(k)  and  Remer c l a s s i f i e s  grammars and  simplest  of  methodology  of  weight symbols  language.  o f k f o r an k  in  the  3  translator  model  modification  15  though  1, t h e t h e o r y  i s discussed. as t h e t y p e s  simplest  t o t h e more c o m p l e x .  presented  with  may be i n c r e a s e d by  and i m p l e m e n t a t i o n  of  the  of the parser  parser  generator  o f LR (k) grammars a r e d i s c u s s e d f r o m  the  The b a s i c model o f t h e p a r s e r i s  examples.  In C h a p t e r  lookup  limit  The c o m p l e x i t y  increases  discussed  this  of the translator.  In C h a p t e r generator  is  2, t h e p r a c t i c a l  and  the  parsing  interpretation  of the  use o f the p a r s e r generator  algorithm tables  i s presented  generated  by  as a the  is  table parser  generator. Chapter with  3  i s a d i s c u s s i o n o f the e r r o r  examples t a k e n  ALGOL 68 c o m p i l e r Chapter  4  the  University  a  description  ALGOL 68 c o m p i l e r  technique  is  reflected  the c o m p i l e r .  The LALR(3) grammar  discussed  relation  parsing  in  technique  of  British  Columbia  of  the U n i v e r s i t y of  implementation. contains  B r i t i s h Columbia parsing  from  recovery  technique.  and how t h e u s e o f t h e  LR (k)  i n t h e d e s i g n and s t r u c t u r e o f given  in  t o t h e ALGOL 68 R e p o r t  the  Appendix  is  [ R ] and t h e LR (k)  4  CHAPTER 1  THEORY AND  In  this  describe  chapter  the  we  notion finite  transformations  that  complexity  1.1  of the  Notation It  need  the r e a d e r  wishes to f a m i l i a r i z e  is  U l l m a n [H  a finite  terminal start  V*  languages,  himself  with  these  generate  the  a CFSM  discuss  the  CFSM  the  as  a  with t h e p r o p e r t i e s of finite  state  (DPDA). notions  machines  I f the he  may  reader  refer  to  SO],  (CFG)  i s a quadruple  set of nonterminal  where A i s i n N and set  definitions,  and to  i s familiar  symbols, P i s a f i n i t e  symbol,  applied  pushdown a u t o m a t a  A c o n t e x t - f r e e grammar N  grammar,  machine)  be  and  Definitions  deterministic  and  LR (k)  state  s t r i n g s of symbols,  and  Hopcroft  an  notation  grammar i s d i s c o v e r e d .  i s assumed  symbols, (FSM)  and  review  of  (characteristic  IMPLEMENTATION  member  (N,T,P,S) where  symbols, T i s a f i n i t e  s e t o f p r o d u c t i o n s and  o f H.  s e t of  S is  the  A p r o d u c t i o n i s w r i t t e n A ->  w is a string  i n V*  where V = N  d e n o t e s t h e s e t o f a l l s t r i n g s i n V,  w  U  T.  The  including  the  empty  string.  Without l o s s o f g e n e r a l i t y  the  productions are  arbitrarily  5  numbered  from  \ S* 4  S -> and  1  to  s and t h e f i r s t  where S» i s a s u b o r d i n a t e s t a r t i n g  occur  nowhere e l s e  In t h e f o l l o w i n g , case L a t i n Latin  letters  letters  Latin  letter  however  letters  capitals  (a-d) and d i g i t s  (u-z)  author  and  digits  the has  denote  empty taken  digits,  where  denote  denote  S,  nonterminals,  the  case  s t r i n g s and l o w e r  case  In  liberty  capitals,  i t i s clear  lower  t e r m i n a l s , lower  string.  and n o n t e r m i n a l s by L a t i n and  s y m b o l and  i n P.  latin  e denotes  the  terminals  p r o d u c t i o n i s o f t h e form  the to  denote  lower  from  examples, both  case  Latin  c o n t e x t which a r e  t e r m i n a l s and which a r e n o n t e r m i n a l s . Given string  Z  derivation,  a p r o d u c t i o n A ->  w,  an  =  Z*  =  u  w  v  written  from  Z' ->*  immediate  u A v i s written  Z, i s t h e t r a n s i t i v e  immediate  derivation  where t h e r e e x i s t  such  Z« = vO ->  v1 ->  that  canonical derivation in  which  for  derivation rightmost The {  from  1,2,  language  unambiguous  form  ...  strings  vn =  Z  n  each of  vO,  a  Z.  A  v1, ...  n  >=  written  vi  a  c o m p l e t i o n o f an  for  derivation,  Z * ->  of  has  , vn  0.  The  Z* ->*R  an  Z,  immediate  production  to  the  nonterminal i n v i - 1 .  terminals  canonical  ->  vi-1 v i a application  L (G)  generated  w | w i s i n T* and S ->*  of  ...  i s the r i g h t  i =  derivation  and  i f  w  }.  nonterminals  and  derivation.  only  by t h e grammar G i s d e f i n e d a s A sentential such  i f each  canonically  S  i s a string  ->*  s e n t e n t i a l form  A c a n o n i c a l form  which i s any s t r i n g  that  form  is  a  derivable  w. has a  right from  .G  w  is  unique  sentential S.  6  The string the  parse  of a string  was d e r i v e d .  reverse  derivation De  The c a n o n i c a l  associated  production  with  be  characteristic  Z'  string  o f Z.  production  A  ->  ->R  Z.  w,  string  o f Z.  that  there  exists  immediately  remove  substring  w which w  with  the input  reduction. iteratively  and  canonical  a  from  there  string  exists  2, e t c . L e t  matches the l e f t v. »•  end the  part He  canonical  a  canonical t o be a  string  derivation  characteristic  of Z  of  the  right  outputs  parser  characteristic  string  of  refer starts  p,  the r e s u l t  ->  Z  as  a  w i n L ( G ) and  of  the  current  i n d i c a t e d by t h e l a s t  makes  and steops when t h e new c a n o n i c a l  w  as  uw t h e  production  with  string  production  string,  to  i t i s  formed  o f Z, and c o n c a t e n a t e then  the  stack  part  an  "... i n d i c a t e s  d e r i v a t i o n o f Z i n which  determines a c h a r a c t e r i s t i c form,  #1  the p ' t h  o f uwfp i s aw, and v i s c a l l e d  canonical  the  define  l e t Z' = u A v and Z = u w v be  A characteristic  string  The  symbol o f t h a t reduction,  1, #2 w i t h  p r e c e d e d by a n o t h e r f o r m Z* which c a n be  follows:  canonical  a  ,#s} n o t i n V s u c h t h a t  Then uwfp i s d e f i n e d  The s t a c k  input  with  in  s t r i n g s as f o l l o w s :  {#1,#2, ...  forms such t h a t  S ->*R  replace  used  o f the s e n t e n t i a l form,  Remer d e f i n e s  canonical  o f how t h e  parse o f a s e n t e n t i a l form i s  o f t h e sequence o f productions  a s p e c i a l s e t o f symbols is  o f symbols i s t h e r e c o r d  the form  corresponding  i s Z=S.  7  1.2 LR (k)  Grammars  The It  of a string  i s convenient'  parser DPDA set  parse  that  at this  consists  o f t a b l e s from DPDA  machine  is  constructed  from  is  o f symbols  language.  canonical  the  decision (tables)  by s t r i n g  terminal  required would than  the  1.  state  from  the  e.g., t h e e m i s s i o n the parse  of  a  used  to  be  to i t s l e f t  characters  immense  Fortunately,  ahead  Thus, c o n s i d e r a b l e  i s k  o f t h e CFG.  strings of  determine  a grammar t o be LR (k)  k symbol l o o k  full  manipulation  a  CFG  characteristic  forms.  by t h e s t r i n g k  lookup.  we c a n c o n s t r u c t a FSM f o r t h a t  derivation of a sentential  k symbol l o o k though  then  [K] defines  determined  a  and a  finite  translates  numbers which d e n o t e  l a n g u a g e and t h a t  The FSM i s  Knuth  greater  which  the s e t of c h a r a c t e r i s t i c  strings of canonical  and  characteristic  machine  CFSM i s c o n s t r u c t e d  regular  of  i n t h e language.  Remer shows t h a t a  a  f r e e language G t o another language,  The De  The model i s  which t h e i n t e r p r e t e r p e r f o r m s t a b l e  of a sequence o f p r o d u c t i o n string  to construct.  o f an i n t e r p r e t e r , a pushdown s t a c k  (CFSM) w h i c h i s a  context  by a p a r s e r .  t i m e t o have a model d e s c r i p t i o n o f t h e  we a r e a t t e m p t i n g  which  The  o f symbols i s performed  savings  i s  always  to i t s right.  I f each of  i f the  uniquely  (the c h a r a c t e r i s t i c  ahead, t h e s i z e  the  string) parsing parser  f o r m o d e r a t e LR (k) grammars f o r k f o r reasonable  required  symbol  form  i f and o n l y  look  f o r most  grammars,  less  than  parser  decisions,  ahead i s r e q u i r e d  f o r others.  i n storage  c a n be  gained  by  taking  8  advantage  of t h i s  For  our  computed DPDA.  state  will  need  complexity  following: lookahead  a)  LR ( k ) , here  may  be  ordering  be  executed  string  each  states be  most*  The  LR (k)  i n turn  time.  t o pay  and  LR ( k ) .  e.g.,  into  LALR(k)  a  further stands  However,  the  of  difficult)  to  generate  and  most f r e q u e n t l y  parser  LALR ( k ) .  (from  f o r that  used  grammars  Grammars  i n space  which  may  LALR (k)  grammar  be for  this class.  difficulty a  of  <c)  makes  represents  o v e r an SLR (k) o r  k  look  one  a member o f t h e g e n e r a l LR (k)  a higher cost  but  only  a s u b c l a s s LmR(k) where m  SLR (k) o r  one  the c o n t e x t .  c o n t e x t t o be c o n s i d e r e d .  are either  the  lookahead  be e x e c u t e d ,  Remer  degree  be  lookahead  a  be c l a s s i f i e d  De  in  looking  Each  called  will  will  states  (b) SLR (k) o r s i m p l e LR ( k ) ,  most i n t e r e s t i n g  have  lookahead  executed,  o f a grammar may  considered  t h o s e which  price  will  by d e s c r i b i n g  also  to  grammar.  are  symbol  o r more l o o k a h e a d  not always  LR (0) ,  t h e amount o f l e f t  easiest  are  state  k  as f a r as i t i s n e c e s s a r y t o d e t e r m i n e  class The  o f one  A t most k l o o k a h e a d  distinction for  the  down t h e i n p u t  states  The  or  model,  use a s e t o f symbol t r a n s i t i o n s  set.  lookahead  the  lookahead  further  symbol  ahead  parser  as a s e q u e n c e  Each  symbol  fact.  which  too h i g h a the  same  language.  The follows:  nature a)  LR (0)  grammars  require  lookahead  symbol  o f e a c h o f t h e above grammars may grammars k sets  symbol  require  no  lookahead,  i s q u i t e easy,  lookahead,  be  stated b)  the computation  c) LALR (k) grammars  as  SLR(k) of  the  require  9  k symbol is  lookahead, the computation o f the lookahead  complicated  d) L R ( k )  grammars  complication increased (De  (ionly t h e l e f t  that  to  are  c o n t e x t may  like  LALR (k)  further  sets  considered) ,  and  grammars w i t h  t h e number o f s t a t e s  provide  be  symbol  in  the  partitioning  the f u r t h e r  parser of  must  left  be  context  Remer r e f e r s t o t h i s p r o c e s s a s s t a t e - s p l i t t i n g ) .  1.3 C h a r a c t e r i s t i c F i n i t e De Remer  defines  deterministic  FSM  s t r i n g s o f G". four  major  State  Machine  (CFSM)  a CFSM o f a CF grammar  which  recognizes  The c o n s t r u c t i o n  categories  as  "a  reduced,  the s e t of c h a r a c t e r i s t i c  o f t h e CFSM  o f grammars  G  (LR(0),  is  basic  to the  SLR (k) , LALR (k) and  LR (k) ) . Each s t a t e which of  i s  are linked together  their  production The  of  configuration the  configuration The  basis  P) ( i . e . ,  A  set  The s t a t e s  under  symbols  configuration  i s a  (a d o t ) i n i t s r i g h t  (synonymous  with  the  part.  starting  CFSM) i s {S ->. |- S* -J} and h a s t h e name 1.  s e t i s the union of a b a s i s  s e t containing there  a r e no o t h e r  are  any  {A -> w.u w*}  from  state  of  a  where A -> w u w• i s  V from  state  1 to state  t r a n s i t i o n s under a J- i n t o s t a t e  transitions  Each  s e t and a c l o s u r e s e t .  | t h i s s e t i s the successor  i s a t r a n s i t i o n under  2 and t h e r e there  transitions  sets.  set  s e t i s {A -> w u.w*  configuration in  configuration  by  i n P w i t h a s p e c i a l marker  initial  state  by a c o n f i g u r a t i o n  a s e t o f ( p o s s i b l y empty) c o n f i g u r a t i o n s .  t h e CFSM  within  o f t h e CFSM i s d e s c r i b e d  2  nor  1 u n d e r a (- t o a s t a t e  10  other  than s t a t e 2 ) .  The b a s i s  a  be no two b a s i s s e t s  partitioning  CFSH as t h e r e  set  i s u n i q u e a n d t h e CFSH i s , t h e r e f o r e ,  reduced).  set  i s {A ->.w  exists a configuration  | & -> w i s i n P and t h e r e  a  marker  before  closure  set}.  If  configurations closure  the  with  has  one  precedes  or  the  which  same  under  the basis  S  the  right  | i s S ->  of  once t h e r e d u c t i o n CFSM, t h e CFSM  The  any  a n o n t e r m i n a l then t h e  symbol  (e.g.,  where  #  symbol  i s to a state i s complete.  the  dot  have a  with the to  S  ->  a l l t h e s y m b o l s on  i s the  f o r that  empty  set  under  production.  The f  which d e t e r m i n e s what t o do n e x t In the a c t u a l will  be l e f t  construction  out u n t i l  such  of time  t o a DPDA.  state i s a s t a t e with  c)  I n any  will  the successor  o f t h e CFSM c a n be c l a s s i f i e d  and  sets,  to another c o n f i g u r a t i o n s e t  the s u c c e s s o r  the  i s converted  only,  configuration  configurations  I f the dot follows  the state t r a n s i t i o n  states  t h e empty  configuration  These  to the r i g h t  b) a r e d u c e s t a t e i s a s t a t e symbol  closure  contain  those configurations  that  hand s i d e t h e n  symbol t r a n s i t i o n  than  successor  J-.S* -J).  transition  read  not  basis  s e t or the  s e t c o n s i s t s of those configurations  .J-  as  does  preceding  symbol.  moved one s y m b o l  the  The  either the basis  set  s e t (other  more  dot  the  dot  s e t , consider  unique t r a n s i t i o n  1  in  (each  s e t i s empty.  configuration  in  A  basis  the  Each c o n f i g u r a t i o n set)  the  t h e same  over  the  with  will  s e t s form  transitions with  a  an i n a d e q u a t e  only  as follows:;  a)  a  u n d e r s y m b o l s i n V,  transition  under  state i s a state  one  with  #  more  11  than  one t r a n s i t i o n u n d e r  transition terminal The  under a # symbol and one o r  (2)  E -> T  (3)  E -> E + T  (4)  T -> P  (5)  T -> T * P  (6)  P -> I  (7)  P -> OPEN E CLOSE.  are  transitions  f o l l o w i l n g grammar g e n e r a t e s t h e CFSM i n F i g u r e  S -> A E B  that  states  more  w i t h a t l e a s t one under  symbols.  (1)  Note  # symbols o r a s t a t e  states  1,  2, 1; 5, 6, 8, 9 and 11 a r e r e a d  3, 10, 12 and 14 a r e r e d u c e s t a t e s ,  inadequate s t a t e s .  and s t a t e s  7  1.1:  states, and  13  12  I  T  \ STATE|  V-  CONFIGURATION SET ;. S -> mh E B  | SYMBOL  STATE  _,—:—|— _ —  1  |  2  I  A  -> -> -> -> ->  I 3  I  P -> I .  #6  1  I  P- > . I P -> .OPEN E CLOSE P -> OPEN .E CLOSE E ~> . E + T T -> .P E -> .T T -> .T * P  I OPEN E  3  P T  6  | | |  |  J  | |  | j  I  -I .OPEN E CLOSE A. E B .E + T .P "> . T "> . T * P  3  P P S E T E T  I OPEN E  4 5  P T  7  6  4 8 7  +  9  I  E -> E.+ T S -> A E.B  B  10  6  I  T -> P..  #4  7  I  T -> T. * P E -> T.  *  5  I  I  8  | I  #2  E -> E. + T P "> OPEN E.CLOSE  -> -> -> -> ->  +  CLOSE  I  P P T E T  10  |  S -> A E B.  #1  11  |  P -> -I< P -> .OPEN E CLOSE T "> T *.P  I OPEN P  9  I  | ( J  .I .OPEN E CLOSE .P E + .T .T * P  I OPEN P T  12  |  P -> OPEN E CLOSE.  #7  13  |  *  I  T -> T. * P E -> E + T.  |  T "> T * P.  14  11  #3  #5 Figure  1.1  9 12  3  4 6 13  3  4 14  11  13  1.4  LR(O) Grammars and DPDA's The  CFSM  inadequate string  for  states;  o f symbols  modification  an  LR(0)  thus,  grammar  a l l the i n f o r m a t i o n  i n the language i s present  o f t h e CFSM t o a d e t e r m i n i s t i c  (DPDA) i s t h e same f o r a l l t h e c l a s s e s DPDA  i s  from  which  an  interpreter, the is  construction  of the tables  must r e p r e s e n t  states  and  natural,  state  table)  than  special  a s an a l g o r i t h m  the  therefore, and  symbol t a b l e ) . larger  reguired i n the  to parse a CFSM.  push down  The  automaton  grammars.  The  and a s e t o f t a b l e s  table  lookup.  i n C h a p t e r 2.  that  we a r e c o n c e r n e d  FSM  and,  t o place  with  therefore,  the states  The number o f s t a t e s  within  actions.  any  The  I t i s the here.  The  represent  the I ti s  i n one t a b l e  (the  t h e symbol t r a n s i t i o n s i n a n o t h e r t a b l e (the within  t h e CFSM a s s t a t e s  the  DPDA  are constructed  F o r example, t h e r e d u c e s t a t e  s p l i t i n t o two s t a t e s  state  performs  contain  t h e s y m b o l t r a n s i t i o n s between t h o s e s t a t e s .  quite  is  given  not  o f LR (k)  a pushdown s t a c k  interpreter  interpreter  tables  does  be  to perform  within  i n t h e DPDA, a pop s t a t e  and f o r a p a r t i c u l a r p r o d u c t i o n  will  t h e CFSM  and a l o o k b a c k  the lookback s t a t e  may  or  may n o t be g e n e r a t e d .  The of  pushdown s t a c k  a string  state  name  o f symbols. of the s t a t e  pushdown s t a c k . some popped  represents  When we r e a d that  read  When we p e r f o r m  of the s t a t e  a finite a  memory o f t h e p a r s e  symbol,  we  place  the  t h e symbol on t h e t o p o f t h e  a reduction  (by a  pop  names on t h e t o p o f t h e pushdown s t a c k  o f f ( t h e number o f names popped  i s equal  state), may be  t o one l e s s  than  1tt  the  number  o f s y m b o l s on t h e r i g h t  reduced).  The  production  lookback i s then  do  in  order  contains  reduction do  process  by  not  place  i t .  1.1.  In t h i s  symbol  ("I")  from  again,  (on  as  the  ( s t a t e 2) i s  hand  side  under " I " t o  The s t a t e  state  in  which  the  (under; "P") f o r t h e n o n t e r m i n a l on t h e l e f t  follow state  the r e s u l t i n g  being  state  i n which t h e r e  reduced  nonterminal  i sa  (production  transition  3  state  name on t h e  hand s i d e o f t h e p r o d u c t i o n  the state  and  on t h e t o p o f t h e  transition  production  of the  number 6 i s o u t p u t b u t no  the  we  2 of f i g u r e  I t i s also  the  This  string  was r e a d .  of  pushdown  point.  input  2 and 2 i s p l a c e d  is  However, we  set f o rstate  popped f r o m t h e s t a c k .  on t h e r i g h t  context  parse i n that  the l e f t  i s a transition  i n state  left  the canonical  the c o n f i g u r a t i o n  3, p r o d u c t i o n  been  the  a t t h e head o f t h e  state there  of the stack  production  and t h e p r o c e s s o f  o f t h e parse t o t h i s  nonterminal  Observe  In s t a t e have  the  what t o do n e x t .  context  history  reduced)  " I " i s read  stack). names  the  being  read  (e.g.,  the  which  t o determine  mechanism d i f f e r s  production  top  number i s o u t p u t  n o t need t o p a r s e t h e l e f t  stack  of  performed.  Lookback i s t h e considered  hand s i d e  first  (P -> I)  nonterminal hand  side  number 6 ) . , we  and c o n t i n u e i n t h a t  ( s t a t e 6) .  T h u s , from states  of  states  within  classified  the  into  t h e above d i s c u s s i o n , CFSM the  i ti s  e a c h have an e q u i v a l e n t DPDA.  types  The  states  as a r e t h e s t a t e s  apparent  that  the  s e t o f one o r more  within within  the  DPDA  are  t h e CFSM.  The  15  CFSM c o n t a i n s equivalent  sets  {lookahead, will  read, reduce of states  The first  they  respectively,  types of states  type i s the read s t a t e  sequential  search  the  f o r m u s e s t h e same symbol  table pair  for a (the  second  form,  on  the  the  speed  entries  of the are  match  name  consists  parser.  terminal  In  The  read  table  We  t h e DPDA and t h e  state  an o r d e r i n g  implementation consists  or indexed)  may be r e a d  by t h i s  where t h e t a b l e  second  table  forms:  a s an i n d e x  into  whereas,  t h e symbol  form, a match c o n s i s t s transition) only  of allow  cases,  state  and  the  us t o  economize  and t o i m p r o v e  the  symbol  table  name t r a n s i t i o n s o f s e t f o rthat  The  read  p e r f o r m s an a l p h a b e t i c a l  state.  s t a t e , and c) an O f f s e t  indexed symbols  ordering).  of information:  i n s t r u c t i o n c o d e , b) number  entries  name  name t r a n s i t i o n s do n o t  entries.  3 pieces  of a  i n the  state  be p e r f o r m e d on t h e t e r m i n a l  of  the  and d o e s a  f o r a match,  i n the configuration  t h e read  state  (sequential  have  t h e DPDA.  of the s t r i n g  symbols and/or s t a t e  symbols  requires  The  within  states  both  n o n t e r m i n a l s y m b o l s and t h e i r  present  table  within  amount o f s p a c e u s e d i n t h e symbol t a b l e  (the  that  state  The two t y p e s o f r e a d  appear w i t h i n state  In the f i r s t  and t h e the  those terminal The  t h r o u g h t h e symbol  match.  symbol  transition.  which  which h a s two  t a k e s t h e s y m b o l a t t h e head  second  states  a r e t o perform.  first  form  these  inadequate  { r e a d } , {pop and l o o k b a c k o r s t o p } and  pop a n d / o r r e a d } ,  now c o n s i d e r  function  and  of  a) r e a d symbols  i n t o t h e symbol  start.  type o f s t a t e  i s t h e pop s t a t e .  The pop s t a t e  16  consists  of three  code,  b)  the  offset  into  pieces  number  the  of of  symbol  information: state  table  production  number  be  after the reduction  followed  transition pop  state,  To  decide  deciding those hand  state,  the s t a t e  where  pair  denotes  which  the  t r a n s i t i o n to  has been p e r f o r m e d .  a push s t a t e  i)  The  a read  state  state, a  or a lookahead  state.  t r a n s i t i o n i s t o be i s e q u i v a l e n t is  necessary  to  for a l l  have t h e same n o n t e r m i n a l on t h e l e f t  side.  understand  construct two  a table  what  i s  f o r each  columns  of  involved,  for  the  state  On o b s e r v a t i o n of  the  for  the goal  same  entries:  transitions state  of these  the f i r s t  terminate  other state  need state  we f i n d  transitions  that  consist  each  column  is  terminate.  table  has  i s empty  terminate  in  one (only the  e n t r i e s a r e a l l t h e s a m e ) , and i i i ) t h e  i n more t h a n one s t a t e  i n column  and  at  least  one  2.  two c a s e s i ) and i i ) a b o v e , a  n o t be c r e a t e d in  to  2 has a s many a s o r more t r a n s i t i o n s t o i t t h a n  the f i r s t  and  2  will  and t h e s e c o n d  c h a r a c t e r i s t i c s : i ) the t a b l e  (column  convenient  column i s f o r the s t a t e  symbol S ) , i i ) a l l t r a n s i t i o n s  i n column  In  tables,  is  Each t a b l e  names where t h e m a t c h i n g  following  state  i t  nonterminal.  names where t h e t r a n s i t i o n o r i g i n a t e s  any  a  or not a lookback s t a t e  productions  instruction  names t o be popped, and c) an  t o any one o f a s t o p s t a t e ,  a lookback what  pop  t o be o u t p u t and i i ) t h e s t a t e  be  whether  To  of  may  a)  as i n i ) the s t a t e  i i ) the state  lookback  state  t r a n s i t i o n i s to the stop  t r a n s i t i o n i s t o t h e one and  only  17  state  appearing  must  be c r e a t e d  pop  states  i n t h e second column. and s t a t e  In i i i ) ,  a lookback  t r a n s i t i o n s generated  productions  hand s i d e .  The  lookback  information:  a) t h e l o o k b a c k i n s t r u c t i o n c o d e and an o f f s e t  the  table  placed.  technique:  i t , 2)  state, end  remove  and 3) p l a c e  of  the  the  match  pushdown  Once  entry the  nonterminal,  with  stack  contains lookback  entries  reduced  with  t h e most  the table  a l ltransitions into  name i n t h e s e c o n d  or  i n column the s t a t e  searching until  the state  0  by  into  the  transitions  column  that  a t the  1 adjacent. name on  the table  the  of  above a r e  the s t a t e  and  i s  The  the top  e n t r i e s f o r a, reached;  the  t r a n s i t i o n t o be t a k e n .  algorithm  the nonterminal  pieces  be  by t a k i n g  column  two  entries constructed  a 0 placed  i s executed  i n the f i r s t  adjacent  from  of  may  the state  table  lookback s t a t e of  1) f i n d  n o n t e r m i n a l on t h e l e f t  consists  where t h e t a b l e  The s i z e o f t h e t a b l e  following into  state  that  t o i t from a l l  for  symbol  with  state  has  been e x e c u t e d  f o r each  t r a n s i t i o n s may be d e l e t e d  from t h e  CFSM. The s t o p s t a t e (S ->  i s only  J- S* i) i s o u t p u t The  following  entered  and s i m p l y  after  production  number  terminates the parse.  L'R-(O) grammar h a s t h e CFSM i n f i g u r e  the  state  and s y m b o l t a b l e s  (1)  S -> START E STOP  (2)  E -> A AA  (3)  E -> B BB  (4)  AA -> C AA  1  i n Figure  1.3:  1.2 a n d  18  (5)  AA -> D  (6)  BB -> C BB  (7)  BB ->  D.  The t e r m i n a l s  have been a s s i g n e d  (2)  (4) D,  (3)  B,  C,  STATE| 1 2  3  |  the following ordering:  (5) START and  (1)  A,  (6) STOP. —i  CONFIGURATION SET  j SYMBOL  S -> .START E STOP  | START  E -> .& AA E -> .B BB S -> S T A B L E  I  STOP  i 1  STATE  i T  2  1  | i i \  A | B J E  3  1  |  *  1  5  1 1  I  s  6  AA -> .C AA AA -> . D E -> A.AA  c t D | AA  BB -> .C BB BB -> .D E -> B. BB  I I  5  S -> START E.STOP  I  6  AA -> .C AA AA -> .D AA -> C.AA  I I  | AA  7  AA ->  I  8  E -> A AA.  |  9  BB -> ,C BB BB -> .D BB -> C.BB  I I  10  BB ->  I  #7  i  |  11  E -> B BB.  |  #3  !  |  12  S -> START E STOP.  f  #1  1  13  AA -> C AA.  ]  #4  !  I  14  BB -> C BB.  I  #6  j  _ _j-  _  4  Figure  1.2  | J 1  I  1 | J  STOP  1  12  |  c  J  6 7  1  13  I I |  #5  i  —  I  #2  i  1  1  D  c D | BB  D.  J  7 8 9 10 11  c D ) BB  D.  j  J j i  | 9 10 14  I | |  I  —  j  19  STATE TABLE  SYMBOL TABLE  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  1  | NUMBER]OFFSET |  :  |—.  T  "I  TYPE  +-4—  IREAD | |READ INDEXED | ) READ INDEXED | |READ INDEXED J (READ | |READ INDEXED | J POP | | POP | |READ INDEXED | | POP | J POP | | POP | | POP | | POP | |LOOKBACK | |LOOKBACK | |STOP J  -j  1 2 2 2 1 2 0 1 2 0 1 3 1 1 0  | ! I I I I | I I I ! I | I I I I  o  0  | SYMBOL|STATE f  y—  • 5  1 2 6 10 14 6 19 20 10 21 22 23 24 25 15 17 0  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  J  Figure From t h e CFSM i n f i g u r e 4, 5, 6 and 9 a r e r e a d in  the  1.2  states.  DPDA i n f i g u r e  The  we o b s e r v e t h a t  name t r a n s i t i o n t o s t a t e input  2.  state  offset  the  adjacent  columns.  read  indexed  For s t a t e  1  I f a match i s n o t  o f f s e t 2 of t h e symbol t a b l e . for  |  ] 1 | J 1 | | | | I | i | 1 | 1 1 I I | 1—  2 3 0 0 0 0 6 0 0 0 9 0 0 12 13 8 14 11 15 5 16 5 17 15 16  1, 2, 3,  read  of  states  read the  state symbol  c o n s i s t s o f "START" and a s t a t e  w h i c h r e a d s one o f a p o s s i b l e  entries  states  1 i s a sequential  s t r i n g i s not a s t r i n g i n the language.  indexed from  entry  4  There are equivalent  1.3. . S t a t e  symbol t a b l e  1  | | 1 |  1.3  which r e a d s one s y m b o l s t a r t i n g f r o m table.  +  |START |0 I 10 1 o 10 |0 17 1 o 10 10 1 10 |0 |STOP 16 |0 |9 ]0 15 12 17 13 11 |4 16 i  In  states  2, t h e  the  found State  then  the  2 i s a read  2 symbols s t a r t i n g table,  the  have been c o m p r e s s e d  into  symbol  symbol  table  entries  are  20  state by  names 3, 4, 0, 0, 0 and 0,  the terminal  equivalent  is  the  state  and  name 3.  I f a 0 i s accessed  and  {pop  stop  and  sets  of  i n the  states  {pop  {pop}, {pop and l o o k b a c k ( s t a t e 1 7 ) } / {pop  lookback(state  and  16) },  lookback (state  16)}, r e s p e c t i v e l y .  have been added t o t h e DPDA, two l o o k b a c k  Thus,  states  15)} three  and  a  state.  The  nonterminals  Observation under the  15) },  ( P ° P and s t o p ( s t a t e  states  the  o f t h e CFSM shows  DPDA from s t a t e a table  12 i s t o  grammar  that  H 1 | COLUMN  2  t~5  12 L  .  i s  output  J  clear  the  are  there  stop  S,  are  E , AA and BB. no  the state  state  transitions transition i n  (state  17).  Now  above f o r t h e n o n t e r m i n a l " E " .  T | \ J  j_.  from  production 5 (i.e.,  a  as described  " — T  COLUMN  state  in  t h e n o n t e r m i n a l S and/ t h e r e f o r e ,  construct  be  then the s t r i n g  7, 8, 10, 11, 12, 13 and 14 a r e r e d u c e s t a t e s  lookback (state  {P°P}#  for  its  e . g . , "A" has a n u m e r i c v a l u e o f 1 and  CFSM a n d i n t h e DPDA t h e y have e q u i v a l e n t  It  s t r i n g using  not a s t r i n g i n the language. States  i |  names a r e a c c e s s e d  s y m b o l a t t h e head o f t h e i n p u t  numeric v a l u e ,  accesses  These s t a t e  this table  that  states  numbers 2 and 3 w i l l  have s t a t e  no l o o k b a c k i s n e c e s s a r y ) .  nonterminal  made f o r s t a t e s  "AA" i n d i c a t e s  which o u t p u t  within  that  production  t h e DPDA  which  transitions to  However,  the  special attention numbers 4 and 5.  table must  21  i | COLUMN  1 | COLUMN 2  | 3 | 6 I  If  T  • — T  | 8 | 13 :  i  L  |  | |  i  J  a 3 i s on t h e t o p o f t h e pushdown s t a c k ,  is  to  the  t r a n s i t i o n i s to state  with  state  symbol  table  production  numbers 6 and 7  states within in any  set  is  16  i s generated (i.e.,  SLR (K) , LALR (K) within  and LR (K)  state  t h e CFSM  generated  S i m i l a r l y , the which  output  t h e n o n t e r m i n a l BB i s on  grammars  the  will  e a c h be t r a n s f o r m e d  The l o o k a h e a d  state  will  of terminal  s y m b o l s which  and a s s o c i a t e  t o take  Observation  place of  with  (i.e., the  state  i n t o a lookahead  have s t a t e  a pop s t a t e  states  read  or a read  state.  u n d e r a new s e t o f t e r m i n a l  To  compute t h e c o m p l e t e  may o c c u r a t t h e head o f t h e i n p u t  t h e symbol o r p e r f o r m  symbol;  i n t h i s case,  i s constructed  look  state  t r a n s i t i o n s to  each o f t h e s e symbols t h e a c t i o n  state will  inadequate  a  s e t o f s y m b o l s may show a c l a s h  u n d e r t h e same t e r m i n a l t o a new l o o k a h e a d  (k > 0) , one o r more  The  t h e s y m b o l lookahead,- we must f i r s t  lookahead  i s  f o r states  t h e CFSM a r e i n a d e q u a t e .  o f a new l o o k a h e a d s t a t e ;  string  A lookback  stack,  Grammars and L o o k a h e a d  t h e DPDA.  perform  transition  s i d e ) ..  1.5 SLR(k) In  13.  e n t r i e s s t a r t i n g a t o f f s e t 15.  state  hand  the  8 and i f a 6 i s on t h e t o p o f t h e pushdown  lookback  left  then  reduction). of actions  a state transition  in  one symbol f u r t h e r symbols.  which  which  this  new  down t h e s t r i n g  Thus, t h e i n a d e q u a t e  state  22  may become a l a r g e branching  construct is the  grammars the  a table  i s  "number"). following Step  1:  require  lookahead  for  the  Entries  3:  f o r each  amount  of  work  in we  column  t h e s e c o n d i s f o r a s t a t e name and  action  will  (read  or  reduce  production  now be made i n t o t h e t a b l e  terminal  symbol  place  using the  read a c t i o n  i n column 3.  f o r ieach  terminal  of the reductions  symbol  1,  under  the  state  i n c o l u m n 2 and  i n the inadequate  state  do  3.  compute  being during  a  list  have  a  reduced  the  (these  perform  lists  (reduction  the  into  are  more  step  perform  the  production computed  F o r e a c h one o f  4.  state of  states  under  easily  o f t h e CFSH).  "as  b e f o r e under t h e same "number") having  production  symbol i n t h i s  reduction  them  hand s i d e o f t h e  of production  reduction  each t e r m i n a l each  names o f a l l t h o s e  s t a t e h a s been v i s i t e d  o t h e r w i s e , mark t h i s under  left  the construction  i f this action  of state  transition  on  these s t a t e s  for  i n the inadequate state  thfe symbol i n column  under t h a t  nonterminal  4:s  least  high  To compute a l o o k a h e a d s e t ,  transition  which  Step  with a p o s s i b l y  algorithm:  step Step  the  sets.  symbols,  consideration  S t e p 2:  states  which c o n s i s t s o f 3 c o l u m n s : t h e f i r s t  f o r the terminal third  o f lookahead  factor.  SLR (k) computing  tree  state  step  6.  then been  return; visited  "number" and f o r  perform  step  5  and  23  Step  5:  place  the  transition action Step  The  6:  under t h a t  construct  as  i n step  hand  side  of  the  the  left  For  each of t h e s e s t a t e s  sort  the  the  same  table  the  that  the  perform  1 such  occur  partitions  s o r t by  duplicate  and  the  3.  being  step  state  nonterminal  on  reduced.  4.  that  a l l entries  many s e t s 1 of  the  c o l u m n 2 and  set  into  e n t r i e s i n the  under  order. as  This  there  are  table. t h e n column: 3 s u c h  names o c c u r i n i n c r e a s i n g  the  2  in consecutive  symbols i n column  state  3 f o r the  production  t a b l e i n t o as  f o r each s e t ,  column  the  sorted:  column  terminal  different 8:  by  be  in  1,  "number") i n c o l u m n  list  must now  i n column  terminal  a  partitions  Step  symbol  (reduce p r o d u c t i o n  resulting table  S t e p 7:  terminal  subsets.  order. If  This  there  subsets then only  one  are  need  be  retained. From what  the  the  table constructed  lookahead  lookahead  computation  not  grammar  the  resolved S t e p 9:  as  set  i s , b)  i s required,  is  SLR ( k ) .  may  and  now  whether o r  possibly  Each of  determine  a ) , b)  not  c) and  further  whether c)  a)  or  above  are  symbol  do  follows:  for  each s e t  step Step  symbol  a b o v e , we  10:  of  a  terminal  10.  place  the  symbol i n the  transition  to  read  all  for  e n t r i e s under  for  production  one  of  a)  symbol t a b l e  a read s t a t e  e n t r i e s i n column 3,  with  i f the b)  the  state  action  a reduce  is  state  "number" i f a l l e n t r i e s i n c o l u m n 3  are  24  reduce and Step  11:  p r o d u c t i o n "number" where "number" i s t h e same,  o t h e r w i s e do s t e p  11.  f o r t h o s e e n t r i e s i n c o l u m n 2, one  e n t r y w i t h t h e same s t a t e  column 3 d i f f e r , the  name and  t h e n t h e grammar i s  a l g o r i t h m f o r SLR (k) l o o k a h e a d  there  are  symbol,  then  performed. perform  in  column  further  A new  3  one  t o i t under  executed  s t a t e s i n which  using  computation  t h e SLR (k) a l g o r i t h m was  states  then  LALR (k) and whose  the  that To  refined  The symbol  may  now  sets  but the s t a t e  which  following lookahead  computation  terminal  (step 2  must  created  down the  be to  string  symbol  compute t h e  is  lookahead  3 to  step  e n t r i e s as  a l l  11) those  the column 3  the  inadequate  be c o n v e r t e d t o a DPDA.  may has  with  inadequate  be computed a  clash  Many states  u s i n g the SLR (k)  must  use  a  more  technique.  computation.  the a c t i o n  The  first  SLR (2) grammar w i t h t h e f o l l o w i n g p r o d u c t i o n s : (1) PROGRAM ->  be  two  action.  examples demonstrate set  this  terminal  successful for  symbol  lookahead  and  However, i f  commences and  LR (k) grammars have CFSM's  lookahead  algorithm,  CFSH  will  column  e n t r i e s as t h e a s s o c i a t e d If  SLR (k)  fails.  symbol f u r t h e r  i n the symbol t a b l e .  be  not  computation  state  symbol s e t , t h e above a l g o r i t h m s must  the a c t i o n s i n  under  lookahead  lookahead  lookahead  a transition  placed  than  no s u c h c l a s h e s b u t t h e r e a r e a t l e a s t  different^ctions  and  i f t h e r e i s more  START CLAUSE STOP  o f the  SLR(k)  example i s o f  an  25  2) CLAUSE -> OPEN  SERIES CLOSE  3) SERIES -> DECLLIST GOON UNITSERIES 4) DECLLIST ->  DECL  5) DECLLIST ->  DECLLIST  6) DECL ->  COMMADECL  DECLARER IDENLIST  7) DECLARER  ->  REAL  8) DECLARER  ->  INT  9) DECLARER  -> OPEN  UNIT CLOSE  10)  DECLARER  11)  IDENLIST -> IDEN  12)  IDENLIST -> IDENLIST COMMA IDEN  13)  UNITSERIES ->  14)  UNITSERIES -> UNITSERIES GOON UNIT  15)  UNIT ->  16)  UNIT -> FORMULA  17)  UNIT ->  18)  ASSIGNATION -> IDEN BECOMES UNIT  19)  FORMULA -> PRIMARY OP PRIMARY  20)  FORMULA -> FORMULA OP PRIMARY  21)  PRIMARY -> IDEN  22)  PRIMARY ->  23)  PRIMARY -> CLAUSE.  This  grammar  computer given  -> PROC  DECLARER  DECLARER  UNIT  ASSIGNATION  PRIMARY  PRIMARY CLAUSE  contains  syntactic  programming l a n g u a g e s .  i n f i g u r e 1.4 and  t r a n s i t i o n s are given  the  constructions The b a s i s s e t s  terminal  i n f i g u r e 1.5.  37 and 38 a r e i n a d e q u a t e .  and States  used  in  some  o f t h e CFSM a r e  nonterminal  symbol  14, 17, 18, 24, 33,  26  | STATE| I • + 1  BASIS SET PROGRAM ->  .START CLAUSE  STOP  2  PROGRAM -> START.CLAUSE  STOP  3  CLAUSE -> OPEN.SERIES CLOSE  4  PROGRAM -> START CLAUSE.STOP  5  DECLARER  -> INT.  6  DECLARER  -> OPEN.UNIT  7  DECLARER  ->  8  DECLARER  ->  9  DECLLIST -> DECL.  10  DECLLIST -> DECLLIST.COMMA DECL SERIES -> DECLLIST.GOON UNITSERIES  11  DECL -> DECLARER.IDENLIST  12  CLAUSE -> OPEN SERIES.CLOSE  13  PROGRAM -> START CLAUSE STOP.  14  ASSIGNATION -> IDEN.BECOMES PRIMARY -> IDEN.  15  UNIT ->  16  PRIMARY -> CLAUSE.  17  FORMULA -> FORMULA.OP PRIMARY UNIT -> FORMULA.  18  FORMULA -> PRIMARY.OP PRIMARY PRIMARY -> PRIMARY.CLAUSE UNIT -> PRIMARY.  19  DECLARER  -> OPEN  UNIT.CLOSE  20  DECLARER  -> PROC  DECLARER.  21  DECLLIST -> DECLLIST  22  SERIES -> DECLLIST  CLOSE  DECLARER  PROC.DECLARER REAL.  UNIT  ASSIGNATION.  Figure  DECLARER  COMMA.DECL  GOON.UNITSERIES  1.4 c o n t i n u e d  on n e x t  page  1  T  1  "  K  | STATE J  1  BASIS SET  1 23 | 24 |  | | |  IDENLIST -> IDEN. IDENLIST -> IDENLIST.COMMA IDEN DECL -> DECLARER IDENLIST.  | 25  |  CLAUSE ->  | 26  |  ASSIGNATION  | 27  J  FORMULA ->  | 28  |  FORMULA -> PRIMARY  OP.PRIMARY  | 29  |  PRIMARY -> PRIMARY  CLAUSE.  | 30  |  DECLARER -> OPEN UNIT  | 31  |  DECLLIST ->  | 32  |  UNITSERIES ->  | 33 |  | |  UNITSERIES -> UNITSERIES.GOON UNIT SERIES -> DECLLIST GOON UNITSERIES.  | 34  |  IDENLIST -> IDENLIST COMMA.IDEN  I  35  |  ASSIGNATION  | 36  |  PRIMARY ->  | 37 \  | |  PRIMARY -> PRIMARY.CLAUSE FORMULA -> FORMULA OP PRIMARY.  I  |  PRIMARY ->  |  FORMULA -> PRIMARY OP  PRIMARY.  39  |  DECLARER -> OPEN UNIT  CLOSE  | 40  |  UNITSERIES ->  | 41  |  IDENLIST -> IDENLIST COMMA  | 42  |  UNITSERIES ->  38  I |  OPEN SERIES ->  IDEN  CLOSE.  BECOMES.UNIT  FORMULA OP.PRIMARY  CLOSE.DECLARER  DECLLIST COMMA  ->  DECL.  UNIT.  IDEN BECOMES  UNIT.  IDEN.  PRIMARY.CLAUSE  DECLARER  UNITSERIES GOON.UNIT IDEN.  UNITSERIES GOON UNIT. Figure  1.4  28  [STATEI 1 | | | |  ]  4 5 6  l | |  | J  7 8  | |  I N T (5) #7  I | | | | | | | I  9 10 11 12 13 14 15 16 17  | | | | | | | J  j  #4 COMMA ( 2 1 ) GOON ( 2 2 ) I D E N (23) I D E N L I S T ( 2 4 ) CLOSE (25) #1 B E C O M E S ( 2 6 ) #21 #15 #23 OP (27) #16  | j  18 19  \ |  OP (28) O P E N (3) C L O S E (;30)  | | | | | | |  20 21  | j | | | | | | | | | J J | | | | | | | | | | | | J |  #10 I N T (5) OPEN (6) P R O C (7) R E A L (8) DECL (31) DECLARER (11) I D E N (14) OPEN (3) A S S I G N A T I O N (15) C L A U S E (16) FORMULA(17) P R I M A R Y ( 1 8 ) U N I T (32) U N I T S E R I E S ( 3 3 ) #11 COMMA ( 3 4 ) #6 #2 IDEN (14) OPEN (3) A S S I G N A T I O N (15) C L A U S E (16) FORMULA (17) PRIMARY (18) U N I T (35) IDEN(36) OPEN(3) CLAUSE(16) PRIMARY(37) I D E N (36) OPEN (3) C L A U S E (16) PRIMARY (38) #22 I N T (5) O P E N (6) P R O C (7) R E A L (8) D E C L A R E R ( 3 9 ) #5 #13 G O O N ( 4 0 ) #3 I D E N (41) #18 #21 O P E N (3) C L A U S E ( 2 9 ) #20 O P E N (3) C L A U S E (29) #19 #9 I D E N (14) O P E N (3) A S S I G N A T I O N (15) C L A U S E (16) FORMULA (17) PRIMARY (18) U N I T (42) #12 #14  | J  22  23 24 l 25 | 26 | \ 27 \ 28 | 29 J 30 | 31 | 32 | 33 J 34 J 35 | 36 | 37 | 38 | 39 | 40 | | 41 | 42  | | | I j  TRANSITIONS  S T A R T £2) O P E N (3) C L A U S E (4) , I N T ( 5 ) O P E N (6) P R O C (7) R E A L (8) D E C L (9) DECLARER(11) S E R I E S (12) STOP (13) #8 I D E N (14.) O P E N (3) A S S I G N A T I O N (15) FORMULA (17) PRIMARX{18) UNIT(19)  J  1 2 2  SYMBOL  O P E N (6)  P R O C (7)  R E A L (8)  C L A U S E (29)  F i g u r e 1.5  D E C L L I S T (10)  C L A U S E (16)  DECLARER (20)  | | j | | | | | | | | I I | | | 1 ! |  #17  I | I | | | | | J I | | | I | | | | | | | I | | | | | | |  29  From  the  transitions.  CFSM The  we  lists  obtain are  given  NONTERMINAL  HAS  ASSIGNATION CLAUSE DECL DECLLIST DECLARER FORMULA IDENLIST PRIMARY, PROGRAM SERIES UNIT UNITSERIES  15 4 16 29 9 31 10 11 20 39 17 24 18  37  38  12 19 33  32  35  above a l g o r i t h m  figure  1.6,  we  symbol s e t 26  in  stated  as  consider  the  we  reduce  yields obtain REDUCE  add  table  21},  of  the 14  see  have a l r e a d y  lookahead  symbol  construct  the  1,  28,  number  f o r production  17.  1.7  2 are  with  35  3  We  name  will  be  number 37  21,  and  38.  REDUCE  21}  consider 42.  the  State  19  i n t h i s manner  and  entries  for first  a state  we  and  continue  removed.  i f i t were not visited  We  {OPEN, 3,  Here  32,  lookahead  (a t a b l e e n t r y  REDUCE 21},  sets.  state  ("PRIMARY") t r a n s i t i o n s 18,  in figure  entries  nonterminal t r a n s i t i o n s  and  Now,  REDUCE 21}.  which  the  i n column 3  READ}).  {OP,  duplicate i f we  and  ("UNIT") t r a n s i t i o n s 19, 30,  1.6.  STATES  "BECOMES" i n column  read  production  {CLOSE, the  and  nonterminal  18,  nonterminal  state  place  {BECOMES, 26,  From s t a t e and  2  in figure  1.6  compute  inadequate  column as  can  follows:  form  nonterminal  I  the  the  in tabular  of  42  Using  Consider  lists  TRANSITIONS TO  Figure  from  the  for  {OPEN,  would have had checking  under a c t i o n  i n step "REDUCE  3,  other 4  to  21".  30  | SYMBOL BECOMES CLOSE CLOSE GOON OP OP OPEN Figure  | ACTION  | J | | | j |  | | | | J J |  26 25 30 40 27 28 3  READ REDOCE REDUCE REDUCE REDUCE REDUCE REDUCE  21 21 21 21 21 21  1.7 l o o k a h e a d s y m b o l s e t f o r s t a t e  The m u l t i p l e difficulty resulting Similar  as  entries  there  symbol  lookahead  information  will  a r e computed  set  1.9.  i n the a c t i o n  appear  as  in  column. figure  f o r inadequate s t a t e s state  computation.  24  The f i r s t  As  we  see  the  second  from f i g u r e  lookahead  The 1.8.  further  s e t computed i s  The comma s y m b o l does n o t g i v e  entries,  any  17, 18,  required  sufficient  t o determine the d i r e c t i o n of the parse.  "NEXT" column  sufficient  entries  However, i n a d e q u a t e  symbol  in figure  computed.  sets  14  f o r "CLOSE" and "OP" do n o t c a u s e  a r e no c l a s h e s  symbol t a b l e  33, 37 and 38.  given  | NEXT  Using the  symbol  set i s  1.10, 2 s y m b o l l o o k a h e a d i s  to determine the d i r e c t i o n of the parse.  | SYMBOL  | STATE TRANSITION  | BECOMES J TO A READ STATE WHICH READS BECOMES I CLOSE | TO A REDUCE STATE WHICH REDUCES 21 | GOON | " | OP | " | OPEN | " i ; i i : : . F i g u r e 1.8 s y m b o l t a b l e e n t r y f o r s t a t e 14  Despite the fact that as  that  t h e grammar i s  SLR ( 2 ) ,  we  can  t h e amount o f symbol l o o k a h e a d need n o t a l w a y s be a s  k f o r an SLR (=k)  grammar  (where k i s  greater  than  1).  see great The  complete  DPDA  i s given  i n f i g u r e 1.11.  [ SYMBOL  MNEXT  ]~~ACTION  ]  | COMMA | COMMA | GOON  | 21 | 34 | 22  | REDUCE 6 | READ | REDUCE 6  | | |  Figure  1.9 l o o k a h e a d  [ SYMBOL  (k=1) symbol  | NEXT  s e t f o r s t a t e 24  | ACTION  '|  | IDEN | 41 I READ | | 1ST | 5 | REDUCE 6 | | OPEN | 6 J REDUCE 6 | | PROC | 7 | REDUCE 6 | | REAL | 8 | REDUCE 6 | i ; \ . i_i L — : i F i g u r e 1 . 1 0 l o o k a h e a d (k=2) symbol s e t f o r s t a t e 24  32  STATE TABLE  SYMBOL TABLE —-,—  | TYPE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  | BEAD ] HEAD | BEAD {BEAD | POP | BEAD | READ | POP | POP | READ | READ | READ | POP |LOOKAHEAD | POP | POP |LOOKAHEAD |LOOKAHEAD | READ | POP | READ | READ | POP |LOOKAHEAD | POP | READ IREAD IREAD | POP | READ | POP | POP | LOOKAHEAD | READ | POP | POP |LOOKAHEAD |LOOKAHEAD | POP J READ | POP | POP ILOOKAHEAD | READ | READ | READ (READ | READ  1  1 1  1  1  1 1  2  —T———"  1  1  | NUMBER jOFFSET | l J : J1 1 • • T 1 30 | | 1 | 1 1 31 | | 4 I 32 | | 1 I 36 | | 0 I 70 | I 37 | I 2 I 32 | I 4 I 71 | I o I 72 | I o i 2 I 39 | I 1 I 41 | I 1 I 42 I I 73 | I 3 | 5 I 1 I 1 74 j i o 1 75 J I o I 3 1 6 | I 4 1 9 | | 1 1 ^7 | 1 78 | I 1 1 4 1 32 | 1 37 | 1 2 1 79 | 1 o 1 13 } 1 2 I 81 | 1 2 I 37 | 1 2 I "9 I 1 2 I 49 | 1 2 | 1 I 82 | I 4 I 32 f I 83 | I 2 I 84 | I o I 20 | I 2 J 1 I 52 | I 86 | I 2 | 87 | I o | 4 | 22 } I 26 | I 4 I 90 | I 3 | 37 | I 2 | 2 I 91 | I 92 | ! 2 I 15 | I 5 J 1 I 43 | I 44 | I 1 I 45 | I 2 I 48 | I 1 | 1 I 51 |  Figure  1.11 c o n t i n u e d  on n e x t  1 SYMBOL|STATE | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 page  r  T  | BECOMES |CLOSE | |GOON | 10P | |0PEN | JCLOSE | JGOON J JOP | \CLOSE J |GOON ] |OP | |OPEN } |COMMA | |GOON | |IDEN | J INT | JOPEN | JPROC | |REAL 1 JCLOSE j \GOON | |CLOSE I |GOON J |OP | |OPEN | |CLOSE | |GOON | |OP J J OPEN | |START J | OPEN | | INT f | OPEN \ |PROC | | REAL | |STOP | |IDEN J |OPEN | |COMMA j |GOON J JIDEN | |CLOSE | |BECOMES |OP | |OP 1 |OPEN | | CLOSE J |COMMA 1 i  i  44 36 36 36 36 57 57 45 58 58 46 46 43 59 47 59 59 59 59 60 48 61 61 61 49 62 62 62 50 2 3 5 6 7 8 13 14 3 21 22 23 25 26 27 28 3 30 34  | | | j | | | | | | I | 1 | | J | | | i | | \ I | f | | | I | I I I I | | I I | | | | J | I | | 1  33  I  *  49 50 51 52 53 54 55 56 57 58 59 60 61 62  I,,  —  —i  —i  — i— i - —  ~  1  | NUMBER|OFFSET |  | READ | READ |LOOKBACK 1 LOOKBACK |LOOKBACK 1 LOOKBACK | STOP | LOOKBACK |POP JPOP |POP |POP |POP 1 POP L  T—  1  1 TYPE  I I I - — — L. -X-. ...  j I  | t I I I I  I I I  I  I I  1 1 0 0 o  0 0 0 0 o  1 2 2 2  | I  | | |  | | | | i I l  | I  31 31 53 58 60 63 0 66 76 77 80 85 88 89  L_-  Figure  '  | I  | | | | I  | | | | | | J j  1.11  49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92  J SYMBOL|STATE| h~ + 1 | IDEN 36 3 |OPEN | GOON 40 | IDEN 41 12 4 | 29 |46 |49 29 |50 29 16 |0 121 I 31 9 I o 20 |7 | 30 39 11 |0 | 27 37 128 1 38 18 |0 32 |22 126 35 |40 42 JO | 19 53 I 8 |7 I 53 10 1 *» 55 1 1 56 |15 | 23 | 54 56 I 16 56 I 17 53 I 10 24 I 11 52 (6 |2 51 54 | 22 10 |5 33 I 13 13 12 |18 15 54 121 | 20 17 | 19 17 53 19 24 1 12 33 1 14  34  The here  s e c o n d example i s an LALR (2) grammar.  to demonstrate the  algorithm.  detection  The p r o d u c t i o n s  of  failure  We a r e u s i n g i t of  o f t h e grammar a r e a s f o l l o w s :  1) PROGRAM -> START CLAUSE STOP 2)  CLAUSE -> OPEN SERIES CLOSE  3)  SERIES -> DECLLIST GOON UNITSERIES  4)  DECLLIST -> DECL '  5)  DECLLIST ->  6)  DECL -> DECLARER  7)  DECLARER -> REAL  8)  DECLARER -> INT  9)  DECLARER -> OPEN UNIT CLOSE DECLARER  DECLLIST  the  COMMADECL  IDENLIST  10  DECLARER -> PROC DECLARER  11  IDENLIST -> IDEN  12  IDENLIST -> IDENLIST COMMA IDEN  13  UNITSERIES -> UNIT  14  UNITSERIES -> UNITSERIES GOON UNIT  15  UNIT -> ASSIGNATION  16  UNIT -> FORMULA  17  UNIT -> PRIMARY  18  ASSIGNATION -> IDEN BECOMES UNIT  19  FORMULA->  PRI01FORMULA  20  FORMULA—>  PRI02FORMULA  21  FORMULA->  MONADICFORMULA  22  PRI01FORMULA~>  PRI010PERAND PRI010P PRI020PERAND  23  PRI010PERAND->  PRI020PERAND  24  PRI010PERAND->  PRIO1FORMULA  SLR(k)  35  (25)  PRI02F0RMULA->  PRI020PERAND  PRI020P MONADICOPERAND  (26)  PRI020PERAND:->  PR 102 FOR MO LA  (27)  PRI020PERAND->  MONADICOPERAND  (28)  MONADICOPERAND->  PRIMARY  (29)  MONADICOPER*AND->  MONADICFORMDLA  (30)  MONADICFORM0LA->  MONADICOP  (31)  PRIMARY -> IDEN  (32)  PRIMARY -> PRIMARY CLAUSE  (33)  PRIMARY -> CLAUSE.  The  b a s i s s e t s o f t h e CFSM a r e g i v e n  MONADICOPERAND  transitions  are  given  in  transitions  are  given  i n figure  24,  25,  29,  similarity example,  for for  45  and  between t h i s  this  successful  37,  48  1.13 1.14.  are  and  grammar i s n o t SLR ( k ) .  1. 12, t h e symbol the  States  inadequate.  grammar a n d t h e grammar The SLR (k)  nonterminal  14, 19, 21, 22, Despite  the  i n the previous algorithm  was  f o r s t a t e s 14, 22, 25, 29, 37, 45 and 48, b u t f a i l e d  s t a t e s 19, 21 and 24. states  figure  i n figure  19,  21  1.17, r e s p e c t i v e l y .  The l o o k a h e a d  and 24 a r e g i v e n  symbol  sets  computed  i n f i g u r e s 1.15, 1.16 and  36  i  ~"i  *•*—  |STATE|  -  -———  BASIS SET  |  1  PROGRAM  2  PROGRAM -> START.CLAUSE STOP  3  CLAUSE -> OPEN.SERIES CLOSE  4  PROGRAM -> START  5  DECLARER  -> INT.  6  DECLARER  -> OPEN.UNIT  7  DECLARER  ->  8  DECLARER  -> REAL.  9  DECLLIST -> DECL.  10  DECL -> DECLARER.IDENLIST  11  DECLLIST -> DECLLIST.COMMA DECL SERIES -> DECLLIST.GOON UNITSERIES  12  CLAUSE -> OPEN SERIES.CLOSE  13  PROGRAM -> START CLAUSE STOP.  14'  ASSIGNATION -> IDEN.BECOMES PRIMARY -> IDEN.  15  MONADICFORMULA ->  16  UNIT ->  17  PRIMARY -> CLAUSE.  18  UNIT ->  19  FORMULA -> MONADICFORMULA. MONADICOPERAND -> MONADICFORMULA.  20  PRI020PERAND  21  PRIMARY -> PRIMARY.CLAUSE UNIT -> PRIMARY. MONADICOPERAND -> PRIMARY.  22  FORMULA -> PRI01FORMULA. PRI010PERAND -> PRI01FORMULA.  -> .START CLAUSE STOP  CLAUSE.STOP  CLOSE  DECLARER  PROC.DECLARER  UNIT  MONADICOP.MONADICOPERAND  ASSIGNATION.  FORMULA.  Figure  ->  MONADICOPERAND.  1.12 c o n t i n u e d  —^  on n e x t  page  STATET  '  BASIS  SET  ~]  23  |  PRIOIFOffMULA ->  24  | |  FORMULA -> P R I 0 2 F 0 R M U L A . PR102OPERAND -> P R 1 0 2 F O R M U L A .  25  PR 1 0 1 O P E R A N D . PR 1 0 1 0 P  PRI020PERAND  | \ j  |  PRI02F0RMULA  ->  PRI020PERAND.PRI020P  |  PRI010PERAND  ->  PRI020PERAND.  26  |  DECLARER  ->  OPEN  UNIT.CLOSE  27  |  DECLARER  ->  PROC  DECLARER.  28  |  IDENLIST  ->  IDEN.  29  | |  I D E N L I S T -> I D E N L I S T . C O M M A D E C L -> D E C L A R E R I D E N L I S T .  30  |  DECLLIST  31  |  SERIES  ->  DECLLIST  32  |  CLAUSE  ->  OPEN  33  |  ASSIGNATION  34  |  PRIMARY  35  |  MONADICOPERAND  ->  MONADICFORMULA.  |  36  |  MONADICFORMULA  ->  MONADICOP  |  37  | |  P R I M A R Y -> P R I M A R Y . C L A U S E M O N A D I C Q P E R A N D -> P R I M A R Y .  38  |  PRIMARY  39  |  PRI01FORMULA  ->  PRI010PERAND  PRIO1OP.PRI020PERAND  |  40  |  PRI02F0B?MULA  ->  PRI020PERAND  P R I 0 2 0 P . MONADICOPERAND  1  41  |  DECLARER  ->  OPEN  42  |  IDENLIST  ->  IDENLIST  COMMA.IDEN  |  43  |  DECLLIST  ->  DECLLIST  COMMA  |  44  | J  U N I T S E R I E S -> :  ->  ->  ->  Figure  1 I  DECLARER  | | |  DECLLIST  IDEN  | |  COMMA.DECL  J  GOON.UNITSERIES  SERIES  ->  MONADICOPERAND  IDEN  |  CLOSE.  |  BECOMES.UNIT  I  IDEN.  -  PRIMARY  MONADICOPERAND.,  >  CLAUSE.  UNIT  4  1.12 continued  | | |  CLOSE.DECLARER  UNIT.  f  DECL.  | I  ,  on n e x t  |  page  38  [STATE!  BASIS  SET  ~]  1 45 |  | |  UNITSERIES -> UNITSERIES.GOON UNIT SERIES -> DECLLIST GOON UNITSERIES.  I |  | 46  |  ASSIGNATION -> IDEN BECOMES UNIT.  |  | 47  j  PRI020PERAND -> PRI02FORMULA.  |  | 48 |  | |  PRI02FORMULA -> PRI020PERAND.PRI020P MONADICOPERAND PRIOlFORMDLA -> PRI01OPERAND PRI010P PRI020PERAND.  J |  l  1  l  '  | 49  |  PRI02FOR>MULA  -> PRI020PERAND PRI020P MONADICOPERAND.  | 50  |  DECLARER -> OPEN UNIT CLOSE DECLARER.  |  ] 51  |  IDENLIST -> IDENLIST COMMA  |  | 52  |  UNITSERIES -> UNITSERIES GOON.UNIT  |  | 53  |  UNITSERIES -> UNITSERIES GOON UNIT.  |  Figure  IDEN,  1.12  |  39  I  '  T~  SYMBOL  |STATE| 1  2 3 4 5 6  7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  32 33  34  TRANSITIONS  START (2) OPEN (3) CLAUSE (4) INT (5) OPEN (6) PROC (7) REAL (8) DECL (9) DECLARER (10) DECLLIST (11) SERIES (12) STOP(13) #8 IDEN(14) MONADICOP (15) OPEN (3) ASSIGNATION(16) CLAUSE(17) FORMULA (18) MONADICFORMULA (19) MONADICOPERAND(20) PRIMARY (21) PRIO 1 FORMULA (22) PRI010PERAND(23) PRI02FORMULA(24) PRI020PERAND (25) UNIT (26i) INT (5) OPEN (6) PROC (7) REAL (8) DECLARER (27) #7 #4 IDEN (28) IDENLIST(29) COMMA (30) GOON (31) CLOSE (32) #1 BECOMES (33) #31 IDEN (34i) MONADICOP (15) OPEN (3) CLAUSE (17) MONADICFORMULA(35) MONADICOPERAND (36) PRIMARY (37) #15 #33 #16^ #21 #29 #27 OPEN (3) CLAUSE(38) #17 #28 #19 #24 PRI010P (39) #20 #26 PRI020P(40) #23 CLOSE (41) #10 #11 COMMA (42) #6 INT (5) OPEN (6) PROC (7) REAL (8) DECL (43) DECLARER (10) IDEN(14s) MONADICOP (15) OPEN (3) ASSIGNATION (16) CLAUSE (17) FORMULA (18) MONADICFORMULA (19) MONADICOPERAND (20) PRIMARY (21) PRIO 1FORMULA(22) PRI010PERAND(23) PRI02FORMULA (24) PRI020PERAND (25) UNIT (44) UNITSERIES (45) #2 IDEN (14) MONADICOP (15) OPEN (3) ASSIGNATION(16) CLAUSE (17) FORMULA (18) MONADICFORMULA (19) MONADICOPERAND (20) PRIMARY (21) PRI01FORMULA (22) PRI010PERAND(23) PRI02FORMULA (24) PRI020PERAND (25) UNIT (46) #31 Figure  1.13 c o n t i n u e d  on n e x t  page  40  |  :  T  SYMBOL  | STATE| J~ -+ 35 36 37 38 39  TRANSITIONS  #29 #30 OPEN (3) CLAUSE (38) #28 #32 IDEN (34) MONADICOP(15) OPEN (3) CLAUSE(17) MONADICFORMULA(35) MONADICOPERAND(20) PRIMARY (37) PRI02FORMULA(47) PRI02OPERAND(48) IDEN (34) MONADICOP (15) OPEN (3) CLAUSE (17) MONADICFORMULA (35) MONADICOPERAND (49) PRIMARY(37) INT (5) OPEN (6) PROC (7) REAL (8) DECLARER (50) IDEN (51) #5 #13 GOON (52) #3 #18 #26 PRIO2OP(40) #22 #25 #9 #12 IDEN (14) MONADICOP (15) OPEN(3) ASSIGNATION(16) CLAUSE(17) FORMULA(18) MONADICFORMULA (19) MONADICOPERAND(20) PRIMARY (21) PRI01FORMULA(22) PRIO10PERAND(23) PRI02FORMULA (24) PRI020PERAND (25) UNIT (53) #14  40 41 42 43 44 45 46 47 48 49 50 51 52  53  Figure j.  i  NONTERMINAL ; , = ASSIGNATION CLAUSE DECL DECLARER DECLLIST FORMULA IDENLIST MONADICFORMULA MONADICOPERAND PRIMARY PR101FORMULA PRIO10PERAND PRI02FORMULA PRI020PERAND PROGRAM SERIES UNIT UNITSERIES ;  HAS +  1.13  TRANSITIONS _  I  16 t 4 17 38 | 9 43 I 10 27 5 I 11 1 18 | 29 J 19 35 | 20 36 4 I 21 37 | 22 I 23 | 24 47 I 25 48 j | 12 | 26 44 4 t 45  53  J  Figure  1.14  TO STATES  41  | SYMBOL  |  J | | | | | | I  | | | I | I | I  CLOSE CLOSE CLOSE CLOSE GOON GOON PRI010P PRI020P  Figure  1.15 l o o k a h e a d  |" SYMBOL r | | | l | | | } |  1.16 l o o k a h e a d  1 | j | | | | |  1.17 l o o k a h e a d  From f i g u r e s clashes  i n each  same t e r m i n a l  column  | | | J | | J 1  3  computation  and,  REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE  21 29 21 29 21 29 29 29  I I  symbol s e t f o r s t t ea 19 -TI  t  ACTION  1  —i  REDUCE 17  1 1 j REDUCE 17 1 | REDUCE 28 1 j REDUCE 17 1 | REDUCE 28 1 | READ I | REDUCE 28 1 | REDUCE 28 1 -Xi s y m b o l s e t f o r s t a t e 21  | REDUCE 28  32 «M 41 52 52 3 39 40  T | NEXT  CLOSE CLOSE CLOSE CLOSE GOON GOON PRI010B PRI020P  the  32 32 41 41 52 52 39 40  I 32  | I I I I | | |  I | SYMBOL  Figure  J ACTION  j NEXT  CLOSE CLOSE CLOSE CLOSE GOON GOON OPEN PRI010P PRI020P  Figure  NEXT  | ACTION +REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE REDUCE  32 32 41 41 52 52 39 40  20 26 20 26 20 26 26 26  1 i I  I i s y m b o l s e t f o r s t a t e 24  1.15, .1.16 and 1.17 we c a n o b s e r v e lookahead symbol, in  symbol s e t . there  column  o f t h e next  are  2,  lookahead  the  A clash  two next  o c c u r s when,  different states  symbol s e t s  a number o f  actions to  for in  commence  a r e t h e same.  It  42  is  by  the o b s e r v a t i o n of such  algorithm  is  searching  for  prevented  from  lookahead  c l a s h e s as t h e s e  that  the  SLR(k)  going  infinite  loop  into  an  symbol s e t s o f a grammar which i s n o t  SLR (k) .  1.6  LALR (k) If  an  attempt symbol  inadequate  LALR(k) s e t f o r an  algorithm context for  Grammars  with  of  reductions  fails  to  lookahead.  The  inadequate  state  the  exception  to determine  each  state  the  is  that  when  we  reductions  within  while touring  marking will  d i r e c t i o n s and  visit a path  i t .  into  two  those  we  The  through  only include sets  to  marking  states;  those  to  that  left  consider states  we  can  may  "mark" a  and  be  state  i s e q u i v a l e n t to marked  thus, p a r t i t i o n we  SLR (k)  transitions  path or paths  c o n t e x t and,  lookahead  states.  of a s t a t e  The  may  must c o n s i d e r t h e  the s t a t e that  we  the  the inadequate  other  such  t h e CFSM.  the l e f t of  of the  similar we  then  which n o n t e r m i n a l t r a n s i t i o n s  encountered  i n both  SLR(k),  computation  The ,CFSM i s m o d i f i e d s u c h t h a t followed  be  out  t h e CFSM  are i n t e r e s t e d  i n and  are not i n t e r e s t e d i n .  Now,  c o n s i d e r an i n a d e q u a t e  within  the  SLR (k)  algorithm.  inadequate CFSM  to  right  hand  inadequate  state,  state  However, we  state. are  for  must f o l l o w  The  treated each  terminal  t h e same as i n t h e  reduction  within  t h e p r o d u c t i o n back t h r o u g h  t h o s e s t a t e s i n t h e CFSM where t h e f i r s t side  symbols  o f the p r o d u c t i o n i s r e a d .  As  we  symbol on follow  the the the the  U3  production For  b a c k , we "mark" e a c h o f t h e s t a t e s  each s t a t e  transition the  i n this  These  states  which s h o u l d  SLR(k)  algorithm.  those  as  states  following into  If  any  LALR(k)  state  The  i n step  the  the  then  hand s i d e o f  us t o a s e t o f  considered the  subset  which  we  and  mark  in  treat  the  a state  states  a l l states  the  grammar i s n o t terminal  but the reductions  through  the  a s we go.  nonterminal  CFSM  within  using  transition  has been "marked", t h e n f o l l o w  on  have  leading  only  been  with s t a t e  the  those  marked;  transitions  state.  11, t h e n  algorithm  i s then t r e a t e d treated  t h e same a s i n  as above.  I f a clash i s  t h e grammar i s n o t LALR ( k ) .  was s u c c e s s f u l algorithm  If  f o r a l l the inadequate  failed)  then the  steps  CFSM  may  the  states now  be  t o a DPOA. following  p r e v i o u s example..  example  about  state  of states  a list  1.18.  uses  The CFSM i s  information  figure  not,  back  with reductions  (where t h e SLR (k) converted  is  state with  table constructed 11  of the s t a t e s  within  must be t r a c e d  follow  through  now f o u n d  in  i t  into the current  The  follow  t h e SLR(k) a l g o r i t h m ,  transitions  leading  then  t r a n s i t i o n s lead  be a s u b s e t If  rules  otherwise,  7  in  the current  state  state  For each s t a t e  symbols  we  under t h e n o n t e r m i n a l s y m b o l on t h e l e f t  production.  LALR ( k ) .  set,  visited  the  CFSM  with  the  the  same  same,  i s required.  grammar a s i n t h e  but  a  little  We r e q u i r e  transitions into i t .  more  f o r each  Such i s  given  44  | STATEJ IS 1 1 ] | | I j I ] I I I j | I i i 1 I 1 I | 1 I 1 1 1 1  r I | ] | 4 I 5 J 6 | 7 | 8 | 9 I 10 | 11 I 12 J 13 | 14 I 15 | 16 | 17 | 18 I 19 I 20 1 21 | 22 I 23 | 24 \ 25 I 26 | 1 2 3  1 2 39 2 3 3 3 3 3 3 3 3 4 6 6 6 6 6 6 6 6 6 6 6 6 6  ENTERED FROM STATES  6 15 21 40 52 7 7 7 7  30 30 30 30  31 33 37  41 41 41 41  30  31 15 31 15 31 31 31 31 31 31 31 31  33 31 33 31 33 33 33 33 33 33 33 33  52 33 52 33 52 52 39 52 52 52 52 52  39 40 52 39 40 52 52  | STATE| i t -i +1 27 | 1 28 1 1 29 | 1 30 J 1 31 | I 32 J I 33 | I 34 | I 35 | I 36 | I 37 J I 38 | I 39 | I 40 | I 41 | I 42 | I 43 | I 44 | I 45 | I 46 | I 47 | I 48 | I 49 | I 50 | I 51 | J 52 j I 53 I  Figure Osing  t h e LALR (k)  symbol s e t f o r s t a t e production  algorithm,  are  6,  from  which  number  40 40  39 37  40  state  t o those s t a t e s  t h e lookahead  19 we w i l l  t h e CFSM.  hand s i d e which  so  follow  Production we  lead  will into  F o r each o f these s t a t e s  the nonterminal  ("FORMULA")  16 b a c k t h r o u g h  have been marked.  State  t h e CFSM  transition  In s t a t e only  18 i s e n t e r e d  18, we  to those  from s t a t e s  go  state  31, 33 and 52.  18, 18, 18 and 18, r e s p e c t i v e l y .  production  39 39  48  numbers 21 and 29 back t h r o u g h  mark them and f o l l o w states  10 10 10 11 11 12 14 15 15 15 15 21 23 25 26 29 30 31 31 33 39 39 40 41 42 45 52  we c a n c o n s t r u c t  19 a s f o l l o w s :  back t h r o u g h t h e CFSM o n l y They  ENTERE  1.18  number 21 has one symbol on fehe r i g h t  19.  IS  we to  follow states 6, 31,  33  and  52.  transitions yields in  Under  to states  44 and l e a d s  21} and t h e r e d u c t i o n vein  until  algorithm  is  ^~  CLOSE CLOSE GOON PRI010P PRI020R  Figure  to state  1.19 l o o k a h e a d  number 3.,  as i n f i g u r e  i n figures  32 41 52 39 40  REDUCE REDUCE REDUCE REDUCE REDUCE  T " | ACTION  | | | | l j  | | | J | |  | REDUCE | REDUCE 1 REDUCE | READ | REDUCE | REDUCE  1  CLOSE CLOSE GOON OPEN PRI010P PRI020P  Figure I  '•  —  1.20 l o o k a h e a d  J SYMBOL  H  32 41 52 3 39 40  21 21 21 29 29  | | | \ | 19 1  J 17 17 17 28 28  | | | | | |  symbol s e t f o r s t a t e 21  1  1  | NEXT  | CLOSE | } CLOSE | | GOON | | PRI010P | 1 PRI020P | I \ X F i g u r e 1.21 l o o k a h e a d  and  ]  symbol s e t f o r s t a t e  | NEXT  •  "  21  ~\ ACTION | | | | |  32 41 52 39 40  T  •  J ACTION j | | | | I  the  State  26  13 i s r e d u c e d  We  continue  REDUCE REDUCE REDUCE REDUCE REDUCE ;  | 20 20 20 26 26  | | | | | J  s y m b o l s e t f o r s t a t e 24  in  1.19.  The LALR(k)  24,  y i e l d i n g the  1.20 and 1.21, r e s p e c t i v e l y .  | SYMBOL  i  follow  45 which y i e l d s {GOON, 52, REDUCE  f o r states  T~NEXT | I | | |  we  P r o d u c t i o n number  of production  repeated  [ SYMBOL  "UNIT",  26, 44; 46 and 53, r e s p e c t i v e l y .  we g e t t h e t a b l e  l o o k a h e a d symbol s e t s  | | \ | I  nonterminal  {CLOSE, 41, REDUCE 21}.  state  this  the  46  1.7 LR (k) The  Grammars and S t a t e - s p l i t t i n g failure  grammar  is  the  context  left  some  of  left  context,  then  will  algorithm  (loops  state,  we must f o l l o w  the  If  are  failed).  ignored) that  leading  state  these  ignored).  grammar  For with  are  example, c o n s i d e r transitions  o t h e r s from  d to states  transitions  leading  i n a d e q u a t e state.*  state  with  a CFSM  other  within  the  transitions  ( f o r which  into  none  back  we f i n d  into  i t  can  one  the state  the inadequate  transition  to  c  through  a state  (loops  be f o u n d  with  within then the  from  Now  with  no  other  let d  local  loops)  ..-}  state  r e p r e s e n t an  until  t r a n s i t i o n leading c and d  into  (states  c*  into  we f i n d  will  and  be no  t o d, d» t o c o r d t o c » ) .  a  i t (state d , f  c ' t o d« and d» t o  a s i n d, b u t t h e r e f  { a , b, c , d,  t r a n s i t i o n s leading  t r a n s i t i o n s from  c to d , c 1  d.  the s t a t e  make a c o p y o f s t a t e s with s t a t e  states  t o c , b t o c , c t o d, d t o c,  (ignoring  d* t o o t h e r s t a t e s  transitions  a  and  We f o l l o w  with  t h a n c and  more t h a n one s t a t e  We w i l l  from  If  from  t h r o u g h t h e CFSM  respectively, and  off  i s n o t LR ( k ) .  state  back  clashes  I f there i s only  CFSM, as f a r as i t i s n e c e s s a r y , u n t i l  states  the  partition  be a number o f s t a t e  t r a n s i t i o n leading  c).  can  perhaps  more t h a n one s t a t e  d  we  i n t o an i n a d e q u a t e s t a t e  transition  that  disappear.  there  o r more) l e a d i n g  LALR(k) l o o k a h e a d  will  indicates  t h e r e d u c e d CFSM d o e s n o t p e r m i t  t o be unambiguous.  t h e CFSM  then  algorithm  LR(k) o r t h a t  symbol s e t s  Within (one  not  the  lookahead  o f t h e LALR (k)  C  state A  state  transition  leading  the  t r a n s i t i o n from b t o c i s removed.  one d) .  state state  into  state  t r a n s i t i o n leading  c* f r o m  t o c from a  S i m i l a r l y , f o r the s t a t e s  transition  leading  to  c»  the  CFSM  from  has  increased.  i s no l o n g e r  b  may  state-splitting  repeated.  may  be  the loop  d»).  one  from state  State  d»  The r e s u l t o f t h i s a c t i o n i s  If  successful  f o r a l l the inadequate  performed,  i t continues  attempted  action  The  there i s only  this action " s t a t e - s p l i t t i n g " .  splitting  algorithm  can  (ignoring  and  r e d u c e d , and b) t h e s i z e o f t h e CFSM  De Remer t e r m e d  be  Now  (ignoring  Once t h e s t a t e - s p l i t t i n g h a s been algorithm  b i s constructed  c * and d» t h e r e i s o n l y  r e p r e s e n t s a new i n a d e q u a t e s t a t e . a)  state  be p e r f o r m e d .  again,  the  LALR(k)  to f a i l ,  until  no  further  I f t h e LR(k) a l g o r i t h m  states  ( f o r which t h e  then  is  LALR (k)  f a i l e d ) t h e n t h e CFSM may now be c o n v e r t e d  t o a DPDA.  following  and  transitions  LR(1)  i n figures  (1)  S -> START EE STOP  (2)  EE -> A AA D  (3)  EE ->  (4)  EE -> B AA C  (5)  EE -> B BB D  (6)  AA -> E AA  (7)  AA -> E  (8)  BB -> E BB  (9)  BB -> E.  A BB C  grammar  1.22 and 1.23,  has  i t s CFSM  respectively:  source  ]STATE| 1  S - > ..START EE  2  EE -> .A AA D EE -> • A BB C EE -> .B A A C EE -> . B BB D S --> START.EE  3  AA AA BB BB EE EE  -> -> ~> -> -> ->  .E A A .E .E BB . E A. A A D A. BB C  AA AA BB BB EE EE  -> -> -> -> -> ->  . E AA . E .E BB .E B. AA C B. BB D  5  S --> START EE.  6  |  AA AA BB BB AA BB AA BB  I  EE -> A  7 8  -> -> -> -> -> -> -> ->  | SYMBOL | STATE -+ -+— START 2 A  3  B  4  EE  5  E  6  AA BB  7 8  AA BB  9  STOP  . E AA •E .E BB .E E. AA E. BB E. E.  E  10 11 6  AA BB #7 #9  12 13  AA.D  D  14  EE -> A BB.C  C  15  9  |  EE -> B  AA.C  C  16  10  |  EE -> B  BB.D  D  17  11  I  s --> START EE  #1  12  |  AA -> E AA. ,  #6  13  |  BB -> E  #8  I  EE -> A AA  14 «  CONFIGURATION SET  BB. D.  #2  .  Figure  1.22 c o n t i n u e d  on n e x t  page  | 1  49  |STATE|  CONFIGURATION SET  -—+-  \  1 15  |  EE  I 16  |  EE  |  EE -> B BB D.  I 17 i  i ~  —  T  STATE  | #3 I | #4  Figure ,  | SYMBOL  1.22  -  | STATE| IS 1 I i I I I | I I  1 2 3 4 5 6 7 8 9  i i | | j | | | |  -J—i—-— | | 10 I I I 11 | I 12 I 13 I | 1 14 I 15 I ] 16 | 1 17 I  1 2 2 2 3 4 3 3 4  L  Figure State  6 i s inadequate.  lookahead lookahead  symbol  ._i  algorithm  i n f i g u r e 1.25 which  I NEXT  ACTION  I I I I  C C D D  I  REDUCE REDUCE REDUCE REDUCE READ  E  I I I I I  with  was p r e c e d e d  1.24 l o o k a h e a d  15 16 14 17 6  the  by t h e  (k=1) symbol  9 7 7 9  set f o r state 6  | SYMBOL  | NEXT  | ACTION  |  | STOP | STOP  111 | 11  | REDUCE 7 | REDUCE 9  | |  Figure  fails  symbol s e t i n f i g u r e 1.24 under "C".  [ SYMBOL  Figur e  4 5 6 6 7 8 9 10  1.23  The LALR (k)  set  1  1.25 l o o k a h e a d  State-splitting  (k=2) symbol i s attempted.  set f o r state 6 The s o u r c e  to  state  6  is  50  split has  up  such that  modified  transitions the  1  ! I j I  2  I 1  |  in  T  CONFIGURATION #  EE -> .A AA D EE -> .A BB C EE -> .B AA C EE -> .B BB D S -•> START.EE STOP  |  1  1  | EE  1  5  1  6  j  |  I  -> A BB.C  :—x—  4  I J  EE  8  ! I  | AA | BB  |  1  B  18  -> A  i  1  1  EE  7  3  |  1 j  |  J  1  .E A A .E . E BB . E B. AA C B.BB D  1  1  1 A  -> -> -> -> -> ->  -> -> -> -> -> -> -> ->  |  2  7 8  AA AA BB BB AA BB AA BB  j  1  1 1  |  | | | | |  —r | START  T~STATE ~|*  | AA | BB  S --> START EE.STOP  6  —  Using  j  |  | ] | | |  source  j j j  1  1  -  state.  symbol s e t s f o r  I SYMBOL .  \ E  J 5  .  .E AA . E . E BB •E A. A A D A. BB C  | | |  I  .  new  respectively.  -> -> -> -> -> ->  ] | |  | |  the lookahead  AA AA BB BB EE EE AA AA BB BB EE EE  4  .  18, a  18 i s i n a d e q u a t e .  SET .  | | | |  |  State  get  i n t o 6 and s t a t e 4  1.26 and t h e m o d i f i e d  1.28 and 1.29,  S - > .START EE STOP  |  figure  we  I  | i I  3 and 6 l e a d  1.27.  6 and 18 i n f i g u r e s  I 3  is  algorithm,  [STATET" —  CFSM  are i n figure  LALR(k)  states  1  states  a d i f f e r e n t t r a n s i t i o n under " E " t o s t a t e  The  1—  only  E  |  {  j  . E AA .E .E BB .E E. AA E. BB E. E.  1  AA.D  Figure  |  1.26 c o n t i n u e d  STOP E  I  |  9  10 11  6  |  j  J  |  | AA | BB  12 13  | 1  #7 #9  I 1 I 1  ]  o  1  14  |  15  1 c _j on n e x t page  _ _ x  _  51  i  ;—~x"  r  +-  |STATE|  CONFIGURATION SET  9  EE -> B AA.C  SYMBOL . I c  10  EE -> B  I D  I  17  11  S --> START EE STOP.  I #1  i  -  12  A A -> E AA.  i  #6  I  -  13  BB -> E BB.  I #8  I  14  EE -> A AA  J #2  !  -  15  EE -> A BB C.  |  #3  I  ~  16  EE -> B AA C.  J #4  1  "  17  EE -> B BB D.  |  1  ~  18  AA AA BB BB AA BB AA BB  | j  18  -—I  -> -> -> -> -> -> -> ->  BB.D  .E AA .:E .E BB .E E. AA E. BB E. E.  D.  I  i  T  |STATE| j. I 1 | I 2 1 | I 3 I 4 I I 1 5 | 1 6 1 7 I 1 8 I I 1 9 L ; j  j J } 1 1 |  ,  T~'  IS ENTERED FROM STATES i  1 2 2 2 3 6 3 3 4  E  |  Figure i  #5  | | AA BB #7 #9  1 I I I  12 13 —  | 4  I a 1 1 i 1 1 I 1 1 1 1 1 • 1 1 1 1 1 • 1 1 i 1 1 • 1 1 1 1 1 1 1 1 1  1.26 '—r  |STATE| _ x \ 10 I I I 11 ) 12 I I 13 I 1 14 I I 15 l I 16 I I 17 I | I 18 i F i g u r e 1.27 +  t STATE H I 16  •  1  IS ENTERED FROM STATES | _ 1 4 I 5 1 6 1 6 1 7 1 8 J 9 1 10 1 4 18 I ._ .. . i  52  '  I  -i  | STATE  y  1_  T" -  | NEXT  ,  1.28  lookahead  | STATE  1.29  Empty  lookahead  productions occurrence  i t  of  is  of such  terminal occurs  To  form  | | |  A  the  within  This  the  of  b)  an  offset  i n t o the  S ->  For  out  of  a  production  a CFG.  example,  s t a t e s may  when t h e  the  appreciably  those s t a t e s  them  or  However,  complicate  o f them, b u t  pushdown  have  need  not  configuration  stack  the  a  new  a push s t a t e  state which  push i n s t r u c t i o n  type  is  consists code  and  symbol t a b l e g i v i n g i ) a s t a t e name which  pushed o n t o the  stack  and  production  f o l l o w i n g SLR(1) A E B  does not  i n f o r m a t i o n : ! a)  r e d u c e s t a t e where t h e  The  have  e within  s t a t e type i s c a l l e d  pieces  be  18  them.  two  to  ->  to  parser.  transitions  of  (1)  ^  | REDUCE 7 | REDUCE 9 J READ  productions of  facilitate  created.  is  - i — i —  convenient  nonterminal t r a n s i t i o n s out  A ->.e  *|  symbol s e t f o r s t a t e  the  construction  have  for state 6  Productions  Sometimes  the  | | I  | ACTION  I 16 | 17 | 18  Figure  |  4  symbol s e t  —+-  l C j D | E  1  | REDUCE 9 | REDUCE 7 | READ  | NEXT  i*  —•  -|  | 15 J 14 | 6  Figure  :  | ACTION  +  I C ID | E  1.8  i  :  i i ) a state transition  to  number i s o u t p u t .  grammar c o n t a i n s  an  empty  production:  a  53  (2) E -> C (3) E -> D (4) D -> (5) D -> D W (6) C -> V D. The CFSM i  1 —  _  STATE] ;_  1 2  - + — I s  —  CONFIGURATION SET —  | SYMBOL .  ]  2  -> -> -> -> -> ->  I I I I i  |  3 4 5  |  —  |  7  .V D .C .0 .D W A.E B  I I I  c -> V.D D -> .D W D -> •  I | J  U  I  E -> C  I  5  I I  6 7  9  —\—  ! A  c E E D s B  8  _  .j  | STATE  -> .A E B  I I I I I I  3  I  is i n  v  c o  E | #U  •  D  | I ] j  6  #4  j J  —  «2  |  -  D -> D. W E -> D.  1 W 1 #3  ] |  —  I  s -> A E.B  1 B  |  9  I I  D -> D. W c -> V D.  1 w 1 #6  | I  —  I  D -> D W.  1 #5  |  —  I  s -> A E B.  1 #1  I  —  -X~~—  Figure  1.30  8  8  J  54  STATE TABLE  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  SYMBOL  j TYPE  | NUMBERJ OFFSET |  j READ J LOOKAHEAD 1 | PUSH | REDUCE |LOOKAHEAD 1 | READ JLOOKAHEAD 1 |REDUCE jREDUCE | READ | READ | READ |LOOKBACK | STOP ] PUSH |REDUCE |REDUCE |REDUCE  | I I 1 j 1 1 1 1 1 I  1  I  i I I 1 1 i  T~*  1 3 0 0 2 1 2 1 3 1 1 1 0 0 0 o 0 1  | | 1 I | 1 | 1 | ! I I  | | | 1 J I  8 1 16 17 4 11 6 20 21 9 10 10 12 0 14 15 18 19  Figure  t | | | 1 1 1 | | I | | | I | | | I  i  1.31  TABLE  i — i 1 | SYMBOL|STATE| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  iB IV  ]  w  IB 1 w IB 1 w U 1v |W 1B 13 JO 1 10 14 1 3 12 | 3 16 15 | 1 i  — i  1  1 I | | | I I I | I I  I 1 1 j | I I  I I 1 i  15 1 10 | 15 f 17 | 11 | 18 | 12 | 2 | 3 I 8 | 9 | 7 J 5 | 16 1 13 | 16 | 6 | 6 | 4 | 13 | 14 l i  55  CHAPTER  PARSER GENERATOR  In  this  algorithm, the  input  LR(k)  of  the the  analysis  is  languages analyser  each  course,  that  stream  360  type  been  again,  We  string  s t a r t s and of  are  that  before  the  integers.  writer  time a symbol there  the  have assumed t h a t  been c o m p l e t e d  sequence  and  f u r t h e r o p t i m i z a t i o n s and  generator.  compiler  parser  is  need read.  the  of  However, only  call  This  output  the  output  lexical  the  lexical  for  simple lexical  assuming,  a l w a y s enough s y m b o l s w i t h i n  of  syntactic  the  is  parsing  the  of  symbol  lookahead.  Parser  The have  CFG,  d i s c u s s the  has  t o perforim  2. 1 The  will  IMPLEMENTATION  string  a  the  we  of the  parser  a n a l y s i s of parse  chapter,  2  of parser  described  only  previously.  to describe  computers.  All the  instructions  how  they  parser  following  (i.e., Here,  read, we  will  appear w i t h i n  the  instructions  etc.)  mention IBM  them  System  f i t i n t o 4 bytes  fullword)  with  Bits  0-3:  instruction  Bits  4-7:;  number o f s y m b o l s l o o k a h e a d ; o t h e r w i s e ,  Bits  8-15:  (a  format:  code.  number o f s y m b o l s i f r e a d state  pop,  names t o be  or  zero.  lookahead,  number  popped i f r e d u c e ; o t h e r w i s e ,  zero.  of  56  Bits  16-31: o f f s e t i n t o s y m b o l t a b l e stop The  the  f o r a l l i n s t r u c t i o n s except  which i s z e r o .  symbol t a b l e  has d i f f e r e n t t y p e s o f e n t r i e s f o r each o f  d i f f e r e n t types of i n s t r u c t i o n s :  &) r e a d  and l o o k a h e a d the  number  entries. pair, B) r e a d  o f s y m b o l s d e n o t e s t h e number o f f u l l w o r d  Each  fullword  a symbol and a s t a t e  i n d e x e d and lookahead the  entry  symbol  length  table  being  grammar  contains  1.  halfword  name.  indexed entries are a l i s t  t h e number o f t e r m i n a l  plus  a  Each h a l f w o r d  of halfwords the  symbols w i t h i n t h e  i s 0 or a s t a t e  name.  C) r e d u c e o r pop the  symbol  production D)  entry  i s  number and a s t a t e  two  halfwords,  the  of halfword  pairs  name.  lookback the of top  symbol t a b l e state of  halfword  e n t r i e s form a l i s t  names; t h e s t a t e  name t o be compared  the  the  transition  E)  table  stack  and  t o be t a k e n .  state  In the l a s t  with the  name d e n o t i n g t h e entry,  the  first  i s 0.  push the  table  entry  names; t h e s t a t e the  The  state  parsing  c o n s i s t s of a halfword  name t o be pushed o n t o t h e s t a c k  name d e n o t i n g  algorithm  pair of state and  t h e t r a n s i t i o n t o be t a k e n .  i s stated  as f o l l o w s :  57  Step  1:  set  state  to  1,  head o f t h e lexeme S t e p 2:  s e t type bits  Step  to bits  0-3, num t o b i t s  search  symbol  symtable[offset], noQe f o u n d  then syntax e r r o r ;  4 (read  entry  +1.  the  u s e t h e lexeme a t  symbol  the entry  Set  pop  and  set  table  to currlex states  number  starting  state  to  ],  halfword name  to  i s found  state  table.  an  index  a t s y m t a b l e [ o f f s e t ]. otherwise,  push  to the state  name.  stack.  Output  the  o f symtable[ o f f s e t ] ) (second  halfword of  symbol for a  table, match  the  at  lexeme  statetable[ state ])).  then syntax e r r o r ;  name a d j a c e n t  to  starting  otherwise,  t h e symbol e n t r y  at If  set state  i n the  symbol  Go t o s t e p 2.  (lookahead (bits  as  Go t o s t e p 2.  ( c u r r l e x - 1 + ( b i t s 4-7 o f none  Set currlex t o  Go t o s t e p 2.  o f f the  state  search  symtable[offset  +1.  (first  s y m t a b l e [ o f f se t ]) . 6 (lookahead) :  state  name a d j a c e n t  currlex  i s 0 then syntax e r r o r ;  num  production  currlex.  o t h e r w i s e , push  o n t o t h e s t a c k and s e t s t a t e  currlex  S t e p 5 (pop) :  i n t h e symbol  at  at  Go t o s t e p 2.  indexed);  state  7  lexeme  table.  If  Step  to  to  (2 + t y p e ) .  starting  the  into  Step  table,  f o r a match  offset  Go t o s t e p  to state  currlex Step  8-15 and  o n t o t o p o f s t a c k and s e t s t a t e symbol  to the  stream.  16-31 o f s t a t e t a b l e [ s t a t e ].  3 (read):  If  t h e s t a c k empty and c u r r l e x  indexed):  use  the  lexeme a t ( c u r r l e x -  4-7 o f s t a t e t a b l e [ s t a t e ]))  a s an i n d e x  into  1 • the  58  symbol entry the Step 8  table  starting  i s 0 then syntax  state  name.  (lookback):  top  entry  state step Step 9 Step  in  the  push  adjacent  the  interrupted or  error  From  the  recovery  set state  to  table,  starting  at  (first  or u n t i l  name  halfword)  to  the  0 i s f o u n d and s e t  (second h a l f w o r d ) .  Go t o  stop. state onto  name the  (first stack  terminates i n step  language;  halfword)  and  set  at  state to  Go t o s t e p 2.  9, t h e n  otherwise;  error,  then  may be a t t e m p t e d  i f  the s t r i n g i s a  the  parse  was  t h e p a r s e may be t e r m i n a t e d  (see CHAPTER 3 ) .  Optimizations  t h e above d i s c u s s i o n ,  may  be  performed  four  (assuming 2,  symbol  stack  name.  by a s y n t a x  2.2 F u r t h e r  state  state  the a l g o r i t h m in  otherwise,  I f the  2.  symtable[offset]  sentence  the  to adjacent state  (push):  If  error;  ], f o r a match  ( s t o p ) : do j u s t t h a t :  10  s y m t a b l e [ o f f s e t ].  Go t o s t e p 2.  search  symtable[offset  at  is  that  an  obvious  optimization  the m u l t i p l i c a t i o n of a l l state  we s t a r t e d  etc.).  This  compiler  writer  with  speeds  state  up  the  which  names by  names s u c h a s s t a t e indexing  1,  into  the  of the decision  as to  statutable.  The  when t o use  a  read  indexed) i n s t r u c t i o n .  or  i s given  control  readindexed  The u p p e r l i m i t  (lookahead  or  lookahead  (number o f s y m b o l s i n t h e  59  set) set  f o r a sequential with  Additionally,  t h e same s y m b o l t a b l e  symbols saving  and  to  integers  are input.  that  of lookahead  either  i f  as f o l l o w s :  then  we  construct  integral  pair  attempt  parser  search  via  the  indexed  number  index  states  of  may  terminal thus  but a convenience  0-LR ( 0 ) ,  can  2  denotes  interested  Two  t o commence  The i n t e g r a l  in  used.  the  1-SLR (k) , 2-LALR (k)  to  algorithm values  are  and 3-LR ( k ) .  SLR (k)  or  LALR (K)  m i n i m i z e t h e amount o f work r e q u i r e d or terminate i n f a i l u r e  2 denote " s t a r t  state-splitting  may  algorithm  denotes the algorithm  (e.g.,  lookahead  to the  b u t do  i f i t fails").  one p a r s e r  be impeded.  w i t h LALR (k)  i n s t r u c t i o n i n which t h e s p e e d  The l o o k b a c k s t a t e d o e s a  t h r o u g h t h e symbol t a b l e and o t h e r  described  earlier,  i t i s difficult  lookback  process  without i n c r e a s i n g  the  i n and a symbol  t r a n s i t i o n s a r e t h e same,  go no f u r t h e r .  the parser  There i s only  of  the  and t h e s e c o n d  example, i f we a r e o n l y  grammars  the  The f i r s t  i f i t fails,  associated  not  symbol  o r read  c o n t r o l the type o f lookahead  construction  For  read  entries  the terminal  be a c c e s s e d  i s n o t n e c e s s a r i l y an o p t i m i z a t i o n  able  such  two  i s read  i n space.  It be  or lookahead  e q u a l o r more s y m b o l s w i l l  mechanism. use  read  of  sequential  than the o p t i m i z a t i o n  to increase  t h e speed o f  the complexity  and/or  the size  parser.  Further performed desirable  optimizations  as described to  keep  on p a r s e r s  in [A].  the  f o r LR(1) grammars may  However, i t was f e l t  schema g e n e r a l  that  and, t h e r e f o r e ,  be  i t was d i d not  60  apply  these  which  optimizations.  causes  implemented perform. or not  2.3  irrelevant  this The  Input  of  the  i t  is  writer should  an  optimization  bypassed.  not  too  I have  not  difficult  have t h e o p t i o n o f  to  whether  format  CFG of the  must a d h e r e t o t h e  CFG  CFG  the  first  and  i a r e used  rules  i s represented  parser  production no  as a sequence of  i s of  as  the  where e l s e  representations  (see D) Each  i n p u t t o t h e LR (k)  generator  following rules:  the  symbol  B)  r e d u c t i o n s t o be  f e a t u r e though  compiler  performs  i t i s applied.  The  A)  De Remer  of S  applied to other  productions,  form S->f-S»4  w i t h i n the |- and  r  where S, fe  grammar.  The  -| f o l l o w t h e  nonterminals  and  same  terminals  below) .  production  or  same n o n t e r m i n a l  on  sequence of p r o d u c t i o n s the  left  hand s i d e  may  with have  the the  format:  C)  nonterminal  symbol,  separated  semicolons,  by  a nonempty a l t e r n a t i v e nonterminal alternative as,  an  empty D)  colon,  may  not  alternatives  point.  i s a sequence o f separated  i n c l u d e the  empty a l t e r n a t i v e  by  terminal  commas.  empty  and  A nonempty  symbol;  where  i s the r e p r e s e n t a t i o n f o r  an  production.  t e r m i n a l and of  symbols  sequence of  nonterminal  upper case  letters,  s y m b o l s may lower  case  be  any  letters,  sequence digits  and  61  any  other  "  E)  character  ")",  " (",  distinguished  from  the  s i d e of a  left  hand  symbol ">".  must The  are  be  terminals  Comments may  occur  only  i f  and  Nonterminals  their  occurrence  the r e p r e s e n t a t i o n  by  ever.y  the  are on  (" and  " ) " or  character  and  between  representation  of  of a  a  them  symbol.  anywhere.  which a r e  a character  A  reduced  o f a symbol  w i t h i n a sequence o f  characters  symbol.  c h a r a c t e r s are  by  p a r t of  i t occurs  terminal  ">".  ";'*,  production.  " " i s r e t a i n e d as  characters or  not  brackets from  and  or  bracketed  deleted  a blank  i n c l u d i n g ":",  "<"  comments which a r e  F)  not  within  sequence of  to 1  and  the  a  if  nonblank  nonterminal  2 or  more b l a n k  above  rule  is  applied. G)  there The  acceptable (001) (002) (003) (004)  i s no  following as  input  representation grammar  to  program (001) : start  the  !  (006)  parser  clause(001,002,018,019): open , s e r i e s ( 0 0 3 ) s e r i e s (002,003) : d e c l l i s t (004) decl  an  the  empty  example  symbol. of  the  , stop  .  , close .  , go  on  , unit series(022)  list(003,004,005,005): ;  d e c l l i s t (004) d e c l (004,005,006) : d e c l a r e r (007)  format  generator:  , clause(002)  d e c l (006) (005)  is  of  , comma , d e c l (006)  , iden  l i s t (020)  .  .  •  62  (007) d e c l a r e r ( 0 0 6 , 0 0 7 , 0 0 8 ^ 0 0 9 , 0 0 9 , 0 1 0 , 0 1 0 ) : real  ;  (008)  i n t;  (009)  open  , unit(011)  (010)  proc  , d e c l a r e r (007) .  , close  , declarer(007) ;  (011) u n i t ( 0 0 9 , 0 1 1 , 0 1 2 , 0 1 3 , 0 1 4 , 0 2 2 , 0 2 3 ) : assignation(014) (012)  ;  f o r m u l a (015) ;  (013)  N  primary(017)  .  (014)  assignation(011,014): i d e n , becomes , u n i t (011) . (015) f o r m u l a ( 0 1 2 , 0 1 5 , 0 1 6 , 0 1 6 ) : p r i m a r y (017) (016) (017)  , op , p r i m a r y (017) ;  f o r m u l a (015) , op , p r i m a r y (017) . primary(013,015,015,016,017,018,018,019): iden  ;  (018)  p r i m a r y (017)  (019)  c l a u s e (002) .  (020) i d e n  , c l a u s e (002) ;  list(006,020,021,021): iden ;  (021)  i d e n l i s t (020)  , comma , i d e n .  (022) u n i t  s e r i e s (003,022,023,023): unit(011) ; (023) u n i t s e r i e s (022) , go on , u n i t (011) . Each p r o d u c t i o n i s preceded by a comment consisting production followed that each  number.  The  by a comment  nonterminal nonterminal  production  nonterminal  which c o n t a i n s  within  on t h e l e f t the  t h e grammar.  i s f o l l o w e d by a  number o f t h e f i r s t  the  hand s i d e i s  c r o s s - r e f e r e n c i n g of  On t h e r i g h t  comment  of  which  hand  contains  p r o d u c t i o n with t h a t  side, the  nonterminal  63  on  the l e f t  hand  side.  Once t h e grammar h a s been r e a d alphabetically.  The  terminal  where n i s t h e number  of  symbols  from  are  ordered  i n t h e symbols  are  symbols a r e ordered  terminal n+1  symbols.  The  t o m where m-n  p where p-m  number  Provision  could  of  be made t o a l l o w  o f s p e c i f y i n g h i s own o r d e r i n g he  has a l r e a d y  this  would  translate  2.4  written  save  t o t h e new  from  in  the compiler  writer  a  that  the  m+1  to  grammar. the o p t i o n  symbols, e.g.,  particular  rewriting  from  ordering,  i f  then  code or having  to  ordering.  Output The  output  successful, PL360 [W]. the  If  o f t h e LR(k) p a r s e r  is  three  The f i r s t  symbol  recovery  table  arrays array  and  generator,  o f i n t e g e r s and s h o r t  i s the s t a t e  the  assuming  third  table,  the  i t  was  integers i n second  is  i s a special table f o r error  ( s e e CHAPTER 3 ) . t h e grammar state  i s not LR(k) t h e n t h e p a r s e r  print  the  symbol  s e t computation  that  code u s i n g  him  productions  of the terminal  1 to n  i s t h e number o f  The # s y m b o l s a r e t h e n o r d e r e d  the  from  nonterminal  n o n t e r m i n a l symbols. is  ordered  was  computed  lookahead  algorithm  names  of those  failed  for  each  failed).  will  s t a t e s i n which t h e l o o k a h e a d  and t h e l a s t one  generator  (i.e.,  lookahead  symbol  set  t h e one on which t h e  64  CHAPTER 3  ERROR RECOVERY  In which  section syntax  2.1, we f o u n d two p l a c e s w i t h i n errors  indexed s t a t e  and w i t h i n  One o f t h e f i r s t fairly  were  discovered;  to  attempt  recovery  a t t h e head o f t h e s t r i n g ,  detected  on a s y m b o l an a r b i t r a r y  string  really  3.1  no p r o b l e m a t a l l a s w i l l  o f a l l , l e t us c a l l the  symbol t h a t  adjacent  or read  be  state.  i s that  i t  the  error  was  the  errJor  was  when  seems  down from t h e head o f  I t turns out that  this i s  shown.  may  names would  i n error"  i s wrong).  The s y m b o l  a sequence o f symbols  to  We c o u l d the  t h e symbol  i n error  be  and t h e  symbols  p e r f o r m e d on them.  inserted  (starting  in error  may  before  with  the  t h e symbol  be r e p l a c e d  by  l e a v e t h e symbol s t r e a m a l o n e and make  pushdown s t a c k .  be e q u i v a l e n t  was  (though i t i s n o t n e c e s s a r i l y  have some t r a n s f o r m a t i o n s  be d e l e t e d ,  symbol.  adjustments  t h e symbol on which t h e e r r o r  a s e q u e n c e o f s y m b o l s may  in, e r r o r ,  error)  another  "symbol  t o i t may  example,  symbol in  distance  in  Some I d e a s  detected,  For  a read  b u t what i f  as i n the lookahead s t a t e ?  First  the  parser  a lookahead or lookahead indexed  detected  the  within  p r o b l e m s which comes t o l i g h t  reasonable  the  to i n s e r t i n g  F o r example,  adding s t a t e  p h r a s e s and p o p p i n g  state  65  names would be e q u i v a l e n t is  desirable  difficult.  state  symbol  may a l s o b e  Neither  action  o f s e m a n t i c s becomes v e r y  names t o be popped, b u t we  push names o n t o t h e pushdown s t a c k  nonterminal  actions  phrases.  the c o n t i n u a t i o n  We do a l l o w  adequately the  since  to deleting  transitions  combined  from  together  a s we have removed  t h e DPDA.  to  cannot  form  The above  more  complex  actions.  There the  are  parser  four  basic  implemented)  error  w h i c h may  recovery be  sequence o f 1 t o 5 symbols s t a r t i n g pop  1  to  5  state  names  symbol  b e f o r e t h e symbol  error  with  are  error  was  from  i n error,  symbol w i t h i n delete  the  special  table  Actions  t h e read last  (budlt  a n d d) r e p l a c e  in  by t h e  state.  i s a state  name.  from  the  that  name i s used  This  the state is  lookahead  due  states  the  stack;  not  t h e read  The  name i n which  to  we  the  leading  fact  in  Action  the that  in  which  the  f o r each  a)  cannot  b) r e q u i r e s  in  which  a  each  When a s t a t e name i s popped t o index the t a b l e to  parse there  i n t o the read  want t o r e s t a r t  Action  generator)  i n the t a b l e  obtain  t h e symbol  state  the s t r i n g .  parser  state  a  c) i n s e r t a  c) and d) a r e r e p e a t e d  entry  stack,  delete  c) and d ) , t h e s y m b o l s  f o r that  o r lookahead  symbol  a)  by  w i t h t h e s y m b o l i n e r r o r , b)  For actions  t h e symbol t a b l e  detected.  performed:  (provided  o f f t h e pushdown s t a c k ,  a n o t h e r symbol.  obtained  actions  will may  state  be  be a s e q u e n c e o f  whose  i n the i n i t i a l  restarted.  name  lookahead  i s on state,  state,  upper l i m i t  of 5 placed  on t h e d e l e t e  and  pop  actions  66  are  justified  as  follows:  s y m b o l s which may delete  the  to  the  implementation, of  the  appears, and  the  well.  errors  the  If state  a semantics stack) program  which  has  semantic  parse could  Such  k  action  is  of  a  compiler  possible  of  5  a satisfactory limit 6  would  already  been  properly  take  s y m b o l s and  an  arbitrary  parsed place  or  symbols  be  a b o v e argument a p p l i e s  then  of to  many as  or  associated  popped,  number  possible an  limit  4  the  quite  programmer as  the  on  responsibility  suggest that  (and  are  is  program.  a c t i o n , the  names  limit  e x p e r i e n c e , t o be  d i d not pop  i t  h i s program.  personal  the  the  show  within  experience For  of  i s no  then  secondary  to  from  better.  deleted,  remainder  detrimental  all  be  i f there  any  equally  phrases  on  amount  of  i s thrown away and  on  that  part  no  of  the  program.  We to  5  c u r r e n t l y allow symbols},  another}, delete  with i n the that  1 to  the  b e n e f i t s are  Define immediately  as  place.  disadvantageous to  the  We, do  action  first  the follows  symbol i n e r r o r  10  sets of  symbols},  not  pop  {insert not the  allow pop  a pop  action  10  {delete  symbols  a c t i o n to  i s rather  a l l that  c l e a r and  be  and 1  combined  messy t o  it  by  replace  done, however, but that  1  1 symbol  s y m b o l s and  be  state  we  is  deal feel  rather  names. symbol  sequence of  i f the  10  1 to  I t could  "exposed" the  1 to  actions:  {replace  5 s t a t e names}, { i n s e r t  another}.  another  following  { i n s e r t 1 to  1 t o 5 s y m b o l s } and  s y m b o l by with  {pop  the  action  as  the  symbol  symbols d e l e t e d ,  i s pop,  c)  a) b)  which  which i s  which i s the  symbol  67 I  just  1  inserted  o r d)  which i s t h e  symbol r e p l a c i n g  t h e symbol  in  error. For each e r r o r is  usually  other way  at  least  actions.  The  i s t o attempt  successful actions. the  i t The  error  however.  recovery action  1  one  was  and  recovery first  semantic  not  want t h e s e  semantic  and  input string  To which  recovery  alleviate performs  parser. e.g.,  The  parser  parses the  string  and  actual  result  action  these  and  on  can  be  parser  input string may  other  used  as  problems, (like  parse  our  and  do  We  the  stack  would have  to  r e s t o r e d t o the  state  discovered i n order  that  we  can We  performs  construct a call  a  i t a  performed  upon a  input string.  The  the  parser  "symbolic"  "symbolic"  pushdown s t a c k and  parse,  "symbolic" "symbolic"  "symbolic"  merely  input  copies  pushdown s t a c k , r e s p e c t i v e l y .  measure t h e  how  during the " e v a l u a t i o n "  pushdown s t a c k a r e and  One  properly tested.  actions are  "symbolic"  be  compilers  be  was  problems,  a "symbolic"  "symbolic"  i s t h a t we  then  a r e a number o f most  error  can  two  recovery  string  the  syntax  one.  types of a c t i o n s cause  t h a t they  a l l the  the p a r s e r , observe  the " e v a l u a t i o n " parse.  input  the  There  i s that  there  process f o r a l l the  a c t i o n s t o go  "symbolic"  the e r r o r  the  which  modified s i g n i f i c a n t l y .  were i n when t h e  each e r r o r  to find- out  actions during a syntactic  make c o p i e s o f them such they  attempted,  (most s u c c e s s f u l ) can  the d i f f e r e n t t o be  be  which i s b e t t e r t h a n  restart  repeat  problem  perform  Secondly,  and  action.  own)  parse.,  i s now  action  best action  The  action  problem  one  t h a t may  effectiveness  of  an  of The  action  68  without  performing  input  string  have  the  error  occurs  error  of  a  its  actions.  The  number  After was  first  c)  to  decide  a c t i o n f o r which  wrong, t h a t  measure b e c a u s e read  T h i s i s due  corrected  the  syntactic  the  during  the  came t o  number  a c t i o n modified  the  down  fact  error, the  but  of  the  not  that the  or  seemed  that with  as  was  symbols.  allow  as  this such many  another  "best" action  not  pushdown  a)  action  most  parse  of  symbol.  i t  evaluated  input s t r i n g .  input s t r i n g  one  reductions  understand  did  can  have used  recovery,  "symbolic"  each  we  any  "best" error recovery  i n p a r t to the  further  on  we  parser read  the  error recovery  based  " b e s t " a c t i o n may  current syntactic  error  error  bad  time.  f o r each a c t i o n and/or  symbolic we  be  t h e " b e s t " a c t i o n c a n n o t be  action.  other  the  the  a short p e r i o d of time,  s y m b o l s t o be  the  considering syntactic  first.  that  unless  to other  the  cause  v e r s a , and  meaningless  b)  a weight f a c t o r  comes  may  implementation,  read,  in  symbolically during  a c t i o n may  In t h i s  symbols  natural  a coarse  vice  effectiveness in relation  of  p e r f o r m e d , and  that  errors  also syntax  symbols  i n t e r m s o f compute  is  e v a l u a t i o n o f an  of  will  another  which e v e r  syntax  the a c t u a l  parser  until  limit  have been r e a d ,  action  a number o f v a r i a b l e s .  quite  specified  i s expensive  error recovery  On  only parse  are t h a t other  attempt  modifying  symbolic  a c t i o n s which are attempted  evaluate  the  and  a c t i o n s t o l o o k good and  recovery  An  The  i t will  input string  recovery  number  that  or u n t i l  main r e a s o n s  error  actions  pushdown s t a c k .  property  "symbolic" The  and  semantic  correct However, stack  a the  such  69  that  the  syntactic  disappeared. the  had  intended.  resulting  of  "analyze"  the  phrase  error we  parse.  of  the  based  resemble  input  semantic what t h e  string meaning  programmer  number o f  reductions  but  it  i f any,  more  emphasis  side  e f f e c t of  be  on  the does  the  not  and  have  point  to and  evaluate  an  Thus,  the  "symbolic"  number o f  reductions  evaluation  i s then  symbols  the  read.  We  s t a t e names popped f o r  each  too  evaluation  actions  to  structures.  number o f  appear  syntactic  emphasizing  the The  number o f  The  the  of  syntactic  this  constructed  parse.  added t o  are.  to  these phrase  made  a "symbolic"  consider  be  the  unreasonable  constructed  may  on  is  consider  which i s a v a i l a b l e from  can  during  bennefits,  which  information  measure  reduction,  It  phrase s t r u c t u r e s  use  also  not  action should  program.  performed  could  an  structures  A  the  '  recovery action  should  down  s y n t a c t i c and  program d i d  evaluation  structure  the  further  a d d i t i o n a l l y , the  of  The  error  obvious  what  measure t h e r e b y  structure, which  but  cause  produces  i t has a  the  the  bad  cascade  of  reductions.  We  can  weights are replaced  use a  weights to counter  function  or  a  function  programming  l a n g u a g e , we  the  symbols  i n the  can  assign  their  For  the of  the  bad  symbol  the  attach  language.  weights to  ranking.  of  the  pop  action.  i s merely a  symbols i n the  example, i n an  effects.  inserted,  s y n t a c t i c and  This  side  ALGOL 68  The  deleted In  a  semantic ranking  computer import  to  and  we  language according program,  we  or  may  to have  70  a choice  o f two a c t i o n s : i n s e r t  symbol. safer  From  to i n s e r t  Therefore, tag  of  the  a s k i p symbol  the  skip  language,  than  symbol  will  follows:,  to  weight  the  value  a  skip  we know t h a t i t i s a  have a h i g h e r  tag  weight  symbol. than the  weight  symbol  and i f a s y m b o l  a constant  same  i f a sequence  i s replaced  of  symbols  by a n o t h e r  weight  are  values  then  the  emphasis  flaw  i s  i n t h e above p r o c e d u r e .  placed  on  a  symbol  a s w e l l a s when i t i s b e i n g  deleted.  effect  on  actions  the  syntactically  error  recovery  i n c o r r e c t ALGOL 68 p r o g r a m s ,  error  recovery  great  deal of semantic information  individual weight value remedy  a c t i o n s chosen  e r r o r recovery was b e i n g this,  F1 i s used weight  assigned  F2  This  being  actions  i s used  In  bad some  in  which  a  An a n a l y s i s o f t h e  symbols  deleted  a  i t was f o u n d t h a t t h e  was l o s t .  to the  has  chosen.  deleted.  The f i r s t  or  f o r symbols  too p o s i t i v e a being  two w e i g h t t a b l e s .  f o r symbols  t o replace another  were d e l e t e  I t i s that  when i t i s b e i n g  actions indicated that  we . u s e  table  We  measure f o r t h e pop a c t i o n .  inserted  second  as  i s i n s e r t e d t h e n t h e w e i g h t measure i s  f o r t h a t symbol,  T h e r e i s one major  table  stream  measure i s t h e sum o f t h e w e i g h t s o f t h e two s y m b o l s .  can g i v e  the  i n the input  t h e n t h e w e i g h t measure i s t h e sum o f t h e w e i g h t  of t h e symbols  used  insert  insert  t h e weights t o t h e symbols  i f  deleted  To  or  symbol. We a p p l y  the  knowledge  a t a g symbol  replaced.  being  weight The  i n s e r t e d or  symbol.  In summary* t h e w e i g h t  f a c t o r f o r t h e pop  action  i s -10.  71  All  other  and/or  weight  F2.  implementation delete  action  t o be d e l e t e d . value for  1 1 1 1  syntactic  1 2 3 4  ! 5 1 6 | 7 1 8 1 9 1 10 (11 I 12 1 13 | 14 I 15 J 16 i 17 I 18 1 19 I 20 I 21 I 22 I 23 I 24 J 25 I 26 I 27 L  sums o f v a l u e s  o f f u n c t i o n s F1  and  F2  the  i n figure  used  3.1.  for  The w e i g h t f a c t o r  i i s t h e sum o f t h e v a l u e s o f F1 g i v e n The w e i g h t f a c t o r  f o r an i n s e r t  t h e s y m b o l t o be i n s e r t e d .  I  | | 1  | ] | | 1  | | | | | | | | | I  | | | | | | | | X  action  to obtain import  the best  results  symbol  regarding  factor to  be  i n error. w r i t e r and  the semantic  o f t h e symbols. —  SYMBOL  r  .  Figure  -  F1  I Ti  | | | |  AGAIN AT BECOMES BEGIN BITS DENOTATION BITS BOOL BUS BY BYTES CASE CHAR CLOSE COLON COMMA COMPL COMPLETER DECLARER OPEN DO EITHER ELSE ELSF EMPTY END EQUALS ESAC FALSE ,  fora  i s the  The weight  the  68  t h e symbols  f u n c t i o n s a r e s u p p l i e d by t h e c o m p i l e r  | _ J i  ALGOL  and F2 g i v e n t h e symbol r e p l a c i n g t h e symbol  two w e i g h t  | NOM L r  a r e given  F1  are  a r e p l a c e a c t i o n i s t h e sum o f F1 g i v e n  may be a d u s t e d and  Functions  o f F2 g i v e n  replaced The  factors  j  | | |  J j  | | j  | J j  | | j }  | | | 1  ;  3.1 c o n t i n u e d  on n e x t  _ —  -10 -1 -1 -10 -1 -1 -1 -10 -5 -1 -10 -1 -10 -1 -1 -1 -5 -10 -5 -1 -10 -10 -1 -10 -1 -10 -1  page  | _L T  j I I  | I  I I  i | I  J | | I I I  J | | I  | | I  | 1  | I ._X  F2 -10 0 1 -10 0 0 4 -JO 0 0 -10 0 -10 4 6 0 -5 -10 1 0 -10 -10 0 -10 1 -10 0 J  1  r-  NU>M I 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76  SYMBOL  — | ——— 1 FI  | | | | | | | | | | | | | \ | 1  | | j | | | | j | | j | | | | 1 I J 1 | | | | | | | | | | | | I  F1  ———•  FILE FLEX FOR FORMAT BEGIN FORMAT END FORMAT FROM GO ON GO TO HEAP IF IN INTEGRAL DENOTATION INTEGRAL IS NOT is LETTER A LETTER B LETTER C LETTER D LETTER E LETTER F LETTER 6. LETTER I LETTER K LETTER L LETTER N LETTER P LETTER R LETTER S LETTER T LETTER O LETTER V LETTER X LETTER. Y LETTER Z LOCAL LONG BYTES LONG COMPL LONG LONG BYTES LONG LONG LONG BYTES LONG LONG LONG LONG BYTES LONG REAL DENOTATION LONG REAL MINOS MODE INDICATION MODE NIL F i g u r e 3.1 c o n t i n u e d on n e x t  10 IO  10 10  10 10  -5 -1 page  F2  |  -10 0 0 0 -10 -10 0 0 2 0 0 -10 -10 0 0 0 0 0 0 0 0 0 -10 -10 0 0 0 -10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  ^  -T-  I  NUM | I+77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125  | | | \ | | | | | | | | | | | | } | | | J | | | J | | | \ | | J | | | | J | f | | | | | | | | | |  SYMBOL OF OPEN OPERATION OPERATOR OUSE OUT PAR PER PLUS POINT PRIORITY PRIORITY 1 OPERATOR PRIORITY, 2 OPERATOR PRIORITY 3 OPERATOR PRIORITY 4 OPERATOR PRIORITY 5 OPERATOR PRIORITY, 6 OPERATOR PRIORITY 7 OPERATOR PRIORITY. 8 OPERATOR PRIORITY 9 OPERATOR PROC REAL DENOTATION REAL REF REP REPLICATE ALIGNMENT REPLICATE LITERAL SEMA SEIAL OPEN SHORT BITS DENOTATION SHORT BITS SHORT BYTES SHORT INTEGRAL DENOTATION SHORT INTEGRAL SKIP START STOP STRING DENOTATION STRING STRUCT SUB TAG THELSE THEN TO TRUE UNION VOID WHILE F i g u r e 3.1  J  F1  F2  I |  -1 -10 - 5 -1 -10 -10 -10 -10  0 -10 0 0 -10 -10 -10 -10 0 0 0 -16 -16 -16 -16 -16 -16 -16 -16 -16 0 0 0 0 -10 -10 -10 0 -10 0 0 0 0 0 10 -10 -50 0 0 0 -10 5 -10 -10 0 0 0 0 -10  I  I | I | |  I I I I I  1 I I  I I I j  I  I I I | | | I | I I I I I  I  |  -1  -1 - 5 ~1  1 ~1 -1 ~1 -1 "* 1 -1 -1  -1 _ 1 -1 ~1  -10 -10 -10 -1 -10 -1 -1 -1 -1 -1  -1  | I j J  -10 ^50 -1 -1  I | I | |  - 5 -10 "7 -10 -10  I I I I |  -1 -1  - 5 ~1 -10  |  74  ' 3.2 E r r o r R e c o v e r y The the  Algorithm  error recovery  parser  can p r o v i d e  e r r o r s t h a t may a r i s e which  is  occur.  the The  than  coded  parser;  affect,  i s based  f a r more e f f e c t i v e an ad hoc  for  the  We c o n s t r u c t a p a r s e r  described not  hand  mechanism  on t h e p r i n c i p l e error recovery  error  recovery  "most l i k e l y "  algorithm  constructed  so  make a s y m b o l i c  c o p y o f t h e symbol  Step  2:  make a s y m b o l i c  c o p y o f t h e pushdown s t a c k .  Step  3:  attempt the  an e r r o r r e c o v e r y  symbolic  parse  the  (parse, or u n t i l Step  5:  p a r s e r (or parse.  string symbolic  string  a syntax the  a c t i o n by summing  symbolically  performed  associated  with  symbolic the  the  using  result  symbolic  e x p o s e d symbol inserted evaluation  then  the  of  stack, the symbolic inserted)  stack  symbols  d i d not  t h e number o f s y m b o l s  number and,  that action  parse  modification  e r r o r i s encountered),  read,  then  by  or the symbolic  symbolically  the  action  string.  a t most, up t o (5 • number  evaluate  if  does  i s as f o l l o w s :  1:  4:  will  previously  f a r )during a "symbolic"  Step  Step  mechanism  t h a t t h e new p a r s e r  i n a n y manner, t h e s t a t u s o f t h e o r i g i n a l  semantics  for a l l  e r r o r s that  which i s a c o p y o f t h e  but i t i s so modified  that  of  the  reductions  weight  factor  ( f u n c t i o n s F1 and F 2 ) . I f read  the  exposed  symbol  of the e v a l u a t i o n i s -10; otherwise, parse  after  the  and 5 o r more s y m b o l s have a l r e a d y  been  add  result  read  the  symbol  t h e number o f s y m b o l s r e a d  again.  to the  75  This algorithm i s repeated evaluations action upon is  i s constructed.  (highest numerical the  symbol s t r i n g  that  then  order.  the f i r s t  inserted symbol  deter  infinite  Step  6:  i s  7:  the  a  parsing the  The ALGOL  in  error  the  parse  symbol  actions  given  steps  in  sequence  the  unless  i s simply to  o f one o r more or the  of  in  error  modified  i s read  go t o s t e p  otherwise  remains  1 t o 6 attempting but not s t a c k  replacement  go t o s t e p 7.  the  i n error  symbols,  symbol, then t h e  the  then  symbol resume  8.,  10 s y m b o l s have been i n s e r t e d  then  stop  go t o s t e p 9. symbol i n e r r o r .  deletion,  i n s e r t i o n and  popping.  Obtained  a b o v e a l g o r i t h m was a p p l i e d  68.  grammar  by a n o t h e r  and r e p o r t f a i l u r e ;  replacement,  3.3 R e s u l t s  and pop  The main r e a s o n  parse; otherwise,  symbol  Repeat  the  i s resumed; o t h e r w i s e ,  If  i f more t h a n  9:  deletion  was t h e d e l e t i o n  symbolic  the a c t u a l  Step  effected  The o r d e r o f s e a r c h  o f one o r more s t a t e s ,  parse  perform  8:  is  sequences.  symbol  string.  Step  For  the only choice.  the popping  Step  of  f o r the best  action  once i n t h e same i n s e r t i o n  insertion  actual  table  d e s i r a b l e t o n o t a l l o w t h e same symbol t o  i f the action  of  that  replacement,  and a  i s searched  o r pushdown s t a c k .  one i s c h o s e n .  more t h a n  that  and  action  I f two a c t i o n s have t h e same e v a l u a t i o n r e s u l t  APPENDIX, i t was f o u n d be  The t a b l e  value)  to consider insertion,  in  f o r each  After  some  t o an  experimenting  with  LALR (3)  parser  the weights,  for  i t was  76  found  that  examples  fairly  reasonable error  recovery  was o b t a i n e d .  Some  follow:  There a r e t h r e e  e r r o r s i n the f o l l o w i n g  program:  begin int  b;  read(b);  £roc g =  (proc  void  p)void:  ( { b <= 0 | p |:  b > 5 | b -:= 6 #; i s m i s s i n g * q ( p )  | b •:=  1; g(££oc v o i d  #: i s m i s s i n g *  12)  ) ; 12:  #unit  i s missing*  ) ; 9(££22 v o i d : 1 1 ) ; 11:  skip_  end. Error first insert  recovery error  i s  are given  and r e p l a c e  attempted. in figure  actions  The e v a l u a t i o n 3.2  (column  have a m a t c h i n g  r e s u l t s f o r the  two  entries  for  name i n f i g u r e 3 . 1 ) .  77  | r  | | J \ | | | J | | | | | | j J J | J | | | | | I | | | | | J 1 | | | J 1 | | | J | | | | J | 1 | i  ACTION -  | SYMBOL (S) | -  INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE  READ  I  REDUCED |  1  1 I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I  1 2 3 8 9 13 14 15 17 19 21 22 24 26 28 36 40 43 44 78 81 82 84 88 89 90 91 92 93 94 95 96 101 117 119 120 121 125  I | | | | | I | I | | | | | | | | | | | | | | | | | | | | ) | | | | | J | |  I  1 2 3 8 9 13 14 15 17 19 21  I | | | | | I \ | | |  l  I I I 1 I I I I I i  i  Figure  A.  5 0 5 0 0 1 0 0 2 0 0 0 0 0 0 5 0 5 5 5 0 0 0 5 5 5 5 5 5 5 5 5 0 5 5 0 0 0 5 0 5 0 0 5 0 0 1 0 0  —-J—  J J 1 J 1 J 1 1 1 1  j 1 J 1 J J 1 1 J 1 1 1 1 1  j 1 J j 1 I 1 J 1  ) 1 J 1 J 1 1 J J J 1 1 I 1 1  __ 24 14 19 14 14 22 14 14 16 17 17 17 17 17 17 21 17 19 19 7 14 14 17 19 17 16 15 14 13 12 11 10 17 7 24 17 14 14 31 14 28 14 14 37 14 14 16 17 17  1 _j  3.2 c o n t i n u e d  j | | | | | | | | 1 | J | | | | | | | | I | | | | | | | | | | I J | I | |  j | I | | | | | | | | | |  L  on n e x t  WEIGHT -10 0 1 -10 0 -10 4 6 -5 1 -10 -10 -10 -10 -10 2 -10 0 0 -10 -10 -10 -10 -16 -16 -16 -16 -16 -16 -16 -16 -16 -10 -10 -10 -10 0 -10 -17 -7 -6 -17 -7 -17 -3 -1 -12 -6 -17 .. _ __  page  I - +t —  |  j  ) j  | | | | | j  j  | | j  | j  | j  |  j  | | | | I j  j  | | | | | |  j  j j  | | | j I _  RESULT 19 -10 25 -10 -10 13 -10 -10 13 -10 -10 -10 -10 -10 -10 28 -10 24 24 2 -10 -10 -10 8 6 5 4 3 2 1 0 -1 -10 2 19 -10 -10 -10 19 -10 27 -10 -10 25 -10 -10 5 -10 -10  78  | SYMBOL (S) |  ACTION i  .j | 1 1 | 1 1 1 1 | 1  REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE DELETE DELETE DELETE DELETE DELETE POP POP POP POP POP  I 1 1 1 1 I 1 I I, I I I I I |  22 24 26 28 36 40 43 44 78 81 82 84 88 89 90 91 92 93 94 95 96 101 117 119 120 121 125 1 2 3 4 5  I I I I I  1 2 3 4 5  I  I | I I I  I  i  1  i  READ i  ^ | | | | j | | | | | | { | | | | I J | | | | 1 J | | | I I | | |  :.  0 0 0 0 5 0 5 5 4 0 0 0 5 5 5 5 5 5 5 5 5 0 4 4 0 0 0 5 0 5 5 0 5 0 5 0 5  I | | |  I .  —  J  Figure The (•';") . figure (":"). figure  action  selected  The e v a l u a t i o n 3.3.  The a c t i o n  The e v a l u a t i o n 3.4.  The a c t i o n  J REDUCED |  _-|—— I I I I I 1 1 i 1 | | | I I I | | I 1 1 1  I I I | I I I I 1 1 1 1 1 1 I 1 i—;  17 17 17 17 28 17 27 27 10 14 14 17 36 35 34 33 32 31 30 29 28 17 10 33 17 14 14 24 0 42 45 0 25 0 15 0 15  WEIGHT |  - j —— ! | | l | | | | | | | | | | | | | | | | | | | I | | | | | | | | 1 | | |  I  —  -17 -17 -17 -17 -5 -17 -7 -7 -17 -17 -17 -17 -23 -23 -23 -23 -23 -23 -23 -23 -23 -17 -17 -17 -17 -7 -17 -7 -17 -24 -34 -44 -10 -10 -10 -10 -10  i  .  RESULT  __  | } | | | \ | | | | l | | | | I | | | | | | | J J J | l | | | | | J | | | a.  -10 -10 -10 -10 28 -10 25 25 -3 -10 -10 -10 18 17 16 15 14 13 12 11 10 -10 -3 20 -10 -10 -10 22 -10 23 16 -10 20 -10 10 -10 10  i  3.2  i s i n s e r t 36 o r i n s e r t a go on symbol  r e s u l t s f o r t h e second selected  are given i n  i s i n s e r t 14 o r i n s e r t a  r e s u l t s f o r the t h i r d selected  error  i s insert  error  colon  are given i n  111 o r i n s e r t a  skip  79  symbol | j. | | I | | | J | | | J | | | | | | | j  ("sjcijo").  ACTION  INSERT INSERT INSERT INSERT INSERT INSERT INSERT REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE DELETE DELETE DELETE DELETE DELETE I POP | POP | POP 1 POP I POP  The s y n t a c t i c ^ p a r s e  |SYMBOL(S)1 1 -|— 1 4 | 1 11 I I It 1 1 39 | 1 78 j 1 83 | 1 105 | I 4 | I 11 1 1 14 | 1 39 | 1 78 | I 83 | 1 105 | I 1 I I 2 | I 3 | I 4 | I 5 J | 1 | I 2 | 1 3 | ! 4 | 1 5 J  READ  |  terminated  REDUCED |  - +  2 2 5 2 5 1  8 8 27 8 19 0 23 0 0 1 0 15 0 0 0 0 0  I  1 t 1 1  1  1 1  I I I  1 5 1 1 0 0 0 0 5 5 0 5 5 0  WEIGHT |  h-  1 1 1 ! 1  5  successfully.  ! I I I I I I I  o  14 28 0 28 28 0  | I  1  | | | | | | | | | I | | | | | | | t | | | | | |  -10 -10 4 -10 -10 -10 -10 -17 -17 -3 -17 -17 -17 -17 -7 -17 -27 -28 -35 -10 -10 -10 -10 -10  +-  | | I  | | | | | | | | | | | | | | | | | | | | |  RESULT 0 0 36 • 0 14 -9 18 -16 -16 -1 -16 3 -16 -16 -10 -10 -10 -10 -16 23 -10 23 23 -10  F i g u r e 3.3 —  [  ACTION  L — _ — — — —  | | | | | | | | | | | | | | | | |  INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT  TsYMBOL (S)T j I I 1 1 1 1  | | 1 I  | 1 1 1  | 1 1  4 5 6 7 9 10 11 12 16 18 19 20 23 27 29 30 31 Figure  | | | | | | | | | | | | | | | | | |  READ 1 5 1 1 1 1 1 1 1 2 1 1 5 5 1 1 1  i  —  1 — + j-  | | | | | j  | | | | | | I  |  3.4 c o n t i n u e d  REDUCED T 0 24 2 2 0 2 0 2 2 2 0 0 24 25 2 0 0 on n e x t  WEIGHT T  _j_ 1 1 1 1 1 1 1  |  -10 0 0 4 0 0 -10 0 0 "10 1 0 0 0 0 0  I  o  i  1 1 I I I I I  page  | | | | | | | | | | | I  | | | | | |  RESU -9 29 3 7 1 3 -9 3 3 -6 2 1 29 30 3 1 1  80  1 ACTION r  INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT  ISYjMBOL (  t 1  1  1 1  1 I | | f I  | I  | I  | | I  | | I  | | 1 | | J | | | | | | | | | | | | J | | I  | 1  | | I  | I  32 34 35 37 38 39 41 42 65 66 67 68 69 70 71 72 74 76 78 80 83 88 89 90 91 92 93 94 95 96 97 98 99 100 101 104 105 106 107 108 109 110 111 114 115 116 117 118 121 122  Figure  READ  | REDUCED  5 1 5  0 2 0 0 0 0 24 2 0 2 2 2 2 2 24 2 1 23 8 1 0 1 1 1 1 1 1 1 1 1 0 24 2 0 0 2 0 24 2 2 24 2 23 24 2 0 0 23 0 25  3.4 c o n t i n u e d  on n e x t  |  WEIGHT  A I I I I I I I I I I I I  I I  | t I I 1 1 1 I I I  "10 0 0 0 0 -10 0 0 0 0 0 0 0 0 0 0 0 o - i o  0 -10 -16 -16 -16 "16 - 1 6 "16 -16 "16 -16  I  I 1 I I I I I I 1  1 I I I I I  I \ I I I I I 1 1 1  page  .-| I  | | | | | | | | | ] | | | | | | 1 |  | | | | J  | | | j I  |  o  |  0 0 0 "10 0 "10 0 0 0 0 0 10 0 0 0  | J  | | | | | | | | | | | | |  - i o  |  5 0 0  | | |  —____  -9 3 1 1 1 -9 29 3 1 3 3 3 3 3 29 3 2 28 3 2 -9 -14 -14 -14 -14 -14 -14 -14 -14 -14 1 29 3 1 -9 3 -9 29 3 3 29 3 38 29 3 1 -9 33 1 30  81  j ACTION  |SYMBOL (S) | "  INSERT INSERT INSERT REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE  _|  | | | I  | I I I I I I I  | I  | | | | | I  | I I I  | I 1  | | | I  | | | I  | | I  | | | j  | | 1 | I  | I  1  j.  123 124 125 4 5 6 v  9 10 11 12 16 18 19 20 23 27 29 30 31 32 34 35 37 38 39 41 42 65 66 67 68 69 70 71 72 74 76 78 80 83 88 89 90 91 92 93 94 95 Figure  -|  1 | I I I I I I I I I I  1 I I I I  1 I I I I I l  1 | I I  | I I  |  I I  1 1 | I I  |  I I I I I I I I  HEAD -Lj  1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 5 5 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 5 1 1 5 1. 1 1 1 1 1 1 1 1 1  | REDUCED | _-|  I  | I I  | I I I I I I 1 I I I  | | I I I I I I  1  I  | | i  |  I I  |  I I  | I  | | I j I I I I I I I I  0 2 0 0 7 2 2 0 2 0 2 2 0 0 0 7 8 2 0 0 0 2 0 0 0 0 7 2 0 2 2 2 2 2 7 2 1 6 0 1 0 1 1 1 1 1 1 1 1  3.4 c o n t i n u e d on n e x t  1 I  | I I I I I 1  1 1 1 I I  1 1  1 1 1  1 1 1 1 1 1 1 1 I  1 1 1 1 1 1 1 I  i | I I I  | | | I  | 1 I I I  WEIGHT 0 0 -10 -20 -10 -10 -6 -10 -10 -20 -10 -10 -20 -9 -10 -10 -10 -10 -10 -10 -20 -10 -10 -10 -10 -20 -10 -10 -10 -10 -10 -10 -10 -10 -10 -10 -10 -10 -20 -10 -20 -26 -26 -26 -26 -26 -26 -26 -26  | RESULT | - j — — 1 I 3 I | -9 | -19 | 2 | -7 | -3 | -9 | -7 J -19 j -7 | -7 \ -19 | -8 | -9 | 2 | 3 | -7 | -9 | -9 | -19 | -7 | -9 \ -9 -9 | | -19 | 2 | -7 | -9 \ -7 -7 | | -7 | -7 | -7 | 2 | -7 | -8 | 1 1 -19 1 -8 1 -19 -24 | | -24 -24 | -24 | -24 | -24 | -24 | J -24 t  page  82  |  | SYjMBO'L (S) j  ACTIOS REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE REPLACE DELETE DELETE DELETE DELETE DELETE POP POP POP POP POP . i  L  i, . L  ....  '-  1  96 97 98 99 100 101 104 105 106 107 108 109 110 111 114 115 116 117 118 121 122 123 124 125 1 2 3 4 5 1 2 3 4 5  I  1 1 \ 1  I I I I I I I I  |  I  1 1 1 1 I I I I  I I I I I I I I I I i_  ^  | ] J  | | | I  | | | ) | | 1 | 1 | | 1 | | | | | I  | | | | I  | | | | j  READ 1 1 5 1 1 1 1 1 5 1 1 5 1 5 5 1 1 1 5 1 5 1 1 1 0 5 5 5 5 0 5 0 0 0 Figure  | REDUCED | | I  | | 1 | | J J  | | 1 1 J I  | J I  | I  | | | I  | | I I I  | I I I  3.4  1 0 7 2 0 0 2 0 7 2 2 7 2 6 7 2 0 0 6 0 8 0 2 0 0 6 5 15 27 0 11 0 0 0 .  |  i  WEIGHT -26 -10 -10 -10 -10 -20 -10 -20 -10 -10 -10 -10 -10 0 -10 -10 -10 -20 -5 ' -10 -10 -10 -10 -20 -10 -11 -18 -28 -29 -10 -10 -10 -10 -10 ,_ „ ,..  \  RESULT -24 -9 2 -7 -9 -19 -7 -19 2 -7 -7 2 -7 11 2 -7 -9 -19 6 -9 3 -9 -7 -19 -10 0 -8 -8 3 -10 6 -10 -10 -10  | I  | | | | J  | | | | | J I I  | I J  |  I j  ! | | I I  | | j | | | J  | . •• J.  ______ i -  83  CHAPTER 4  ALGOL 68 IMPLEMENTATION  In given  this  c h a p t e r , we w i l l  d i s c u s s the context free  i n t h e APPENDIX and t h e e f f e c t  parser  t h e grammar and  have had on t h e d e s i g n and s t r u c t u r e  grammar  the  LR (k)  of the compiler,  4.1 The Grammar In time,  1968, t h e ALGOL 68 R e p o r t  v a r i o u s changes to the language  c h a n g e s a r e now  being  Revised  on ALGOL 68.  Report  at  the University  in  touch  which  considered  of British  been  free  Since  have been p r o p o s e d .  for  introduction  Columbia  have e n d e v o u r e d  into  and  officially  the group  to  remain  c h a n g e s and, i n p a r t i c u l a r ,  unofficially  that These  The ALGOL 68 i m p l e m e n t a t i o n  with a l l t h e proposed  have  context free  [ R ] was r e l e a s e d .  those  accepted.  The  grammar g i v e n i n t h e APPENDIX d e s c r i b e s t h e c o n t e x t  structure  o f the proposed  language  f o r t h e ALGOL 68 R e v i s e d  Report. The  CFG i s an LALR (3) grammar.  productions symbols. time of  with  125  terminal  The p a r s e r t a b l e s  128  compute t i m e .  are  inadequate  The l o o k a h e a d  symbols  were g e n e r a t e d  on an IBM S y s t e m s 360/67. which  The grammar c o n s i s t s o f 444 and  153  nonterminal  i n 80 s e c o n d s  compute  The CFSM c o n s i s t s o f 719 s t a t e s , and was g e n e r a t e d  symbol  sets  were  i n 18  computed  seconds in  42  84  seconds  (with  the  l o o k a h e a d s y m b o l s e t s p r i n t e d out)  LALR (k) a l g o r i t h m .  Four inadequate  lookahead, t h i r t y - f o u r rest  only  On in  the  will  one  observation  of the  grammar which a r e  "stop"  be  found  symbols a r e  introduced  into  compiler.  There  "start" "serial  and  not  the  no  ALGOL 68  Report.  In  However, t h e r e a r e  terminal  "declarer  open"  symbol,  and  symbols are  The n symbol the  symbols  "replicate  transformations  i n order  input  these  symbols.  transformation  string  "start"  and  Report.  the l e x i c a l  of  number which can  into  be  of  the  for  14  255  we  the  find  we  find  found  in  "replicate  (productions  character  of the  and  "letter  184  and  120, the  representations  context  an  For  the  of and  "open" literal"  symbol.  open symbol o r a  arbitrary the  of  open"  "replicate n"  a  alignment"  "serial  transformations  a  the  t h e grammar t o make  example,  alignment"  known.  number  are  symbols are " t r a n s f o r m a t i o n s "  For are  analyzer  representations  w e l l as  no  symbols  •], r e s p e c t i v e l y , and  i s a p p l i e d t o an  t h a t the is  The  symbols  grammar LR ( k ) .  other  nor  neither  have been i n t r o d u c e d  them; t h a t i s t o s a y ,  was  Report  ALGOL  production  respectively)  for  DPDA  68  i n production  literal"  the  i n the  by  These symbols as  "replicate  and  are  character  symbol,  The  symbol  notice that there  f- and  to  " s t o p " symbols.  lookahead  lookahead.  Revised  input string  are  open",  we  the  three  the  time.  found  equivalent  open" s y m b o l and  "declarer  CFG,  in  symbol  symbol  i n 3 s e c o n d s compute  they  and  r e q u i r e d two  required  constructed  states required  using  open  distance symbol,  letter down i t  is  85  desireable symbols  t o know, b e f o r e h a n d ,  ". (-a:b)  be a s e r i a l " (a:b)"  o r " ( £ § § 1 x, y " .  n  clause  may  how t o  be  parse  In the f i r s t  i n which " a : " i s a l a b e l followed  by  the  "real",  and "b" (a u n i t )  symbol the  sequence  start  x+y".  declarer; text,  then " r e a l "  "actual" a  go  " o p e n " symbol matching then  i f  i s  (";")  formal  i s followed  i t is  symbol i s c h a n g e d  desirable  symbol  what  distance  follows  dynamic  symbol  "replicate  literal"  1",  p", " l e t t e r  "letter  f o r a routine semantics  for  T h u s , i f we  find  ( " e x i t " ) , then t h e  then  and  i f the  symbol;  unchanged.  the  "letter  n"  t h e dynamic r e p l i c a t o r .  down t h e i n p u t  denotation"  actual  symbol.  t o know whether o r n o t t o a p p l y c e r t a i n  a c t i o n to take,  the  an  t o a " d e c l a r e r open"  follows f o r  r u l e s or t o parse  determine  arbitrary  symbol  by " ) r e a l :  is  The  the  by a row o f mode d e c l a r a t o r ,  t h e "open" symbol r e m a i n s  production to  declarer.  or a completion  The same e x p l a n a t i o n Here  "real"  by  x, y" may be  i s c h a n g e d t o a " s e r i a l open" s y m b o l  "open"  otherwise,  then  declarers are different.  " c l o s e " symbol  the  clause,  lower  x, y" may be  followed  i t i s the parameters plan  a  and " f o r m a l "  on symbol  " (real  the  t e x t where " y " may be f o l l o w e d  serial  whereas,  is  x := 3.1U; r e a d ( y ) " o r " ( r e a l  of a r o u t i n e  If i ti s a  i s t h e u p p e r bound.  c l a u s e where " y " may be  ";  may  i n which c a s e we have an  bound  of a s e r i a l  " (a:b)"  and " b " i s a u n i t o r  row o f mode d e c l a r a t o r where " a " (a u n i t )  start  of  case,  actual  the  sequence  order  we must know t h e c o n t e x t  string,  replicator.  e.g.,  symbol and i f we f i n d  what  I f we f i n d  we change t h e " l e t t e r  x" o r " l e t t e r  In  n"  an  terminal a  symbol  "string to  a  a "letter  k",  "letter  y" s y m b o l t h e n  we  change  86  the  "letter  otherwise,  4.2  The  symbol  the " l e t t e r  to  a  "replicate  n" s y m b o l r e m a i n s  that  we  structure  language sentence  have a f e e l of  became a p p a r e n t  was  the  that  could  information  symbol;  unchanged.  not  must be  indication"  compiler.  We  wish  a  can  "priority  consider  sentence  the l e x i c a l mention  the  here  lexical  operator  in  analysis that  analysis  an " o p e r a t o r i n d i c a t i o n "  of  the  certain such  from  that  a "mode and  after  an  o c c u r r e n c e o f t h e " o p e r a t o r " o r "mode", i t r e q u i r e s  two  of the i n p u t s t r i n g  may  indication".  the  Since  " o p e r a t o r " o r "mode" d e c l a r a t i o n applied  parse of a  to  o b t a i n e d from  we  In t h e p r e v i o u s s e c t i o n , i t  commence u n t i l  distinguish  or  f o r t h e grammar,  the s y n t a c t i c  complete.  t h e p a r s e r can  passes  alignment"  Compiler  Now the  n"  occur before  t o r e c o g n i z e and  or  a d j u s t the  terminal  symbols a c c o r d i n g l y .  With structure compiler  that of  in the  two  t r e e  of [ T ] ) .  The  2)  Parse  and  executed  University  t h r e e passes  1  s e e  five  now  d e s c r i b e and  of  British  justify  the  ALGOL  68  Columbia  compiler c o n s i s t s of f i v e  each  scan  the i n p u t s t r i n g parse  graph  passes  once  and  (called  a  'Program T r e e R e p r e s e n t a t i o n ' i n C h a p t e r  passes are  Ambiguity 5)  The  can  p a s s e s t o u r the r e s u l t a n t  •program  Scan,  we  implementation.  where t h e f i r s t the l a s t  mind,  Scan,  3)  Code G e n e r a t i o n .  to completion  1)  Lexical  Syntactic Each  Analyzer  P a r s e , 4)  pass  1  will  and  2  Corral  Mode Dependent be  called  b e f o r e the next pass i s invoked.  and  87  Pass  1, t h e L e x i c a l A n a l y z e r  initial  a n a l y s i s o f the input  lexical  analyzer  left  to  are  denotations, up  string,  The  then  character  handled  tags  strings  according  or boldface.  than  A denotation  may  string  denotation)  already  there).  The r e s u l t  which  is  accession  an  the  which  member  and p l a c e d of t h i s  they  may  process  are  be  looked  i n t o the  form  i n a table  the  (other  ( i f i t i s not  i s called  a  lexeme  i n t e g e r p a i r c o n s i s t i n g o f t h e r e p r e s e n t a t i o n and  numbers.  which  whether  into internal  from  from  then i t i s e n t e r e d  be c o n v e r t e d  a  resulting  to  The  by c h a r a c t e r ,  A tag or boldface  i n a t a b l e and i f i t i s n o t t h e r e  table.  an ALGOL 68 program.  s c a n s t h e program, c h a r a c t e r  right.  analysis  and C o r r a l S c a n , p e r f o r m s t h e  parser  The  representation  recognizes  of  that  number  and t h e a c c e s s i o n  representation  i s  the  number  number i n d i c a t e s  (i.e.,  which  real  denotation). The input  lexeme i s passed t o t h e C o r r a l Scan  string  priority  ranges  declarations.  halfword  integer  consisting pairs.  for  only  The  of  second  information  of  range  declarations  priority  The f i r s t  the  is  an  operator  i s t h e lexeme  and  accession  auxiliary  the fact  The  mode,  array  operator  under t h e a p p r o p r i a t e that there  f o r that  was  indication  a  stream number  containing  and  boldface.  mode,  and  two a r r a y s o f  a b o u t t h e lexeme s t r e a m , e . g . , t h e  analysis.  declaration  mode,  array  representation  array  are entered  merely e n t e r i n g  recognizes  The C o r r a l Scan c o n s t r u c t s  pairs.  pragmatic the  and  which a n a l y s e s t h e  result priority We a r e  operator  or  and, i n t h e c a s e o f a  88  priority  declaration,  The stream  second one  auxiliary The and  pass,  lexeme  stream  purpose "letter  we  also  the at  a  time  of the Ambiguity  i t assigns i t s p r i o r i t y  occurrence  d e c l a r a t i o n s or  3  will  the  is  the  parse  stream)  and  routines  for  program  is  4  tree  independent  d e p e n d e n t on  occurrence  program  tree  o f mode and  as c o e r c i o n s e q u e n c e s ,  widening,  sequence of output,  etc.  recognize i s dyadic defined  The  numbers  production  the  semantic  tree are c a l l e d  p a r s e , we  with  the  e.g.,  have a program  of the  program.  now  We we  have p e r f o r m e d must  a  parse  the  operators.  The  tags are i d e n t i f i e d  with  3  i s " e g u i v a l e n c e d " [R ].  t h e modes o f t a g s and  to s u i t  to  symbols  input string.  structure  mode t a b l e  o f o p e r a t o r s and  i s modified  program.  Prelude [R].  i s - t h e Mode Dependent P a r s e .  parse  the  the Program T r e e ' i n Chapter  of the s y n t a c t i c  3 terminates, the  applied  such  number  which r e p r e s e n t s t h e s y n t a c t i c a l  syntactic  the  (the, r e p r e s e n t a t i o n a  lexeme uses  programmer  of the  output  (see ' B u i l d i n g  At t h e end  Before Pass  to  c o n s t r u c t i n g t h e program  number  [T]).  Pass  within  and  I f the o p e r a t o r  according  the i n p u t s t r i n g  the  i s t o r e s o l v e "open"  S y n t a c t i c Parse  As each: p r o d u c t i o n  tree  Scan  scans  to r i g h t  ranges  of o p e r a t o r s .  numbers.  of  left  according to the Standard  lexeme  production  Scan,  assigned.  n" s y m b o l s a s d e s c r i b e d p r e v i o u s l y and  then  in  from  t o c o n s t r u c t the  applied  parser  the p r i o r i t y  Ambiguity  the  Pass  note  and  the  the a d d i t i o n a l i n f o r m a t i o n  dereferencing, deproceduring,  89  P a s s 5 i s t h e Code G e n e r a t i o n Here  i t  generating stored passes.  is  a  straight  code a s we  forward  proceed  and  pass tour  of  the  of  using  w i t h i n t h e program t r e e as a r e s u l t  program  the  a l l the  program  tree. tree  information  of the previous  four  90  CONCLUSION  We LB (k)  have d i s c u s s e d  parsing  implemented syntactic LR (k) has  not  a parser  us  mechanism.  technique an  However,  be  i s very  efficient  the e n d - a l l of  someday  and  implementation  of  the  by De Remer [ D ] and we  have  f o r ALGOL 68, p r o v i d i n g  error recovery  grammar.  theory  technique as d e s c r i b e d  parsing  given  the  We  feel  i t with  a powerful  confident  that  the  p o w e r f u l i n o u r a p p l i c a t i o n and  parser  for  a  large  and  complex  i t i s w e l l u n d e r s t o o d t h a t LR(k) p a r s i n g i s a l l parsing  replaced  by  techniques  another  and  that  technique  i t  within  may our  implementation.  The e r r o r r e c o v e r y be  quite  powerful  investigation. and  we  feel  project  programmers  and  that  represents  The f u n c t i o n s  i s developed a  determine  in  relation  that  use i t ) .  optimum to  has shown t o  groundwork  for  F1 and F2 do n o t have t o be  i t would be an i n t e r e s t i n g  to  (possibly  mechanism  the  Artificial  values  for  programming  future fixed  Intelligence  these habits  functions of  the  91  BIBLIOGRAPHY A  Anderson, Parsers.  T., E v e , J . , H o r n i n g , J . J . E f f i c i e n t LR(1) ACTA I n f o r m a t i c a 2, pp. 12-39(1973).  D  DeRemer, F r a n k l i n L . P r a c t i c a l T r a n s l a t o r s f o r LR(k) Languages. Ph.D. Thesis, Massachusetts I n s t i t u t e of T e c h n o l o g y , C a m b r i d g e , M a s s a c h u s e t t s , O c t o b e r , 1969.  H S U  Hopcroft, John E. and U l l m a n , Jeffrey D. Formal Languages and their Relation to Automata. A d d i s o n - W e s l e y , 1969.  K  K n u t h , D.E. On t h e T r a n s l a t i o n o f L a n g u a g e s From L e f t to Right. I n f o r m a t i o n C o n t r o l 8, O c t o b e r , 1965, pp. 607-639.  R  van Wijngaarden, A. ( E d i t o r ) , Mailloux, B.J., Peck, J . E . L . , and K o s t e r , C.H.A. R e p o r t on the Algoithmic Language ALGOL 68. N u m e r i s c h e Mathematik, m, 1969, pp. 79-218.  T  Thomson, J . D. Mode C h e c k i n g i n ALGOL 68. MSc. T h e s i s , U n i v e r s i t y o f B r i t i s h C o l u m b i a , A u g u s t , 1973.  W  Wirth* N. Computers".  PL360, "A Programming Language f o r t h e 360 JACM 15(1968) 37.  92  APPENDIX  see  See s e c t i o n 2.3 f o r a d e s c r i p t i o n o f t h e grammar f o r m a t and c h a p t e r 4 f o r d e t a i l s a b o u t t h e grammar.  (001) program ( 0 0 1 ) : s t a r t symbol, p a r t i c u l a r program(002), s t o p symbol. (002) p a r t i c u l a r label (003)  program(001,002,003): sequence (004),  enclosed  (004) l a b e l  enclosed  clause(007) ;  c l a u s e (007).  s e q u e n c e (002,004,005,005,013,406,407): l a b e l (006) ;  (005)  label  s e q u e n c e (004),  l a b e l (006).  (006) l a b e l (004,005,006,404): tag symbol, c o l o n symbol. (007) e n c l o s e d clause(002,003,007,008,009,010,011,036,120,170, 188,195,214): c l o s e d c l a u s e (012); (008)  collateral  c l a u s e (408) ;  (009)  parallel  (010)  c o n d i t i o n a l c l a u s e (414);  (011)  c a s e c l a u s e (424).  c l a u s e (413);  (012) c l o s e d c l a u s e (007,012,013,014,015): open s y m b o l , u n i t ( 0 1 6 ) , c l o s e s y m b o l ; (013)  open s y m b o l , l a b e l c l o s e symbol;  s e q u e n c e (004) , u n i t (016),  (014)  s e r i a l open s y m b o l , s e r i a l c l o s e symbol;  (015)  begin  symbol, s e r i a l  c l a u s e (355),  clause(355),  end s y m b o l .  (016) u n i t (012,013,016,017,018,019,020,021, 175, 176, 177, 178, 178, 204^204,204,205,205,206,206,207,208,209,209,210,211, 213,263,263,264,265,266,309,349,350,351,353,381,385, 394,401,402,41 1,411,412,419,436): assignation(021); (017)  tertiary(022);  93  (018)  routine  (019)  identity  (020)  l o o p (316).  (021)  (022)  t e x t (309); r e l a t i o n (314) ;  assignation(016,021): t e r t i a r y (022), becomes  symbol, u n i t (016).  tertiary (;017,021,022,023,024,025,026,027,028,029,030,031, 032,314,314,315,315): secondary(033);  (023)  priority  1 f o r m u l a (270) ;  (024)  priority  2 f o r m u l a (289) ;  (025)  priority  3 f o r m u l a (290) ;i  (026)  priority  4  (027)  priority  5 f o r m u l a (292);  (028)  priority  6  formula(293);  (029)  priority  7  formula(294);  (030)  priority  8 f o r m u l a (295) ;•  (031)  priority  9 f o r m u l a (296) ;  (032)  operator indication  formula(291);  (297) , monadic o p e r a n d (307) .  (033) s e c o n d a r y ( 0 2 2 , 0 3 3 , 0 3 4 , 0 3 5 , 0 3 5 , 3 0 8 ) : p r i m a r y (036) ; (034) (035) (036)  g e n e r a t o r (268) ; t a g symbol, of symbol, secondary(033). primary(033,036,037,038,039,040,041,042,043,043,044,044, 045^045,046,046,047): e n c l o s e d c l a u s e (007);  (037)  go t o s y m b o l , t a g s y m b o l ;  (038)  tag symbol;  (039)  s k i p symbol;  (040)  n i l symbol;  (041)  d e n o t a t i o n (048) ;  94  (042)  format  text(059);  (043)  p r i m a r y ( 0 3 6 ) , open s y m b o l , c l o s e symbol;  (044)  p r i m a r y (036) , sub s y m b o l , bus s y m b o l ;  trimscript  (045)  p r i m a r y ( 0 3 6 ) , sub s y m b o l ,  bus symbol;  (046)  p r i m a r y ( 0 3 6 ) , open s y m b o l ,  (047)  c a s t (214).  trimscript  close  l i s t i n g (199), l i s t i n g (199) ,  symbol;  (048) ' d e n o t a t i o n ( 0 4 1 , 0 4 8 , 0 4 9 , 0 5 0 , 0 5 1 , 0 5 2 , 0 5 3 , 0 5 4 , 0 5 5 , 0 5 6 ) : short integral  denotation  (049)  integral  (050)  long  real  (051)  real  denotation  (052)  boolean denotation(057);  (053)  string  (054)  empty  symbol;  (055)  shorft  bits  (056)  bits  (057) (058) (059)  (060) (061)  denotation  symbol;  denotation  symbol;  symbol;  denotation  symbol;  denotation  denotation  symbol;  symbol;  symbol.  boolean denotation(052,057,058): t r u e symbol; f a l s e symbol. f o r m a t t e x t (042,059,060): format b e g i n symbol, c o l l e c t i o n f o r m a t end symbol; format begin symbol, collection  l i s t (061),  f o r m a t end s y m b o l .  list(059,061,062,062,063,063,197):  collection(064); (062)  collection  l i s t ( 0 6 1 ) , comma  (063)  collection  l i s t (061), comma s y m b o l ,  (064)  symbol; c o l l e c t i o n (064).  c o l l e c t i o n ; (061,063,064,065,066,067,068,06 9,070,071,072) : p i c t u r e (073) ;  /  95  (065)  insertion(179) , replication(195) , collation(197), insertion(179);  (066)  i n s e r t i o n (179), r e p l i c a t i o n ( 1 9 5 ) ,  (067)  insertion(179),  (068)  i n s e r t i o n (179) , c o l l a t i o n (197) ;  (069)  r e p l i c a t i o n ( 1 9 5 ) , c o l l a t i o n (197),  (070)  replication(195),  (071)  c o l l a t i o n ( 1 9 7 ) , i n s e r t i o n (179) ;  (072)  collation(197).  (073)  c o l l a t i o n (197) ,  (075)  bits  (076)  r e a l p a t t e r n (128) ;  (077)  boolean  (078)  complex p a t t e r n (153);  (079)  s t r i n g p a t t e r n (156)  (080)  format  p a t t e r n (170) ;  (081)  format  pattern(170),  (082)  loose  general  frame(171);  (083)  loose  general  frame(171),  p a t t e r n (125) ;  pattern(146);  insertion(179);  insertion(179).  i n t e g r a l pattern(073,084,085,086,087): s i g n mould ( 0 8 8 ) , i n t e g r a l mould (098); i n t e g r a l mould (098) ;  (086)  i n t e g r a l choice  p a t t e r n (112),  (087)  i n t e g r a l choice  p a t t e r n (112).  (089)  80,081,082,083):  pattern(084);  i n s e r t i o n (179);  (088)  i n s e r t i o n (179) ;  collation(197);  (074)  (085)  insertion(179);  p i c t u r e (064,073,074,075,076,077,078,079,0 integral  (084)  collation(197) ;  sign  insertion(179) ;  mould (084,088,089,128,138,140,141): loose r e p l i c a t a b l e zero frame(090), sign loose  sign  frame (096).  frame ( 0 9 4 ) ;  96  (090)  loose  r e p l i c a t a b l e zero insertion(179),  (091)  r e p l i c a t a b l e zero  r e p l i c a t a b l e zero  (092) r e p l i c a t a b l e z e r o  letter  frame(092);  frame (092).  f r a m e (090,091,092,093):  replication(195), (093)  f r a m e (088,090,091):  letter  z symbol;  z symbol.  (094) s i g n f r a m e (088,094,095,096,097): plus (095)  symbol;  minus  symbol,  (096) l o o s e (097) (098)  (099)  s i g n frame (089,096,'097) : i n s e r t i o n (179) , s i g n f r a m e (094); s i g n frame(094). i n t e g r a l mould(084,085,098,099,125,131,131,132,133,138, 139, 141, 1 4 3 ) : s i m p l e i n t e g r a l mould ( 1 0 0 ) , i n s e r t i o n (179) ; s i m p l e i n t e g r a l mould (100).  (100) s i m p l e i n t e g r a l mould (098,099,100,101, 101): l o o s e r e p l i c a t a b l e s u p p r e s s i b l e d i g i t frame (102); (101)  s i m p l e i n t e g r a l mould (100), loose r e p l i c a t a b l e suppressible d i g i t  frame (102).  (102) l o o s e  r e p l i c a t a b l e s u p p r e s s i b l e d i g i t f r a m e (100, 101, 102, 103) : insertion(179), r e p l i c a t a b l e s u p p r e s s i b l e d i g i t f r a m e (104);  (103)  r e p l i c a t a b l e s u p p r e s s i b l e d i g i t . f r a m e (104).  (104) r e p l i c a t a b l e s u p p r e s s i b l e d i g i t  frame(102,103,104,105):  r e p l i c a t i o n (195) ,'" s u p p r e s s i b l e (105)  suppressible  (106) s u p p r e s s i b l e d i g i t letter  digit  digit  f r a m e (106).  f r a m e (104,105, 106,107):  s symbol, d i g i t  f r a m e (108);  (107)  digit  (108) d i g i t  f c a n e (106,107,108,109, 110,111): l e t t e r z symbol; l e t t e r u symbol;  (109)  frame (108).  f r a m e (106);  97  (110)  letter v  symbol;  (111)  letter d  symbol.  (112)  i n t e g r a l choice pattern(086,087,112,113): i n s e r t i o n ( 1 7 9 ) , l e t t e r c symbol, open l i t e r a l l i s t (114), c l o s e s y m b o l ;  (113) (114)  l e t t e r c symbol, c l o s e symbol. literal  open s y m b o l ,  symbol,  literal  l i s t (114),  l i s t ( 1 1 2 , 1 1 3 , 1 1 4 , 1 1 5 , 115) :  l i t e r a l (116) ; (115) (116)  (117)  literal  l i s t ( 1 1 4 ) , comma s y m b o l , l i t e r a l (116).  l i t e r a l (114,115,116,117,118,119, 152, 152, 179, 180, 184,186): r e p l i c a t e l i t e r a l (120), s t r i n g d e n o t a t i o n symbol, r e p l i c a t e d l i t e r a l s e q u e n c e (122); replicate literal(120), s t r i n g d e n o t a t i o n symbol;  (118)  s t r i n g d e n o t a t i o n symbol, r e p l i c a t e d l i t e r a l sequence(122);  (119)  string  (120)  replicate  denotation  literal(116,117,120,121,124):  replicate (121)  symbol.  integral  literal  symbol,  denotation  enclosed clause(007);  symbol.  (122)  replicated l i t e r a l sequence(116,118,122,123,123): replicated literal(124); (123) r e p l i c a t e d l i t e r a l s e q u e n c e (122), r e p l i c a t e d l i t e r a l (124). (124)  replicated literal(122,123,124): replicate literal(120), s t r i n g d e n o t a t i o n symbol.  (125)  bits  (126)  (127) (128)  radix  pattern(075,125): r a d i x mould ( 1 2 6 ) , i n t e g r a l mould(125,126,127) : insertion(179), integral l e t t e r r symbol; integral  mould(098).  denotation  d e n o t a t i o n symbol,  letter r  r e a l p a t t e r n (076, 128, 129, 130, 153, 1 5 3 ) :  symbol, symbol.  98  sign  mould(088), r e a l  (129)  real  mould (131);  (130)  floating  (131) r e a l  mould(128,129,131,132,133,140,142): i n t e g r a l mould (098), s u p p r e s s i b l e p o i n t i n t e g r a l mould (098) ;  point  mould ( 1 3 1 ) ;  mould(138).  (132)  integral  mould (098),  suppressible  (133)  loose suppressible point i n t e g r a l mould ( 0 9 8 ) .  point  frame (134), frame(134);  f r a m e (136),  (134) s u p p r e s s i b l e p o i n t f r a m e (131, 132, 134, 135, 136, 137): l e t t e r s symbol, p o i n t symbol; (135)  point  (136) l o o s e  symbol.  suppressible  point  insertion(179), (137)  suppressible  f r a m e (133, 136, 1 3 7 ) :  suppressible  point  point  f r a m e (134);  f r a m e (134).  (138) f l o a t i n g p o i n t mould (130,138, 1 3 9 ) : s t a g n a n t mould (140), s u p p r e s s i b l e e x p o n e n t f r a m e (144), s i g n m o u l d ( 0 8 8 ) , i n t e g r a l mould (098) ; (139) s t a g n a n t mould ( 1 4 0 ) , s u p p r e s s i b l e e x p o n e n t f r a m e (144), i n t e g r a l mould (098). (140) s t a g n a n t  mould (138, 139,140, 141, 142, 1 4 3 ) :  sign  mould ( 0 8 8 ) , r e a l  mould (131);  (141)  sign  mould(088), i n t e g r a l  (142)  real  mould (131) ;  (143)  integral  mould (098) ;  mould ( 0 9 8 ) .  (144) s u p p r e s s i b l e e x p o n e n t f r a m e (138, 139, 144,145): l e t t e r s symbol, l e t t e r e symbol; (145) l e t t e r e symbol. (146) b o o l e a n  (147)  p a t t e r n (077,146,147):  simple  boolean  p a t t e r n (148),  simple  boolean  p a t t e r n (148).  (148) s i m p l e  boolean  i n s e r t i o n (179);  p a t t e r n (146, 147,148, 149, 150, 151) :  99  i n s e r t i o n ( 1 7 9 ) , l e t t e r b symbol, boolean c h o i c e mould(152); 149)  insertion(179), letter  150)  letter  [ 151) 152)  !153)  154)  b symbol, b o o l e a n c h o i c e  letter  b symbol.  c o m p l e x p a t t e r n (078, 153) : r e a l p a t t e r n (128), s u p p r e s s i b l e complex f r a m e ( 1 5 4 ) , r e a l p a t t e r n (128) . s u p p r e s s i b l e complex f r a m e (153,154, 1 5 5 ) : l e t t e r s symbol, l e t t e r i symbol; letter string  i symbol.  p a t t e r n (079,156, 157, 158, 1 5 9 ) :  simple  string  ;157)  simple  string  158)  loose  ;159) 160)  mould ( 1 5 2 ) ;  b o o l e a n c h o i c e mould(148,150,152): open s y m b o l , l i t e r a l ( 1 1 6 ) , comma s y m b o l , l i t e r a l ( 1 1 6 ) , c l o s e symbol.  [155) 156)  b symbol;  string  p a t t e r n (160),  i n s e r t i o n (179) ;  pattern(160); f r a m e (168),  insertion(179);  l o o s e s t r i n g frame (168). simple s t r i n g pattern(156,157,160,160;161): simple s t r i n g pattern(160), loose r e p l i c a t a b l e suppressible character  frame (162);  161: loose 162)  ;163) 164)  [165) 166)  loose  replicatable  suppressible character  frame (162),  r e p l i c a t a b l e s u p p r e s s i b l e c h a r a c t e r frame (160,161, 162, 1 6 3 ) : i n s e r t i o n (179) , r e p l i c a t a b l e s u p p r e s s i b l e c h a r a c t e r frame (164); replicatable  suppressible character  frame (164).  r e p l i c a t a b l e s u p p r e s s i b l e c h a r a c t e r frame (162, 163, 164, 165) : r e p l i c a t i o n ( 1 9 5 ) , s u p p r e s s i b l e character frame(166); suppressible  character  frame (166).  s u p p r e s s i b l e c h a r a c t e r f r a m e (164,165,166, 1 6 7 ) : l e t t e r s symbol, l e t t e r a symbol;  100  (167)  l e t t e r a symbol.  (168) l o o s e  string  f r a m e (158, 159, 168, 169):  i n s e r t i o n (179), (169)  letter  l e t t e r t symbol;  t symbol.  (170) f o r m a t p a t t e r n ( 0 8 0 , 0 8 1 , 170) : l e t t e r f symbol, e n c l o s e d c l a u s e ( 0 0 7 ) . (171) l o o s e g e n e r a l f r a m e (082,083,171,172): i n s e r t i o n ( 1 7 9 ) , g e n e r a l frame (173); (172)  general  f r a m e (173).  (173) g e n e r a l f r a m e ( 1 7 1 , 1 7 2 , 1 7 3 , 1 7 4 ) : l e t t e r g symbol; (174)  l e t t e r g symbol, width s p e c i f i c a t i o n  brief  pack (175).  (175) w i d t h s p e c i f i c a t i o n b r i e f p a c k ( 1 7 4 , 1 7 5 , 1 7 6 ) : open s y m b o l , u n i t ( 0 1 6 ) , c l o s e s y m b o l ; (176)  open s y m b o l , u n i t ( 0 1 6 ) , a f t e r c l o s e symbol.  (177) a f t e r  specification(176,177,178) : comma  (178) (179)  s p e c i f i c a t i o n (177),  symbol, u n i t (016);  comma s y m b o l , u n i t ( 0 1 6 ) , comma s y m b o l ,  unit(016).  insertion(065,065,066,067,067,068,069,071,074,081,083, 086,090,096,098, 102,:112, 126, 136, 146, 148, 149, 156, 158, 162,168,171,179,180,181): l i t e r a l (116), i n s e r t s e q u e n c e ( 1 8 2 ) ;  (180)  literal(116);  (181)  i n s e r t sequence(182).  (182) i n s e r t s e q u e n c e ( 1 7 9 , 1 8 1 , 1 8 2 , 1 8 3 , 1 8 3 ) : i n s e r t (184) ; (183) i n s e r t s e q u e n c e (182) , i n s e r t (184). (184) i n s e r t (182, 183 , 184, 185, 186<, 187) : r e p l i c a t e alignment(188), alignment(190), l i t e r a l (116) ; (185)  replicate  a l i g n m e n t (188), alignment(190) ;  (186)  alignment(190),  l i t e r a l (116);  101  {187) (188)  a l i g n m e n t (190) . replicate  a l i g n m e n t (184,185,188, 1 8 9 ) :  replicate (189) (190)  integral  alignment  symbol,  denotation  symbol.  enclosed  c l a u s e (007);  a l i g n m e n t (184,185,186,187, 190,191, 192, 193, 194) : letter  k symbol;  (191)  letter  x symbol;  (192)  letter  y symbol;  (193)  letter  1 symbol;  (194)  letter  p symbol.  (195)  replication(065,066,069,070,092,104,164,195,196) : l e t t e r n s y m b o l , e n c l o s e d c l a u s e (007); (196) i n t e g r a l d e n o t a t i o n symbol. (197) c o l l a t i o n (065, 066,067, 068, 069, 070, 071,072, 197,i198) : open s y m b o l , c o l l e c t i o n l i s t ( 0 6 1 ) , c l o s e symbol; (198) (199)  open symbol,  close  symbol.  t r i m s c r i p t listing(043,044,199,200,200,201,201,202,203) : trimscript(204);  (200)  trimscript  listing(199),  comma  symbol;  (201)  trimscript listing(199), trimscript(204);  comma  symbol,  (202)  comma  (203)  comma s y m b o l ,  (204)  symbol; trimscript(204).  trimscript(199,201,203,204,205,206,207,208,209,210,211, 212,213) : u n i t ( 0 1 6 ) , c o l o n s y m b o l , u n i t ( 0 1 6 ) , a t symbol, u n i t (016) ;  (205)  u n i t (016), c o l o n  symbol,  u n i t (016);  (206)  u n i t (016), c o l o n  symbol,  a t symbol,  (207)  unit(016),  symbol;  (208)  u n i t (016) ;  colon  unit(016);  102  (209)  colon  symbol,  unit(016),  (210)  colon  symbol,  u n i t (016) ;?  (211)  colon  symbol,  a t symbol,  (212)  colon  symbol;  (213)  a t symbol,  (214) (215)  a t symbol,  unit(016);  unit(016).  cast(047,214) : d e c l a r e r (215), e n c l o s e d  c l a u s e (007).  declarer(214,215,215,216,217,218,219,220,221,221,222,223, 225,226,248,249,268,269,310, 311,312, 313,370,371, 372, 373^375,437,438): r e f e r e n c e t o symbol, d e c l a r e r ( 2 1 5 ) ;  (216)  p r o c e d u r e symbol;  (217)  union close  (218)  primitive declarator(227);  (219)  mode i n d i c a t i o n  (220)  s t r u c t u r e symbol, c l o s e symbol;  (221)  f l o w e r (252),  (222) (223) (224)  (225) (226) (227)  unit{016);  o f symbol, symbol;  procedure p l a n (222); open  symbol,  d e c l a r e r l i s t (225),  symbol; open  symbol,  field  list(248),  declarer(215).  p r o c e d u r e plan(216,222,223,365) : d e c l a r e r l i s t pack ( 2 2 4 ) , d e c l a r e r ( 2 1 5 ) ; d e c l a r e r (215) . d e c l a r e r l i s t pack ( 2 2 2 , 2 2 4 ) : d e c l a r e r open s y m b o l , d e c l a r e r c l o s e symbol.  list(225),  declarer list(217,224,225,226,226): declarer(215); declarer list(225),  comma s y m b o l ,  d e c l a r e r (215).  p r i m i t i v e d e c l a r a t o r ( 2 1 8 , 2 2 7 , 2 2 8 , 2 2 9 , 2 3 0 , 231,232,233, 234, 235;236,237,238,239/240/241,242,243,244,245,246,247): v o i d symbol;  (228)  short  integral  (229)  integral  symbol;  symbol;  (230)  real  symbol;  (231)  long  real  (232)  short  (233)  b y t e s symbol;  (234)  long  b y t e s symbol;  (235)  long  long  b y t e s symbol;  (236)  long  long  long  b y t e s symbol;  (237)  long  long  long  long  (238)  bits  symbol;  (239)  short  bits  (240)  compl  symbol;  (241)  long  (242)  string  (243)  sema  symbol;  (244)  file  symbol;  (245)  boolean symbol;  (246)  character  (247)  format  (248) (249) (250)  field  symbol;"  b y t e s symbol;  b y t e s symbol;  symbol;  compl  symbol;  symbol;  symbol;:  symbol.  list(220,248,249,249) : d e c l a r e r (215) , t a g l i s t ( 2 5 0 ) ; field list(248), tag list(250).  comma symbol,  declarer(215),  t a g l i s t (;248,249, 250, 251 ,251,312, 313) : tag  symbol;  (251)  tag list(250),  (252)  flower(221,252,253,254): flexible  comma s y m b o l ,  symbol,  (253)  either  symbol,  (254)  r o w e r (255).  rower (255);  rower ( 2 5 5 ) ;  t a g symbol.  104  (255)  rower(252,253,254,255,256,257,258): d e c l a r e r open s y m b o l , p a i r l i s t ( 2 5 9 ) , c l o s e symbol;  (256)  declarer  (257)  sub s y m b o l ,  pair  (258)  sub s y m b o l ,  bus symbol.  (259)  pair  open  symbol,  l i s t ( 2 5 9 ) , bus s y m b o l ;  symbol;  (260)  pair  l i s t ( 2 5 9 ) , comma  (261)  pair  list(259),  (262)  p a i r (263).  symbol;  comma s y m b o l ,  symbol,  (264)  unit(016),  symbol;  (265)  u n i t (016);  (266)  c o l o n symbol,  (267)  colon  (270) (271)  (272) (273)  (274) (275) (276)  colon  unit(016);  u n i t (016);  symbol.  generator(034,268,269): local  (269)  p a i r (263) ;  p a i r (261,262,263,264,265,266,267): unife(016), c o l o n  (268)  symbol;  list(255,257,259;260,260,261,261,262): comma  (263)  close  symbol,  heap s y m b o l ,  d e c l a r e r (215); d e c l a r e r (215) .  p r i o r i t y 1 formula(023,270,271): p r i o r i t y 1 operand(271), p r i o r i t y 1 o p e r a t o r symbol, p r i o r i t y p r i o r i t y 1 o p e r a n d (270,271,272): priority  1 formula(270);  priority  2 operand (273).  priority  2  operand(270,272,273,274,289):  priority  2 formula(289);  priority  3 operand(275) .  p r i o r i t y 3 operand(274,275,276,289,290) : p r i o r i t y 3 f o r m u l a (290) ;! p r i o r i t y 4 operand(277).  2 operand(273).  105  (277)  (278) (279)  (280) (281)  (282) (283)  (284) (285)  (286) (287)  priority  4 o p e r a n d ( 2 7 6 , 2 7 7 , 2 7 8 , 2 9 0 , 291) :  priority  4 f o r m u l a (291) ;  priority  5 operand(279).  priority  5  priority  5 f o r m u l a (292) ;  priority  6 o p e r a n d (281) .  priority  6 operand(280,281,282,292, 293):  priority  6 f o r m u l a (293);  priority  7 operand(283).  priority  7  (289)  (290) (291) (292) (293) (294)  operand(282,283,284,293,294):  priority  7 formula(294);  priority  8 operand(285) .  priority  8  operand(284,285,286,294,295):  priority  8 formula(295);  priority  9 operand(287).  priority  9  priority (288)  operand(278,279,280,291,292):  monadic  operand(286,287,288,295,296): 9 f o r m u l a (296); operand(307).  p r i o r i t y 2 formula(024,273,289): p r i o r i t y 2 operand(273), p r i o r i t y 2 o p e r a t o r symbol, p r i o r i t y 3 formula(025,275,290): p r i o r i t y 3 operand(275), p r i o r i t y 3 o p e r a t o r symbol, p r i o r i t y 4 formula(026,277,291): p r i o r i t y 4 operand(277), p r i o r i t y 4 o p e r a t o r symbol, p r i o r i t y 5 formula(027,279,292): p r i o r i t y 5 operand(279), p r i o r i t y 5 o p e r a t o r symbol, p r i o r i t y 6 formula(028,281,293): p r i o r i t y 6 operand(281), p r i o r i t y 6 o p e r a t o r symbol, p r i o r i t y 7 formula(029,283,294): p r i o r i t y 7 operand(283), p r i o r i t y 7 o p e r a t o r symbol,  priority  3  operand(275)  priority  4  operand(277)  priority  5  operand(279)  priority  6 o p e r a n d (281)  priority  7 o p e r a n d (283)  priority  8 o p e r a n d (285)  106  (295)  p r i o r i t y 8 formula(030,285,295): p r i o r i t y 8 operana(285), p r i o r i t y 8 o p e r a t o r symbol, p r i o r i t y  9 operand(287),  (296)  p r i o r i t y 9 formula(031,287,296): p r i o r i t y 9 operand (287), p r i o r i t y 9 o p e r a t o r s y m b o l , monadic o p e r a n d (307) .  (297)  o p e r a t o r i n d i c a t i o n (032,297,298,299,300,301,302,303,304, 305,306,307,394,397,400): o p e r a t o r symbol;  (298)  priority  1 operator  symbol;  (299)  priority  2 operator  symbol;  (300)  priority  3 operator  symbol;  (301)  priority  4 operator  symbol;  (302)  priority  5 operator  symbol;  (303)  priority  6 operator  symbol;  (304)  priority  7 operator  symbol;  (305)  priority  8 operator  symbol;  (306)  priority  9 operator  symbol.  (307)  monadic o p e r a n d (032,288,296,307,307,308): o p e r a t o r i n d i c a t i o n ( 2 9 7 ) , monadic o p e r a n d ( 3 0 7 ) ;  (308) (309) (310)  (311) (312) (313) (314) (315)  s e c o n d a r y (033) . r o u t i n e text(018,309,388,391,397): p a r a m e t e r s p l a n ( 3 1 0 ) , c o l o n symbol, u n i t ( 0 1 6 ) . parameters plan(309,310,311): d e c l a r e r open s y m b o l , p a r a m e t e r s l i s t ( 3 1 2 ) , c l o s e symbol, d e c l a r e r (215); d e c l a r e r (215) . parameters list(310,312,313,313): d e c l a r e r (215) , t a g l i s t ( 2 5 0 ) ; parameters l i s t ( 3 1 2 ) , tag list(250).  comma s y m b o l ,  declarer(215),  identity relation(019,314,315): t e r t i a r y ( 0 2 2 ) , i s symbol, t e r t i a r y (022); tertiary(022),  i s not symbol,  t e r t i a r y (022).  107  (316)  l o o p (020,316,317,318,319,320,321, 322,323, 324, 325,326,327, 328,329,330,331,332/333,334,335,336,337,338,339,340, 341,342,343,344,345,346,347): f o r p a r t ( 3 4 8 ) , f r o m p a r t (349), by p a r t ( 3 5 0 ) , t o p a r t ( 3 5 1 ) , w h i l e p a r t (352), do c l a u s e ( 3 5 3 ) ;  (317)  f o r p a r t (348), f r o m p a r t (349), t o p a r t (351), do c l a u s e (353) ;  by p a r t ( 3 5 0 ) ,  (318)  f o r p a r t (348), f r o m p a r t (349), by p a r t ( 3 5 0 ) , w h i l e p a r t ( 3 5 2 ) , do c l a u s e (353) ;  (319)  f o r p a r t (348), from do c l a u s e (353);  (320)  f o r p a r t ( 3 4 8 ) , f r o m p a r t (349), t o p a r t ( 3 5 1 ) , w h i l e p a r t (352), do c l a u s e ( 3 5 3 ) ;  (321)  f o r p a r t (348) , from do c l a u s e (353) ;  p a r t (349) , t o p a r t ( 3 5 1 ) ,  (322)  f o r p a r t (348), from do c l a u s e ( 3 5 3 ) ;  p a r t (349),  while  (323)  f o r p a r t (348), from  p a r t (349),  do c l a u s e (353) ;  (324)  f o r p a r t (348), by p a r t (350), t o p a r t (351), w h i l e p a r t ( 3 5 2 ) , do c l a u s e (353);  (325)  f o r p a r t (348), by p a r t (350), do c l a u s e (353) ;  (326)  f o r p a r t ( 3 4 8 ) , by p a r t ( 3 5 0 ) , w h i l e do c l a u s e (353) ;  (327)  f o r p a r t (348),  (328)  f o r part(348), to part(351), while do c l a u s e (353) ;  (329)  f o r p a r t ( 3 4 8 ) , t o p a r t (351),  (330)  f o r p a r t (348),  (331)  f o r p a r t ( 3 4 8 ) , do c l a u s e (353) ;  (332)  from p a r t (349), by p a r t (350), t o p a r t (351), w h i l e p a r t ( 3 5 2 ) , do c l a u s e (353) ;  (333)  f r o m p a r t ( 3 4 9 ) , by p a r t (350), do c l a u s e ( 3 5 3 ) ;  (334)  from  p a r t (349),  by p a r t ( 3 5 0 ) ,  by p a r t (350),  part(352),  t o p a r t (351), part(352),  do c l a u s e ( 3 5 3 ) ; part(352),  do c l a u s e ( 3 5 3 ) ;  w h i l e p a r t (352) , do c l a u s e (353);  t o p a r t (351),  p a r t ( 3 4 9 ) , by p a r t (350) , w h i l e  p a r t (352),  108  do c l a u s e ( 3 5 3 ) ; (335)  from  p a r t ( 3 4 9 ) , by p a r t (350) , do c l a u s e (353) ;!  (336)  f r o m p a r t (349), t o p a r t (351), do c l a u s e (353) ;  while  (337)  from  do c l a u s e (353) ;i  (338)  from, p a r t (349) , w h i l e  (339)  from  (340)  by p a r t ( 3 5 0 ) , t o p a r t ( 3 5 1 ) , do c l a u s e ( 3 5 3 ) ;  while  (341)  by p a r t ( 3 5 0 ) ,  to p a r t (351),  do c l a u s e ( 3 5 3 ) ;  (342)  by p a r t ( 3 5 0 ) ,  while  (343)  by p a r t (350),  do c l a u s e (353);  (344)  t o p a r t (351),  w h i l e p a r t (352),  (345)  t o p a r t ( 3 5 1 ) , do c l a u s e (353) ;  (346)  while  (347)  do c l a u s e (353) .  p a r t (349),  t o p a r t (351),  p a r t (352),  p a r t (352),  do c l a u s e ( 3 5 3 ) ;  p a r t (349) , do c l a u s e (353);  p a r t (352),  p a r t (352),  p a r t (352),  do c l a u s e (353);  do c l a u s e ( 3 5 3 ) ;  do c l a u s e (353);  (348)  f o r p a r t (316,317,318,319,320,321, 322,323,324,325,326,327, 328,329,330,331,348): f o r symbol, t a g symbol.  (349)  from  (350)  by p a r t (316,317,318,319,324,325,326,327,3 340,341,342,343,350): by s y m b o l , u n i t ( 0 1 6 ) .  (351)  t o p a r t ( 3 1 6 , 3 1 7 , 3 2 0 , 3 2 1 , 3 2 4 , 3 2 5 , 3 2 8 , 3 2 9 , 3 3 2 , 333, 336,337, 340,341,344,345*351): t o s y m b o l , u n i t (016).  (352)  w h i l e p a r * (316,318,320,322,324,326,328,330,332,334,336, 338,340,342*344,346,352): w h i l e symbol, s e r i a l c l a u s e (355).  (353)  do c l a u s e ( 3 1 6 , 3 1 7 , 3 1 8 , 3 1 9 , 3 2 0 , 3 2 1 , 3 2 2 , 3 2 3 , 3 2 4 , 3 2 5 , 3 2 6 , 327,328,329,330,331,332,333,334,335,336,337,33 8,339, 340,341,342,343,344,345,346,347,353,354): do s y m b o l , u n i t ( 0 1 6 ) ;  p a r t ( 3 1 6 , 3 1 7 , 3 1 8 , 3 1 9 , 3 2 0 , 3 2 1 , 3 2 2 , 323,332,333,334, 335,336,337,338,339,349): from s y m b o l , u n i t (016). 32,333,334,335,  109  rep  symbol,  serial  c l a u s e (355), p e r s y m b o l .  serial clause(014,015,352,354,355,356,414,416,416,417, 417,418,420,421,421,422,422,423,424,425,428,429,431, 432^439,440,442,443): d e c l a r a t i o n p r o l o g u e ( 3 5 7 ) , go on s y m b o l , parade(403); parade (403). d e c l a r a t i o n p r o l o g u e (355,357,358,358): s e r i e s with def (359); d e c l a r a t i o n p r o l o g u e ( 3 5 7 ) , go on s y m b o l , s e r i e s w i t h d e f (359) . s e r i e s with def(357,358,359,360): s i n g l e d e c l a r a t i o n l i s t (361); u n i t s e r i e s ( 4 0 1 ) , go on s y m b o l , s i n g l e d e c l a r a t i o n l i s t (361). s i n g l e d e c l a r a t i o n list(359,360,361,362,362) : s i n g l e d e c l a r a t i o n (363) ;? s i n g l e . d e c l a r a t i o n l i s t ( 3 6 1 ) , comma single declaration(363).  symbol,  s i n g l e declaration(361,362,363,364,365,366,367): mode s y m b o l , mode a s s o c i a t i o n l i s t ( 3 6 8 ) ; identifier  d e c l a r a t i o n (371);  operation operation  symbol, p r o c e d u r e p l a n (222), association list(392);  operation  symbol,  priority  symbol,  operation priority  associated  association  l i s t (395); list(398).  mode a s s o c i a t i o n l i s t (363,368,369,369): mode a s s o c i a t i o n (370) ; mode a s s o c i a t i o n l i s t ( 3 6 8 ) , comma mode a s s o c i a t i o n ( 3 7 0 ) .  symbol,  mode a s s o c i a t i o n (368,369,370): mode i n d i c a t i o n s y m b o l , e q u a l s s y m b o l , d e c l a r e r (215). identifier declaration(364,371,372,373,374,375,376,377, 378);: declarer(215), identity association list(379);  110  (372)  d e c l a r e r (215) , t a g a t i c m  (373)  heap s y m b o l ,  d e c l a r e r (215), t a g a t i o n  (374)  heap s y m b o l ,  p r o c e d u r e symbol,  (375)  local  symbol,  declarer(215),  (376)  local  symbol,  p r o c e d u r e symbol,  (377)  p r o c e d u r e symbol,  identity  (378)  p r o c e d u r e symbol,  tag i n i t  (379)  (380)  list(382); list(382);  tag i n i t  tagation  l i s t (386); list(382);  tag init  init  list(386);  list(389);  list(386).  i d e n t i t y a s s o c i a t i o n l i s t (371,379,380,380): identity association(381); identity identity  association list(379), a s s o c i a t i o n (381).  comma  (381)  identity tag  a s s o c i a t i o n (379,380,381): symbol, e q u a l s symbol, u n i t (016).  (382)  tagation  list(372,373,375,382,383,383):  symbol;  t a g a t i o n (384); (383) (384)  tagation  (386) (387) (388) (389) (390) (391) (392)  comma s y m b o l ,  t a g a t i o n (384).  tagation(382,383,384,385): tag  (385)  list(382),  symbol;  t a g symbol,  becomes s y m b o l ,  u n i t (016).  t a g i n i t l i s t (374,376,378,386,387,387) : tag init(388); t a g i n i t l i s t ( 3 8 6 ) , comma symbol, t a g i n i t ( 3 8 8 ) . t a g i n i t (;386,387,388) J t a g s y m b o l , becomes symbol, r o u t i n e t e x t ( 3 0 9 ) . identity init identity identity identity  list(377,389,390,390) : init(391); N  init list(389), init(391).  comma  identity init(389,390*391): tag symbol, e q u a l s symbol,  symbol,  routine  text(309).  operation a s s o c i a t i o n list(365,392,393,393) : operation association(394);  111  (393) (394)  (395)  o p e r a t i o n a s s o c i a t i o n l i s t (392) , comma o p e r a t i o n a s s o c i a t i o n (394).  o p e r a t i o n a s s o c i a t i o n (392,393,394): o p e r a t o r i n d i c a t i o n (297), e q u a l s symbol,  (398)  o p e r a t i o n a s s o c i a t e d l i s t (395), comma o p e r a t i o n a s s o c i a t e d (397). operation associated(395,396,397): o p e r a t o r i n d i c a t i o n (297), e q u a l s r o u t i n e t e x t (309).  (401)  symbol,  symbol,  p r i o r i t y a s s o c i a t i o n l i s t (367,398,399,399): priority association(400);  (399) (400)  u n i t (016).  o p e r a t i o n a s s o c i a t e d l i s t (366,395,396,396): o p e r a t i o n a s s o c i a t e d (397);  (396) (397)  symbol,  priority priority  a s s o c i a t i o n l i s t (398), comma a s s o c i a t i o n (400).  p r i o r i t y a s s o c i a t i o n (398,399,400): o p e r a t o r i n d i c a t i o n (297), e q u a l s i n t e g r a l d e n o t a t i o n symbol. unit  symbol,  symbol,  series(360,401,402,402,405,406,407) : u n i t ^016) ;  (402) (403) (404) (405)  unit  s e r i e s ( 4 0 1 ) , go on s y m b o l ,  parade(355,356,403,404,404): t r a i n (405); p a r a d e (403), c o m p l e t i o n s y m b o l , t r a i n (405) .  u n i t (016).  l a b e l (006),  train(403,404,405,406,407,407): unit series(401);  (406)  label  (407)  t r a i n (405), go on s y m b o l , l a b e l s e q u e n c e ( 0 0 4 ) , unit series(401).  (408)  s e q u e n c e (004) ? u n i t  s e r i e s (401);  c o l l a t e r a l c l a u s e (008,408,409,410,413): open s y m b o l , c l o s e s y m b o l ;  (409)  open s y m b o l , u n i t c l o s e symbol;  (410)  b e g i n symbol, end s y m b o l .  unit  list list  p r o p e r (411), p r o p e r (411),  112  (411)  unit  l i s t proper(409,410,411,412,412,428,429,430,4 39,440, 441) : unit(016), unit  list  comma s y m b o l , proper (411),  unit(016);  comma s y m b o l ,  unit(016).  parallel clause(009,413): p a r a l l e l s y m b o l , c o l l a t e r a l c l a u s e (408). c o n d i t i o n a l c l a u s e (010,414,415): i f s y m b o l , s e r i a l c l a u s e (355), i f c h o i c e (416), f i symbol; open s e r i a l ( 4 1 9 ) , c l o s e symbol. if  open s e r i a l  c h o i c e (421),  choice(414,416,417,417,418): then symbol, s e r i a l c l a u s e ( 3 5 5 ) , s e r i a l c l a u s e (355);  else  symbol,  then symbol, s e r i a l s e r i a l c l a u s e (355),  c l a u s e (355), e l s f i f c h o i c e (416);  symbol,  then  clause(355).  symbol,  serial  open s e r i a l ( 4 1 5 , 4 1 9 , 4 2 0 , 4 2 6 , 4 2 7 ) : open s y m b o l , u n i t (016); serial  open s y m b o l ,  serial  c l a u s e (355).  open s e r i a l c h o i c e ( 4 1 5 , 4 2 1 , 4 2 2 , 4 2 2 , 4 2 3 ) : t h e l s e symbol, s e r i a l c l a u s e ( 3 5 5 ) , t h e l s e symbol, s e r i a l c l a u s e ( 3 5 5 ) ; t h e l s e s y m b o l , s e r i a l c l a u s e (355), a g a i n s y m b o l , s e r i a l c l a u s e (355), open s e r i a l c h o i c e ( 4 2 1 ) ; t h e l s e symbol, case  c l a u s e (355).  clause(011,424,425,426,427): c a s e s y m b o l , s e r i a l c l a u s e (355), esac symbol; case esac  case  serial  symbol, s e r i a l symbol;  c l a u s e (355),  case  1 c h o i c e (428),  case  2 c h o i c e (431),  open s e r i a l ( 4 1 9 ) , c l o s e symbol;  open c o l l a t e r a l  1 c h o i c e (439),  open s e r i a l ( 4 1 9 ) , c l o s e symbol.  open c o l l a t e r a l  2 c h o i c e (442),  1 choice(424,428,429,429,430):  113  i n symbol, u n i t l i s t s e r i a l c l a u s e (355) ;  p r o p e r (411), o u t  symbol,  (429)  i n s y m b o l , u n i t l i s t p r o p e r (411), ouse s y m b o l , s e r i a l c l a u s e (355), c a s e 1 c h o i c e ( 4 2 8 ) ;  (430)  i n symbol,  (431) c a s e  2 choice(425,431,432,432,433): i n symbol, a l t e r n a t i v e l i s t ( 4 3 4 ) , s e r i a l c l a u s e (355);  unit  list  proper(411).  out  symbol,  (432)  i n s y m b o l , a l t e r n a t i v e l i s t ( 4 3 4 ) , ouse symbol, s e r i a l c l a u s e (355) , c a s e 2 c h o i c e ( 4 3 1 ) ;  (433)  i n symbol, a l t e r n a t i v e  (434) (435)  l i s t (434).  alternative list(431,432,433,434,435,435,442,443,444): alternative(436); a l t e r n a t i v e l i s t (434), comma a l t e r n a t i v e (436).  symbol,  (436)  alternative(434,435,436): shape (437), u n i t ( 0 1 6 ) .  (437)  s h a p e (436,437,438) : open s y m b o l , d e c l a r e r ( 2 1 5 ) , t a g s y m b o l , c l o s e symbol, c o l o n symbol;  (438) (439)  open s y m b o l , d e c l a r e r ( 2 1 5 ) , c l o s e c o l o n symbol.  symbol,  open c o l l a t e r a l 1 c h o i c e ( 4 2 6 , 4 3 9 , 4 4 0 , 4 4 0 , 4 4 1 ) : t h e l s e s y m b o l , u n i t l i s t p r o p e r (411), t h e l s e s y m b o l , s e r i a l c l a u s e (355);  (440)  t h e l s e s y m b o l , u n i t l i s t p r o p e r (411), a g a i n s y m b o l , s e r i a l c l a u s e (355), open c o l l a t e r a l 1 c h o i c e (439);  (441)  thelse  (442)  symbol,  unit  list  p r o p e r (411).  open c o l l a t e r a l 2 c h o i c e ( 4 2 7 , 4 4 2 , 4 4 3 , 4 4 3 , 4 4 4 ) : t h e l s e symbol, a l t e r n a t i v e l i s t ( 4 3 4 ) , t h e l s e symbol, s e r i a l c l a u s e (355);  (443)  t h e l s e s y m b o l , a l t e r n a t i v e l i s t (434), a g a i n s y m b o l , s e r i a l c l a u s e (355), open c o l l a t e r a l 2 c h o i c e ( 4 4 2 ) ;  (444)  thelse  symbol,  alternative  list(434).  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052015/manifest

Comment

Related Items