Content deleted Content added
Line 25:
'''Then''' string is member of language
'''Else''' string is not member of language
===Informally===
In informal terms, this algorithm considers every possible substring of the string of letters and sets P[i,j,k] to be true if the substring of letters starting from i of length j can be generated from R<sub>k</sub>. Once it has considered substrings of length 1, it goes on to substrings of length 2, and so on. For substrings of length 2 and greater, it considers every possible partition of the substring into two halves, and checks to see if there is some production P → Q R such that Q matches the first half and R matches the second half. If so, it records P as matching the whole substring. Once this process is completed, the sentence is recognized by the grammar if the substring containing the entire string is matched by the start symbol.
Line 47 ⟶ 49:
| she || eats || a || fish || with || a || fork
|}
===Algorithm extension===
It is simple to extend the above algorithm to not only determine if a sentence is in a language, but to also construct a parse tree, by storing parse tree nodes as elements of the array, instead of booleans. Since the grammars being recognized can be ambiguous, it is necessary to store a list of nodes (unless one wishes to only pick one possible parse tree); the end result is then a forest of possible parse trees.
| |||