Parsing Techniques Sample Clauses

Parsing Techniques. Two different parsing techniques are used for different perspectives of processing. As stated in Section 3.1.1, the techniques are selected by considering the amount of unknown words in an input sentence. If there are no unknown words, the GLR technique is selected first; otherwise, the chart technique is selected. In case that the GLR technique fails to parse, the system switches to the chart technique instead. This section will compare the two methods in terms of efficiency and noise tolerance. GLR (abbreviation of ‘Generalized Left-to-Right’) is an almost nondeterministic parsing technique extended from LR algorithm to handle syntactic ambiguity. The technique is based on shift-reduce parser in which the parser is a stack-oriented pushdown automaton. As an input symbol is consumed, the parser moves from a state to another and performs a stack operation. The stack operations of the GLR algorithm are classified into two operations: shift and reduce. A shift operation saves the current state to the stack and then moves to a new state. A reduce operation pops away topmost stack symbols and pushes a new one with respect to the production rules. These operations are described in the parsing action table, which is generated from the state transition analysis of the production rules (▇▇▇ 1970). The term ‘almost nondeterministic’ accounts for the fact that the parser deals with syntactic ambiguity, called action conflict, by means of pseudo-backtracking as old states are saved in the stack. This parsing algorithm is speed-efficient and suitable for parsing long sentences, because most of ambiguities in state transition are eradicated in the state transition analysis resulting in the speed of O(n2) in the best case and O(n3) in average and the worst cases. However this method cannot handle unknown words and this leads us to the awkwardness of informing failure after the parser attempts to parse in any alternatives. The other parsing method used in the system is the chart parsing. This technique is based on Dynamic Programming, which considers parsing as optimization problem and sub- trees as overlapping sub-problems and optimal sub-solutions. The algorithm makes use of graph-like data structure called chart to represent all possible constituencies constructed from an input sentence. In the chart each word of the input sentence is represented as edges connected from the start node to the final node. Then each word is attached with its all- possible parts of speech...