编译原理语法1[文法及语言].pptVIP

第 4 讲;第三章 语法分析;第三章《语法分析》 3.1 文法和语言 文法和语言的基本概念 形式语言分类（4类） 正规表达式与上下文无关文法 重点掌握 文法的表示 ;定位 语法分析是编译过程的第二个阶段，也是核心部分 任务 根据语言的语法规则对单词序列进行语法分析，识别合法的语法单位（如表达式、语句、程序段等），若不存在语法错误则给出正确的语法结构（语法树） 理论依据：上下文无关文法 方法 自顶向下分析（推导：开始符号 句子） 自底向上分析（规约：句子 开始符号） ;;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;P→α1P→α2… … P→αn;例如，定义一个仅包含加和乘运算的表达式的文法G[E]:  G[S]?=?(VT，VN，S，ξ):  VT ={+ * ( ) i} VN = {E, T, F} S = E ξ 为以下产生式的集合： E→E + T | T T→T * F | F F→ (E)|i 两种文法都可以识别包含加和乘运算的表达式，它们的区别将在后面的课程中讲解;3.1.1 文法和语言的基本概念 关于文法表示的约定： 在此后的讨论中，用大写字母A、B、S、E等表示非终结符，用小写字母a、b、i、j等表示终结符，并用希腊字母等表示文法符号串，即α、β、δ、γ等均属于(VT∪VN)*。;例3.1 试构造产生标识符的文法。[解答] 首先，标识符是以字母开头的字母数字串， 用L表示“字母”类非终结符， 用D表示“数字”类非终结符，  ; 　因此，产生标识符的文法G[I]为： G[I] = (VT， VN， I，ξ):　　　　 ;[解答] 根据题意，将奇数划分为三个部分:　　;课本例题; 所以，不允许出现以0打头的奇数集合文法G[N]为：;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;3.1 文法和语言;例题： 用上下文无关文法描述正规表达式1(0|1)*101;构造的上下文无关文法：;3.1 文法和语言