Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: James Harris Newsgroups: comp.compilers Subject: Compiling expressions Date: Sat, 29 Dec 2012 05:11:16 -0800 (PST) Organization: Compilers Central Lines: 79 Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <12-12-035@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: leila.iecc.com 1356818105 96881 64.57.183.58 (29 Dec 2012 21:55:05 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 29 Dec 2012 21:55:05 +0000 (UTC) Keywords: parse, question Posted-Date: 29 Dec 2012 16:55:05 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:819 Compiling expressions is turning out to be more 'interesting' than I anticipated! My requirements I believe to be fairly generic but they seem not to be supported by standard algorithms so it's not as simple as it might be. I thought I would post here as much out of interest as anything. I'm not after a prebuilt solution but would be interested to hear from other folks who have had similar issues to address. The requirements are: 1. Hand-written, not the output of a parser generator. 2. Efficient and without backtracking. 3. Precedences (and possibly associativities) defined in tables. 4. Output to be a tree structure. 5. Parenthesised subexpressions allowed. 6. Some operator families are *not* to associate with each other. See below. 7. Monadic prefix, dyadic infix and monadic postfix operators are all allowed. 8. Prefix and infix operators can use some same symbols (e.g. minus sign). Infix and postfix operators use distinct symbols. For example, if a certain symbol were used as a postfix operator it could not also be used as an infix operator. Point 6 about some operator families not associating is because, at least in the proposed version of the language, bitwise operators and, xor, or, not are not to have any defined precedence relative to the arithmetic operators plus, minus, times, power, unary minus etc Operators in these two families are to have precedences relative to other symbols in the same family and to families below and above them but there is no defined precedence between, say, plus and bitwise and. Some examples of operators of lower precedence would be comparisons (less than, equal to etc) and boolean conjunctions (logical and, logical or etc). Operators of higher precedence include binding, dereference, function application etc. So if the compiler sees a + b & c then it is to complain about + and & being adjacent. One of the sides must be parenthesised such as either of these two: (a + b) & c a + (b & c) By contrast the following are both OK without needing parens because < can interact with either family. a + b < x b & c < x I have considered: recursive calls, shunting yard stacking of operators, stacking of pairs (symbol, operand), of triples (precedence, symbol, operand), some bitwise modification of stacked precedences and some table-driven recognition of exceptions. I have tried to avoid a two-dimensional grid-based solution but having concluded it may be the way to go my copy of the dragon book advises that such a solution does not work with unary minus! It says it should be separated out in the lexer. That is something I don't want to do. The parsing should be controlled wholly in the expression parser. Perhaps strangely prefix operators seem to me easy enough to distinguish from infix as they are seen in two different contexts. What is acceptable before an operand is not the same as what is acceptable after an operand. Am currently thinking this might need a grid per context - i.e. two grids - but I've never seen an algorithm with such. Er, fun this, isn't it! James