[Haskell-cafe] So far, so good! Until... (Haskell 98 Report questions)

Christopher L Conway cconway at cs.nyu.edu
Fri Aug 17 08:08:53 EDT 2007


This is all programming language parsing jargon. If the Wikipedia
doesn't help (try http://en.wikipedia.org/wiki/Formal_grammar), I
recommend the first few chapters of Aho, Sethi, & Ullman's "Compilers:
Principles, Techniques, and Tools" aka "the dragon book", or any good
book on compilers, e.g., Andrew Appel's "Modern Compiler


On 8/17/07, Ian Duncan <iand675 at gmail.com> wrote:
> ... I hit Chapter 3 and started reading about expressions.
> *If you are able to answer any of these questions, please send me an email.
> I am very lost and confused in this section, so even one answered question
> may help greatly.*
> I actually decided to sit down and figure out the Haskell 98 Report today.
> Everything was going well until I began Chapter 3. Here's the section that
> has me baffled:
>  "In the syntax that follows, there are some families of nonterminals
> indexed by precedence levels (written as superscript). Similarly, the
> nonterminals op, varop, and conop may have a double index: a letter l, r, or
> n for left-, right- or non-associativity and a precedence level. A
> precedence-level variable i ranges from 0 to 9; an associativity variable,
> a, varies over {l,r,n}. For example, aexp ->  ( exp^(i+1) qop^(a,i) )
> actually stands for 30 productions, with 10 substitutions for i and 3 for
> a." *note that the "^" was used to indicate superscript.
> So here's my list of questions so far:
> 1. What are nonterminals?
> 2. What are productions and substitutions?
> I tried the dictionary and wikipedia, but neither were very helpful in
> defining those terms.
> Next, it says:
>  exp -> exp^0 :: [context=>] type   (expression type signature)
>   |  exp^0
>  exp^i -> exp^(i+1) [qop^(n,i) exp^(i+1)]
>     |   lexp^i
>     |   rexp^i
>  ...
> From there it continues with more syntax stuff, but I'll stop there for the
> sake of not typing too much. So here are some questions about this section:
> 1. What the heck is going on?
> 2. How is an expression with a precedence of i considered to be an
> expression of i+1?
> 3. Within the ... section it mentions lexp and rexp. Do those stand for
> left-associative expressions and right-associative expressions respectively?
> I understand the concept of fixity when I see it mentioned in code, but I
> truly have no idea what 3.0 is talking about. Can anyone shed some light on
> any of this? I'm still in high school, so if anyone could please explain it
> to me in layman's terms primarily, or provide some resources explaining more
> complex terms, It would be greatly appreciated.
> Thanks a bunch!
>  Ian Duncan
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list