Re: Q: Operator Precedence Parser

>Sander Hahn (shahn@galjas.cs.vu.nl) wrote:
>: i want to learn more about operator precedence parsers. The operators
>: should be dynamically overloadable, like in Prolog. Where can i find
>: more information about this subject? (preferably online)


User fs29 <fs29@rummelplatz.uni-mannheim.de> wrote:
>When implementing my T2 compiler, I was looking for a way to speed up
>expression parsing (it used recursive procedure calls at that time).
>Finally, I have managed to do almost the entire expression parsing
>in a single procedure driven by a table containing integers to
>represent the operator precedences. Because of the table-driven
>approach, it should be easy to add, remove, and modify operators.


I've used a similar approach in Ivy
(ftp://ftp.worcester.com/pub/joe/ivy.tar.Z). The table indicates
associativity as well as precidence. Also I use two hash tables
initialized from this table to scan the operators. One hash table
contains an entry for each full operator, and the other only indicates
whether there are operators which match the current scanned
left-sub-string.


For example, if the operator is '>>=', there will be a hash entry for
>>= and left sub-string entries for '>' and '>>'. So to scan for an
operator, you read input for as long as you have a match in the left
sub-string table and note any matches in the full-string hash table.
You return the longest matching operator and unget any unmatching
readahead (which is just a pointer change in Ivy's scanner).


You could make a language with user defined operators with this
approach... I'm don't actually allow that in Ivy and I'm not going to
allow it in the language I'm currently working on- I'm trying to make
an N-pass header-file-less language, so parsing is not allowed to
depend on declarations (like C's typedefs).
--
/* jhallen@world.std.com (192.74.137.5) */ /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
--

Return to the comp.compilers page.
Search the comp.compilers archives again.