Parsing (syntax analysis) is the process of correlating the line sequence of lexemes (words) of the programming language with its formal grammar. The result of this is usually a parse tree or an abstract syntactical tree. Context-free grammar is used to analyze the syntax of computer languages. This is because the grammar of more general types in Chomsky's hierarchy (context-sensitive and, even more so, unrestricted) is much more difficult analyze. Moreover, the simpler grammar (regular grammar) does not allow you to describe the embedded programming language constructs and thus is not expressive enough. Methods of syntax analysis 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 root. They try to develop it so that the following tree nodes correspond to the syntax of the sentence being analyzed. Ascending methods (bottom-up methods) start from the final nodes of the parse tree and try to unite them by building nodes of higher and higher levels until the tree root is reached.
0