文法和语言的定义(推导) 文法的作用是描述某种语言的句子的构 成方式。使用文法我们可以产生对应语 言的句子。 从识别符号开始,不断将当前符号串中 的非终结符号替换为该符号的某个规! 的右部。直到当前的符号串中所有的符 号都是终结符号为止
文法和语言的定义（推导） • 文法的作用是描述某种语言的句子的构 成方式。使用文法我们可以产生对应语 言的句子。 • 从识别符号开始，不断将当前符号串中 的非终结符号替换为该符号的某个规则 的右部。直到当前的符号串中所有的符 号都是终结符号为止
文法和语言的定义(推导) 例子: 〈句子〉→>〈主语〉〈谓语〉〈状语〉 >〈名词〉〈谓语〉〈状语〉 = Peter swims in river
文法和语言的定义（推导） • 例子： 〈句子〉=>〈主语〉〈谓语〉〈状语〉 =>〈名词〉〈谓语〉〈状语〉 => …… => Peter swims in river
文法和语言的定义(推导) 直接推导:ⅴ=xUy,wxuy,并且U:=u 是文法中的一个重写规则,那么我们说v 可以直接推导到w,或者w可以直接规约 到v。记作ⅴ=>w ·例如: 〈主语〉〈谓语〉〈状语〉 〈名词〉〈谓语〉〈状语〉
文法和语言的定义（推导） • 直接推导：v=xUy，w=xuy，并且U::=u 是文法中的一个重写规则，那么我们说v 可以直接推导到w，或者w可以直接规约 到v。记作 v => w。 • 例如： 〈主语〉〈谓语〉〈状语〉 =>〈名词〉〈谓语〉〈状语〉
文法和语言的定义(推导) 推导:对于符号串v和w,如果存在一个 直接推导序列u0=>u1→>=→un,并且 u0=V,unW,那么我们说v可以推导到w, 或者w规约到v。记作ⅴ=>+w。 这个推导长度为n,且称w为对应于ⅴ的一 ·V=>*w表示v=w或者v=>+wo
文法和语言的定义（推导） • 推导：对于符号串v和w，如果存在一个 直接推导序列u0=>u1=>…=>un，并且 u0=v，un=w，那么我们说v可以推导到w， 或者w规约到v。记作v =>+ w。 • 这个推导长度为n，且称w为对应于v的一 个字。 • v=>* w 表示v=w或者v =>+ w
文法和语言的定义(推导) 推导的例子:P21页例2.12
文法和语言的定义（推导） • 推导的例子：P21页例2.12