1第四章文法和语言为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具--“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述2本章内容文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明3文法和语言的形式定义如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。4文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造文法的定义推导的概念句型、句子和语言的定义.5文法定义文法G定义为四元组(VN，VT，P，S)其中VN:非终结符号(或语法实体，或变量)集；VT:终结符号集；P:规则的集合；VN，VT和P是非空有穷集。S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如→或∷=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。6文法的定义例文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号例文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a…<字母>→z<数字>→0…<数字>→9}S=<标识符>8文法的写法元符号:→∷=|<>习惯大写字母表示非终结符小写字母表示终结符(1)G：S→aAbA→abA→aAbA→ε(2)G[S]：A→abA→aAbA→εS→aSb(3)G[S]:A→ab|aAb|εS→aSb9推导的定义直接推导“”α→β是文法G的产生式，若有v,w满足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*则称v直接推导到w,记作vw也称w直接归约到v例：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S110推导<程序><分程序>.(<程序><分程序>.)<分程序>.<变量说明部分><语句>.(<分程序><变量说明部分><语句>)VAR<标识符>;BE...
