| --- Log opened Sun Nov 22 00:00:37 2009 |
| 00:33 | | You're now known as TheWatcher[T-2] |
| 00:38 | | You're now known as TheWatcher[zZzZ] |
| 01:01 | | AbuDhabi [annodomini@Nightstar-b8fb3614.adsl.tpnet.pl] has quit [[NS] Quit: I return to the fetid darkness.] |
| 02:11 | | Orthia [Orthianz@Nightstar-474b9e0e.xnet.co.nz] has joined #code |
| 02:53 | | Attilla [The.Attilla@FBC920.58502B.59021B.52988F] has quit [Connection reset by peer] |
| 05:29 | | Netsplit *.net <-> *.split quits: Alek, EvilDarkLord, Syloqs-AFH, Rhamphoryncus, @McMartin, @ToxicFrog, crem |
| 05:31 | | Netsplit over, joins: crem, EvilDarkLord |
| 05:31 | | EvilDarkLord [jjlehto3@Nightstar-f1ccbb45.hut.fi] has quit [Ping timeout: 121 seconds] |
| 05:31 | | EvilDarkLord [jjlehto3@Nightstar-f1ccbb45.hut.fi] has joined #code |
| 05:32 | | Netsplit over, joins: Alek |
| 05:32 | | Netsplit over, joins: Rhamphoryncus |
| 05:32 | | Netsplit over, joins: ToxicFrog, McMartin |
| 05:32 | | mode/#code [+o ToxicFrog] by Reiver |
| 05:32 | | mode/#code [+o McMartin] by Reiver |
| 07:28 | | Syloqs_AFH [Syloq@NetworkAdministrator.Nightstar.Net] has joined #code |
| 07:30 | | Syloqs_AFH is now known as Syloqs-AFH |
| 07:48 | | Netsplit *.net <-> *.split quits: Syloqs-AFH, @McMartin, @ToxicFrog, crem |
| 07:50 | | Netsplit over, joins: crem |
| 07:51 | | crem [moo@Nightstar-8ca3eea7.adsl.mgts.by] has quit [Ping timeout: 121 seconds] |
| 07:51 | | Netsplit over, joins: McMartin |
| 07:51 | | mode/#code [+o McMartin] by Reiver |
| 07:51 | | crem [moo@Nightstar-8ca3eea7.adsl.mgts.by] has joined #code |
| 07:51 | | mode/#code [+o ToxicFrog] by Reiver |
| 07:51 | | Netsplit over, joins: ToxicFrog |
| 07:53 | < Tarinaky> | I'm trying to get my head around Parsing. :/ Can someone suggest which algorithm I should start with trying to implement for simple arithmetic? |
| 07:54 | | * Vornicus uses two stacks for arithmetic, and when he ended up writing a full language he added a third. |
| 07:56 | < Tarinaky> | This book seems to be suggesting that I need to make a tree somehow >.> |
| 08:02 | < Tarinaky> | My inability is frustrating >.> |
| 08:08 | | Derakon is now known as Derakon[AFK] |
| 08:32 | < Tarinaky> | So... Do I need to construct a tree or not :/ Now I'm confused. |
| 08:42 | <@Vornicus> | You may need to build a tree; it is in fact probably your best bet! |
| 08:42 | <@Vornicus> | However, in order to build the tree you have to do stuff; you can probably build the tree using a stacky method. |
| 08:43 | < Tarinaky> | I see. |
| 08:43 | <@Vornicus> | Now i sleep. |
| 08:43 | < Tarinaky> | G'night! |
| 08:49 | < Rhamphoryncus> | A tree basically means you turn "a + b * c" into (+, a, (*, b, c)) |
| 08:50 | < Rhamphoryncus> | So that the next stage doesn't care about the order in the sourcecode. All they see is a + node with two arguments, one of which is a * node (which in turn also has two arguments) |
| 08:51 | | Vornicus is now known as Vornicus-Latens |
| 08:51 | < Tarinaky> | Rhamphoryncus: The Dragon Book is a bit vague on how to do this and how to construct a tree... Am I missing something here? >.> |
| 08:52 | < Rhamphoryncus> | Might be. I've generally avoided doing any serious parsing, so I can't recall how to do it |
| 08:53 | < Namegduf> | For arithmetic, I don't think you need a tree. |
| 08:54 | < Tarinaky> | Well. My long term goal isn't arithmetic. It's just I'm struggling with the material. |
| 08:54 | < Namegduf> | At least not if you're okay to convert into RPN instead. |
| 08:54 | < Rhamphoryncus> | Depends what your order of operations are |
| 08:54 | < Rhamphoryncus> | wait, misread you |
| 08:54 | <@Vornicus-Latens> | For arithmetic with parentheses, you will need: a precedence table and two stacks. |
| 08:54 | < Rhamphoryncus> | If you want to understand real parsing as is normally used, you want a tree as your output |
| 08:55 | < Namegduf> | Vornicus-Latens: Is one a number, one operation, or is there something else to the way you're describing it? |
| 08:55 | <@Vornicus-Latens> | As you step over the tokens, you maintain the stacks: operators and parentheses go onto one stack, operands onto the other. |
| 08:55 | < Namegduf> | Ah, thought so. |
| 08:55 | < Tarinaky> | I think Vorn is describing a Shunting Yard algorithm. |
| 08:55 | < Rhamphoryncus> | That sounds familiar.. |
| 08:55 | | * Namegduf used a single stack when he implemented it |
| 08:55 | < Namegduf> | (But another stack at evaluation time for results) |
| 08:56 | <@Vornicus-Latens> | You just push each operand onto the stack as you encounter it; when you see an operator you pop off every operator that is lower (and for right-associative operators, equal) priority and process them in turn. |
| 08:57 | <@Vornicus-Latens> | A close parenthesis pops operators until you hit an open parenthesis; when you reach the end of the expression you pop stuff until there's nothing left. |
| 08:58 | < Namegduf> | Hmm. This is combined parsing/evaluation, right? |
| 08:58 | <@Vornicus-Latens> | Only complication at all is that you need to keep track of what mode you're in; you don't want an operand immediately after another one, a non-unary operator after an operator, or an rparen after an operator. |
| 08:58 | < Namegduf> | Yeah. |
| 08:58 | <@Vornicus-Latens> | (lparens after operands are acceptable if you're doing function calls that way) |
| 08:58 | < Namegduf> | I've seen an interesting solution to that. |
| 08:59 | <@Vornicus-Latens> | In /mine/ I do evaluation as I destack stuff. |
| 08:59 | <@Vornicus-Latens> | You can fix it up so it's a tree instead though. |
| 08:59 | <@Vornicus-Latens> | anyway really sleep. |
| 08:59 | < Rhamphoryncus> | Yeah, evaluation is the same as emitting a tree |
| 09:00 | < Namegduf> | Way I did it, which was based on a previous implemention, involved recursing up and down a set of functions; if you were going down, each non-unary operator's function would just pass you down right away until you hit the bottom, which would read parens and operands. |
| 09:00 | < Namegduf> | Then when they returned back up, it'd be looking for an operator. |
| 09:00 | < Namegduf> | When the operator's found, it goes back down the chain looking for an operand again. |
| 09:01 | < Namegduf> | Pushing things onto the stack as they're 'handled' to produce a single stack in RPN (non-string, naturally) format. |
| 09:01 | <@Vornicus-Latens> | Gah. Oh, and: most binary arithmetic operators are right-associative; exponentiation and prefix operators are left-associative. |
| 09:01 | < Namegduf> | (This is because evaluation has to be delayed for this) |
| 09:01 | <@Vornicus-Latens> | think that's the right handedness. |
| 09:01 | | * Rhamphoryncus throws Vornicus-Latens a pillow to lay on his keyboard |
| 09:01 | <@Vornicus-Latens> | ow |
| 09:02 | | * Vornicus-Latens is beaned by the pillow, falls unconscious. |
| 09:02 | | * Namegduf looks vaguely confused, then throws Vornicus-Latens another, softer pillow |
| 09:02 | < Rhamphoryncus> | oh, guess that was the one with a doorknob in it |
| 09:03 | < simon`> | when an article says "parsing a regex takes linear time with respect to the length of the regex", then "parsing" means converting it into an automaton, right? i.e., it has nothing to do with matching it against a string yet. |
| 09:03 | < Rhamphoryncus> | simon`: right |
| 09:04 | < Rhamphoryncus> | Maybe you can do binary operators as left vs right associative, but normally there's a series of precedences. |
| 09:05 | < Rhamphoryncus> | Consider "a+b*c.d,e&f[g]and h or j" in python |
| 09:06 | | You're now known as TheWatcher |
| 09:07 | < Tarinaky> | Am I missing something on the construction of trees and where can I obtain this missing knowledge? |
| 09:08 | < Tarinaky> | :/ |
| 09:14 | < Rhamphoryncus> | If you have a stack (or two) like they suggested then that's all you need |
| 09:14 | < Rhamphoryncus> | if the stack lets you evaluate a*b then you evaluate that to Mul(a, b) or (*, a, b) (however you want to spell it) |
| 09:15 | < Tarinaky> | Okay. I think I might have this... I'm going to have a nap and try to do this when I wake up. |
| 09:15 | < Tarinaky> | Thanks for the help. |
| 09:17 | < Rhamphoryncus> | np |
| 09:32 | | AnnoDomini [annodomini@Nightstar-b8fb3614.adsl.tpnet.pl] has joined #code |
| 09:32 | | mode/#code [+o AnnoDomini] by Reiver |
| 09:36 | | Rhamphoryncus [rhamph@Nightstar-a62bd960.abhsia.telus.net] has quit [Client exited] |
| 09:47 | | Syloqs_AFH [Syloq@NetworkAdministrator.Nightstar.Net] has joined #code |
| 09:48 | | Syloqs_AFH is now known as Syloqs-AFH |
| 10:43 | < simon`> | are there any guidelines towards deciding whether some CFG can be transformed into LL(1) or not? |
| 11:55 | <@McMartin> | That's a really good question. I suspect the usual route is to try factoring it and see if you fail |
| 11:56 | <@McMartin> | For designing languages to be such, you probably implement it as LL and add keywords every time you get stuck. |
| 11:56 | <@McMartin> | Judging by both Python and Go. =P |
| 11:58 | < Namegduf> | LL? |
| 12:02 | <@McMartin> | Parsable with a recursive-descent parser. |
| 12:03 | <@McMartin> | The (1) means "with one token of lookahead". |
| 12:03 | <@McMartin> | There's also a more formal definition, bu that's the rough-and-ready one. |
| 12:22 | | Attilla [The.Attilla@FBC920.58502B.59021B.52988F] has joined #code |
| 12:23 | | mode/#code [+o Attilla] by Reiver |
| 12:55 | | dmlandrum [dmlandrum__@8E7DA3.838E9A.6CA65A.A8EF5A] has quit [[NS] Quit: Leaving] |
| 12:57 | | dmlandrum [dmlandrum__@8E7DA3.838E9A.6CA65A.A8EF5A] has joined #code |
| 12:59 | | AbuDhabi [annodomini@Nightstar-cba3ab52.adsl.tpnet.pl] has joined #code |
| 13:01 | | AnnoDomini [annodomini@Nightstar-b8fb3614.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 13:37 | < simon`> | McMartin, what bothers me is my weekly assignment where I have to left-factorize a postfix notation, and it occurs to me that the operator is rightmost, i.e. far beyond what a one-symbol lookahead can handle. still, that just suggests it's probably difficult, and not impossible. |
| 13:39 | < simon`> | Namegduf, LL is "read from the left, derived from the left" |
| 13:39 | < simon`> | Namegduf, unlike LR parsers that derive from the right and have it much easier. |
| 13:39 | < Namegduf> | Ah. |
| 13:40 | < simon`> | LR parsers use a stack and just push stuff onto it whenever they don't get a satisfying match. moment they do, they pop whatever number of tokens their non-terminals want. |
| 13:41 | < simon`> | LL(k) parsers need to have all their grammars rewritten to avoid infinite recursion and perfect prediction |
| 15:16 | | gnolam [lenin@Nightstar-38637aa0.priv.bahnhof.se] has joined #code |
| 16:04 | | mode/#code [-o ToxicFrog] by ChanServ |
| 17:00 | | Rhamphoryncus [rhamph@Nightstar-a62bd960.abhsia.telus.net] has joined #code |
| 17:20 | | You're now known as TheWatcher[afk] |
| 18:14 | | Vornicus-Latens is now known as Vornicus |
| 18:27 | | Syloqs-AFH [Syloq@NetworkAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 18:29 | | Syloqs_AFH [Syloq@NetworkAdministrator.Nightstar.Net] has joined #code |
| 18:29 | | You're now known as TheWatcher |
| 18:30 | | Syloqs_AFH is now known as Syloqs-AFH |
| 18:43 | | Derakon[AFK] is now known as Derakon |
| 19:21 | | Tarinaky [Tarinaky@Nightstar-102bd586.adsl.virginmedia.net] has quit [Ping timeout: 121 seconds] |
| 19:22 | | Tarinaky [Tarinaky@Nightstar-102bd586.adsl.virginmedia.net] has joined #code |
| 20:48 | | crem [moo@Nightstar-8ca3eea7.adsl.mgts.by] has quit [Connection reset by peer] |
| 20:54 | | crem [moo@Nightstar-8ca3eea7.adsl.mgts.by] has joined #code |
| 22:58 | | Rhamphoryncus [rhamph@Nightstar-a62bd960.abhsia.telus.net] has quit [Client exited] |
| 23:41 | | Derakon is now known as Derakon[AFK] |
| --- Log closed Mon Nov 23 00:00:52 2009 |