|
expand procedure definition presented in 3-40 answer video is not really a complete one. If you run it on it will expand only one found "exp" per each returned list ...and as i prsume it should return |
|
Depth is not for saying how many "exp"s from tokens are to be evaluated, but how many times do we expand the whole tokens list. But during each expand it should "touch" every each nonterminal that it finds in the tokens list. If i will expand only first one, then i will never touch the second "exp". As you can see, the last exp is never touched. If we would have we would never got to ["exp","+","exp","+","exp","+","exp"] which is a valid sentence in that grammar. Hmm, I re-watched the video and indeed, it could be treated either way. Ah, the ambiguities of spoken language. Well, in any case all possible strings would be generated, though a replacement in formal grammars is generally defined one non-terminal at a time, and a path as the transitive closure (*, repeat) of that. I suppose you could also treat depth as the height of the syntax tree - and we've come full circle again. Anyway, your "grab everything" approach would be more efficient as the memory usage depends on the height of the tree, which might be as little as Θ(log n) where n is the parts of the final string Never the less, the procedure was mented to generate all possibile sentences in the grammar, and it wont. Why would it not? That is how all the possible sentences in a grammar is defined: a word w is in the language of the grammar if there exists a path from the starting symbol to w, by replacing one non-terminal in a single step. The procedure in the video only expands the string one more step further, and when you apply it to all possible strings (not just words in the language) that can be generated in n steps, you get all that can be generated in n+1 steps. In fact it will generate even more strings than your proposed procedure, though of course both will catch all the words in the language (so you might say it's wasteful, and it is, but it is not incorrect). Edit: I think I should include this wikipedia link that precisely defines it. Look under the semantics of grammars - yes it's formal, but there's definitely no room for ambiguity. How would you expand [exp,+,exp] into [exp,-,exp,+,exp,-,exp] ? There are two paths you can take : Now, these only the first steps would appear after you call expand ones. Let's say for brevity that the - was your only rule, then calling expand will yield ( [exp,-,exp,+,exp],[exp,+,exp,-,exp] ). Then, as you advance to the next level - all paths of length two, expanding the first item in the generator would yield your desired result once, expanding the second item would yield it again. Each word isn't even guaranteed to appear only once, but that's a side effect of the grammar ambiguity and not the method of choice - yours would do the same if you wanted to, say, get a long string of num+num+num+num... starting from exp. |
|
I was also searching for the same answer, so +1 on that question, But most probably it is because, simply writing two expression does not mean anything! for example, writing : does not mean anything! |
|
I agree with Tomasz .. depth applies to how many times you should expand a resulting token (from an expansion). Even with depth 1. processing each token (an not its resultant) you should be able to generate all possible combinations resulting from the grammar definition. +1 |
