Many parsing techniques are available, some of them being designed long before TFSGs were developed. As mentioned in the previous section, one of the most suitable technique for TFSGs is bottom-up parsing. Most natural language processing or computational linguistics textbooks ([Allen1994], [Jurafsky and Martin2000], [Gazdar and Mellish1989], [Pereira and Shieber1987]) include detailed presentations of bottom-up parsing. Therefore, just some notational details are required here.
Bottom-up parsing can traverse the input string from right to left or from left to right. When not specified, it will be assumed here that the traversal is right to left (this is the approach taken in the EFD parsing method, described in the next section.) Rules also can be processed in both directions; the default assumption will be that the processing is left to right (as in the EFD algorithm). Several books (such as [Allen1994]) use the term active arc to denote a rule in the course of being completed; in this thesis, the term active edge will be used. Similarly, constituents in the chart are named edges (or passive edges) instead of (passive) arcs. The left-hand side of a rule is the mother of the rule, while categories on the right-hand side are daughters. The process of traversing a rule and matching its daughters with edges in the chart is called the completion of the rule.