parse_table_routines.pro (Documentation for /home/davin/idl/socware/)

;+
;Procedure: parse_table_routines
;
;Purpose: Compiles a library of helper routines for the parse_table generator
;          It contains general purpose routing routines
;          anything table specific will be stored in slr.pro,
;          lk1.pro & lalr.pro (right now there is only support for slr parse tables)
;
; $LastChangedBy: pcruce $
; $LastChangedDate: 2012-07-12 15:50:21 -0700 (Thu, 12 Jul 2012) $
; $LastChangedRevision: 10702 $
; $URL: svn+ssh://thmsvn@ambrosia.ssl.berkeley.edu/repos/spdsoft/trunk/general/mini/parse_table_routines.pro $
;-




;constructs an item or a set of items from a production
;an item is just like a product with the exception that
;it has a placeholder that can be placed before the right side
;of the production,after it, or between any element on the right side.
;This is specified with pos. Pos is a number from 0 to length
;which specifies up to length + 1 different positions.
function make_item,prod,pos

  compile_opt idl2,hidden

  item = {type:'item',left:prod[0].left,right:prod[0].right,op:prod[0].op,index:prod[0].index,length:prod[0].length,pos:long(pos[0])}

  items = replicate(item,n_elements(prod))

  items[*].left = prod[*].left
  items[*].right = prod[*].right
  items[*].op = prod[*].op
  items[*].index = prod[*].index
  items[*].length = prod[*].length
  items[*].pos = long(pos)

  return,items

end

;helper function checks if an element is in a vector of elements
function in_vector,ele,vec

  compile_opt idl2,hidden

  len = csvector(vec,/length)

  for i = 0,len-1 do begin

     out = csvector(i,vec,/read)

     if is_equal(ele,out) then begin
        return,1
     endif

  end

  return,0

end

;find the index of an item
function vec_index,ele,vec

  compile_opt idl2,hidden

  len = csvector(vec,/length)

  for i = 0,len-1 do begin

     out = csvector(i,vec,/read)

     if is_equal(ele,out) then begin
        return,i
     endif

  end

  return,-1

end

;syntactic sugar to concatenate arrays in a way that is a little more
;useful that the standard idl syntax
function concat,val,arr

  compile_opt idl2,hidden

  if ~keyword_set(arr) || (is_string(arr) && arr[0] eq '') then begin
    return,[val]
  endif else begin
    return,[arr,val]
  endelse

end


;empty is fail(although not necessarily serious)
;the function first is a standard function used in
;LL, top-down parsers, SLR, LR(k) & bottom-up parsers
;you will found this routine described in those texts
function parse_first,ele,grammar,added

  compile_opt hidden,idl2
  
  out = ''
  
  for i = 0, n_elements(ele) - 1 do begin
  
    if in_set(ele[i],grammar.terminals) then begin
      return,concat(ele[i],out)
    endif else if ele[i] eq grammar.empty then begin
      return,concat(ele[i],out)
    endif else begin
     
      idx = where(ele[i] eq grammar.production_list.left)
      
      ;consider adding error checking on this har index
      
      ;prevent infinite loop
    
      if ~keyword_set(added) then begin
        added = intarr(n_elements(grammar.production_list))
      endif
      
      prods = grammar.production_list[idx]
      
      first_list = ''
  
      for j = 0,n_elements(prods)-1 do begin
      
        if added[idx[j]] eq 0 then begin 
      
          added[idx[j]] = 1
      
          first = parse_first(prods[j].right,grammar,added)
      
          if first[0] ne '' then begin
            first_list = concat(first,first_list)
          endif
        endif
    
      endfor
      
      first_list = first_list[uniq(first_list,sort(first_list))]
      
      out = concat(first_list,out)
      
      out = out[uniq(out,sort(out))]
      
      if ~in_set(grammar.empty,first_list) then begin
        return,out
      endif
    endelse 
     
  endfor
  
  out = concat(grammar.empty,out)
  
  out = out[uniq(out,sort(out))]
  
  return,out
  
end

;empty is fail(although not necessarily serious)
;the function follow is a standard function used in
;LL, top-down parsers, SLR, LR(k) & bottom-up parsers
;you will find this routine described in texts referenced in calc.pro
function parse_follow,nonterminal,grammar,added

  compile_opt hidden,idl2

  ;only nonterminal are acceptable inputs
  if in_set(nonterminal,grammar.terminals) then begin
    ;error
    return,''
  endif
  
  ;if the input is the start symbol add a newline to follow
  if is_equal(nonterminal[0],grammar.start) then begin
    follow =[grammar.endline] 
  endif else begin 
    follow = ''  ;otherwise initialize as blank
  endelse
  
  ;initialize added if it was not passed in
  ;this argument should only be initialized if this is
  ;a non-user recursive call.  added exists to prevent
  ;an infinite loop
  if ~keyword_set(added) then begin
    added = intarr(n_elements(grammar.nonterminals))
  endif
  
  ;get the numerical index of the input nonterminal
  idx = where(nonterminal eq grammar.nonterminals)
  
  ;so added will be correctly marked
  if added[idx] eq 1 then begin
    return,''
  endif else begin
    added[idx] = 1
  endelse
  
  ;now loop over all the productions
  for i = 0,n_elements(grammar.production_list)-1 do begin
    
    ;local variable for this iteration, just for ease of typing
    prod = grammar.production_list[i]
    
    ;if the requested nonterminal exists in the right side of the production
    if in_set(nonterminal,prod.right) then begin
      
      idx = where(prod.right eq nonterminal)
      
      for j = 0,n_elements(idx) - 1 do begin

      ;if the nonterminal is at the rightmost on the right side of production
        if idx[j] eq prod.length-1 then begin
          follow_tmp = parse_follow(prod.left,grammar,added) ;make a recursive call
        
          if ~is_equal(follow_tmp[0],'') then begin
            follow = concat(follow_tmp,follow) ;if there is a valid result add it to the outpu
          endif
        
        endif else begin

          first = parse_first(prod.right[idx+1],grammar) ;generate first for the symbol next to the right
        
          if in_set(grammar.empty,first) then begin ;if empty symbol is in first
        
            follow_tmp = parse_follow(prod.left,grammar,added) ;make a recursive call to follow
        
            if ~is_equal(follow_tmp[0],'') then begin ;and add valid outputs to overall output
              follow = concat(follow_tmp,follow)
            endif
          
            idx = where(first ne grammar.empty) ;also add all non-empty symbols in first to output
          
            follow = concat(first[idx],follow)
          
          endif else begin
        
            follow = concat(first,follow) ;add the symbols in first to the output
          
          endelse
        endelse
      endfor
    endif
  endfor
  
  return,follow[uniq(follow,sort(follow))] ;the recursive method may duplicate some results, eliminate dups
end  

pro parse_table_routines

;just compiles the appropriate routines

end