Grammatical analysis (grammatical parse)
Grammatical analysis (grammatical parse). The process of correlating the line sequence of lexemes (words) of the language with its formal grammar. The result of this is usually a parse tree or an abstract syntactical tree. For grammatical parsing of computer languages context-free grammars are used. It is explained by that the grammars of more general types in Homsky's hierarchy (context-dependent and, moreover, unlimited) are much more difficult to be analyzed, and simpler grammars (regular grammars) do not allow you to describe the embedded language constructions and thus are not enough expressive. Grammatical parse methods can be divided into two large classes - ascending and descending - according to the order of building the parse tree. Descending methods (top-down methods) begin with the grammar rule defining the purpose of analysis from the parse tree's root and try to develop it so that the following tree's nodes correspond the syntax of the sentence being analyzed. Ascending methods (bottom-up methods) begin from the final parse tree's nodes and try to unite them by building nodes of higher and higher levels till the tree's root is reached.
- Wikipedia. "Parsing"
- Wikipedia. Top-down parsing.
- Wikipedia. Bottom-up parsing.