Path: utzoo!utgpu!water!watmath!watvlsi!mccool
From: mccool@watvlsi.waterloo.edu (Michael McCool)
Newsgroups: comp.lang.prolog
Subject: Yacc in Prolog, Parsing and Dali
Keywords: Yacc, Parsing, Errors, Precedence, Dali
Message-ID: <3833@watvlsi.waterloo.edu>
Date: 15 Feb 88 16:18:35 GMT
Distribution: na
Organization: U of Waterloo, Ontario
Lines: 58


	Does anyone know if there's anything like yacc written for Prolog?
I.e. not just grammar rules, but left-factoring, precedence parsing of
expressions, etc;  what I'd like is some kind of preprocessor that takes
simple non-deterministic grammar rules, with some extra
bits thrown in to indicate associativity, precedence etc, and converts it to
a grammar-rule or prolog program that will do an efficient parse.

	It seems like a useful thing to have so I'm *sure* somebody's already
written it :-) 

	My wish list is:

	1) Public domain, in a common syntax --> Quintus pref
	2) can accept a token-production function instead of a list
		this is to save memory.  WHY does everybody assume
		that the ENTIRE token list is in memory???  The token
		function would return a structure that could be recognized
		as a terminal, and the parser would poke it everytime
		it needed a new token.  
			The parser might have to maintain a list
		to back up into (unput-style).  (Of course, if we had 
		list-streams this wouldn't be a problem... but that's
		a different wish list)
	3) has a simple way to handle syntax errors --> 
		a way to resynch, e.g. skip tokens until you see
		a token.  This should be done in a way similar to
		yacc's "error ;" so I don't have to fool around with
		writing tail-recursive loops to scan for these kind of
		constructs.
	4) precedence/associativity parser         
		for operations, I would like to give only one rule like
			expr(binary(Op,E1,E2)) --> 
				$left,expr(E1),['+'],expr(E2),{Op = plus} | 
		 	        $left,expr(E1),['-'],expr(E2),{Op = minus} | 
			        $left,expr(E1),['*'],expr(E2),{Op = times} | 
				$left,expr(E1),['/'],expr(E2),{Op = divide} |...
		with "$left" indicating left associativity, and the order 
		indicating precedence.

	I'm working on a front end for a "silicon compiler", and have already
written a parser for a pascal-like language, but the grammar gets pretty
horrible after you add syntax checking and other fuzz. In the interests of
software engineering, I'd much rather have a high-level description that can
be changed easily (the operator stuff is *particularly* important) than
some grotesque Dali-like byzantine code-cathedral. 

	advTHANKSance for any help/pointers.  

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
        O_o          Michael McCool <-- mccool@watvlsi.waterloo.edu
       ={  }= oOp! aAK VLSI! gaG Symple C snARf! foo when bar LIthP! forkKKK...
       // U         __ 
     /{ }\ __     /__/|   WARNING DANGER WARNING DANGER WARNING DANGER WARNING
     \[]}/\ /===_|   ||_  ==>==>==>==>==>  Hacking Kills <==<==<==<==<==<==<==
    _^{_/  /_% /_|___|/|  DANGER    * Kick the Habit, logout NOW *      DANGER
   %   /__/   |_______|   DANGER        BEFORE IT'S TOO LATE            DANGER