语法与语义分析详解.ppt

(四) 语法与语义分析;语法与语义分析;一、常用的终结符号集;1、首符号集 定义：设有文法G=（VT，VN，S，P），字汇表为V，则符号串?的首符号集定义为 First（?）={?|? ? ?y， ?? VT ， y ? V*} 特别，若?为空串?，则有 First（ ? ）= ? 例如：文法：G=({i，+，*，(，)}，{T，E，F}，E，P) ;P： E::=E+T|T T::=T*F|F F::=i|(E) 则 First（E）={i,(}; First(T*F)={I,(}; First((i))={(}; First(i+i)={i};;2、向前看集 定义：设有文法G=（VT，VN，S，P），非终结符号U的向前看集定义为 Follow（U）={a|S ? …Ua…,a? VTU{#}} #:非终结符号U后面的符号串为空,则将U后的符号记作特殊符号#; Follow(U)={所有含有U的句型中紧跟U之后的终结符}U{#} 例如：文法：G=({i，+，*，(，)}，{T，E，F}，E，P) ;P： E::=E+T|T T::=T*F|F F::=i|(E) 则因: E E; E E+T; E (E) Follow（E）={#,+,)};;P： E::=E+T|T T::=T*F|F F::=i|(E) 则因: E F; E T*F +T; E F*F; E (F) Follow（E）={#,+,*,)};;一、常用的终结符号集（续六）;一、常用的终结符号集（续七）;二、自顶向下分析;二、自顶向下分析（续一）;二、自顶向下分析（续二 ）;二、自顶向下分析（续二 ）;二、自顶向下分析（续三 ）;二、自顶向下分析（续四 ）;二、自顶向下分析（续五）;推导与归约自顶向下与自底向上;推导与归约自顶向下与自底向上;推导与归约自顶向下与自底向上;四、虚拟机;四、虚拟机（续一）;五、递归子程序方法;五、递归子程序方法(续一);五、递归子程序方法(续二);六、逆波兰表达式;六、逆波兰表达式（续一）;中缀、前缀、后缀表示法功能等价 共同点： 1、运算符的个数不变； 2、运算分量的次序不变； 后缀表示法的好处： a:无括号，形式简洁； b:运算符的顺序与运算的次序完全相同。;六、逆波兰表达式（续二）;六、逆波兰表达式（续三）;六、逆波兰表达式（续四）;开始;六、逆波兰表达式;实例2