So far, so good! Until... (Haskell 98 Report questions)
... 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
On Fri, Aug 17, 2007 at 04:50:02AM -0700, Ian Duncan wrote:
So here's my list of questions so far: 1. What are nonterminals? 2. What are productions and substitutions? [snip]
Sounds to me like you want a book on language design, grammars, parsing, etc. :-) There are many good ones out there, but a quite nice, free, and (as it happens, though it's irrelevant for this question) Haskellish example is "Grammars and Parsing" by Jeuring & Swierstra (PDF, 1.2MB): http://www.cs.uu.nl/docs/vakken/gont/diktaat.pdf (Ignore the Dutch foreword, the rest is in English). Chapter 2 answers the questions asked above, with copious examples and exercises. Hope this helps, -Andy -- Andy Gimblett Computer Science Department University of Wales Swansea http://www.cs.swan.ac.uk/~csandy/
Ian,
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
Implementation".
Chris
On 8/17/07, Ian Duncan
... 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (3)
-
Andy Gimblett -
Christopher L Conway -
Ian Duncan