assignment 4

hi, is anyone making any head way for this assignment? I am stuck on the earley algorythm as well as the last question - the one for while and during

Hi

I am also struggling with the Early algorithm

Going to have to email the lecturer for some explanations

did you understand the while/during question?

If you get any feedback can you let me know? Also, have you received any marked assignment back?

only assignment 1... and i haven't started this one yet

did you actually get assignment 1 back? I got a mark but thats it

I also didn't get Assignment 1 back...

Haven't go to the while/during question yet.
Will let you know if i get any feedback regarding this assignment.

Thanks

Question 10.1 refers to figure 10.7...is it supposed to refer to figure 10.6?

if thats the earley algorythm, then yes, it should be 10.6. If its another questio nthen I am not sure - I don't have the textbook with me today

My recognizer is working fine, but I'm completely baffled by the parse tree requirement. I understand, sort of, the idea of having a back pointer to the state that was used in the derivation of the completed state, in other words, using the example on page 386, I understand, say, how state S10 has a back pointer to S9, and why S20 has a back pointer to S18...but I do NOT understand how S21 has TWO backpointers, to S14 and S19 - why isn't it just to S19?

Perhaps you've found a place on the internet that explains it better than the textbook?

I haven't even figured the normal parser out I understand the theory but my practical coding part is not up to scratch

I kinda understand the earley algorithm and the parse tree addition to it - well i understand it enough to code it.

Let me try to explain it the way i understand it...

S21 is derived from running the completer on S19 [so one of its backpointers is S19].
Furthermore, we note how S21 is derived by running the completer on S19 - This is done by finding "all previously created states that were looking for this (S19) grammatical category at this position in the input". When these previous states are found, we create a copy of this state and advance the dot.
Now, in the case of S21, one of the states that was expecting S19, was S15. So we look at the backpointers that S15 already has, and append all its backpointers to S21 (that being just S14). Then i assume we do this recursively, and append also the backpointers of S14 to S21... etc

Hope it helps

Hey Peeps...

I'm struggling with the Early algorithm... anyone please share some light...

Thanks Lois, I'll see if I can code this up

Using a longer sentence ("does this flight include a meal", I get this chart

Chart[0]
S0 Gamma->* S [0,0] Dummy Start State
S1 S->* NP VP [0,0] Predictor
S2 S->* Aux NP VP [0,0] Predictor
S3 S->* VP [0,0] Predictor
S4 NP->* Det Nominal [0,0] Predictor
S5 NP->* ProperNoun [0,0] Predictor
S7 VP->* Verb [0,0] Predictor
S8 VP->* Verb NP [0,0] Predictor
Chart[1]
S6 Aux->does * [0,1] Scanner
S9 S->Aux * NP VP [0,1] Completer
S10 NP->* Det Nominal [1,1] Predictor
S11 NP->* ProperNoun [1,1] Predictor
Chart[2]
S12 Det->this * [1,2] Scanner
S13 NP->Det * Nominal [1,2] Completer
S14 Nominal->* Noun [2,2] Predictor
S15 Nominal->* Noun Nominal [2,2] Predictor
Chart[3]
S16 Noun->flight * [2,3] Scanner
S17 Nominal->Noun * [2,3] Completer
S18 Nominal->Noun * Nominal [2,3] Completer
S19 NP->Det Nominal * [1,3] Completer
S20 Nominal->* Noun [3,3] Predictor
S21 Nominal->* Noun Nominal [3,3] Predictor
S22 S->Aux NP * VP [0,3] Completer
S23 VP->* Verb [3,3] Predictor
S24 VP->* Verb NP [3,3] Predictor
Chart[4]
S25 Verb->include * [3,4] Scanner
S26 VP->Verb * [3,4] Completer
S27 VP->Verb * NP [3,4] Completer
S28 S->Aux NP VP * [0,4] Completer
S29 NP->* Det Nominal [4,4] Predictor
S30 NP->* ProperNoun [4,4] Predictor
Chart[5]
S31 Det->a * [4,5] Scanner
S32 NP->Det * Nominal [4,5] Completer
S33 Nominal->* Noun [5,5] Predictor
S34 Nominal->* Noun Nominal [5,5] Predictor
Chart[6]
S35 Noun->meal * [5,6] Scanner
S36 Nominal->Noun * [5,6] Completer
S37 Nominal->Noun * Nominal [5,6] Completer
S38 NP->Det Nominal * [4,6] Completer
S39 Nominal->* Noun [6,6] Predictor
S40 Nominal->* Noun Nominal [6,6] Predictor
S41 VP->Verb NP * [3,6] Completer
S42 S->Aux NP VP * [0,6] Completer

I'd be interested to see what backpointers you get from S42 (assuming you get the same chart, that is!)

sorry, I don't know either, I am going to be looking at mine now.... if I get any bright sparks I will let you know

Well, I eventually figured it out. The example in the textbook is spectacularly obtuse and in my opinion simply serves to confuse. For me, the solution was to simply store two pointers for each new state generated by the completer step: a pointer to the completed state that we are trying to match against, and a pointer to the older incomplete state that matches. So for instance, state S21 is generated by completed state S19, while the completer step identifies state S15 as the incomplete state that matches. Similarly state S11 has back pointers to S3 and S9.

To generate the parse tree, one recursively backtracks through these back pointers - eventually the pointers will point to a word (from a scanner production) or to nothing (by nothing, I mean a dead-end state, i.e., a state that is not producing a word in our sentence and does not have any backpointers). For instance, using the examples above, S15 points to S14, which is the word "that", while S3 points to nothing and is ignored.

Of course, I may be barking up the wrong tree - but it seems to be working correctly with quite large grammars and sentences.

Hey, as long as it works!

I still need to test mine with a different grammar and sentence. I am praying very hard that it doesn't crash!

I haven't even written mine yet

I think if you understand the algorithm completely you can write the code very swiftly. I had no idea how the algorithm worked and attempted to figure it out while coding it. As a result it took me many days to write the code, and I'm still not sure I fully understand the algorithm If I rewrote it now it would probably be half the length, if not shorter.

Is it just me, or is submitting this assignment going to be tricky? My email is being bounced, and my.unisa.ac.za is not answering...

My email also keeps getting blocked. I have contacted the IT department in my company to have it released. In the meantime, just email the lecturer to let her know that the email is being blocked, and that you will keep trying. I was having the same problem for Assignment 02. She was very understanding. She will even give you confirmation when she receives the programs files. Also, she had told me that Unisa also has a filter that blocks some of her incoming emails. So if you make sure it gets sent on your side, the rest is up to Unisa.

I submitted my assignment yesterday - without the programmign question in it. I got a mesage from unisa saying my assignment was late but would still be accepted. this is after the fac tath tin march I sent them about 3 emails sayign the submission date on myUnisa was wrong. With assignment 2 I had to send the code to lecturer about 3 times, someones firewall kept removing the code. I hope though you guys manage to get your stuff through today

What I mean is, my emails to the lecturer are being bounced back. Any my browser times out trying to connect to my.unisa.ac.za. It's been like this since last night.

Edit: turns out if I use https rather than http, I can get to my.unisa.

Hi, out results for COS460 and COS405 have been fixed - the % is set to 100 now - well, mine was

Mine too!

Woohoo!!!

yay!