黄维通 编译原理（中英双语）第四章课件.pptVIP

zhangjing@hrbeu.edu.cn Chapter4 Top –down Syntax Analysis Syntax analysis is a very important part in compiler and its position in compiler is shown by Figure 4.1. Its task is to analyze grammar structure and judge if a string can be recognized by a grammar. There are two types syntax analysis; one is top-down syntax analysis, the other is bottom-up syntax analysis. In this chapter, we introduce top-down syntax analysis; bottom-up syntax analysis will be described in Chapter 5. Top-down syntax analysis can be viewed as an attempt to find a leftmost derivation for an input string. . Equivalently, it can be viewed as an attempt to construct a parsing tree for the input starting from the root and creating the nodes of the parsing tree in preorder. There are two problems that we should address before we consider top-down syntax analysis. The first problem is to eliminate left recursive rules and deduce, and the second one is to avoid backtracking. The second one is to discuss two syntax analysis techniques, one is recursive-descent parsing, the other is LL(1) method. . Practical limitation of grammar Usually, in compiling a program, there are some limitations. That is, there is no such rules: U::=ε, U ? +U , and so on. In this section, we will introduce some methods to obtain a new grammar from an old one. . (1) There is no rule, U::= U, because this rule has no meaning and easily leads to ambiguous grammar. For example, S::=0S1|01|S should be replaced by S::=0S1|01. . (2) There are no useless rules. That is, Rules in grammar should be limited as follows. . (a) U must appear in a rule, such as Z ? ＊xUy . (b) we can deduce a terminal from U, U ? +t（t∈VT+）. . For example, S::= AB | CA