<br><br><div class="gmail_quote">On Tue, Aug 14, 2012 at 1:04 AM, Евгений Пермяков <span dir="ltr"><<a href="mailto:permeakra@gmail.com" target="_blank">permeakra@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Your idea looks _much_ better from code
clarity point of view, but it's unclear to me, how to deal with it
internally and in error messages. I'm not a compiler guy, though.<br></div></div></blockquote><div><br>How to deal with it internally: It's pretty easy, actually. The hardest part is implementing an extensible partial order; once you have that and you can use it to drive comparisons, parsing is not hard.<br>
<br>Basically, at each step when you read an operator token, you need to decide to "shift", that is, put it onto a stack of operations, "reduce", that is, apply the operator at the top of the stack (leaving the current token to check again at the next step), or give a parse error. The rules for deciding which of those to do are pretty simple:<br>
<br>Given X, the operator at the top of the stack, and Y, the operator you just read:<br><br>(1) Compare the precedence of X and Y. If they are incomparable, it's a parse error.<br>(2) If Y is higher precedence than X, shift.<br>
(3) If Y is lower precedence than X, reduce.<br><br>(At this point, we know X and Y have equal precedence)<br><br>(4) If X or Y is non-associative, it's a parse error.<br>(5) If X and Y don't have the same associativity, it's a parse error.<br>
<br>(At this point we know X and Y have the same associativity)<br><br>(6) If X and Y are left associative, reduce.<br>(7) Otherwise they are both right associative, shift.<br><br>So, for example, reading the expression<br>
<br>x * y + x + g w $ z<br><br>Start with stack [empty x].<br><br>The empty operator has lower precedence than anything else (that is, it
will never be reduced). When you finish reading an expression, reduce
until the empty operator is the only thing on the stack and return its
expression.<br><br>* is higher precedence than empty, shift. [empty x, * y]<br>+ is lower precedence than *, reduce. [empty (x*y)]<br>+ is higher precedence than empty, shift. [empty (x*y), + x]<br>+ is the same precedence as +, and is left associative, reduce. [empty ((x*y)+x)]<br>
+ is higher precedence than empty, shift [empty ((x*y)+x), + g]<br>function application is higher precedence than +, shift. [empty ((x*y)+x), + g, APP w]<br>$ is lower precedence than function application, reduce. [empty ((x*y)+x), + (g w)]<br>
$ is lower precedence than +, reduce. [empty (((x*y)+x) + (g w))]<br>$ is higher precedence than empty, shift. [empty (((x*y)+x) + (g w)), $ z]<br>Done, but the stack isn't empty. Reduce. [empty ((((x*y)+x) + (g w)) $ z)]<br>
Done, and the stack is empty.<br>Result: ((((x*y)+x) + (g w)) $ z)<br><br>Each operator is shifted exactly once and reduced exactly once, so this algorithm runs in a number of steps linear in the expression size. Parentheses start a new sub-stack when parsing the 'thing to apply the operator to' part of the expression.<br>
<br>Something like this:<br><br>simple_exp :: Parser Exp<br>simple_exp =<br> (ExpId <$> identifier) <|> (ExpLit <$> literal) <|> (lparen *> expression <* rparen)<br><br>expression :: Parser Exp<br>
expression = do<br> first <- simple_exp<br> binops [ (Empty, first) ]<br><br>reduceAll [ (Empty, e) ] = return e<br>reduceAll ((op1, e1) : (op2, e2) : rest) = reduceAll ((op2, (ExpOperator op1 e1 e2)) : rest)<br>
<br>binops :: Stack -> Parser Exp<br>binops s = handle_binop <|> handle_application <|> reduceAll s where<br> handle_binop = do<br> op <- operator<br> rhs <- simple_exp<br> reduce_until_shift op rhs s<br>
handle_application = do<br> rhs <- simple_exp<br> reduce_until_shift FunctionApplication rhs s<br><br>reduce_until_shift implements the algorithm above until it eventually shifts the operator onto the stack.<br>
identifier parses an identifier, operator parses an operator, literal parses a literal (like 3 or "hello")<br>lparen and rparen parse left and right parentheses.<br><br>I haven't considered how difficult it would be to expand this algorithm to support unary or more-than-binary operators; I suspect it's not ridiculously difficult, but I don't know. Haskell's support for both of those is pretty weak, however; even the lip service paid to unary - is a source of many problems in parsing Haskell.<br>
<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><div>
Worse, it does not allow to set up fixity relative to operator
that is not in scope and it will create unnecessary intermodule
dependencies. One should fall back to numeric fixities for such
cases, if it is needed.</div></div></blockquote><div><br>You can get numeric fixity by just declaring precedence equal to some prelude operator with the desired fixity; this will likely be the common case.<br><br>I would expect modules to declare locally relative fixities between operators imported from different modules if and only if it was relevant to that module's implementation. In most cases I expect the non-ordering to be resolved by adding parentheses, not by declaring additional precedence directives; for example, even though (a == b == c) would be a parse error due to == being non-associative, both ((a == b) == c) and (a == (b == c)) are not. The same method of 'just add parentheses where you mean it' fixes any parse error due to incomparable precedences.<br>
<br> -- ryan<br></div></div><br>