第四章文法和语言 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描 述。(严谨、简洁、易读) 形式工具-“形式”是指这样的事实:语言的 所有规则只以什麽符号串能出现的方式来 陈述
1 第四章 文法和语言 为语言的语法描述寻求工具 工具要对程序设计语言给出精确无二义的语法描 述。（严谨、简洁、易读） 形式工具--“形式”是指这样的事实：语言的 所有规则只以什麽符号串能出现的方式来 陈述
本章内容 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明
2 本章内容 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明
文法和语言的形式定义 如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以 将句子逐一列出来表示 如果语言是无穷的,找出语言的有穷表示。语言的 有穷表示有两个途经: 生成方式(文法):语言中的每个句子可以用严 格定义的规则来构造。 识别方式(自动机):用一个过程,当输入的一任 意串属于语言时,该过程经有限次计算后就会停止 并回答“是”,若不属于,要么能停止并回答“不 是”,要么永远继续下去
3 文法和语言的形式定义 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严 格 定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任 意串属于语言时，该过程经有限次计算后就会停止 并回答“是” ，若不属于，要么能停止并回答“不 是” ，要么永远继续下去
文法即是生成方式描述语言的:语言中的 每个句子可以用严格定义的规则来构造 文法的定义 推导的概念 句型、句子和语言的定义
4 文法即是生成方式描述语言的：语言中的 每个句子可以用严格定义的规则来构造 文法的定义 推导的概念 句型、句子和语言的定义
文法定义 文法G定义为四元组(VN,V,P,S)其中 VR:非终结符号(或语法实体,或变量)集 Vr:终结符号集; P:规则的集合; V,V和P是非空有穷集 s:称作识别符号或开始符号的一个非终结符,它至 少要在一条产生式中作为左部出现。 Vn和V不含公共的元素,即Vn1∩V=中 用V表示VN∪V,称为文法G的字母表或字汇表 规则,也称重写规则、产生式或生成式,是形如 α→B或α:邛β的(α,β)有序对,其中α是字母表V 的正闭包V中的一个符号,β是V*中的一个符号 α称为规则的左部,β称作规则的右部
5 文法定义 文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至 少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如 →或 ∷ =的( ，)有序对，其中是字母表V 的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部