Changes between Version 10 and Version 11 of FixityResolution


Ignore:
Timestamp:
Jul 31, 2009 1:26:24 PM (5 years ago)
Author:
simonmar@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FixityResolution

    v10 v11  
    6161== Report Delta == 
    6262 
     63=== Section 3 (Expressions) === 
     64 
     65'''remove''' 
     66 
     67  In the syntax that follows, there are some families of nonterminals 
     68  indexed by precedence levels (written as a superscript). Similarly, 
     69  the nonterminals op, varop, and conop may have a double index: a 
     70  letter l, r, or n for left-, right- or non-associativity and a 
     71  precedence level. A precedence-level variable i ranges from 0 to 9; an 
     72  associativity variable a varies over {l, r, n}. For example 
     73 
     74{{{   
     75  aexp  ->      ( expi+1 qop(a,i) ) 
     76}}} 
     77 
     78  actually stands for 30 productions, with 10 substitutions for i and 3 
     79  for a. 
     80 
     81'''replace''' 
     82 
     83{{{ 
     84  exp    -> exp0 :: [context =>] type    (expression type signature) 
     85          | exp0 
     86 
     87  expi   -> expi+1 [qop(n,i) expi+1] 
     88          | lexpi 
     89          | rexpi 
     90  lexpi  -> (lexpi | expi+1) qop(l,i) expi+1 
     91  lexp6  -> - exp7 
     92  rexpi  -> expi+1 qop(r,i) (rexpi | expi+1)  
     93}}} 
     94 
     95'''with''' 
     96 
     97{{{ 
     98  exp      -> infixexp :: [context =>] type      (expression type signature) 
     99            | infixexp 
     100 
     101  infixexp -> exp10 qop infixexp 
     102            | - infixexp 
     103            | exp10 
     104}}} 
     105 
     106'''replace''' 
     107 
     108{{{ 
     109  | ( expi+1 qop(a,i) )          (left section) 
     110  | ( lexpi qop(l,i) )           (left section) 
     111  | ( qop(a,i)<-> expi+1 )      (right section) 
     112  | ( qop(r,i)<-> rexpi )       (right section)  
     113}}} 
     114 
     115'''with''' 
     116 
     117{{{ 
     118  | ( infixexp qop )     (left section) 
     119  | ( qop<-> infixexp )  (right section) 
     120}}} 
     121 
     122'''replace''' 
     123 
     124  Expressions involving infix operators are disambiguated by the 
     125  operator's fixity (see Section 4.4.2). Consecutive unparenthesized 
     126  operators with the same precedence must both be either left or right 
     127  associative to avoid a syntax error. Given an unparenthesized 
     128  expression "x qop(a,i) y qop(b,j) z", parentheses must be added 
     129  around either "x qop(a,i) y" or "y qop(b,j) z" when i=j unless a=b=l 
     130  or a=b=r. 
     131 
     132'''with 
     133 
     134  Expressions involving infix operators are disambiguated by the 
     135  operator's fixity (see Section 4.4.2). Consecutive unparenthesized 
     136  operators with the same precedence must both be either left or right 
     137  associative to avoid a syntax error. Given an unparenthesized 
     138  expression "x qop(a,i) y qop(b,j) z" (where "qop(a,i)" means an 
     139  operator with associativity "a" and precedence "i"), parentheses 
     140  must be added around either "x qop(a,i) y" or "y qop(b,j) z" when 
     141  i=j unless a=b=l or a=b=r. 
     142 
     143  An example algorithm for resolving expressions involving infix 
     144  operators is given in Section 9.6. 
     145 
     146 
     147'''remove''' 
     148 
     149  A note about parsing. Expressions that involve the interaction of 
     150  fixities with the let/lambda meta-rule may be hard to parse. For 
     151  example, the expression 
     152 
     153{{{ 
     154    let x = True in x == x == True 
     155}}} 
     156 
     157  cannot possibly mean 
     158 
     159{{{ 
     160    let x = True in (x == x == True) 
     161}}} 
     162  because (==) is a non-associative operator; so the expression must 
     163  parse thus: 
     164 
     165    (let x = True in (x == x)) == True 
     166 
     167  However, implementations may well use a post-parsing pass to deal 
     168  with fixities, so they may well incorrectly deliver the former 
     169  parse. Programmers are advised to avoid constructs whose parsing 
     170  involves an interaction of (lack of) associativity with the 
     171  let/lambda meta-rule. 
     172 
     173'''replace''' 
     174 
     175  For the sake of clarity, the rest of this section shows the syntax of 
     176  expressions without their precedences. 
     177 
     178'''with''' 
     179 
     180  For the sake of clarity, the rest of this section will assume that 
     181  expressions involving infix operators have been resolved according 
     182  to the fixities of the operators. 
     183 
     184=== Section 3.5 (Sections) === 
     185 
     186replace the grammar, as above.  The text is still correct. 
     187 
     188=== Section 9 (Syntax reference) === 
     189 
     190Make the corresponding changes as for Section 3. 
     191 
     192=== Section 9.6, Resolving expressions with infix operators === 
     193 
     194'''New sub-section''' 
     195 
     196The following is an example implementation of fixity resolution for 
     197Haskell expressions.  The function @resolve@ takes a list consisting 
     198of alternating expressions and operators (an instance of the 
     199@infixexp@ non-terminal in the context-free grammar), and returns 
     200either @Just e@ where @e@ is the resolved expression, or @Nothing@ if 
     201the input does not represent a valid expression. 
     202 
     203{{{ 
     204data Op     = Op String Prec Fixity                deriving Eq 
     205data Fixity = Leftfix | Rightfix | Nonfix          deriving Eq 
     206type Prec   = Int 
     207 
     208data Exp    = Var Var | OpApp Exp Op Exp | Neg Exp deriving Eq 
     209type Var    = String 
     210 
     211data Tok    = TExp Exp | TOp Op | TNeg 
     212    
     213resolve :: [Tok] -> Maybe Exp 
     214resolve tokens = fmap fst $ parseNeg (Op "" (-1) Nonfix) tokens 
     215  where 
     216    parseNeg :: Op -> [Tok] -> Maybe (Exp,[Tok]) 
     217    parseNeg op1 (TExp e1 : rest) = parse op1 e1 rest 
     218    parseNeg op1 (TNeg : rest) 
     219       = do guard (prec1 < 6) 
     220            (r, rest') <- parseNeg (Op "-" 6 Leftfix) rest 
     221            parse op1 (Neg r) rest' 
     222       where 
     223          Op _ prec1 fix1 = op1 
     224 
     225    parse :: Op -> Exp -> [Tok] -> Maybe (Exp, [Tok]) 
     226    parse _   e1 [] = Just (e1, []) 
     227    parse op1 e1 (TOp op2 : rest)  
     228       -- case (1): check for illegal expressions 
     229       | prec1 == prec2 && (fix1 /= fix2 || fix1 == Nonfix) 
     230       = Nothing 
     231 
     232       -- case (2): op1 and op2 should associate to the left 
     233       | prec1 > prec2 || (prec1 == prec2 && fix1 == Leftfix) 
     234       = Just (e1, TOp op2 : rest) 
     235 
     236       -- case (3): op1 and op2 should associate to the right 
     237       | otherwise 
     238       = do (r,rest') <- parseNeg op2 rest 
     239            parse op1 (OpApp e1 op2 r) rest' 
     240       where 
     241         Op _ prec1 fix1 = op1 
     242         Op _ prec2 fix2 = op2 
     243}}} 
     244 
     245The algorithm works as follows.  At each stage we have a call 
     246 
     247{{{ 
     248      parse op1 E1 (op2 : tokens) 
     249}}} 
     250 
     251which means that we are looking at an expression like 
     252 
     253{{{ 
     254      E0 `op1` E1 `op2` ...  (*1) 
     255}}} 
     256 
     257(the caller holds E0).  The job of @parse@ is to build the expression 
     258to the right of @op1@, returning the expression and any remaining 
     259input. 
     260 
     261There are three cases to consider: 
     262 
     263  (1) if @op1@ and @op2@ have the same precedence, but they do not 
     264  have the same associativity, or they are declared to be nonfix, then 
     265  the expression is illegal. 
     266 
     267  (2) If @op1@ has a higher precedence than @op2@, or @op1@ and @op2@ 
     268  should left-associate, then we know that the expression to the right 
     269  of @op1@ is @E1@, so we return this to the caller. 
     270 
     271  (3) Otherwise, we know we want to build an expression of the form 
     272  @E1 `op2` R@.  To find R, we call @parseNeg op2 tokens@ to compute 
     273  the expression to the right of @op2@, namely @R@ (more about 
     274  @parseNeg@ below, but essentially if @tokens@ is of the form @(E2 : 
     275  rest)@, then this is equivalent to @parse op2 E2 rest@).  Now, we 
     276  have 
     277    
     278      E0 `op1` (E1 `op2` R) `op3` ... 
     279 
     280  where @op3@ is the next operator in the input.  This is an instance of 
     281  (*1) above, so to continue we call parse, with the new E1 == (E1 
     282  `op2` R) 
     283 
     284To initialise the algorithm, we set @op1@ to be an imaginary operator 
     285with precedence lower than anyything else.  Hence @parse@ will consume 
     286the whole input, and return the resulting expression. 
     287 
     288The handling of the prefix negation operator, @-@, complicates matters 
     289only slightly.  Recall that prefix negation has the same fixity as 
     290infix negation: left-associative with precedence 6.  The operator to 
     291the left of @-@, if there is one, must have precedence lower than 6 
     292for the expression to be legal.  The negation operator itself may 
     293left-associate with operators of the same fixity (e.g. @+@).  So for 
     294example @-a + b@ is legal and resolves as @(-a) + b), but @a + -b@ is 
     295illegal. 
     296 
     297The function @parseNeg@ handles prefix negation.  If we encounter a 
     298negation operator, and it is legal in this position (the operator to 
     299the left has precedence lower than 6), then we proceed in a similar 
     300way to case (3) above: compute the argument to '-' by recursively 
     301calling @parseNeg@, and then continue by calling @parse@. 
     302 
     303Note that this algorithm is insensitive to the range of precedences. 
     304There is no reason in principle that Haskell should be limited to 
     305integral precedences in the range 1 to 10; a larger range, or 
     306fractional values, would present no additional implementation 
     307difficulties. 
     308 
     309 
     310