第4章文法和语言.ppt

[本章小结] 考察本章知识点最典型的题目是 1.已知文法G[A]，写出它定义的语言描述 如：G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同. 2.给出语言描述，构造文法. 如：构造一文法,其定义的语言是由算符+, *, (,)和运算对象a构成的算术表达式的集合. 答案1: G[E] E→E+T|T T→T*F|F F→(E)|a 答案2: G[E] E→E+E|E*E|(E)|a 相关术语的回顾（英文版） 上下文无关文法 A context free grammar(grammar for short) consists of terminals ,nonterminals,a start symbol,and productions. Terminals are the basic symbols from which strings are formed. Nonterminals are syntactic variables that denote sets of strings that help define the language generated by the grammar. In a grammar,one nonterminal is distinguished as the start symbol,and the set of strings it denotes is the language defined by the grammar. The productions of a grammar specify the manner in which the terminals and nonterminals can be combined to form string. 句型句子和语言 Given a grammar G with start symbol S,we can use the =* relation to define L(G),the language generated by G. Strings in L(G) may contain only terminal symbols of G. We say a string of terminals w is in L(G) if and only if S =* w .The string w is called a sentence of G. If S =* α,wher α may contain nonterminals then we say that α is a sentential form of G 验证文法生成的语言 A proof that a grammar G generates a language L has two parts:we must show that every string generated by G is in L,and coversely that every string in L can indeed be generated by G. 语法树和推导 A parse tree may be viewed as a graphical representation for a derivation that filt out the choice regarding replacement order. The leaves of the parse tree are labeled by nonterminals or terminals and ,read from left to right,they constitute a sentential form,called the yield or frontier of the tree. 句型分析，语法分析 Parsing is the process of determing if a string of token can be generated by a grammar. Most parsing methods fall into one of two classes,called the top-down and bottom-up methods. These terms refer to the order in which nodes in the parse tree are construct